Description 你有一棵有 nnn 个点的树，树上的每条边权值都为 111。现在有 qqq 次询问，每次询问一个整数 xxx，并将叶子结点全部相连上权值为 xxx 的边（操作不会保留）。问每次操作后图的直径是多少。图的直径定义为 max⁡1≤u<v≤nd(u,v)\underset{1\leq u<v\leq n}{\max}d(u,v)1≤u<v≤nmax​d(u,v

Description 给定 n,kn,kn,k，求： ∑i=1n(ni)×ik\displaystyle\sum_{i=1}^{n}{\binom{n}{i}\times i^k} i=1∑n​(in​)×ik 1≤k≤5000,1≤n≤1091\leq k\leq 5000,1\leq n\leq 10^91≤k≤5000,1≤n≤109。 Solution 看到那个 iki^kik 很不

Description 给定正整数 NNN，和两个长为 NNN 的 010101 序列 aaa 和 bbb。定义一次操作为： 将 bbb 序列中的一个值翻转（即 000 变成 111，111 变成 000，下同）。 对于 bbb 序列中每个值为 111 的位置，将 aaa 序列中对应位置的值翻转。 将 bbb 序列向右循环移位 111 位。即若当前 bbb 序列为 b1b2⋯bnb_1b_2\

Description link Solution 显然是用平衡树维护，感觉 Splay 比较好维护。 设 deltadeltadelta 表示当前总共加了多少工资，delta<0delta < 0delta<0 则表示扣了 −delta-delta−delta 的工资。 对于 I 操作，直接在平衡树里插入 k−deltak-deltak−delta。 对于 A 操作，就将

Description link Solution 首先 fff 很好求，f[i]f[i]f[i] 就等于 f[i−1]+f[i−2]+...+f[i−m]f[i-1]+f[i-2]+...+f[i-m]f[i−1]+f[i−2]+...+f[i−m]，看到 mmm 很小，所以矩乘优化成 m3log⁡nm^3\log nm3logn 的复杂度，假设单位矩阵为 AAA。设 mim_imi​ 表示

Description 给定一个 n×nn\times nn×n 的网格图，其中部分格点有障碍物使得箱子不能置于其上。规定箱子是一个奇数边长的正方形，其坐标为其中心格点的坐标。箱子只能上下左右移动，每次询问从一个格点能移动到另一个格点的最大箱子。 Solution 首先对于每个点 (x,y)(x,y)(x,y) 用二分求出以这个点为中心格点的最大边长 d[x][y]d[x][y]d[x][y]

Description link Solution 显然是道 DS。 想到建两个个平衡树。一个用来维护所有数的最小差值，插入 xxx 时，找到 xxx 的前驱和后继更新答案即可。 另一个用来维护相邻数的最小差值。假设操作时在 kkk 后插入 xxx，那么 lst[k]lst[k]lst[k] 和 a[k+1]a[k+1]a[k+1] 就不再相邻，需要删除，然后插入 ∣lst[k]−x∣|lst

Description link Solution 容易发现一种结果串的合法分割方案就对应着一种原字符串所以可以考虑 dp。 令 f[i][a][b][c]f[i][a][b][c]f[i][a][b][c] 表示将 s[1∼i]s[1\sim i]s[1∼i]，且最后一个字串尾字母为 aaa，首字母为 bbb，倒数第 222 段首字母为 ccc。 那么对于 s[i]s[i]s[i] 则有两种

Description link Solution 可以发现 m≤5×104m\leq 5\times 10^4m≤5×104 所以可以直接枚举 mmm 来得到答案。 可以建 444 个图，两个正图，两个反图，分别是求 1→i1\to i1→i 的最短路，i→ni\to ni→n 的最短路，n→in\to in→i 的最短路，i→1i\to 1i→1 的最短路。 先对于每个图跑最短路并求出最短

Description link Solution 如果两个团子重合肯定是下面三种情况： 123 R RGW R G G RGWRGW W W 我们会发现两个重合团子的 G 一定是在从右上到左下的对角线上的，且距离小于等于 111。根据这个性质就可以发现任意两个对角线上的团子肯