看到这题第一想法就是口罩，感觉做过口罩这题的过程就很自然了。我们考虑设 $f(k)$ 表示恰好 $k$ 条边与原树相同的树的个数，$g(k)$ 表示钦定 $k$ 条边，于是： \sum_{k \ge 0} f(k)k2^k\\ \sum_{k \ge 0} k2^k \sum_{j \ge k} g(j)(-1)^{j-k} \binom j k\\ \sum_{j \ge 0} jg(j) \sum_{k \le j} 2^k(-1)^{j-k} \binom {j-1} {k-1}\\ \ ...

考虑第一次操作，必然会放在当前 Snuke 的任意一边。 然后考虑第二次操作，必然放在当前 Snuke 的另一边。 然后现在 Snuke 就被圈起来了，仔细考虑一下会发现，它的决策必然是往尽量中间的位置靠。因为在下一次放方块的操作中，你肯定会让 Snuke 的活动范围尽量减少。也就是说，设你放方块的时候 Snuke 到左边长度是 $l$ ，到右边是 $r$ ，那么放完后他的范围肯定是变为 $\min(l,r)$ 。 我们考虑什么样的 B 操作，会导致能确定之后必然能堵死 Snuke 。对于最后两 ...

大概有两种做法。 首先写一下官方题解的做法。 我们设 $i \to P_i$ 存在一条边，同时将 $P_i=-1$ 看做 $P_i = 0$ ，并添加虚点 $0$ ，于是对于任意一个排列，必然可以对应成为一棵树的形态。也就是说现在我们只需要统计这种树的种类数即可。 然后会发现，对于整棵树的一个子树，它必然在序列上对应一个区间，而它的根就是区间的左端点。考虑任意一个位置 $i$ ，它后面的第一个比它大的位置在 $j$ ，考虑 $[i+1,j-1]$ 这一段之间的所有数，显然它们不会连到 $i$ 的 ...

神仙构造题。写一下 pb 讲的做法。 考虑极差不超过 $2$ 这个限制。可以把每条边 $u,v$ ，令 $u<v$ ，则变成 $u,v+n$ 的一条边，也就是拆成一个二分图。 考虑在这个图上染色，然后再把 $u,u+n$ 合并起来。如果在这个得到的二分图上可以染色使得每个点极差不超过 $1$ ，那么合并后一定可以让每个点极差不超过 $2$ 。 下面将说明这样的合法的染色方案一定存在。假设一个点 $u$ 的度数是 $ak+b$ ，那么我们可以把一个点拆成 $a+1$ 个点，然后前 $a$ 个 ...

