牛客周赛 Round 48 解题报告 | 珂学家
小红的整数自增
https://ac.nowcoder.com/acm/contest/85187/A
前言
题解
这场感觉有点难，D完全没思路, EF很典，能够学到知识.
E我的思路是容斥+贡献，F很典，上周考过一次，引入虚拟节点质数(有点像种类并查集类似的技巧).
欢迎关注
A. 小红的整数自增
题型: 签到
贪心即可，所以值往最大值靠拢即可
arr = list(map(int, input().split()))
z = max(arr)
res = 0
for v in arr:
res += (z - v)
print (res)
B. 小红的伪回文子串（easy）
思路: 暴力
暴力枚举+模拟即可
s = input()
def compute(cs):
res = 0
i, j = 0, len(cs) - 1
while i < j:
if cs[i] != cs[j]:
res += 1
i+=1
j-=1
return res
n = len(s)
res = 0
for i in range(n):
for j in range(i, n):
res += compute(s[i:j+1])
print (res)
C. 小红的01串取反
思路: 模拟
模拟即可，顺序执行相同操作
- 最后一个元素不等，即无解
- 最后一个元素相等，即有解，且按序操作最优
n = int(input())
s1 = input()
s2 = input()
res = []
ss1 = list(s1)
ss2 = list(s2)
for i in range(n - 1):
if ss1[i] != ss2[i]:
res.append([i+1, i+2])
ss1[i] = '0' if ss1[i] == '1' else '1'
if i + 1 < n:
ss1[i+1] = '0' if ss1[i+1]=='1' else '1'
if ss1[-1] != ss2[-1]:
print (-1)
else:
print (len(res))
for (a, b) in res:
print (a, b)
D. 小红的乘2除2
思路: 枚举+前后缀拆解
可以枚举除2的点，然后快速寻找那个那个点乘2收益最大
所以它的思路非常的直接
- 预处理x2的结果
- 枚举除2的点
由于不确定x2的点的位子在枚举点那一侧，所以引入前后缀拆解
这题绕的地方在于， x2和除2太接近，彼此会互相影响
所以这里需要打个补丁，即在(-1， 0， 1)的位子，特殊枚举x2的结果
这就是大致的思路
时间复杂度为
n = int(input())
arr = list(map(int, input().split()))
def evalute(arr):
res = 0
n = len(arr)
for i in range(n - 1):
res += abs(arr[i] - arr[i + 1])
return res
pre = [0] * n
suf = [0] * n
def gain(i):
res = 0
if i >= 1:
res += abs(arr[i] * 2 - arr[i - 1]) - abs(arr[i] - arr[i - 1])
if i < n - 1:
res += abs(arr[i] * 2 - arr[i + 1]) - abs(arr[i] - arr[i + 1])
return res
def divgain(i):
res = 0
if i >= 1:
res += abs(arr[i] // 2 - arr[i - 1]) - abs(arr[i] - arr[i - 1])
if i < n - 1:
res += abs(arr[i] // 2 - arr[i + 1]) - abs(arr[i] - arr[i + 1])
return res
from math import inf
pre[0] = inf
for i in range(1, n):
pre[i] = min(pre[i - 1], gain(i - 1))
suf[n - 1] = inf
for i in range(n - 2, -1, -1):
suf[i] = min(suf[i + 1], gain(i + 1))
# 前后缀拆解
from math import inf
res = inf
now = evalute(arr)
def recompute(arr, i):
acc = 0
for k in (-1, 0, 1, 2):
if i + k >= 1 and i + k < n:
acc += abs(arr[i + k] - arr[i + k - 1])
return acc
for i in range(n):
res = min(res, now + divgain(i) + min(pre[i - 1] if i >= 1 else inf, suf[i + 1] if i + 1 < n else inf))
acc = recompute(arr, i)
cb = arr[i]
arr[i] = cb // 2
for k in (-1, 0, 1):
if i + k < 0 or i + k >= n:
continue
old = arr[i + k]
arr[i + k] = old * 2
res = min(res, now + recompute(arr, i) - acc)
arr[i + k] = old
arr[i] = cb
print (res)
E. 小红的伪回文子串（hard）
思路: 容斥+贡献
正难则反
正面求解很难，所以试试反向解法，就是统计相同的字符对
总的配对数 - 相同配对数
而这边的相同配对(i, j)，其实有一个加权，这个加权
可以先写一个的解法
一旦写出的解法，基本上半只脚迈入成功的道路上了
因为这里能找到一个技巧点，使得时间复杂度降为
s = input()
n = len(s)
# 考虑贡献法
r = 0
for i in range(n):
d = i + 1
x = n - 1 - i
if x >= i:
r += d * (x - i)
r += d * (d - 1) // 2
else:
d2 = (n - i - 1)
r += (d2 + 1) * d2 // 2
hash = [[] for _ in range(26)]
for (i, c) in enumerate(s):
p = ord(c) - ord('a')
hash[p].append(i)
res = 0
for i in range(26):
ls = hash[i]
m = len(ls)
pre = [0] * (m + 1)
for j in range(m):
pre[j + 1] = pre[j] + (n - ls[j])
# 双指针优化
tmp = 0
k = m - 1
for j in range(m):
while k >= 0 and n - ls[k] < ls[j] + 1:
k -= 1
if k > j:
tmp += (k - j) * (ls[j] + 1)
tmp += pre[m] - pre[k + 1]
else:
tmp += pre[m] - pre[j + 1]
res += tmp
# 容斥
print (r - res)
F. 小红的迷宫行走
思路: 引入虚节点 + 0-1BFS
- 虚节点为质数
- 节点到虚节点代价为0
- 虚节点到节点代价为1
然后就跑一下0-1BFS，即可
h, w = list(map(int, input().split()))
g = []
for _ in range(h):
row = list(map(int, input().split()))
g.append(row)
from math import inf
dp = [[inf] * w for _ in range(h)]
from collections import deque
from collections import defaultdict
# 建图
cnt = defaultdict(list)
es = [[[] for _ in range(w)] for _ in range(h)]
for i in range(h):
for j in range(w):
k = 2
v = g[i][j]
while k * k <= v:
if v % k == 0:
cnt[k].append((i, j))
es[i][j].append(k)
while v % k == 0:
v = v // k
k += 1
if v > 1:
cnt[v].append((i, j))
es[i][j].append(v)
deq = deque()
deq.append((0, 0, 0, 0))
dp[0][0] = 0
from collections import Counter
opt = Counter()
from math import gcd
while len(deq) > 0:
op, y, x, c = deq.popleft()
if op == 0:
if y + 1 < h:
if dp[y + 1][x] > c + 1:
dp[y + 1][x] = c + 1
deq.append((0, y+ 1, x, c + 1))
if x + 1 < w:
if dp[y][x + 1] > c + 1:
dp[y][x + 1] = c + 1
deq.append((0, y, x + 1, c+ 1))
for v in es[y][x]:
if v not in opt:
opt[v] = c
deq.appendleft((1, v, 0, c))
else:
for (ty, tx) in cnt[y]:
if dp[ty][tx] > c + 1:
dp[ty][tx] = c + 1
deq.append((0, ty, tx, c + 1))
print (dp[-1][-1])
