网站建设与维护服务,敦化市建设局网站,wordpress自建,网站高质量链群怎么做博弈论练习2 \;1.AGC010F - Tree Game
题目描述
Solution
一道简单博弈题#xff08;不知道为啥能作为AGC的F题#xff09;。 考虑树形dpdpdp#xff0c;设f[x]f[x]f[x]表示以xxx为根的子树中是否先手必胜。
则f[x]1f[x]1f[x]1当且仅当能找到xxx的子节点vvv满足f[v]0f[v…博弈论练习2
\;
1.AGC010F - Tree Game
题目描述
Solution
一道简单博弈题不知道为啥能作为AGC的F题。 考虑树形dpdpdp设f[x]f[x]f[x]表示以xxx为根的子树中是否先手必胜。
则f[x]1f[x]1f[x]1当且仅当能找到xxx的子节点vvv满足f[v]0f[v]0f[v]0且a[x]a[v]a[x]a[v]a[x]a[v]因为这样就可以把后手摁死在vvv子树里让后手输掉自己就赢了。
对于每一个结点都把它当做整一棵树的根dpdpdp一遍即可。 时间复杂度O(n2)O(n^2)O(n2)
#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;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int a[MAXN],f[MAXN];
vectorint e[MAXN];
bool dfs(int x,int father)
{for (auto v:e[x]){if (vfather) continue;dfs(v,x);if (a[x]a[v]!f[v]) return f[x]1;} return f[x]0;
}
int main()
{int nread();for (int i1;in;i) a[i]read();for (int i1;in;i){int uread(),vread();e[u].PB(v);e[v].PB(u);}for (int i1;in;i)if (dfs(i,0)) printf(%d ,i);return 0;
}
2.SPOJ COT3 - Combat on a tree
题目描述
Solution
一道SG 数据结构好题。
每一次选择一条到根的路径清零就相当于断成若干个独立的子树因此就可以求子树SGSGSG值计算答案用可持久化trietrietrie树维护整体xorxorxor和求mexmexmex。
#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;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN200005;
const int MAXMMAXN5;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int sum[MAXN],c[MAXN],rt[MAXN],sg[MAXN],up[MAXN];
vectorint e[MAXN],Ans;
struct Trie_Tree
{int nodenum0,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[xnodenum]Dep;down(x);if (Dep31) { flag[x]1; return; } if (y(1(31-dep[x]-1))) Insert(ch[x][1],y,Dep1);else Insert(ch[x][0],y,Dep1);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 xy;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 (vfather) 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 (vfather) 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];
// coutx father sum[x] sg[x] up[x]endl;for (auto v:e[x]){if (vfather) continue;getans(v,x);}if ((!c[x])((up[x]^sum[x])0)) Ans.PB(x);
}
int main()
{int nread();for (int i1;in;i) c[i]read();for (int i1;in;i){int uread(),vread();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
典型的翻硬币博弈模型。 整体的SGSGSG值为所有单独一个格子为黑色的SGSGSG值的异或和。 离散化行线段树维护列信息求解。
#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;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN100005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }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.xy.x; }
int getans(int l,int r)
{l--;int ret0;for (int i1;ik;i1) ret|((r/i-l/i-(i*2k?r/i/2-l/i/2:0))1)?i:0;return ret;
}
struct Segment_Tree
{int nodenum0,ls[MAXN5],rs[MAXN5];struct segnode{ int c,ans,flag; } tree[MAXN5];void up(int x){if (tree[x].flag) tree[x].anstree[x].c;else tree[x].anstree[ls[x]].ans^tree[rs[x]].ans;}void change(int x,int L,int R,int l,int r,int c){
// coutx L R l rendl;if (!x) xnodenum,tree[x].cgetans(L,R);if (LlRr) { tree[x].flagc,up(x); return; }int mid(LR)1;if (rmid) change(ls[x],L,mid,l,r,c);else if (lmid) change(rs[x],mid1,R,l,r,c);else change(ls[x],L,mid,l,mid,c),change(rs[x],mid1,R,mid1,r,c);up(x);}
} segment;
int main()
{mread(),nread(),kread(),K1;while (Kk) K1;for (int i1;in;i){int x1read(),y1read(),x2read(),y2read();a[i*2-1](anode){x1,y1,y2,1};a[i*2](anode){x21,y1,y2,-1}; }sort(a1,a(n1)1,compare);int ans0,rt0;for (int i1;i(n1);i){
// couta[i].x a[i].l a[i].r a[i].cendl;if (a[i].x!a[i-1].x){int xgetans(a[i-1].x,a[i].x-1),ysegment.tree[1].ans,sx0,sy0;
// coutAns:a[i].x a[i].l a[i].r x yendl;for (int jK;j;j1){int sumsx*sy;sx((xj)0),sy((yj)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;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char st[MAXN];
int cnt[30];
int lowbit(int x){ return x(-x); }
int main()
{int nread(),SG0;scanf(%s,st1);reverse(st1,stn1);for (int i1;in;i)if (st[i]1){SG^lowbit(i);for (int j20;j0;j--) cnt[j]((ij)1);}int Caseread();while (Case--){int xn-read()1,c;if (st[x]1) st[x]0,c-1;else st[x]1,c1;SG^lowbit(x);for (int j20;j0;j--) cnt[j]((xj)1)*c;if (!SG) { puts(0); continue; }int mx20;while (!(SGmx)) mx--;printf(%d\n,cnt[mx]);}return 0;
}
5.CF1033GChip Game
题目描述
Solution
8会8会留坑定补flagflagflag。
