HDU-5963 朋友 思維
- 2020 年 4 月 11 日
- 筆記
題目鏈接http://acm.hdu.edu.cn/showproblem.php?pid=5963
吐槽
這道題我第一眼看，嗯？？博弈論？還是樹上的？我好像不會啊。。。但是一想某人的話，感覺這個應該也不會太難，可能有規律
分析
於是我就從樣例開始仔細思考找規律，第一個樣例應該是看不出來啥，但第二個內容量就比較豐富了。但我模擬完樣例二依舊沒發現什麼，難道這道題真要建個線段樹什麼的？？接著我把關注點放到了輸出上，輸出只有兩種，那是不是應該存在某種奇偶關係？還是要先考慮鏈的情況，因為從無根樹上的一個點出發遍歷就相當於走幾條鏈（好像樹的問題大部分都跟鏈有關）。下面模擬一下
首先要注意到題目中的暗示，每次都要找一個到父親節點權值為1的點，這就說明了這個問題的限制，它總會結束。先不考慮修改，如果以1為根，不難看出女孩會贏，其中一種走法是
當然也有別的走法，但總會是女生贏。
如果以2為根呢？不難得出還是女孩贏，其中一種走法為
那麼是不是圖中邊權為1的邊數為偶數時，就是女生贏呢？仍舊以2為根，我們在4後邊再跟一個節點。
會發現這樣還是女生贏。
那在根節點2後邊跟這個節點呢？
這時候再去模擬就會發現是男生贏了。所以我們猜測，讓女生贏的並不是圖中邊權為1的邊數，而是根節點周圍邊權為1的邊數，根據這個大膽的猜測，我寫出了下面的程式碼，好像還白寫了一個加邊函數。如果你去用樣例測試，發現是對的，所以我興奮的交了上去，WA
#include<cstdio> #include<cstring> using namespace std; const int N=4e4+10; struct Edge{ int to,nxt,val; }e[N<<1]; int Head[N],len; void Ins(int a,int b,int c){ e[++len].to=b;e[len].val=c; e[len].nxt=Head[a];Head[a]=len; } int cnt[N]; int main(){ int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d%d",&n,&m); memset(cnt,0,sizeof(cnt)); for(int i=1;i<n;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); cnt[a]+=c; cnt[b]+=c; } for(int i=1;i<=m;i++){ int op,x,y,z; scanf("%d",&op); if(op==1){ scanf("%d%d%d",&x,&y,&z); if(z==1)cnt[x]++,cnt[y]++; else cnt[x]--,cnt[y]--; } else { scanf("%d",&x); if(cnt&1)printf("Girls win!n"); else printf("Boys win!n"); } } } } 二次分析
既然這個程式碼過了樣例，就說明它應該不是偶然，所以應該是我少考慮了什麼。再回去讀了一邊題，發現題中並沒有說當(op==1)時，變換的權值與原來的權值相等，也就是說如果我每次都把1變為0，0變為1，那麼我上邊的程式碼是可以的，也就是樣例情況，但問題就出在它可能是1變為1，0變為0，所以每次必須掃描一邊根周圍的邊權之和，即下邊的程式碼。
#include<cstdio> #include<cstring> using namespace std; const int N=4e4+10; struct Edge{ int to,nxt,val; }e[N<<1]; int Head[N],len; void Ins(int a,int b,int c){ e[++len].to=b;e[len].val=c; e[len].nxt=Head[a];Head[a]=len; } int main(){ int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d%d",&n,&m); memset(Head,0,sizeof(Head)); len=0; for(int i=1;i<n;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); Ins(a,b,c);Ins(b,a,c); } for(int i=1;i<=m;i++){ int op,x,y,z; scanf("%d",&op); if(op==1){ scanf("%d%d%d",&x,&y,&z); for(int i=Head[x];i;i=e[i].nxt) if(e[i].to==y)e[i].val=z; for(int i=Head[y];i;i=e[i].nxt) if(e[i].to==x)e[i].val=z; } else { int cnt=0; scanf("%d",&x); for(int i=Head[x];i;i=e[i].nxt)cnt+=e[i].val; if(cnt&1)printf("Girls win!n"); else printf("Boys win!n"); } } } } 證明
寫完之後感覺就這麼過去的話不是很好，萬一猜錯了就很尷尬，所以想一下證明。
為了簡化問題，我們只把鏈的情況證明了就好。如果連接根節點的邊權值為1，其餘邊有兩種情況，一是全為1的，二是含0的，分開討論一下。
如果含有0，
因為是女生先任意選點，所以讓女生選擇最後一個點，這樣連接根節點的那條邊就會被置為0，而因為含有0，所以肯定還會剩下邊權為1的，這時由於男生不得不去變換邊，所以一定會去變換權值為1的，由於根節點在男生變換的時候為0，所以這樣的話只有可能是女生讓根節點變為0，也就是只有女生會贏。
如果不含0都是1呢？那女生就可以一次性讓男生沒的變換，仍然是女生贏。
當連接根節點的邊權值為0時就會反過來，證畢。
