签到题

枚举最终的字符，求最小的修改

这个方法更有通用性

s = input()from math import inf
import stringans = inf
for c in string.ascii_letters:ans = min(ans, sum([1 for z in s if z != c]))print (ans)

思路: 模拟

也是为后续的E题做铺垫

因为关注的个位数，所以乘积的时候，可以$mod10$, 从而避免大数乘法

n = int(input())arr = list(map(int, input().split()))ans = 0
acc = 1
for v in arr:acc = acc * v % 10if acc == 6:ans += 1
print (ans)

思路: 贪心构造

移项转化，可以观察到

偶数项 $a_0<a_2<a_4<...<a_x,x是偶数$

奇数项 $a_1<a_3<a_5<...<a_y,y是奇数$

两个序列大小没有制约关系

由于是严格小于，所以序列中必然没有3个以上的相同项

注：特别注意0最多一个，而且只能在偶数序列中

1. 先分配出现次数为2的数，偶数/奇数序列各一个
2. 0这个数一定要放在偶数序列中
3. 剩下单个数，那个序列数不足，放哪里

# a1 < a3 < a5
# a2 < a4 < a6n = int(input())
arr = list(map(int, input().split()))from collections import Counterdef solve():m1 = (n + 1) // 2m2 = n // 2ext = []ls1, ls2 = [], []cnt = Counter(arr)if cnt[0] >= 2:return Nonefor (k, v) in cnt.items():if v > 2:return Noneif v == 2:ls1.append(k)ls2.append(k)else:if k == 0:ls1.append(0)else:ext.append(k)while len(ls1) < m1:ls1.append(ext.pop())while len(ls2) < m2:ls2.append(ext.pop())# 排序组合ls1.sort()ls2.sort()res = []for (k1, k2) in zip(ls1, ls2):res.append(k1)res.append(k2)return resls = solve()
if ls is None:print ("NO")
else:print ("YES")print (*ls, sep=' ')

思路: BFS

有些绕，遇到1或者边界会存在跳跃情况

n = int(input())g = []
for _ in range(n):row = list(map(int, input().split()))g.append(row)from math import inf
dp = [[inf] * n for _ in range(n)]from collections import deque
dp[0][0] = 0
deq = deque()
deq.append((0, 0))while len(deq) > 0:y, x = deq.popleft()for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:ty, tx = y + dy, x + dxif 0 <= ty < n and 0 <= tx < n:if g[ty][tx] == 0:if dp[ty][tx] > dp[y][x] + 1:dp[ty][tx] = dp[y][x] + 1deq.append((ty, tx))continueif dy == -1:ty += 2while ty < n and g[ty][tx] == 0:ty += 1if g[ty - 1][tx] == 0 and dp[ty - 1][tx] > dp[y][x] + 1:dp[ty - 1][tx] = dp[y][x] + 1deq.append((ty - 1, tx))elif dy == 1:ty -= 2while ty >= 0 and g[ty][tx] == 0:ty -= 1if g[ty + 1][tx] == 0 and dp[ty + 1][tx] > dp[y][x] + 1:dp[ty + 1][tx] = dp[y][x] + 1deq.append((ty + 1, tx))elif dx == -1:tx += 2while tx < n and g[ty][tx] == 0:tx += 1if g[ty][tx - 1] == 0 and dp[ty][tx - 1] > dp[y][x] + 1:dp[ty][tx - 1] = dp[y][x] + 1deq.append((ty, tx - 1))elif dx == 1:tx -= 2while tx >= 0 and g[ty][tx] == 0:tx -= 1if g[ty][tx + 1] == 0 and dp[ty][tx + 1] > dp[y][x] + 1:dp[ty][tx + 1] = dp[y][x] + 1deq.append((ty, tx + 1))#print (dp)
print (dp[-1][-1] if dp[-1][-1] != inf else -1)

思路: 贡献法 + DP

非常好的一道题

引入$dp[i][s],s\in [0,9]$, 表示前i项中，个位数为s的序列总数

那为何引入贡献法呢？

其实只要出现6，那它就贡献 $dp[i][6]\ast 2^{n-1-i}$ 次数

那这个dp，只需要维护序列总数即可

第一维，可以借助滚动数组优化

这样时间复杂度为$O(10\ast n)$, 空间复杂度为$O(10)$

def pow(b, v, m):r = 1while v > 0:if v % 2 == 1:r = r * b % mb = b * b % mv //= 2return r    n = int(input())arr = list(map(int, input().split()))dp = [0] * 10mod = 10 ** 9 + 7
res = 0
for (i, v) in enumerate(arr):dp2 = dp[:]if v % 10 == 6:res += pow(2, (n - 1 - i), mod)res %= moddp2[v % 10] += 1lv = v % 10;for j in range(1, 10):if j * lv % 10 == 6:res += dp[j] * pow(2, (n - 1 - i), mod) % modres %= moddp2[j * lv % 10] += dp[j]dp2[j * lv % 10] %= moddp = dp2print (res)

下次补上