Posts with tag 240929

教学计划-找规律II

2024-09-29
240929julyfunnoteswilliam工作

Circular Barnhttps://usaco.org/index.php?page=viewproblem2&cpid=1255首先考虑一个房间内如果一直拿,谁会赢。从 1 开始推导,发现当数量为 4k 时,后手赢,其他先手赢。需要拿几次可以取完?如果后手赢,那么先手要尽可能让对方赢所需拿的次数多一点。如果先手赢,每个房间遵循尽快赢的策略。有,若偶数,则次数为 i // 2,否则若为 4k + 1,则取最大质数满足取完后为 4k,而 4k + 3 类似: if i % 2 == 0: towin[i] = i / 2 elif i % 4 == 1: if once[i]: m1 = i towin[i] = 1 else: towin[i] = (i - m1) / 2 + 1 elif i % 4 == 3: if once[i]: m3 = i towin[i] = 1 else: towin[i] = (i - m3) / 2 + 1首先用质数筛筛出质数。对于取完次数为 k 的房间,需要第 k / 2 + 1 轮到这个房间才能有人输。N = int(5e6) once = [True] * (N + 1) prime = [] for i in range(2, N + 1): if once[i]: prime.append(i) for j in range(len(prime)): v = prime[j] if v * i > N: break once[v * i] = False if i % v == 0: break m3 = 3 # largest i: 4i + 3 prime m1 = 1 towin = [0, 1, 1, 1] + [0] * int(N + 10) for i in range(4, int(N + 1)): if i % 2 == 0: towin[i] = i // 2 elif i % 4 == 1: if once[i]: m1 = i towin[i] = 1 else: towin[i] = (i - m1) // 2 + 1 elif i % 4 == 3: if once[i]: m3 = i towin[i] = 1 else: towin[i] = (i - m3) // 2 + 1 t = int(input()) for _ in range(t): n = int(input()) a = [0] + list(map(int, input().split())) firstmin = 1e9 win = 0 for i in range(1, n + 1): rd = towin[a[i]] // 2 + 1 if rd < firstmin: firstmin = rd win = towin[a[i]] % 2 if win == 1: print("Farmer John") else: print("Farmer Nhoj")Sleepy Cow Herdinghttps://usaco.org/index.php?page=viewproblem2&cpid=918最少的步数:假设最后所有奶牛集中到 p ~ q,显然有 a[0] <= p < q <= a[n - 1],长度为 n,那么发现任意指定一个 p ~ q,每一步都可以把一头在外面的奶牛移进来。只需要双指针法找到长度为 n 的包含奶牛个数最多的区间就行。最多的步数:定义总距离为每对相邻奶牛之间距离 - 1 的和。如果边缘有两头奶牛相邻,发现每步一定可以只让距离减 1,而第一步一定会把两端移到中间某个位置,故最优方案就是两端先造成一个相邻,之后不断减 1n = int(input()) a = [int(input()) for _ in range(n)] a.sort() t = 0 minans = 1e9 for s in range(n): while t + 1 <= n - 1 and a[t + 1] - a[s] + 1 <= n: t += 1 minans = min(minans, n - (t - s + 1)) print(minans) totdis = a[n - 1] - a[0] - (n - 1) print(totdis - min(a[2] - a[1], a[n - 1] - a[n - 2]) + 1)作业题:COW Operationshttps://usaco.org/index.php?page=viewproblem2&cpid=123

No more posts to load.