原題鏈接：https://vjudge.net/problem/UVA-1624
分類：思維題
備注：好題,模擬

實(shí)在沒(méi)有什么明確的思路，一開(kāi)始想解開(kāi)繩子變成圓，不會(huì)。然后想是不是和奇偶性有關(guān)，也找不到規(guī)律。

最后題解還是解開(kāi)繩子：https://www.cnblogs.com/zhengkunjia/p/12906096.html
主要是用平移和旋轉(zhuǎn)兩種操作：①如果兩個(gè)小段的兩端呈覆蓋關(guān)系，嚴(yán)格保證兩個(gè)小段一上一下，且它們中間沒(méi)別的覆蓋點(diǎn)，那么通過(guò)平移可以去掉這兩個(gè)覆蓋點(diǎn)；②如果某個(gè)點(diǎn)是覆蓋點(diǎn)，且將這兩個(gè)點(diǎn)連起來(lái)的那條小段中沒(méi)有其它覆蓋點(diǎn)，則可以旋轉(zhuǎn)去掉這個(gè)覆蓋點(diǎn)。

#include<bits/stdc++.h> using namespace std; const int maxl=1e6+5; int link[maxl],ud[maxl],l,p,t,kase,vis[maxl],head,tag; struct Node{int pre,nxt; }k[maxl]; void del(int pos){ud[pos]=0;k[k[pos].pre].nxt=k[pos].nxt;k[k[pos].nxt].pre=k[pos].pre;head=k[pos].nxt; } int main(void){// freopen("in.txt","r",stdin);scanf("%d",&t);while(t--){scanf("%d%d",&l,&p);memset(ud,0,sizeof(ud));memset(link,0,sizeof(link));memset(vis,0,sizeof(vis));for(int i=0;i<l;i++){k[i].pre=i-1;k[i].nxt=i+1;}k[0].pre=l-1;k[l-1].nxt=0;for(int i=0;i<p;i++){int x,y;scanf("%d%d",&x,&y);link[x]=y; link[y]=x;ud[x]=1; ud[y]=-1;}for(int i=0;i<l;i++)if(!ud[i])del(i);head=tag=0; while(!ud[head])head++;while(p){bool flg=false; tag++;for(int i=head;vis[i]!=tag&&!flg;i=k[i].nxt){vis[i]=tag;int x=k[i].nxt;if(x==link[i]||k[x].nxt==i){//一定可以旋轉(zhuǎn)del(i); del(x);p--; flg=true;}else if(ud[i]==ud[x]&&(k[link[i]].nxt==link[x]||k[link[x]].nxt==link[i])){//顯然可以平移走del(i); del(x);del(link[i]); del(link[x]);p-=2; flg=true;}}if(!flg)break;}printf("Case #%d: ",++kase);if(!p)printf("YES\n");else printf("NO\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的习题 8-28 打结（Knots, ACM/ICPC ACM/ICPC Jakarta 2012, UVa1624）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。