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 / 23 elif i % 4 == 1:4 if once[i]:5 m1 = i6 towin[i] = 17 else:8 towin[i] = (i - m1) / 2 + 19 elif i % 4 == 3:10 if once[i]:11 m3 = i12 towin[i] = 113 else:14 towin[i] = (i - m3) / 2 + 1
首先用质数筛筛出质数。对于取完次数为 k 的房间,需要第 k / 2 + 1 轮到这个房间才能有人输。
1N = int(5e6)2once = [True] * (N + 1)3prime = []4for 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 break11 once[v * i] = False12 if i % v == 0:13 break14m3 = 3 # largest i: 4i + 3 prime15m1 = 132 collapsed lines
16towin = [0, 1, 1, 1] + [0] * int(N + 10)17for i in range(4, int(N + 1)):18 if i % 2 == 0:19 towin[i] = i // 220 elif i % 4 == 1:21 if once[i]:22 m1 = i23 towin[i] = 124 else:25 towin[i] = (i - m1) // 2 + 126 elif i % 4 == 3:27 if once[i]:28 m3 = i29 towin[i] = 130 else:31 towin[i] = (i - m3) // 2 + 132
33t = int(input())34for _ in range(t):35 n = int(input())36 a = [0] + list(map(int, input().split()))37 firstmin = 1e938 win = 039 for i in range(1, n + 1):40 rd = towin[a[i]] // 2 + 141 if rd < firstmin:42 firstmin = rd43 win = towin[a[i]] % 244 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
1n = int(input())2a = [int(input()) for _ in range(n)]3a.sort()4t = 05minans = 1e96for s in range(n):7 while t + 1 <= n - 1 and a[t + 1] - a[s] + 1 <= n:8 t += 19 minans = min(minans, n - (t - s + 1))10print(minans)11totdis = a[n - 1] - a[0] - (n - 1)12print(totdis - min(a[2] - a[1], a[n - 1] - a[n - 2]) + 1)