【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;
}

【POJ 3922】A simple stone game

相关链接

题目传送门:http://poj.org/problem?id=3922
神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2012/12/19/2825539.html

解题报告

根据$k = 1$的情况,我们发现在二进制下,我们取走最低位的$1$,对手取不走较高位的$1$
所以如果不是二的整次幂,那么先手必胜

再来看看$k = 2$的情况
根据$HINT$我们把每个整数拆成若干个不同、不相邻的斐波那契数之和,表示成二进制状态
之后跟据$k = 1$时的推论,我们取走最低位的$1$,对手不能直接取走较高位的$1$

先在我们看我们依赖拆分数列的哪些性质:

存在一种拆分使得选中的项的任意相邻两项超过$k$倍

于是我们尝试构造拆分数列$a_i$
我们设$b_i$为$a_1 \to a_i$能拼出的极长的前缀长度
不难发现$a_i = b_{i-1}+1, b_i=a_i+b_j$,其中$j$尽可能大,且$a_j k < a_i$

于是这题就做完啦
似乎这个问题还是博弈论里的一个经典问题,叫”$k$倍动态减法问题”
似乎某年国家集训队论文里还提出了另外的算法,对于某些数据会更优

Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[N]; 

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;
}

int main() {
	for (int t = 1, T = read(); t <= T; ++t) {
		n = read(); k = read();
		a[0] = b[0] = x = y = 0;
		while (a[x] < n) {
			a[x + 1] = b[x] + 1;
			for (++x; (LL)a[y + 1] * k < a[x]; ++y);
			b[x] = y? b[y] + a[x]: a[x];
		}
		if (a[x] == n) {
			printf("Case %d: lose\n", t);
		} else {
			int ans = 0;
			for (; n && x; --x) {
				if (n >= a[x]) {
					n -= a[x];
					ans = a[x];
				}
			}
			printf("Case %d: %d\n", t, ans);
		}
	}
	return 0;
}

【BZOJ 2437】[NOI2011] 兔兔与蛋蛋

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2437
神犇题解:http://blog.csdn.net/qpswwww/article/details/45368587

解题报告

我们先将整个棋盘黑白染色,将空格棋子所在方格的颜色分类
在可相互转化的状态之间连边,那么这就是一张二分图了

那么原题的问题转换为:

给定一张二分图,每次沿边移动一次
每个点只能到达一次,最后谁不能动谁就输了
询问每一个点作为起点时是否先手必胜

考虑一个点如果在任意一种最大匹配当中,那么先手每一次走匹配边,则后手必败
换一句话来说,如果一个点一定在最大匹配当中,那么这个点是先手必胜的
再考虑一下,如果一个点不一定在最大匹配当中,那么删掉这个点之后存在最大匹配,那后手走到那个点去就可以了!
再换一句话来说,如果一个点不一定在最大匹配中,那么这个点先手必败

现在我们只需要求出一个点是否在最大匹配中就可以了!
我们可以枚举这个点,将其删掉后跑最大匹配验证,但复杂度是$O(n^4)$的
或者我们可以用今年冬令营的那个一般图匹配的算法来做,时间复杂度是$O(n^3)$的

不过我们可以又一个常数更小的算法

我们可以先求出一个最大匹配,然后假设当点在点$a$
将其删掉后,看$a$的匹配点$b$还能不能匹配即可

吐槽

博弈题居然还能这么玩!
真的是长见识了 _(:з」∠)_
不过代码好难写啊,不想写代码 ┑( ̄Д  ̄)┍

【BZOJ 3576】[HNOI2014] 江南乐

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3576
神犇题解Ⅰ:http://blog.csdn.net/regina8023/article/details/45034045
神犇题解Ⅱ:http://blog.csdn.net/gromah/article/details/27326991

解题报告

这么麻烦的游戏过程,不是找规律就是SG函数来做咯!
然后手玩一下样例,发现这货并没有什么性质的样子

于是考虑SG函数:
因为每一堆石子相互独立,由SG定理可得:
一个石子堆的SG函数等于分开后各堆石子的SG函数的NIM和
于是考虑暴力枚举M。
这样的话,我们就可以在 $ O({n^2})$ 的时间复杂度内解决该问题了

更进一步,我们发现在枚举M的过程中
因为亦或同一个数偶数次相当于没有亦或
所以我们不必枚举所有的M,只需要分奇偶讨论一下就可以了
于是就用莫比乌斯反演经常用到的“下底函数分块”来解决这个问题啦!
时间复杂度:$ O(n\sqrt n )$

Code

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

const int N = 100000+9;

int F,T,n,vis[N],sg[N];

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;
}

inline int Get_Sg(int w) {
	if (w < F) return sg[w] = 0;
	else if (~sg[w]) return sg[w];
	else if (sg[w] = 0, 1) {
		for (int l=2,r,a,b;l<=w;l=r+1) {
			r = w / (w / l);
			for (int i=l;i<=min(w,l+1);i++)	{
				Get_Sg(w / i + 1);
				Get_Sg(w / i);
			}
		}
		for (int l=2,r,a,b,tmp;l<=w;l=r+1) {
			r = w / (w / l); 
			for (int i=l,tmp=0;i<=min(w,l+1);i++,tmp=0)	{
				if ((w % i) & 1) tmp ^= sg[w / i + 1];
				if ((i - (w % i)) & 1) tmp ^= sg[w / i];
				vis[tmp] = w;
			}
		}
		for (int i=0;;i++)
			if (vis[i] != w)
				return sg[w] = i;
	}
}

