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


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


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


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