A.2023
暴力即可
import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
# INF = 0x3f3f3f3f3f3f
# sys.setrecursionlimit(100000)
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
a = 12345678
b = 98765432
cnt_all = 0
ans = 0
for num in range(a, b + 1):
cnt_all += 1
tmp = [int(i) for i in str(num)]
flag_2_0 = False
flag_0 = False
flag_2_1 = False
flag_3 = False
for i in range(len(tmp)):
if flag_2_0 == False and tmp[i] == 2:
flag_2_0 = True
if flag_2_0 == True and flag_0 == False and tmp[i] == 0:
flag_0 = True
if flag_2_0 == True and flag_0 == True and flag_2_1 == False and tmp[i] == 2:
flag_2_1 = True
if flag_2_0 == True and flag_0 == True and flag_2_1 == True and flag_3 == False and tmp[i] == 3:
flag_3 = True
ans += 1
break
print(cnt_all - ans)
# 85959030
B.硬币兑换
注意，只有新币可以兑换，最后结果不论硬币新旧。 故应当将1 + 2022， 2 + 2021， … ，1011 + 1012。
a = [i for i in range(2024)]
a = a + [0] * 2024
left = 1
right = 2022
while left < right:
a[left + right] += a[left]
a[right] -= a[left]
a[left] = 0
left += 1
right -= 1
print(max(a))
# 513589
C.松散子序列
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
s = input()
n = len(s)
f = [0] * n
if s == '':
print(0)
elif n == 1:
print(ord(s[0]) - ord('a') + 1)
else:
f[0] = ord(s[0]) - ord('a') + 1
f[1] = max(f[0], ord(s[1]) - ord('a') + 1)
for i in range(2, n):
f[i] = max(f[i - 1], f[i - 2] + ord(s[i]) - ord('a') + 1)
print(max(f))
D.管道
直接遍历每一个阀门，定义数组
v
i
s
i
vis_i
visi 为第
i
i
i 个阀门最早感应到水流的时间。
import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
INF = int(1e12)
# sys.setrecursionlimit(100000)
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
n, len = read()
a = []
for _ in range(n):
l, s = read()
a.append([l, s])
vis = [INF] * (len + 1)
for i in range(n):
l, s = a[i]
vis[l] = min(vis[l], s)
for i in range(n):
l, s = a[i]
t = s + 1
left = l - 1
right = l + 1
while left >= 1 and t < vis[left]:
vis[left] = t
t += 1
left -= 1
t = s + 1
while right <= len and t < vis[right]:
vis[right] = t
t += 1
right += 1
print(max(vis[1::]))
E.保险箱
写的贪心，感觉不对。
import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
# INF = 0x3f3f3f3f3f3f
# sys.setrecursionlimit(100000)
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
n = I()
x = input()
y = input()
prev = 0
ans = 0
for i in range(n-1, -1, -1):
tmp_x = int(x[i]) + prev
tmp_y = int(y[i])
if tmp_x > tmp_y:
if (tmp_x - tmp_y) - (tmp_y + 10 - tmp_x) > 1:
ans += (tmp_y + 10 - tmp_x)
prev = 1
else:
ans += tmp_x - tmp_y
prev = 0
elif tmp_x == tmp_y:
prev = 0
else:
if (tmp_y - tmp_x) - (tmp_x + 10 - tmp_y) > 1:
ans += (tmp_x + 10 - tmp_y)
prev = -1
else:
ans += tmp_y - tmp_x
prev = 0
print(ans)
F.树上选点
暴力枚举第一个点，再找第二个点。
import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
# INF = 0x3f3f3f3f3f3f
# sys.setrecursionlimit(100000)
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
def dfs_deep(u, depth):
deep[u] = depth
for v in g[u]:
dfs_deep(v, depth + 1)
def dfs(u, fa, x):
if fa == x:
vis[u] = True
for v in g[u]:
if v == x:
vis[u] = True
dfs(v, u, x)
n = I()
g = [[] for _ in range(n + 1)]
f = list(read())
for i in range(n - 1):
g[f[i]].append(i + 2)
value = list(read())
value = [0] + value
deep = [0] * (n + 1)
dfs_deep(1, 0)
ans = 0
for x in range(1, n + 1):
vis = [False] * (n + 1)
vis[0] = True
for i in range(1, n + 1):
if deep[i] == deep[x]:
vis[i] = True
dfs(1, 0, x)
tmp = []
maxm1 = 0
for i in range(1, n + 1):
if not vis[i] and i != x:
if value[i] > maxm1:
maxm1 = value[i]
ans = max(ans, value[x] + maxm1)
print(ans)
G.T字消除
没做。
H.独一无二
开个cnt数组，每次dis[u]+w == dis[v]的时候+1
import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
INF = 0x3f3f3f3f3f3f
# sys.setrecursionlimit(100000)
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
class Edge:
v = 0
w = 0
ne = -1
def add(a, b, c):
global idx
e[idx].v = b
e[idx].w = c
e[idx].ne = h[a]
h[a] = idx
idx += 1
def dijkstra(s):
vis = [False] * (n + 1)
dis = [INF] * (n + 1)
cnt = [0] * (n + 1)
dis[0] = dis[s] = 0
vis[0] = True
q = []
heapq.heappush(q, [0, s])
while q:
_, u = heapq.heappop(q)
if vis[u]:
continue
vis[u] = True
i = h[u]
while i != -1:
v = e[i].v
w = e[i].w
i = e[i].ne
if dis[u] + w < dis[v]:
dis[v] = dis[u] + w
if not vis[v]:
heapq.heappush(q, [dis[v], v])
if dis[u] + w == dis[v]:
cnt[v] += 1
cnt[s] = 1
for i in range(1, n + 1):
print(cnt[i] - 1)
n, m = read()
h = [-1] * (n + 1)
idx = 0
e = [Edge() for _ in range(m)]
for _ in range(m):
u, v, c = read()
add(u, v, c)
dijkstra(1)
I.异或和
a维护以x为根的子树异或和, prev维护每个结点的点权。 每次change只需要向上更改贡献即可。 正解应该是 dfs序+树状数组/线段树 维护
import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
# INF = 0x3f3f3f3f3f3f
# sys.setrecursionlimit(100000)
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
def dfs(u):
for v in g[u]:
a[u] ^= dfs(v)
return a[u]
def change(u, x, y):
if u == x:
a[x] = a[x] ^ prev[x] ^ y
# 注意要把点权也修改了，比赛的时候忘记了。。。。
prev[x] = y
return prev[x] ^ y
for v in g[u]:
a[u] ^= change(v, x, y)
return 0
n, m = read()
a = list(read())
a = [0] + a
prev = copy.deepcopy(a)
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
u, v = read()
g[u].append(v)
dfs(1)
for _ in range(m):
op = list(read())
if op[0] == 1:
x, y = op[1], op[2]
change(1, x, y)
if op[0] == 2:
x = op[1]
print(a[x])
J.混乱的数组
手算
x
≤
10
x\le10
x≤10
import bisect
import sys
import copy
from collections import deque, defaultdict
import heapq
from itertools import accumulate, permutations, combinations
import math
input = lambda: sys.stdin.readline().rstrip("\r\n")
printf = lambda d: sys.stdout.write(str(d) + "\n")
# INF = 0x3f3f3f3f3f3f
# sys.setrecursionlimit(100000)
def read():
line = sys.stdin.readline().strip()
while not line:
line = sys.stdin.readline().strip()
return map(int, line.split())
def I():
return int(input())
x = I()
if x == 1:
print(2)
print(2, 1)
if x == 2:
print(3)
print(2, 1, 1)
if x == 3:
print(3)
print(3, 2, 1)
if x == 4:
print(4)
print(2, 2, 1, 1)
if x == 5:
print(4)
print(3, 2, 1, 1)
if x == 6:
print(4)
print(4, 3, 2, 1)
if x == 7:
print(5)
print(3, 2, 2, 2, 1)
if x == 8:
print(5)
print(3, 3, 2, 1, 1)
if x == 9:
print(5)
print(4, 3, 2, 1, 1)
if x == 10:
print(5)
print(5, 4, 3, 2, 1)
注意
非官方题解，只是我自己的做法，如果有错误，或者有更好的做法都欢迎指正。
精彩链接
发表评论