题解 P1203 【[USACO1.1]坏掉的项链Broken Necklace】

· · 题解

什么？32篇题解竟然没有一个用链表做的？于是我就来写一篇用链表做的题解。利用链表可以节省空间，以免浪费。而这道题是要把环拆成链的，正好符合链表，而我用的就是循环链表。尝试每一个断点，然后开始往前往后数，数到等于n时就直接停下输出答案，否则如果颜色不一样且不为白色，就终止循环。，注意一点，如果断点是白色的，就要每循环一个点就尝试更新颜色，否则就WA了亲身经历，代码对初学者有一些不友好，请见谅。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
    node *prv,*nxt;//为了防止CE我把元音吃掉了
    char color;
};//双向链表的基本模型
node *head,*tail,*p;//头指针、尾指针、辅助指针（尾指针其实只在刚开始有用）
int n,ans=1;
char c;
int main(){
    scanf("%d",&n);
    while(getchar()!='\n');//吃掉换行符
    head=new node;//先申请一个节点
    head->color=getchar();
    head->prv=head,head->nxt=head,tail=head;//把前驱后继都先指向自己，且与尾指针重合
    for(int i=1;i<n;++i){
        p=new node;//对于每个辅助指针都先申请
        p->prv=tail,p->nxt=head;//把这个指针的前驱改为尾指针，后继改成头指针
        p->prv->nxt=p,p->nxt->prv=p;//接着改变头指针和尾指针的前驱与后继
        tail=p,p->color=getchar();//把尾指针向后移动一位，并输入
    }//这样输入完之后头指针和尾指针也相连了，符合项链的样子
    p=head;//把这个指针先指向头指针
    do{
        node *q=p->prv;//q节点先默认为p节点的前驱
        int temp=1;
        char color=p->color;//把颜色先默认为p节点的颜色
        while(q->color=='w'||q->color==color||color=='w'){//循环的条件
            if(temp==n) return 0&printf("%d",n);//这个地方用了简写，本应写为if(temp==n){printf("%d",n);return 0;}
            color=(color=='w'?q->color:color)/*如果颜色还是白色，就更新颜色*/,++temp,q=q->prv;//答案++，指针向后移动一位
        }q=p->nxt,color=p->nxt->color;//把q改为p的后继，还要注意颜色应为q节点的颜色
        while(q->color=='w'||q->color==color||color=='w'){
            if(temp==n) return 0&printf("%d",n);
            color=(color=='w'?q->color:color),++temp,q=q->nxt;//类似
        }p=p->nxt,ans=max(ans,temp);//p指针向后移动一位，并尝试更新答案
    }while(p!=head);
    return 0&printf("%d",ans);//这个地方也是简写
}

这道题目的方法有很多种，如果看不懂我的题解你还可以看别人的题解。如果看懂了，并A了，请给我一个赞，谢谢！