目前咕咕咕：T6 T8 以及 T5 的 魔改 Min25 。 T1$T\le 5000,a,b\le 10^9$ 求： \sum_{i=a}^b \text{lcm}(i,b) \bmod 10^9 + 7前缀和一下即求 \sum_{i=1}^n \text{lcm}(i,b)有一种曾经卷老师教过的非常不错的推法，考虑求和 $\gcd$ 的时候可以直接转乘 $\varphi$ ， \begin{aligned} & \sum_{i=1}^n \gcd(i,n)\\ &= \sum_{i=1 ...

题目： Powerful Number 筛也是一种筛，它是 $O(\sqrt n)$ 的。应用时必须满足 它是积性函数 这个东西在质数处取值的函数可以快速计算前缀和。例如此题，显然有 $f(p) = 1$ 。 首先 Powerful Number 的定义，是所有质因子次数都 $\ge 2$ 的数。这种数的个数是 $O(\sqrt n)$ 级别的。因为显然，每个这样的数都可以被表示成 $a^2b^3$ ，所以寻找这种数的时候可以暴力枚举这里的 $a,b$ ，复杂度是 $\sum_{i=1 ...

神仙题。大概是一篇只有做法没有思路的题解。。 显然这个题 $\gcd > 1$ 就是想建补图。然后问题就变成了选出一个点集使得大小正好为 $k$ 且要么每个点都在导出子图里有边，要么所有点都是孤立点。构造一组方案即可。 需要注意的是第二种情况，如果可以找到一个 $\ge k$ 的独立集，那么只需要保留 $k$ 个点即可。 首先要会求所有点的度数。不难发现 $a_i$ 的度数是 \sum_{1 \le j \le v} occ[j][\gcd(a_i,a_j) = 1]\\ =\sum_{ ...

这场我感觉题很不错的QwQ C DFS Game考虑先手到达一个根。然后先手必然会取走这个根上的硬币。然后后手会选择一个儿子向下，然后又变成先手到达一个根的问题。所以感觉上需要考虑 $dp$ 。但是事实上从这个子树回溯回来之后，不一定开始的先手仍然作为先手。所以可以考虑 $dp[u]$ 表示先手到达 $u$ 后可以获得的价值减去后手可以获得的价值的最大值。设最终先手获得硬币数是 $a$ ，后手是 $b$ ，那么 $a+b=n$ ，所以只需要最大化 $a-b$ 即可。 考虑如何转移。不难发现当我们 ...

时间好快啊，感觉 SCOI 2020 游记还没写多久就到 2021 年的省选了。 终于，没有了垃圾 SCOI 计算几何。 Day 0早上看了看字符串板子，该看的板子其实大多都看过了，再复习了一遍 SAM PAM 以及 KMP 之类的，虽然多半也用不上。 下午一直在颓，大概 FC 了个 GOODFORTUNE，希望为明天考试带来好运。 晚上写了一遍 cdq 分治 NTT 的板子，发现好像这个板子没有以前想的那么难写。 反正感觉能准备的都准备了，实在不行就听天由命了。 Day 1又是笔记本差评，但 ...

好题。类似 Students Camp 的优化。考虑 $dp[i][j][k]$ 表示当前还剩下 $i$ 个熊两血，$j$ 个一血，其中有 $k$ 个是人。 直接转移复杂度是 $O(1)$ 状态共 $O(n^3)$ 种，复杂度 $O(n^3)$ 。 考虑怎么优化这个 $dp$ 。先把状态转移的式子写出来 dp[i][j][k] = \frac{i+1}{i+j}dp[i+1][j-1][k]+\frac{j+1-k}{i+j+1}dp[i][j+1][k]+\frac{k+1}{i+j+1}d ...

Min_25 筛也是一种求积性函数前缀和的算法。 Min_25 筛的应用前提是可以找到一个完全积性函数在质数处和要求的函数相同。所以我们假装得到了一个完全积性函数 $f’$ 它在质数处的取值和 $f$ 相同。 首先，我们把 $1$ 扣掉，最后把 $1$ 加回来即可。所以后面的范围的下界都是 $2$ 。 我们考虑把所求拆一下，然后在非质数部分枚举一下最小的质因子以及这个质因子的次数： \sum_{i \in P} f(i) + \sum_{p^e \le n , p \le \sqrt n} f ...

A Strange Addition水题。 考虑 $dp[i]$ 表示当前考虑到第 $i$ 位，有多少种有序对 $(a,b)$ 在前 $i$ 位满足条件。 转移考虑每次往 $(a,b)$ 后面分别添加一位，然后考虑得到的数，要么得到的数会添加两位，要么只添加一位。所以转移就是 dp[i] = dp[i-1]S[A_i] + dp[i - 2] S[A_i+10A_{i-1}]其中 $S[i]$ 表示有多少种两个一位数加起来是 $i$ 。 这个转移显然可以写成矩阵乘法的形式，每个位置维护一个矩阵 ...

A 一次函数不难发现一个数真正重要的只有这个数中的连续段个数以及这个数最后一位是 $0/1$ 。 我们设 $f(x)$ 表示 $x$ 二进制表示下的连续段的个数。那么答案就是在 \sum_{i=1}^n f(ai + b)的基础上再减去除开最后一个位置的奇数的个数，因为这些数会和下一个数的 $1$ 合并成一段。 这个东西怎么求？不难发现这是个 $\bmod a$ 不变的式子，而这题正好 $a$ 非常小。所以我们考虑求 \sum_{i=1}^{an+b} [i \bmod a = 0] f( ...

A 环游看起来是毒瘤题，其实不然。 我们设首都是 $a$ ，秘密都市是 $b$ ，新建城市是 $c$ ，我们需要找到的就是一条 $a \to c \to b \to a$ 的路径，且保证 $a \to b$ 有至少三条点不相交路径。 现在假装我们已经拿出了三条 $a \to b$ 的路径。我们考虑先尝试找到一条 $a \to c$ 的路径，然后找出它最后一次经过 $a \to b$ 的三条路径之中的任意一条的某个点 $v$ 。然后我们可以把 $a \to c$ 变成 $a \to v \to c ...

剩下的题有些不可做，可做的也懒得去写了。（咕咕咕 DifferenceSequence 定义对一个序列进行一次操作为 A_1,A_2,\dots ,A_n\\ \to |A_1-A_2|,|A_2-A_1|,\dots ,|A_n-A_1|对于任意一个序列，进行操作后必然会进入一个循环。我们定义循环内的最大字典序串为此串的代表串，求所有长度为 $n$ 的串的代表串去重后字典序第 $k$ 小的串。 我们先打个表观察一下会发现，任意一个序列在进行很多次操作后都会变成一些相同大小的数字与 $0$ ...

A Codechef LUCKYDAY阴间题。除开卡常和细节还是道很好的题。 $L,R \le 10^{18}$ ，会想到寻找循环节。由于下一个数会和前两个数有关，因此循环结最大不会超过 $p^2$ ，也就是 $10^8$ 级别。但是这个数是可以卡满的，而这题 $500\text{ms}$ 显然不会放过去暴力。 如何找循环节呢，考虑这个转移写成矩乘，设转移矩阵是 $T$ ，于是问题就变成了找最小的 $k$ 使得 T^{k}A = A其中 $A$ 是初始的矩阵也就是 \begin{bmatr ...

考虑当前在 $u$ ，如何确定带权重心在哪个子树中。考虑往某个子树移动一个微小距离，那么所有点到这个点距离的变化是 \sum_{t\notin S_v} (x_t^{1.5} - (x_t - \Delta x)^{1.5} ) - \sum _{t \in S_v} ((x_t + \Delta x)^{1.5} - x_t^{1.5})如果这个东西大于 $0$ ，就意味着往这个点移是优的，也就是 \sum_{t\notin S_v} (x_t^{1.5} - (x_t - \Delta ...

A Power看到这题数据随机就可以想到可不可以乱搞。我们考虑从 $P-1$ 开始向下枚举，每次用 BSGS 解出这个数第一次出现的位置，如果这个数小于之前的最小位置，我们就用它来代替最小位置继续做。然后考虑设置一个阈值 $B$ ，如果当前的数已经小于了 $B$ 就停止这个做法直接枚举前 $B$ 个数。 然后写出来试了试发现只能过 $10^7$ 。冷静分析一波复杂度，会发现如果 $B$ 控制合理大概是 $O(P^{\frac 3 4})$ 的东西。具体来说，随机情况下如果我们找到了一个比当前最优 ...

任意模数下的积和式并没有多项式解法。考虑积和式的组合意义，$i,A_i$ 都是互不相同的，可以看作是二分图的一个完美匹配。因此任意矩阵的积和式就是 $A_{x,y}$ 看作左侧 $x$ 右侧 $y$ 之间的边权后所有完美匹配边权的积的和。 如果我们给所有 $A_{x,y} \neq 1$ 拆成 $1,A_{x,y} - 1$ 这两个东西，然后所有边上都有了一个长度为 $1$ 的边。于是现在就可以不考虑所有长度为 $1$ 的边了。我们求出除开边权为 $1$ 的边后的任意一个二分图匹配，那么这个匹配 ...

以前做的，没发博客。 如果两个串的 endpos 等价类相同，显然把任意一个放进 $s_i$ 里面是一样的效果。 于是我们可以建出 SAM 的 fail 树，考虑做 $dp[u]$ 表示当前在树上的 $u$ 节点，同时我们最后一次选择的是这个点上的最长串，最多可以选出的序列长度。 显然，我们选择一个深度更大的位置比选择一个深度更小的位置作为序列的上一个位置好。因为深度更小的位置一定在深度更大的位置的所有 endpos 中出现过。所以我们可以考虑找到最深的一个位置，满足这个位置在当前串中出现过至少 ...

Ｂ口罩太经典的题了，以前这场之后都见过两次了。 考虑钦定 $k$ 条边，然后把这 $k$ 条边删掉，再加入回去，求有多少种树。最后再二项式反演回去即可。 一个结论：有一个 $n$ 个点的森林，其中有 $k$ 个连通块，设每个连通块大小是 $d_i$ ，连边可以形成的树的个数是 n^{k-2} \prod d_i考虑 $\text{prufer}$ 序，构造一个长度为 $k-2$ 的值为 $1 \sim n$ 的 $\text{prufer}$ 序。然后还原方法是把连通块看成点，把 $1 \do ...

好题。也是一个会一半的题目，最后一半是一个没怎么见过的套路。 考虑字典序比较，常见的方法是枚举 $\text{LCP}$ 长度，然后固定下一位小于，然后剩下的随便放。 在这个题中，我们一样可以枚举 $\text{LCP}$ 的长度，比如长度为 $k$ ，也就意味着第 $p_1 \dots p_k$ 小在 $A,B$ 中是相等的，而 $A$ 的第 $p_{k+1}$ 小比 $B$ 的小。 我们考虑对两个集合分别排序后处理。对于每个 $k$ ，我们考虑 $p_{k+1}$ 处 $A$ 的取值对答案的 ...

CF Edu 30E Awards For Contestants考虑枚举前两个奖分别有多少人获得，然后会发现合法第三种奖的数量形成了一段区间，我们可以预处理 RMQ 来快速得到第三种奖的最大 $c_3 - d_{-1}$ 这个东西。 然后复杂度就是 $O(n\log n + n^2)$ 了。 F Forbidden Indices套路题。 有两种做法。首先最简单的就是建一棵 $\text{SAM}$ 然后插入 $1$ 的节点的时候把 $siz$ 设置为 $0$ ，否则为 $1$ ，然后直接算出 ...

CF Edu 20 / CF803A Maximal Binary Matrix贪心填数，每次先填 $(i,i)$ ，然后两个两个填 $(i,i+k),(i+k,i)$ ，如果只能填一次就放到 $(i+1,i+1)$ 上。不难发现每步都最优了，满足最大字典序。 罚时是代码在 $k = 0$ 的时候会放个 $1$ 进去。 B Distances to Zero$L[i],R[i]$ 分别表示左右最近的 $0$ ，然后转移显然讨论下这个位置是否为 $0$ 即可。 C Maximal GCD如果最终整 ...

CF Edu 25 / CF825D Suitable Replacement+1 二分 check 时候没有注意，炸 int 了。 二分一下会拿多少个 $T$ ，然后判断一下字母个数够不够用即可。复杂度 $O(n + 26\log n)$ 。 E Minimal Labels1A 以前的 Edu round 总是可以做到做过的套路题欸。 字典序最小的拓扑序是在 菜肴制作 见过。做法是建反图，然后每次拿最大的点放当前能放的最大标记。 考虑证明，最大的标记肯定出现在出度为 $0$ 的点里面。考虑出 ...

区间赋值与区间最小值，并且下标可以达到 $10^9$ 。 遇到这种下标很大的情况，往往做法有几种，要么离散化后变成一个下标不大的情况，要么用动态开点线段树，要么用平衡树来维护连续段。 然后可以考虑利用动态开点线段树来维护这个东西。如果初始序列全是 $0$ ，那么这个东西是很好维护的，只需要区间赋值后打上标记，每个节点维护区间中的最小值。 那么在初始区间非 $0$ 的时候是否可以套用这个做法？实际上，如果可以快速查询一个区间的最小值，也就是查询一个区间在主席树节点上应是的值，那么可以用类似的做法， ...

题目来源： CF316D3 CF477D CF468D A 队伍分配考虑建反图。然后问题就变成了把这个图分成两个集合，使得这两个集合内部没有任何边，仅在集合间有边。不难发现这就是在问这是不是一个二分图。 然后由于反图不一定联通，我们相当于是把若干个二分图联通块拼起来。也就是说相当于是有很多个数 $S_R - S_L$ ，每个数的贡献是 $+x$ 或者 $-x$ ，我们需要找到一种选贡献的方法使得最后得到的数的绝对值尽量大。由于显然 $S_R - S_L$ 是 $O(n)$ 的，和也是 $O( ...

A 小鸣的疑惑曾经做过。 考虑归纳证明。假设我们已经得到了前 $n-1$ 个数得到的答案是 $A_1 - A_2$ 。现在考虑 $n$ 个数的情况。 如果合并的两个数不包含 $A_1,A_2$ ，那么就得到了一个子问题，答案是 $A_1 - A_2$ 。 如果合并的两个数包含 $A_1,A_2$ ，有两种情况，要么一步变成了 $A_1 - A_2 , A_3$ ，要么变成了 $A_1,A_2 - A_3$ 。出现这两种情况的概率是一样的，于是这两种情况的期望值就是 $\frac 1 2(A_1 ...

CF1307F Cow and Vacation首先在边上建点，于是距离就从 $k$ 变成了 $2k$。 距离变成偶数后，对于两个位置，它们可达的条件就是从其中一个走 $k$ 另一个走 $k$ 能到的点有交。 首先考虑以每个点作为中转点可以到达的点。也就是只要某一步到达了这个点就一定可以通过转驿站来走到的点。做法是把所有驿站加入队列距离设置为 $0$ 进行一次 bfs 。考虑当我们从一个点到达另一个已经访问过的点，那么这两个点所对应的联通块可以直接合并，因为总是可以通过这两个点的初始驿站互相到达 ...

后面是某 $dp$ 讲义的习题，前面是前两天讲的题。 APIO 2018 New Home 新家考虑按照年份枚举一下，相当于在 $l_i$ 加入 $i$ ，在 $r_i + 1$ 删除 $i$ 。然后询问就是二分一下答案，考虑 $[a-m,a+m]$ 是否存在所有类型的商店，也就是是否存在某个 $(a+m,\infin)$ 的数的 $pre$ 小于 $a-m$ ，是否存在某个 $(-\infin ,a-m)$ 的数的 $nxt$ 大于 $a+m$ 。 线段树维护，在线段树叶子结点开个 set 即 ...