## 【Codeforces 812E】Sagheer and Apple Tree

### 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];

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

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
for (int i = 1; i <= n; i++) {
}
for (int i = 2; i <= n; 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

### 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];

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) {
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 3576】[HNOI2014] 江南乐

### 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];

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));
for (int t=T,vout;t;--t) {
n = read(); vout = 0;
for (int i=1;i<=n;i++)
if (t<=1) printf("%d\n",!vout?0:1);
else printf("%d ",!vout?0:1);
}
return 0;
}

## 【Codeforces 662A】Gambling Nim

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

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(){
for (int i=1;i<=n;i++) {
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游戏

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

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

MD之前看的中文体面有问题，浪费了两个小时

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

const int MAXN = 1000+9;

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){
}

int Get(int w){
if (!~f[w]) {
int tmp = ++tot;
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)) {
for (int i=1,tmp;i<=n;i++) {
if (!tmp) f[i] = 0;
}
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

#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

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

const int MAXN = 100000+9;

int arr[MAXN],n;

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

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

const int MAXN = 100000+9;

int arr[MAXN],n;

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

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

const int MAXN = 10+9;

int arr[MAXN],n;

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(){
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

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

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

## 【Vijos 1196】吃糖果游戏

#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);
else cout<<"Matrix67"<<endl;
}
return 0;
}

## 【Vijos 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);
else cout<<"MengMeng"<<endl;
}
return 0;
}

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

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

1）所有堆中石子的个数都为1：如果NIM和为0，则先手必胜，否则后手必胜
2）有至少一堆的石子个数大于1，如果NIM和大于0，则先手必胜，否则后手必胜

1）如果所有堆中石子数都为1：

2）有至少一堆的石子个数大于1：

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

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--) {