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
存一下每个字符出现位置,以及每个字符现在已经走到了哪个位置
Replay
这场比赛由chelly打的。
chelly首先切了A和J。然后跟榜开D,想了很久分块做法,发现都比较玄学,后来发现对于每个询问可以for一遍之前的操作计算对答案的影响,然后就1A了。后来E和F也都想不出,就GG了。