2017 Silver January p2

Posted on In , ,

题目

Famer John 和 Bessie 猜拳。在 $n$ 次猜拳中 ($1 ≤ n ≤ 100000$)，Bessie 只会变一次手势，给出 Farmer John 每次出的手势，求 Bessie 能赢的最大次数

思路

将 FJ 每次出的手势装进一个 prefix 数组中，数组的每个元素是当前 FJ 出过三个手势分别的次数。遍历装 FJ 手势的数组，计算每次 Bessie 赢的次数，并求出最大值

复杂度

创建一个 prefix 数组的复杂度为 $O(n)$，遍历数组的复杂度为 $O(n)$，利用 prefix 计算赢的次数的复杂度为 $O(1)$，总复杂度为 $O(n)$，$n$ 最大为 100000，不会超时

代码

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
def win(a, b, i):
	global gestures, prefix

	count = 0
	count += prefix[i][a] + prefix[-1][b] - prefix[i][b]
	return count

lines = open('hps.in').read().strip().split('\n')
n = int(lines[0])
gestures = lines[1:]
prefix = []
for i in range(n):
	if i == 0:
		if gestures[i] == 'H': prefix.append((1,0,0))
		elif gestures[i] == 'P': prefix.append((0, 1, 0))
		else: prefix.append((0,0,1))
	else:
		h = prefix[i - 1][0]
		p = prefix[i - 1][1]
		s = prefix[i - 1][2]
		if gestures[i] == 'H': prefix.append((h + 1, p, s))
		elif gestures[i] == 'P': prefix.append((h, p + 1, s))
		else: prefix.append((h, p, s + 1))
# print(gestures, prefix)

max_count = 0
for i in range(n):
	count = max(win(0, 1, i), win(0, 2, i), win(1, 0, i), win(1, 2, i), win(2, 0, i), win(2, 1, i))
	max_count = max(max_count, count)
	
print(max_count)
file = open('hps.out', 'w')
file.write(str(max_count))
file.close()