【Codeforces 812E】Sagheer and Apple Tree

相关链接

题目传送门:http://codeforces.com/contest/812/problem/E
官方题解:http://codeforces.com/blog/entry/52318

解题报告

我们发现,如果操作同叶子结点的深度奇偶性不同的结点
那么对手总可以操作刚刚你操作的那些苹果

所以结果只与深度同叶子结点奇偶性相同的点有关
更进一步观察发现,实质上就是这些点组成的$NIM$游戏
于是乘一乘、加一加就好了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 10000009;

int n, prt, tot, dep[N], v[N], in[N];
int head[N], nxt[N], to[N], cnt[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1; in[v]++; in[u]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

void DFS(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		dep[to[i]] = dep[w] + 1;
		DFS(to[i]);
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i <= n; i++) {
		v[i] = read();
	}
	for (int i = 2; i <= n; i++) {
		AddEdge(read(), i);
	}
	DFS(1);
	for (int i = 2; i <= n; ++i) {
		if (in[i] == 1) {
			prt = (dep[i] & 1);
			break;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			ans ^= v[i];
		}
	}
	LL vout = 0;
	tot = n;
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) == prt) {
			cnt[v[i]]++;
			--tot;
		}
	}
	for (int i = 1; i <= n; i++) {
		if ((dep[i] & 1) != prt) {
			int tt = ans ^ v[i];
			if (tt < M) {
				vout += cnt[tt];
			}
		}
	}
	if (!ans) {
		vout += tot * (tot - 1ll) / 2;
		vout += (n - tot) * (n - tot - 1ll) / 2;
	}
	cout<<vout<<endl;
	return 0;
}

【算法笔记】Bouton定理

概述

对于NIM游戏,相信大家都知道一个结论:

每一堆石子的数量给异或起来,若为0则先手必败,否则先手必胜

这个结论就是Bouton定理。
但对于这个定理,我一直没有找到简洁的证明
今日再一次翻看《白书》,终于觅得,于是记录于此

Bouton定理的结论

对于原版的NIM游戏
若每队石子的个数的NIM和为0,则先手必败
否则,先手必胜

Bouton定理的证明

参见《算法竞赛·入门经典·训练指南》P135

后记

为什么感觉这么鬼畜…..
最关键的证明部分是一个引用QAQ
唉,懒癌晚期,放弃治疗…..
jslugcg9lhkh0ix9zh

【Codeforces 662A】Gambling Nim

题目传送门:http://codeforces.com/problemset/problem/662/A
官方题解:http://codeforces.com/blog/entry/44408

说人话就是亦或和为0的概率是多少
考虑把ai全部亦或起来为sum的话
那就是求{ai^bi}有多少个子集亦或和为sum
这样的话,岂不就是线性基的拿手好戏了?

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500000+9;
const int SGZ = 61+9;

int n,cnt;
LL a[N],b[N],bas[SGZ],sum; 

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool insert(LL w) {
	for (int i=61;~i;i--) if (w&(1LL<<i)) {
		if (bas[i]) {
			w ^= bas[i];
		} else {
			bas[i] = w;
			return true;
		}
	}	
	return false;
}

inline LL pow(LL w, int t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret *= w;
		w *= w; t >>= 1;
	}
	return ret;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
		b[i] = read();
		sum ^= a[i];
		cnt += insert(a[i] ^ b[i]);
	}
	if (!cnt && !sum) {
		puts("0/1");
	} else if (insert(sum)) {
		puts("1/1");
	} else {
		printf("%I64d/%I64d\n",pow(2LL,cnt)-1,pow(2LL,cnt));
	}
	return 0;
}

【BZOJ 3105】[cqoi2013] 新Nim游戏

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3105

这个题目,考虑两个回合之后。
假如对手能够在在第二个回合搞出一个Nim和为0的东西,那我们岂不是输了?
所以我们不能给对手搞出Nim和为0的机会,而Nim和为Xor,不存在子集Nim和为0是线性无关
而我们又要子集最大(损失最小),所以我们要求的是一个极大线性无关子集
然后我们发现,这货不是线性基吗?
于是水之

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int bas[32],arr[109];
inline bool update(int w) {
	for (int i=0;i<=31;i++) if (w & 1<<i) 
		if (bas[i]) w ^= bas[i];
		else {bas[i] = w; return 1;}
	return 0;
}

int main(){
	int k = read(); LL vout = 0; 
	for (int i=1;i<=k;i++) arr[i] = read(), vout += arr[i];
	sort(arr+1,arr+1+k);
	for (int i=k;i;i--) vout -= update(arr[i])*arr[i];
	printf("%lld\n",vout);
	return 0;
}

