ARC105 D.Let’s Play Nim,E.Keep Graph Disconnected题解

总结两个非常好的博弈题！

D. Let’s Play Nim

相信大家都知道NIM游戏的结论吧: 如果$\oplus x_i=0$则后手必胜，否则先手必胜。

则问题转变为:

轮流将一个包里的东西放到盘子里，问最后拿出包里物品的人能否让$\oplus x_i=0$?

这个比较复杂，我们可以分情况讨论。

若每一个物品出现的次数为偶数，则后手必胜。这是显然的，由于后手可以不断复刻先手的操作。

否则，我们考虑倒数第二个拿走的那个人，如果他在没用的那两个中选择最大的，放入权值最大的盘子中，这个盘子里的权值和最终一定$\ge \frac{sum}{2}$ 。这说明了什么呢？我们不妨可以再次分类讨论：

若$\max \{w_i\}>\frac{sum}{2}$,则其余盘子异或和一定$<\max \{w_i\}$,则最终的异或和$\ne 0$ （Tips:异或可以看作不进位的加法！ ）

若$\max \{w_i\}=\frac{sum}{2}$ ,假设其余盘子里的异或和$=\frac{sum}{2}$,若这个满足，最后放入的两个数一定相等。这个归纳一下就会发现这正是case1。

综上所述：若每一个数出现的次数都为偶数，后手必胜；否则拿走倒数第二个的人必胜。

总结：这题只需要分类讨论，耐心证明就可以快速做出来。结论还是比较优美的！

Code:

/* { ###################### # Author # # Gary # # 2020 # ###################### */ //#pragma GCC target ("avx2") //#pragma GCC optimization ("O3") //#pragma GCC optimization ("unroll-loops") #pragma GCC optimize(2) #include<bits/stdc++.h> #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a<b;++a) #define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(a) rng()%a #define ALL(a) a.begin(),a.end() #define POB pop_back #define ff fflush(stdout) #define fastio ios::sync_with_stdio(false) #define check_min(a,b) a=min(a,b) #define check_max(a,b) a=max(a,b) using namespace std; const int INF=0x3f3f3f3f; typedef pair<int,int> mp; /*} */ map<int,int> app; int N; void solve(){ app.clear(); scanf("%d",&N); rb(i,1,N) { int ai; scanf("%d",&ai); app[ai]++; } bool ok=true; for(auto ite=app.begin();ite!=app.end();ite++){ ok&=!((ite->SEC)&1); } ok^=1; ok^=(N&1); cout<<(ok? "First":"Second")<<endl; } int main(){ int t; cin>>t; while(t--){ solve(); } return 0; } /** 程序框架： * * * * **/

E. Keep Graph Disconnected

考验思维的题目！（做了一晚上总算自己独自ac了）

首先若只剩下两个联通快(1所在的和n所在的)，最终谁会胜利呢？

很明显，和能够加的边数有关。设1所在的联通块能加入的边数为$c_1$,n所在的为$c_2$。

则可以发现若$c_1+c_2$为奇数，先手胜。否则后手胜。

我们扩展到一般情况，若有多个联通快，总共能加的边数为$K$（假设不在联通快之间连边）。

若$K$为奇数，显然答案可能不是先手！这是为什么呢？

后手可以在块与块之间连边，打破原来的规律！

怎么解决？

假设在联通快$i$与$j$之间连一条边，我们冷静分析就会发现：

若$c_i\equiv c_j\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)$,则在i,j之间连一条边之后会增加$c_i\ast c_j$条边$\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)$，最后在减去连接的这条边，奇偶性相当于没变，相当于反转了胜负。其他情况下奇偶性就会改变，和一个联通快内的影响是一样的。

这样假设奇数块有$Z$个。

若$Z$是奇数，反转的次数为$\lfloor Z/2\rfloor$若$Z$是偶数，反转的次数为$[Z/2,Z/2-1]$次（若最后刚好剩下1号块和n号块都是奇数）

这个$[Z/2,Z/2-1]$对于比赛的胜负至关重要。

最终问题转变成：

先手/后手能否使得最后1号块和2号块都为奇数？

看似任然不好做。

其实这存在一个非常优美的结论：

若初始状态1，2的奇偶性不一样，则先手一定可以完成目标。若1，2初始都为1，则不管先后手都可以完成目标若1，2初始都为0，则不管先后手都不可能。

具体方法大概就是，若已经满足要求就随便拿两个消掉，否则用一个实现目标。

Code:

/* { ###################### # Author # # Gary # # 2020 # ###################### */ //#pragma GCC target ("avx2") //#pragma GCC optimization ("O3") //#pragma GCC optimization ("unroll-loops") #pragma GCC optimize(2) #include<bits/stdc++.h> #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a<b;++a) #define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(a) rng()%a #define ALL(a) a.begin(),a.end() #define POB pop_back #define ff fflush(stdout) #define fastio ios::sync_with_stdio(false) #define check_min(a,b) a=min(a,b) #define check_max(a,b) a=max(a,b) using namespace std; const int INF=0x3f3f3f3f; typedef pair<int,int> mp; /*} */ const int MAXN=100000+20; int n,m; int fa[MAXN]; int cnt_node[MAXN],cnt_edge[MAXN],cnt[MAXN]; int root(int x){return fa[x]=(fa[x]==x? x:root(fa[x]));} string result[2]={"First","Second"}; int cnt_1,cnt_0; bool check(bool cnt_o,bool who){ if(cnt_node[root(1)]==cnt_node[root(n)]){ if(cnt_node[root(1)]==0){ return false; } else{ return true; } } else{ return (!who); } } void solve(){ scanf("%d %d",&n,&m); rb(i,1,n) cnt_node[i]=cnt_edge[i]=cnt[i]=0,fa[i]=i; vector<mp> edges; rb(i,1,m){ int u,v; scanf("%d %d",&u,&v); edges.PB(II(u,v)); fa[root(u)]=root(v); } for(auto it:edges) cnt_edge[root(it.FIR)]++; rb(i,1,n) cnt_node[root(i)]^=1; bool rest=0; cnt_1=0,cnt_0=0; rb(i,1,n){ cnt[root(i)]++; if(cnt_node[i]) cnt_1+=cnt_node[i]; else if(root(i)==i) ++cnt_0; } rb(i,1,n){ if(root(i)==i){ rest^=(1ll*cnt[i]*(cnt[i]-1)/2-cnt_edge[i])&1; } } bool ok; int times=(cnt_1)/2; times&=1; if(cnt_1&1){ if(times^rest){ ok=0; } else{ ok=1; } } else{ if((times^rest)){ ok=check(cnt_0&1,1); } else{ ok=!check(cnt_0&1,0); } } cout<<result[ok]<<endl; } int main(){ int t; cin>>t; while(t--){ solve(); } return 0; } /** 程序框架： * * * * **/

推荐阅读:

AGC 045 D

CF 1369 F

AGC010 A,B,C,D,F