### 情况三 ： $n > 2L$

$n=7$的时候，Alice 可以这样做，她能取得胜利：

$$—\;—\;—\;S\;—\;—\;—$$

$$—\;—\;S\;S\;—\;—\;—$$

$$—\;—\;S\;S\;—\;—\;S$$

$$S\;—\;—\;S\;—\;—\;—$$

n 为奇数的时候，Alice 肯定有优势，可能会赢，由上面的讨论，易知 $n \geq 7$的时候是一定能赢的，因为 Alice 能构造出不可能平局的阵型 $S\;—\;—\;S$
n 为偶数的时候，则是 Bob 有优势，这个时候 Alice 会尽力阻止 Bob 形成不可能平局阵型，因此 Alice 会在正中间下一个 O，

$$—\;—\;—\;S\;—\;—\;—\;—\;O\;—\;—\;—\;—\;—\;—\;—$$

$$SG(i)=mex \{SG(j)\;xor\; SG(k) | i \lt j \leq k = n \}$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define ll long long
#define N 105
int T, n, num[N], a, b, c, sg[N], now, fl[N], ans;
inline int mex (int x)
{
int i = 0;
while (fl[i] == x) ++i;
return i;
}
int main ()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
fo (i, 1, n)
scanf("%d", &num[i]);
sg[n] = 0;
fd (i, n - 1, 1)
{
++now;
fo (j, i + 1, n)
fo (k, j, n)
fl[sg[j] ^ sg[k]] = now;
sg[i] = mex(now);
//          printf("sg[%d] = %d\n", i, sg[i]);
}
ans = 0;
fo (i, 1, n)
if (num[i] & 1) ans ^= sg[i];
if (!ans) printf("-1 -1 -1\n0\n");
else
{
int cnt = 0;
a = b = c = 0;
fo (i, 1, n)
if (num[i])
{
fo (j, i + 1, n)
fo (k, j, n)
if ((ans ^ sg[i] ^ sg[j] ^ sg[k]) == 0)
{
if (!a)
{
a = i; b = j; c = k;
}
++cnt;
}
}
printf("%d %d %d\n%d\n", a - 1, b - 1, c - 1, cnt);
}
}
}


#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define ll long long
#define N 105
int T, n, num[N], a, b, c, sg[N], now, fl[N], ans;
inline int mex (int x)
{
int i = 0;
while (fl[i] == x) ++i;
return i;
}
int main ()
{
scanf("%d", &n);
sg[0] = 0;
fo (i, 1, n)
{
++now;
fl[0] = now; //choose zero
fo (j, 1, i - 1)
fl[sg[j]] = now;
fo (j, 1, i - 1)
fo (k, j + 1, i - 1)
fl[sg[j] ^ sg[k]] = now;
sg[i] = mex(now);
}
fo (i, 1, n)
printf("%d %d %d\n", i, sg[i], i * 2 - sg[i]);
}


$$SG[i]=i*2- ( count ( a [ i ] -1 ) \& 1 ) -1$$

（注意题目中的 $a[i]$可能重复，要去重）

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define lowbit(x) (x & -x)
int n, a[1005], ans, sg;
inline int count (int x)
{
int ret = 0;
while (x)
{
x -= lowbit(x);
++ret;
}
return ret;
}
int main ()
{
while (~scanf("%d", &n))
{
ans = 0;
fo (i, 1, n)
scanf("%d", &a[i]);
std::sort(a + 1, a + n + 1);
n = std::unique(a + 1, a + n + 1) - a - 1;
fo (i, 1, n)
{
++a[i];
if (a[i] == 1) sg = 1; else
sg = a[i] * 2 - ((count(a[i] - 1) & 1) ? 2 : 1);
ans ^= sg;
}
if (ans)
printf("No\n");
else
printf("Yes\n");
}
}


AFO 有缘再见

### 2 条评论

Orz 跪膜巨犇

#### quhengyi11 · 2018年10月1日 7:44 下午

您太强啦 qwq，也祝您 NOIP2018rp++