【POJ 2425】A Chess Game

题目传送门:http://poj.org/problem?id=2425

这个题目,第一眼想到肯定是状压SG,然后发现MLE+TLE
于是发现棋子之间互不影响,于是等价为NIM
证明不会QAQ,不过贾志豪的论文里讲:这是性质QAQ

MD之前看的中文体面有问题,浪费了两个小时
以后还是乖乖看原题面吧!

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000+9;

int n,head[MAXN],T,nxt[MAXN*MAXN],to[MAXN*MAXN],m,f[MAXN],vout,dig[MAXN],tot;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void AddEdge(int u, int v){
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

int Get(int w){
	if (!~f[w]) { 
		int tmp = ++tot;
		for (int i=head[w];i;i=nxt[i]) Get(to[i]);
		for (int i=head[w];i;i=nxt[i]) dig[f[to[i]]] = tmp;
		for (int i=0;i<MAXN;i++) if (dig[i] != tmp) {f[w] = i; break;}
	} return f[w];
}

int main(){
	while (~scanf("%d",&n)) {
		T = 0; memset(head,0,sizeof(head)); memset(f,-1,sizeof(f));
		for (int i=1,tmp;i<=n;i++) {
			tmp = read(); 
			if (!tmp) f[i] = 0;
			else for (int j=tmp;j;j--) AddEdge(i,read()+1);
		}
		while (m = read()) { vout = 0;
			for (int i=1;i<=m;i++) vout ^= Get(read()+1); 
			if (!vout) printf("LOSE\n");
			else printf("WIN\n");
		} 
	}
	return 0;
} 

【POJ 2975】Nim

题目传送门:http://poj.org/problem?id=2975

最开始一直在想,怎么优化DP
然而后来发现,这TM只求有效的第一步有几种走法QAQ

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 1000+9;

int arr[MAXN],n,sta,vout; 

int main(){
	while (cin>>n && n) { 
		sta = vout = 0;
		for (int i=1;i<=n;i++) cin>>arr[i], sta ^= arr[i];
		if (sta) for (int i=1;i<=n;i++) {
			sta ^= arr[i]; 
			if (sta < arr[i]) vout++;
			sta ^= arr[i];
		}
		printf("%d\n",vout);
	}
	return 0;
}

【BZOJ 1022】[SHOI2008] 小约翰的游戏John

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1022

anti-nim游戏,证明的话,网上到处都是,不过我还想是想自己证一下,证明如下:

结论:
1)所有堆中石子的个数都为1:如果NIM和为0,则先手必胜,否则后手必胜
2)有至少一堆的石子个数大于1,如果NIM和大于0,则先手必胜,否则后手必胜

证明:
1)如果所有堆中石子数都为1:
不难看出决策也唯一,结论显然成立
2)有至少一堆的石子个数大于1:
如果NIM和大于0,显然先手可以通过调整使最高的1为1的那堆石子,使NIM和变为0,使得先手必败,故先手必胜
如果NIM和为0,则先手无论调整任意一堆石子的个数,都会使NIM和变为大于0,使得先手必胜,故先手必败
该条证明,看似是循环证明,但实际上,堆中的石子数一直在减少,所以我们可以加上如下边界条件,使得该证明严密:
不难发现,大于1的堆数在慢慢减少,总有一个时刻,只会有一堆的石子数大于1。明显,此时的NIM和不为0。
显然现在的先手可以控制留下奇数个单石子堆或是偶数个。这将直接决定游戏的胜负。也就是说谁进入“只有一个多石子堆的状态”谁胜
明显,该状态符合NIM和大于0的情况,符合该情况中描述的先手必胜。而NIM和不为0的情况,也将间接转移进入该情况。
所以这个证明过程,不会一直循环下去,且结果确定。

哎,这个证明我自己都觉得是乱搔,大家还是看论文里的证明吧:
https://oi.qizy.tech/wp-content/uploads/2016/08/sg_jiazhihao.pdf

#include<iostream>
#include<cstdio>
using namespace std;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

int main(){
	int T = read(); while (T--) {
		int n = read(),sg=0,tag=0;
		for (int i=1,tmp;i<=n;i++) {
			tmp = read(); sg ^= tmp;
			if (tmp > 1)  tag = 1;
		}
		if ((!sg && !tag) || (sg && tag)) printf("John\n");
		else printf("Brother\n");
	}
	return 0;
}