int main(){
	memset(sg,-1,sizeof(sg));
	T = read(); F = read();
	for (int t=T,vout;t;--t) {
		n = read(); vout = 0;
		for (int i=1;i<=n;i++) 
			vout ^= Get_Sg(read());
		if (t<=1) printf("%d\n",!vout?0:1);
        else printf("%d ",!vout?0:1);
	}
	return 0;
}

【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;
}

【算法笔记】博弈论

这货,做了一点题,看了一点论文,觉得有以下几个要点:
1)先猜结论,之后再想办法证明
2)不要试图手玩,玩不出来的
3)SG值相同的子游戏,对于游戏和来说可以相互替换
4)以上都不行的时候,就先找一种比较宽泛的必胜/必败状态,再试图推广

另外,还学到了一点绍一的黑科技,现在先暂时不研究,特意截图以供以后研究:
sg_min_one

【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;
}

【SPOJ 2021】Moving Pebbles

题目传送门:http://www.spoj.com/problems/PEBBMOV/

同BZOJ_1982

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

const int MAXN = 100000+9;

int arr[MAXN],n;

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(){
	while (~scanf("%d",&n)) {
		for (int i=1;i<=n;i++) arr[i] = read();
		sort(arr+1,arr+1+n);
		if (n%2) {cout<<"first player"<<endl; continue;} int tag = 1;
		for (int i=1;i<=n;i+=2) if (arr[i] != arr[i+1]) {cout<<"first player"<<endl; tag = 0; break;}
		if (tag) cout<<"second player"<<endl;
	}
	return 0;
} 

【BZOJ 1982】[Spoj 2021] Moving Pebbles

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

同POJ_1740

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

const int MAXN = 100000+9;

int arr[MAXN],n;

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(){
	while (~scanf("%d",&n)) {
		for (int i=1;i<=n;i++) arr[i] = read();
		sort(arr+1,arr+1+n);
		if (n%2) {cout<<"first player"<<endl; continue;} int tag = 1;
		for (int i=1;i<=n;i+=2) if (arr[i] != arr[i+1]) {cout<<"first player"<<endl; tag = 0; break;}
		if (tag) cout<<"second player"<<endl;
	}
	return 0;
} 

【POJ 1740】A New Stone Game

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

这一次,打印了二维的情况,没能找出规律
可耻地看了题解:
如果有偶数堆,且石子个数相同的堆可以两两配对,则先手必败,因为不论先手怎么走,后手都可以走一样的步骤
其余的情况,先手都可以通过一次移动,达到上述的情况,即后手必败

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

const int MAXN = 10+9;

int arr[MAXN],n;

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(){
	while (n = read()) {
		for (int i=1;i<=n;i++) arr[i] = read();
		sort(arr+1,arr+1+n);
		if (n%2) {cout<<1<<endl; continue;} int tag = 1;
		for (int i=1;i<=n;i+=2) if (arr[i] != arr[i+1]) {cout<<1<<endl; tag = 0; break;}
		if (tag) cout<<0<<endl;
	}
	return 0;
} 

【POJ 2234】Matches Game

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

卧槽,真™有板题QAQ
证明可以看这里:https://maxmute.com/

#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 n; while (~scanf("%d",&n)) {
		int vout = read();
		for (int i=1;i<n;i++) vout ^= read(); 
		if (!vout) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	return 0;
} 

【Vijos 1196】吃糖果游戏

题目传送门:https://vijos.org/p/1196

卧槽,这个和1655不一毛一样吗?

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

const int MAXN = 100000;

char s1[MAXN],s2[MAXN];
int l1,l2;

inline bool leg(int c){
	return c == 2 || c == 3 || c == 7 || c == 8;
}

int main(){
	while (scanf("%s%s",s1+1,s2+1) == 2){
		l1 = strlen(s1+1); 
		l2 = strlen(s2+1);
		if (leg(s1[l1]-'0') && leg(s2[l2]-'0')) cout<<"Shadow"<<endl;
		else cout<<"Matrix67"<<endl;
	}
	return 0;
}

【Vijos 1655】萌萌的糖果博弈

题目传送门:https://vijos.org/p/1655

这个题嘛,暴力打印一下40以内的情况如下:
78973673526
不难发现,个位为2,3,7,8的话,则为先手必败
于是乎,读入+输出即可

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

const int MAXN = 100000;

char s1[MAXN],s2[MAXN];
int l1,l2;

inline bool leg(int c){
	return c == 2 || c == 3 || c == 7 || c == 8;
}

int main(){
	while (scanf("%s%s",s1+1,s2+1) == 2){
		l1 = strlen(s1+1); 
		l2 = strlen(s2+1);
		if (leg(s1[l1]-'0') && leg(s2[l2]-'0')) cout<<"SheepDaddy"<<endl;
		else cout<<"MengMeng"<<endl;
	}
	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的情况,也将间接转移进入该情况。
所以这个证明过程,不会一直循环下去,且结果确定。

哎,这个证明我自己都觉得是乱搔,大家还是看论文里的证明吧:
http://oi.cyo.ng/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;
}