牛客网暑期ACM多校训练营（第十场） Replay
| Rank | Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 54/394 | 3/10 | O | . | . | O | Ø | Ø | . | Ø | Ø | O |
O: 当场通过
Ø: 赛后通过
.: 尚未通过
A Rikka with Lowbit
solved by chelly
chelly's solution
容易发现一个位置的期望始终等于刚开始这个位置上的数字
B Rikka with Burrow-Wheeler Transform
unsolved
C Rikka with Rotate
unsolved
D Rikka with Prefix Sum
solved by chelly
chelly's solution
因为询问操作很少，所以对于每个询问操作可以for一遍之前的修改操作，考虑对答案的影响。
E Rikka with Equation
upsolved by chelly
chelly's solution
F Rikka with Line Graph
upsolved by chelly
chelly's solution
设(d(i,j))表示图(G)中两点之间的最短距离，用floyd即可跑出
我们来考虑(L(G))中的两个点((a,b))和((c,d))，那么这两个点的最短路径一定是(w(a,b)+w(c,d)+min(d(a,c),d(a,d),d(b,c),d(b,d)))
我们主要就是要计算(sum_{a,b,c,d}min(d(a,c),d(a,d),d(b,c),d(b,d)))，直接枚举是四次方的
我们考虑只枚举a和b，那么对于一个固定的a和b，我们需要计算的就是(sum_{c,d} min(d(a,c),d(a,d),d(b,c),d(b,d)))
设(p(i)=min(d(a,i),d(b,i)))，那么我们要计算的是(sum_{c,d} min(p(c),p(d)))，这个东西我们可以把p数组排序，然后算每个数字的贡献即可
这样时间复杂度是(O(n^3 log n))，我们其实也可以预处理出所有的p，然后在内层排序的时候直接归并就行，复杂度降到(O(n^3))
G Rikka with Shortest Path
unsolved
H Rikka with Ants
upsolved by chelly
chelly's solution
不妨设(frac{a}{b}<frac{c}{d})
考虑对于a,b来说，什么样的点会在路径上
若一个点((x,y))在路径上，那么首先该点需要在直线下方，即(y leq frac{a}{b}x)，其次，点((x-1,y+1))要在直线上方，即(y+1 > frac{a}{b}(x-1))
那么对于a,b,c,d，可以列出四个不等式，然后发现只有两个不等式是有用的
问题变成了，有两条直线，问夹在两条直线中的整点个数
这个直接类欧即可
I Rikka with Zombies
upsolved by chelly
chelly's solution
(f(u,i))表示以u为根的子树的边权都确定下来，能到达u点的能力值最强的僵尸是第i个(该僵尸可能在树外)情况下的方案数
考虑(f(son,j))并到(f(u,i))上如何转移
- 若j==i，那么就是说i号僵尸要能过((u,son))这条边
- 若j!=i，那么就是说i号和j号僵尸都不能通过((u,son))这条边并且i在子树son外，j在子树son内
这样时间复杂度是(O(n^3))的，无法通过
我们可以先按照每个僵尸的能力值排序，然后就可以用前缀和优化转移，变成的(O(n^2))的
J Rikka with Nickname
solved by chelly
chelly's solution
存一下每个字符出现位置，以及每个字符现在已经走到了哪个位置
这场比赛由chelly打的。
chelly首先切了A和J。然后跟榜开D，想了很久分块做法，发现都比较玄学，后来发现对于每个询问可以for一遍之前的操作计算对答案的影响，然后就1A了。后来E和F也都想不出，就GG了。