前言

alt

题解

参加了内测，内测的结果和比赛的结果差别很大。

个人觉得蛮难的, 但是也学到了。

E. 相依

思路: DP

看着像划分形DP，但中间需要绕一下

从刷表法的思路推，会发现很难，如果从填表法，就能找到优化的点

dp[u] = min(dp[v] + 1), 满足 str[v + 1] == str[u]

核心是如何优化这个min

实际上，这边有技巧，存在单调性

最终的时间复杂度为

n = int(input())

arr = list(map(int, input().split()))

from collections import Counter
from math import inf

dp = Counter()
dp[arr[0]] = 0

res = inf
f = None
g = None
for i in range(1, n):
    if arr[i] in dp:
        if i == n - 1:
            res = dp[arr[i]] + 1
        else:
            g = (arr[i + 1], dp[arr[i]] + 1)
    if f is not None:
        if f[0] not in dp:
            dp[f[0]] = f[1]
        else:
            dp[f[0]] = min(dp[f[0]], f[1])
    f = g
    g = None

if res == inf:
    print (-1)
else:
    print (res)

F. 异或炸弹（hard）

灵机一动，想了一种类似二阶差分的思路，即对角线差分，然后再常规按行差分

但是再内测中，TLE到崩溃，尽力了

alt

方法一：旋转变换 + 二维差分（官解）

思路: 旋转变换

核心:

知识点：

alt

这样就可以把45度的平行四边形，转化为正方形

alt

然后用二维差分板子，即可求解

n, q = list(map(int, input().split()))

# 曼哈顿距离 转到 切比雪夫距离转换
arr = []
for _ in range(q):
    y, x, r = list(map(int, input().split()))
    arr.append((y - 1, x - 1, r))

nm = 2 * n + 1
diff = [[0] * nm for _ in range(nm)]

for (y, x, r) in arr:
    # 偏移一下
    dy, dx = y + x, y - x + n
    a = max(0, dy - r)
    c = min(2 * n - 1, dy + r)
    b = max(0, dx - r)
    d = min(2 * n - 1, dx + r)
    
    diff[a][b] += 1
    diff[a][d + 1] -= 1
    diff[c + 1][b] -= 1
    diff[c + 1][d + 1] += 1
    
res = 0
for i in range(nm):
    for j in range(nm):
        if i > 0:
            diff[i][j] += diff[i - 1][j]
        if j > 0:
            diff[i][j] += diff[i][j - 1]
        if i > 0 and j > 0:
            diff[i][j] -= diff[i - 1][j - 1]
            
        sy = (i + j - n) // 2
        sx = (i - j + n) // 2
        if (i + j - n) % 2 == 0 and 0 <= sy < n and 0 <= sx < n:
            if diff[i][j] % 2 == 1:
                res += 1
     
print (res)

方法二：对角线差分

后期补上

写在最后

alt