首页 > 代码库 > Uva1624 Knots

Uva1624 Knots

2024-08-22 12:45:42   209人阅读

极其鬼畜的题。

初见根本没有思路。

二见根本没有思路。

……

多年（并不）之后突然想到，也许可以用链表模拟。

先用链表把每一个节点串起来，并对有覆盖的地方进行标记。

模拟解锁操作，如果一个节点和它所覆盖的节点之间没有其他结，那么进行逆self loop操作。

同理进行逆passing操作。

如果能把所有的结都解开，则答案是有解。

 

优化：把没有覆盖/被覆盖的节点提前删掉，缩短链表长度。

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<list> 8 using namespace std; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13     return x*f;14 }15 struct node{16     int pre,nxt;17 }a[1000010];18 int link[1000010];19 int ud[1000010];20 int L,P;21 void Del(int x){22     ud[x]=0;23     a[a[x].pre].nxt=a[x].nxt;24     a[a[x].nxt].pre=a[x].pre;25 }26 int T;27 int main(){28     T=read();29     int L,P,i,j;30     for(int cas=1;cas<=T;cas++){31         memset(link,0,sizeof link);32         memset(ud,0,sizeof ud);33         L=read();P=read();34         for(i=0;i<L;i++){35             a[i].pre=i-1;36             a[i].nxt=i+1;37         }38         a[0].pre=L-1;a[L-1].nxt=0;39         int u,v;40         for(i=1;i<=P;i++){41             u=read();v=read();42             link[u]=v;link[v]=u;43             ud[u]=1;ud[v]=-1;//???? 44         }45         for(i=0;i<L;i++)if(!ud[i])Del(i);46         int hd=0;47         while(P){48             bool flag=1;49             while(!ud[hd])hd++;50             for(i=a[hd].nxt; i!=hd && flag; i=a[i].nxt){51                 int u=i,v=a[i].nxt;52                 if(ud[u]==ud[v] && (a[link[u]].nxt==link[v] ||53                     a[link[v]].nxt==link[u])){54                         Del(u);    Del(v);55                         Del(link[u]);56                         Del(link[v]);57                         P-=2;58                         flag=0;59                     }60                 //passing61                 else if(link[v]==u || link[u]==v){62                     Del(u);Del(v);63                     P--;64                     flag=0;65                 }66                 //selfloop67             }68             if(flag)break;69         }70         printf("Case #%d: ",cas);71         if(!P)printf("YES\n");72         else printf("NO\n");73     }74     return 0;75 }

 

Uva1624 Knots


联系
我们