教学计划-找规律II

Circular Barn

https://usaco.org/index.php?page=viewproblem2&cpid=1255

首先考虑一个房间内如果一直拿，谁会赢。从 1 开始推导，发现当数量为 4k 时，后手赢，其他先手赢。

需要拿几次可以取完？如果后手赢，那么先手要尽可能让对方赢所需拿的次数多一点。如果先手赢，每个房间遵循尽快赢的策略。

有，若偶数，则次数为 i // 2，否则若为 4k + 1，则取最大质数满足取完后为 4k，而 4k + 3 类似:

1
    if i % 2 == 0:
2
        towin[i] = i / 2
3
    elif i % 4 == 1:
4
        if once[i]:
5
            m1 = i
6
            towin[i] = 1
7
        else:
8
            towin[i] = (i - m1) / 2 + 1
9
    elif i % 4 == 3:
10
        if once[i]:
11
            m3 = i
12
            towin[i] = 1
13
        else:
14
            towin[i] = (i - m3) / 2 + 1

首先用质数筛筛出质数。对于取完次数为 k 的房间，需要第 k / 2 + 1 轮到这个房间才能有人输。

1
N = int(5e6)
2
once = [True] * (N + 1)
3
prime = []
4
for i in range(2, N + 1):
5
    if once[i]:
6
        prime.append(i)
7
    for j in range(len(prime)):
8
        v = prime[j]
9
        if v * i > N:
10
            break
11
        once[v * i] = False
12
        if i % v == 0:
13
            break
14
m3 = 3 # largest i: 4i + 3 prime
15
m1 = 1
32 collapsed lines
16
towin = [0, 1, 1, 1] + [0] * int(N + 10)
17
for i in range(4, int(N + 1)):
18
    if i % 2 == 0:
19
        towin[i] = i // 2
20
    elif i % 4 == 1:
21
        if once[i]:
22
            m1 = i
23
            towin[i] = 1
24
        else:
25
            towin[i] = (i - m1) // 2 + 1
26
    elif i % 4 == 3:
27
        if once[i]:
28
            m3 = i
29
            towin[i] = 1
30
        else:
31
            towin[i] = (i - m3) // 2 + 1
32

33
t = int(input())
34
for _ in range(t):
35
    n = int(input())
36
    a = [0] + list(map(int, input().split()))
37
    firstmin = 1e9
38
    win = 0
39
    for i in range(1, n + 1):
40
        rd = towin[a[i]] // 2 + 1
41
        if rd < firstmin:
42
            firstmin = rd
43
            win = towin[a[i]] % 2
44
    if win == 1:
45
        print("Farmer John")
46
    else:
47
        print("Farmer Nhoj")

Sleepy Cow Herding

https://usaco.org/index.php?page=viewproblem2&cpid=918

最少的步数：假设最后所有奶牛集中到 p ~ q，显然有 a[0] <= p < q <= a[n - 1]，长度为 n，那么发现任意指定一个 p ~ q，每一步都可以把一头在外面的奶牛移进来。只需要双指针法找到长度为 n 的包含奶牛个数最多的区间就行。

最多的步数：定义总距离为每对相邻奶牛之间距离 - 1 的和。如果边缘有两头奶牛相邻，发现每步一定可以只让距离减 1，而第一步一定会把两端移到中间某个位置，故最优方案就是两端先造成一个相邻，之后不断减 1

1
n = int(input())
2
a = [int(input()) for _ in range(n)]
3
a.sort()
4
t = 0
5
minans = 1e9
6
for s in range(n):
7
    while t + 1 <= n - 1 and a[t + 1] - a[s] + 1 <= n:
8
        t += 1
9
    minans = min(minans, n - (t - s + 1))
10
print(minans)
11
totdis = a[n - 1] - a[0] - (n - 1)
12
print(totdis - min(a[2] - a[1], a[n - 1] - a[n - 2]) + 1)

作业题:

COW Operations

https://usaco.org/index.php?page=viewproblem2&cpid=1232