net网站开发教学视频,项目建设流程,wordpress班级模板,企业网站seo优帮云PP and QQ
思路
删边游戏了解一下#xff0c;其实就是个nim博弈吧#xff0c;只是删边个数有特殊限制#xff0c;
然后就是一个反nim博弈了。
删边定理#xff1a; 遇到分叉口时#xff0c;它的子树上的可操作的sg函数为所有子树节点的sg函数的异或值#xff0c; 然后…PP and QQ
思路
删边游戏了解一下其实就是个nim博弈吧只是删边个数有特殊限制
然后就是一个反nim博弈了。
删边定理 遇到分叉口时它的子树上的可操作的sg函数为所有子树节点的sg函数的异或值 然后这个异或值以一颗子树的形式与这个点连为一棵树然后不断递归得到这一整棵树的sg函数
反nim博弈
必胜满足sg0,numvalue1evensg 0, num_{value 1} evensg0,numvalue1even或者sg0,numvalue11sg 0, num_{value 1} 1sg0,numvalue11,
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h#define mp make_pair
#define pb push_back
#define endl \n
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int pii;const double pi acos(-1.0);
const double eps 1e-7;
const int inf 0x3f3f3f3f;inline ll read() {ll 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 1) (x 3) (c ^ 48);c getchar();}return f * x;
}vectorint G[110];int dfs(int rt, int fa) {int ans 1, now 0;for(int i : G[rt]) {if(i fa) continue;now ^ dfs(i, rt);}return ans now;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T;while(scanf(%d, T) ! EOF) {int ans 0, num 0;for(int cas 1; cas T; cas) {int n; scanf(%d, n);for(int i 1; i n; i) {G[i].clear();}for(int i 1; i n; i) {int x, y;scanf(%d %d, x, y);G[x].pb(y);G[y].pb(x);}int temp dfs(1, 0) - 1;ans ^ temp;if(temp 1) num;}if((ans num) || (!ans !num)) puts(PP);else puts(QQ);}return 0;
}
