博弈論練習2

\;

1.AGC010F - Tree Game

題目描述

Solution

一道簡單博弈題（不知道為啥能作為AGC的F題）。
考慮樹形$dp$，設$f[x]$表示以$x$為根的子樹中是否先手必勝。

則$f[x]=1$當且僅當能找到$x$的子節點$v$滿足$f[v]=0$且$a[x]>a[v]$（因為這樣就可以把后手摁死在$v$子樹里，讓后手輸掉，自己就贏了）。

對于每一個結點都把它當做整一棵樹的根$dp$一遍即可。
時間復雜度$O(n^2)$

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=600005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int a[MAXN],f[MAXN]; vector<int> e[MAXN]; bool dfs(int x,int father) {for (auto v:e[x]){if (v==father) continue;dfs(v,x);if (a[x]>a[v]&&!f[v]) return f[x]=1;} return f[x]=0; } int main() {int n=read();for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<n;i++){int u=read(),v=read();e[u].PB(v);e[v].PB(u);}for (int i=1;i<=n;i++)if (dfs(i,0)) printf("%d ",i);return 0; }

2.SPOJ COT3 - Combat on a tree

題目描述

Solution

一道SG （數據結構）好題。

每一次選擇一條到根的路徑清零就相當于斷成若干個獨立的子樹，因此就可以求子樹$SG$值計算答案，用可持久化$trie$樹維護整體$xor$和求$mex$。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=200005; const int MAXM=MAXN<<5; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int sum[MAXN],c[MAXN],rt[MAXN],sg[MAXN],up[MAXN]; vector<int> e[MAXN],Ans; struct Trie_Tree {int nodenum=0,flag[MAXM],tag[MAXM],dep[MAXM],ch[MAXM][2];void up(int x) { flag[x]=flag[ch[x][0]]&&flag[ch[x][1]]; }void Xor(int x,int y) {if (!x) return;tag[x]^=y; if (y&(1<<(31-dep[x]-1))) swap(ch[x][0],ch[x][1]);}void down(int x){if (!x||!tag[x]) return;Xor(ch[x][0],tag[x]);Xor(ch[x][1],tag[x]);tag[x]=0;}void Insert(int &x,int y,int Dep) { if (!x) dep[x=++nodenum]=Dep;down(x);if (Dep==31) { flag[x]=1; return; } if (y&(1<<(31-dep[x]-1))) Insert(ch[x][1],y,Dep+1);else Insert(ch[x][0],y,Dep+1);up(x);}int Mex(int x){if (!x||dep[x]==31) return 0;if (flag[ch[x][0]]) return (1<<(31-dep[x]-1))+Mex(ch[x][1]);return Mex(ch[x][0]);}int Merge(int x,int y){if (!x||!y) return x+y;if (dep[x]==31) { flag[x]=flag[x]||flag[y]; return x; }down(x),down(y);ch[x][0]=Merge(ch[x][0],ch[y][0]);ch[x][1]=Merge(ch[x][1],ch[y][1]);up(x);return x;} } Trie; void tree_dp(int x,int father) {for (auto v:e[x]){if (v==father) continue;tree_dp(v,x);sum[x]^=sg[v];}if (!c[x]) Trie.Insert(rt[x],sum[x],1);for (auto v:e[x]){if (v==father) continue;Trie.Xor(rt[v],sum[x]^sg[v]);rt[x]=Trie.Merge(rt[x],rt[v]);}sg[x]=Trie.Mex(rt[x]); } void getans(int x,int father) {if (father) up[x]=up[father]^sum[father]^sg[x]; // cout<<x<<" "<<father<<" "<<sum[x]<<" "<<sg[x]<<" "<<up[x]<<endl;for (auto v:e[x]){if (v==father) continue;getans(v,x);}if ((!c[x])&&((up[x]^sum[x])==0)) Ans.PB(x); } int main() {int n=read();for (int i=1;i<=n;i++) c[i]=read();for (int i=1;i<n;i++){int u=read(),v=read();e[u].PB(v);e[v].PB(u);} tree_dp(1,0);getans(1,0);if (!Ans.size()) { puts("-1"); return 0; }sort(Ans.begin(),Ans.end());for (auto v:Ans) printf("%d\n",v);return 0; }

3.CF494E.Sharti

題目描述

Solution

典型的翻硬幣博弈模型。
整體的$SG$值為所有單獨一個格子為黑色的$SG$值的異或和。
離散化行，線段樹維護列信息求解。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=100005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int n,m,k,K; struct anode{ int x,l,r,c; } a[MAXN]; int compare(anode x,anode y) { return x.x<y.x; } int getans(int l,int r) {l--;int ret=0;for (int i=1;i<=k;i<<=1) ret|=((r/i-l/i-(i*2<=k?r/i/2-l/i/2:0))&1)?i:0;return ret; } struct Segment_Tree {int nodenum=0,ls[MAXN<<5],rs[MAXN<<5];struct segnode{ int c,ans,flag; } tree[MAXN<<5];void up(int x){if (tree[x].flag) tree[x].ans=tree[x].c;else tree[x].ans=tree[ls[x]].ans^tree[rs[x]].ans;}void change(int &x,int L,int R,int l,int r,int c){ // cout<<x<<" "<<L<<" "<<R<<" "<<l<<" "<<r<<endl;if (!x) x=++nodenum,tree[x].c=getans(L,R);if (L>=l&&R<=r) { tree[x].flag+=c,up(x); return; }int mid=(L+R)>>1;if (r<=mid) change(ls[x],L,mid,l,r,c);else if (l>mid) change(rs[x],mid+1,R,l,r,c);else change(ls[x],L,mid,l,mid,c),change(rs[x],mid+1,R,mid+1,r,c);up(x);} } segment; int main() {m=read(),n=read(),k=read(),K=1;while (K<=k) K<<=1;for (int i=1;i<=n;i++){int x1=read(),y1=read(),x2=read(),y2=read();a[i*2-1]=(anode){x1,y1,y2,1};a[i*2]=(anode){x2+1,y1,y2,-1}; }sort(a+1,a+(n<<1)+1,compare);int ans=0,rt=0;for (int i=1;i<=(n<<1);i++){ // cout<<a[i].x<<" "<<a[i].l<<" "<<a[i].r<<" "<<a[i].c<<endl;if (a[i].x!=a[i-1].x){int x=getans(a[i-1].x,a[i].x-1),y=segment.tree[1].ans,sx=0,sy=0; // cout<<"Ans:"<<a[i].x<<" "<<a[i].l<<" "<<a[i].r<<" "<<x<<" "<<y<<endl;for (int j=K;j;j>>=1){int sum=sx*sy;sx+=((x&j)>0),sy+=((y&j)>0);if ((sx*sy-sum)&1) ans^=j;}}segment.change(rt,1,m,a[i].l,a[i].r,a[i].c);}puts(ans?"Hamed":"Malek");return 0; }

4.[ZROJ十連測 Day5].銀

題目描述

Solution

有題解，思路神仙學不來，貼個程序溜了。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=600005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } char st[MAXN]; int cnt[30]; int lowbit(int x){ return x&(-x); } int main() {int n=read(),SG=0;scanf("%s",st+1);reverse(st+1,st+n+1);for (int i=1;i<=n;i++)if (st[i]=='1'){SG^=lowbit(i);for (int j=20;j>=0;j--) cnt[j]+=((i>>j)&1);}int Case=read();while (Case--){int x=n-read()+1,c;if (st[x]=='1') st[x]='0',c=-1;else st[x]='1',c=1;SG^=lowbit(x);for (int j=20;j>=0;j--) cnt[j]+=((x>>j)&1)*c;if (!SG) { puts("0"); continue; }int mx=20;while (!(SG>>mx)) mx--;printf("%d\n",cnt[mx]);}return 0; }

5.CF1033GChip Game

題目描述

Solution

8會8會，留坑定補$flag$。

總結

以上是生活随笔為你收集整理的博弈论练习2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。