T2
发现自己傻傻地排序了，应该直接max最大值（
T4
看出来是差分了，但是时间不够了，没想到需要一边差分一边维护求和。
因为只能成年人给未成年人所以推出只能前面的人给后面的人，然后又因为成年的顺序就是输入的顺序，所以可知一定是越前面的越可能拿到成年礼，等价于当前的人尽可能的把自己的石头发给后面的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def main():
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N+1)
c = 0
for i in range(N):
if i:
c = c + b[i]
a[i] += c
give = min(N - i - 1, a[i])
a[i] -= give
b[i+1] += 1
b[i+1+give] -= 1
for i in range(0, N):
print(a[i], end=" ")
main()
|
T5
二分，但是二分的往往不是那个，而是那个，你滴明白？
相当于找到最少的k个，后面的数组满足其要求。验证是O(n)的，枚举是O(logn)，合理！
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
|
def main():
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
A = list(map(int, data[1:N+1]))
# 判定函数
def check(K):
for i in range(K):
if A[i] * 2 > A[N - K + i]:
return False
return True
# 二分搜索
left = 0
right = N // 2
result = 0
while left <= right:
mid = (left + right) // 2
if check(mid):
result = mid
left = mid + 1
else:
right = mid - 1
print(result)
if __name__ == "__main__":
main()
|
T6
前置芝士：
- 小凯的疑惑NOIP2017 (x * y - x - y)
- 过河 NOIP2005
过河如下：
首先是朴素的二维dp，用所有能跳到当前位置的点来更新当前位置，如果是当前位置石头那么就+1
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
|
def main():
L = int(input())
S, T, M = map(int, input().split())
stones = set(map(int, input().split()))
# 既有可能是跳到桥也有可能是跳过桥
max_pos = L + T
dp = [float('inf')] * (max_pos + 1)
dp[0] = 0
# 遍历每个位置 1-indexed
for i in range(1, max_pos + 1):
# 检查从前面的位置是否可以跳到当前位置 [i-T, i-S]
for j in range(max(0, i-T), max(0, i-S+1)):
dp[i] = min(dp[i], dp[j] + (1 if i in stones else 0))
# 找到最小结果
result = float('inf')
for i in range(L, L+T+1):
result = min(result, dp[i])
print(result)
if __name__ == "__main__":
main()
|
30%的分数拿到，你已经掌握了OI赛制的精髓，可以洗洗睡了。然后就是离散化石头，因为虽然石头距离远，但是它们个数少啊。
所以说根据最大不能表示的数的结论，只要是大于S*T-S-T的距离就一定能跳到，所以说我们就可以把它视作这个距离，因为它并没有要求你求步数。此题目中S、T均小于10，取最大值9 * 10 - 9 - 10 = 71， 71 + 1 = 72，所以大于72的距离就可以视作72（下面的base直接变成72就好了，大多数题解也是这么写的，反正没人搞你），下面的代码一定要注意base有可能在前面那个公式下运算成负数，会导致你怀疑人生（所以不要怀疑这个做法的正确性。
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
|
def main():
# 输入处理
L = int(input())
s, t, m = map(int, input().split())
base = max(s * t - s - t + 1, s)
stone = [0] + list(map(int, input().split())) # 1-based indexing
# 特殊情况：s == t
if s == t:
cnt = sum(1 for i in range(1, m + 1) if stone[i] % s == 0)
print(cnt)
return
# 初始化
stone.sort() # 排序
a = [0] * (m+1) # 离散化后的位置
stone_positions = set() # 改用set存储石头位置
# 离散化过程
for i in range(1, m + 1):
d = stone[i] - stone[i-1]
d = min(d, t)
a[i] = a[i-1] + d
stone_positions.add(a[i])
# 最远能跳的地方，可大不可小
max_position = a[m] + base
# 动态规划
dp = [0x3f3f3f3f] * (max_position + 1)
dp[0] = 0
# 二维常规dp
for i in range(1, max_position + 1):
# [S, T] 是跳动的步伐 摩擦摩擦
for j in range(s, t + 1):
if i - j >= 0:
if i in stone_positions: # 是石头
dp[i] = min(dp[i], dp[i-j] + 1)
else:
dp[i] = min(dp[i], dp[i-j])
# 寻找最小值 从最后一块石头到最远
ans = min(dp[i] for i in range(a[m], max_position + 1))
print(ans)
if __name__ == "__main__":
main()
|
好了！下面我应该会做这道题了！还是不会！所以我们照着c++写！
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
73
74
75
76
77
78
79
80
|
def main():
n, m, a, b = map(int, input().split())
l = [0] * (m+2)
r = [0] * (m+2)
# 读取区间 1-indexed
for i in range(1, m + 1):
l[i], r[i] = map(int, input().split())
# 特殊情况：a==b
if a == b:
if (n - 1) % b != 0:
print("No")
return
for i in range(1, m + 1):
if (r[i] - l[i] + 1) >= b:
print("No")
return
# 对于每个区间，如果从起点蹦到里面，那就寄了
for j in range(l[i], r[i] + 1):
if (j - 1) % b == 0:
print("No")
return
print("Yes")
return
ll = [0] * (m+2)
rr = [0] * (m+2)
tot = 0
mp = {}
f = [0] * 343
"""
tot 表示区间的索引 区间从1开始
区间1 坏区间1 区间2 坏区间2 ... 区间m 坏区间m 区间m+1 终点N
"""
for i in range(1, m + 1):
tot += 1
ll[tot] = r[i-1] + 1
rr[tot] = l[i] - 1
tot += 1
ll[tot] = r[m] + 1
rr[tot] = n
# f bool数组是否可达
f[0] = 1
for i in range(1, 343):
for j in range(a, b + 1):
if i - j >= 0:
f[i] |= f[i-j]
mp[1] = 1
# 遍历每一个区间
for i in range(1, tot + 1):
# 区间的每一个位置，最右侧要注意可能存在从最左侧无法一步跳到最右侧的情况
for pos in range(ll[i], min(rr[i], ll[i] + b) + 1):
# 判断pos是否可达
for j in range(a, b + 1):
if pos - j in mp:
mp[pos] = 1
break
# 如果pos可达，若pos可以跳到当前区间右侧那么[ pos, rr[i] ]也可达，但是pos + b可能没到有边界，所以左侧不一定从pos开始
# 这个循环用来从右往左更新可达
if pos in mp:
for j in range(max(pos, rr[i] - b), rr[i] + 1):
# >= 342是结论， f[j - pos]是预处理可达
if j - pos >= 342 or f[j - pos]:
mp[j] = 1
print("Yes" if n in mp else "No")
if __name__ == "__main__":
main()
|