题解：P8901 [USACO22DEC] Circular Barn S
先考虑 $N = 1$ 的情况。若先手胜，我们称 $a_i$ 为必胜点，否则为必败点。显然 $1,2,3$ 均为必胜点；而 $4 = 1 + 3 = 2 + 2$，无论如何都是后手胜，所以为必败点。如果这时候你不知道如何去分析，可以尝试打出必败点的表（猜测必败点并不多），对于一个 $a_i$ 若无法拆分成质数或 $1$ 与另一个比它小的必败点的形式，那么这个 $a_i$ 便是必败点。
1
2
3
4
5
|
ok = 0;
for (auto i : lose)
if (p[x - i]) ok = 1;
if (!ok) lose.push_back (i)
|
通过打表发现必败点都是 $4$ 的倍数。其实这很好理解，由于 $4$ 为最小的必败点，那么对于 $(4,8)$ 的数，都可以通过 $4 + 1,4 + 2,4 + 3$ 来表示，而 $8$ 只能表示成 $4$ 加上一个质数，显然不存在。那么以此类推，可知必败点为 $4k(k \in N^*)$。
现在将问题还原，对于某一格的数，如果是必败点，那么先手会尽量拖延时间，也就是说选择数使其能够经过尽可能多的轮数；否则就会用尽可能少的轮数结束来赢得游戏。现在进行分类讨论：
$a_i$ 为 $1$ 或质数，显然一轮就能结束；
$a_i$ 为奇数，从第一个不大于它的质数（或 $1$，下同）开始判断，找到尽可能大的质数符合质数加上必败点的形式；
$a_i$ 为偶数，无论是必胜还是必败点，每次都只会取 $2$。下面给出证明：
- $a_i$ 为必败点，先手会尽量拖延时间，取的数尽可能小，不难发现取 $2$ 会比取 $1$ 优。
- $a_i$ 为必胜点，由于必败点为偶数，所以只能取 $2$ 这一个唯一的偶质数。
至此，取数的策略已经讲解完毕。所以只要找到若干轮后最先结束的 $a_i$，判断其是必胜点还是必败点即可。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 5e5 + 5,M = 5e6 + 500;
const int MOD = 1e9 + 7;
inline int read ();
int t,n,ok,times,cnt,a[MAX],vis[M + 5],p[MAX];
int main ()
{
for (int i = 2;i <= M;++i)
{
if (!vis[i]) p[++cnt] = i;
for (int j = 1;j <= cnt;++j)
{
if (i * p[j] > M) break;
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
p[0] = 1;
t = read ();
while (t--)
{
n = read ();
ok = 1;times = INF;
for (int i = 1;i <= n;++i) a[i] = read ();
for (int i = 1;i <= n;++i)
{
if (a[i] % 2 == 0 && times > a[i] / 4) ok = (a[i] % 4 != 0),times = a[i] / 4;
if (a[i] & 1)
{
int x = upper_bound (p,p + 1 + cnt,a[i]) - p - 1;
while (~x)
{
if ((a[i] - p[x]) % 4 == 0)
{
if (times > (a[i] - p[x]) / 4) ok = 1,times = (a[i] - p[x]) / 4;
break;
}
--x;
}
}
}
puts (ok ? "Farmer John" : "Farmer Nhoj");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
