Post List

题解 树上博弈是真的好玩…… 首先看到这道题发现答案具有单调性，于是想到可能会二分。 先钦定陷阱所在的结点为根节点，这样老鼠向陷阱走的过程就是向根节点走的过程 先考虑这样一种情况： Bob 刚开始只在当前子树中向下走 通过画图模拟可以发现，当 Bob 向下走走到叶子节点或其通往更深层的子树的边都被 Alice 封住的时候，它就陷入了一个通往父亲结点的路被弄脏，向下又走不通的局面，这时 Alice 不要先去清理路径让 Bob 向上走，而是要去做另一些有意义的事情 如上图，假设（注意只是假设，不要去问为什么 Alice 刚开始不去堵 2→42\to 42→4 的边） Bob...

初步 对于 SSS 的每一位向他的后一位连一条边，记 g[u][v]g[u][v]g[u][v] 为 u→vu \to vu→v 连边的边数。 然后考虑每一条边 u→vu\to vu→v 对答案的贡献，记 posupos_uposu​ 为给 uuu 安排的位置 w(u,v)={posv−posu(posu<posv)k×(posx+posy)(posu>posv)w(u,v)= \{ \begin{aligned} &pos_v-pos_u &(pos_u<pos_v)\\ &k\times...

数论分块 数论分块可以在 O(N)O(\sqrt{N})O(N​)​ 的时间复杂度求出以下式子的值： ∑i=1n⌊ni⌋\sum_{i=1}^{n}\lfloor{\frac{n}{i}}\rfloor i=1∑n​⌊in​⌋ 通过打表发现，有许多 ⌊ni⌋\lfloor{\frac{n}{i}}\rfloor⌊in​⌋​​ 的值是相同的且呈块状分布，设一段相同的值起始位置为 lll​​ ，则其终止位置为 ⌊n⌊ni⌋⌋\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor } }\rfloor ⌊⌊in​⌋n​⌋ 证明： 令...