Z CF 板刷记录-526互联

七点半的灯火，人潮将我吞没，连同我小小的歌。

CF1783E

难点在读题，一句话题意是对于两个元素大小在 \(n\) 以内的序列 \(a,b\) ，找到所有的 \(k\) 能够满足 \(\forall i \in [1, n] , \lfloor \frac{a_i}{k} \rfloor \leq \lfloor \frac{b_i}{k} \rfloor\) 。

假设我们已经对于每一对 \(a_i, b_i\) 都求出了满足条件的 \(k\) 的集合，对他们求交就可以得到整个序列的答案集合，那么只需要考虑怎么对 \(a_i, b_i\) 求所有的 \(k\) 即可。这个条件等价的可以转换成 \(b_i \leq kx \leq a_i - 1\) ，于是可以差分预处理出来不能成为 \(k\) 的倍数的数，于是可以直接枚举这样的 \(k\) 的倍数，检查是否满足条件即可，复杂度 \(\Theta(n \log n)\) 。

CF1783F

考虑单个序列怎么做，这个东西是个置换，把所有的环扣出来即可，那么答案就是 \(n - cnt\) ，其中 \(cnt\) 是环的个数。

如果两个序列，同时操作需要保证两个环同时还原。再返回去看 \(n - cnt\) 的来的过程，操作一次相当于把一个环的点数减一，而每个环都有一个不会动的点，于是可以通过这个不动点去同步两个序列，具体而言，对于 \(i\) 在 \(a\) 中的环记为 \(ca_i\) ，同样地定义 \(cb_i\) ，那么将 \(ca_i\) 和 \(cb_i\) 连边，跑最大匹配即可。

CF1749E

一道很有意思的建图题，使得这张图隔断的条件很简单，需要存在一条联通的栅栏，长度为 \(m\) ，于是建边为：\((i, j)\) 向斜方向上的点连边，如果该点已经被放置，那么边权为 \(0\) ，否则边权为 \(1\) ，然后再弄起始节点，跑 \(0/1\) 最短路就可以了，复杂度 \(\Theta(nm)\) 。

CF1749F

首先是一个很套路的分类，可以把子树内的贡献和子树外的贡献分开来考虑。

但是我并没有第一时间想到，因为受到了另外一道题的误导，这一道题大概算是弱化版，只用更新到某个点的距离不超过 \(d\) 的节点的权值，这个时候就可以用 \(bfs\) 序来维护，因为是一圈一圈的，还非常好写。

也可以发现这两道题本质不同的地方，在于数据范围，并且上一道限制了节点的度数小于 \(2\) ，就不会被双重菊花图卡爆。

而这一道比较关键的地方在于 \(k \le 20\) ，可以盲猜这个会出现在复杂度里面。
显而易见的是把要把贡献叠到被计算的单点上，再结合第一个分类，往子树上贡献可以搞一个数据结构解决，往子树外贡献可以非常平凡的 \(\Theta(k)\) 暴力爬。

现在的问题是会算重，我想了半天就是不会，流汗。

接下来是形式化的题解。

定义 \(sum_{d,u}\) 为与 \(u\) 结点距离为 \(d\) 的在 \(u\) 的子树内的节点的增值。

query：\(\large {\sum_{i=0}^{d} sum_{i, fa_{i, u}}}\)
update: 是一个迭代的过程，当前在节点 \(u\) ，需要更新的距离为 \(d\) ，那么重复以下操作 \(sum_{d,u} := sum_{d,u} + \Delta, sum_{d-1,u}:=sum_{d-1,u} + \Delta, d:=d-1, u=fa_u\) 。

然后把这个玩意搬到一条链上面，套上一个重链剖分，用树状数组维护就可以了。

CF1743F

感觉比 E 要难，但是评分低了。
拿到题感觉下不了手，观察到这个集合最大也只有 \(3e5\) 个元素，那么可以套路地去给每一个元素计算贡献。

还是不会。。。

其实发现我们关心的是这个元素和当前操作集合是否有包含关系。分类讨论一下 \(x\) 和 \(S_n\) 的关系。

包含，那么在交和并操作之后依然包含。
不包含，那么在异或和并操作之后可以使得包含关系成立。

如果这个元素最后一次是被包含在了 \(S_k\) 那么对于之前所有集合操作方式有 \(2 \times 3^{k-2}\) 使得这个元素被包含，对于之后的序列有 \(2^{n-k+1}\) 中操作序列，乘起来便是整个贡献。

现在我们需要求到这个 \(k\) ，于是我们从前往后依次枚举每一条线段，每次查询 \([L,R]\) 中 \(0\) 的个数，直接累加贡献，然后把区间赋 \(1\) 。
注意要离散化或动态开点。

CF1821F

挺好一道题，可惜我是暴力二项式反演丑陋做法。

贪心的判定很显然，能往左边倒就往左边倒。先按计数 dp 方法写个式子， \(dp_{i, j}\) 表示前 \(i\) 棵树最后一棵倒下来放到了 \(j\) 的方案数。

\[dp_{i, j} = \sum_{l = 0}^{j - k - 1} dp_{i - 1, l} + \sum_{l = j - 2k}^{j - k - 1} dp_{i - 1, l} \]

然后我对 GF 不怎么熟，就观察了一下这个式子，发现可以改写为

\[dp_{i, j} = 2 \sum_{l = j - 2k}^{j - k - 1} dp_{i, l} + \sum_{l = 0}^{j - 2k} dp_{i, l} \]

继续观察，发现可以转化这个问题，对于一个长度为 \(n\) 的序列分成 \(m\) 段，使得每一段的长度都大于等于 \(k\) ，当一段的长度大于 \(2k\) 时，该段的贡献为 \(2\) 。

于是定义 \(f_i\) 表示恰好有 \(i\) 段的长度大于 \(2k\) 的方案数，则答案为 \(\sum_{i = 0}^m 2^{m - i} f_i\) ，然后开始吟唱，定义 \(g_i\) 表示至少 \(i\) 段的长度大于 \(2k\) ，那么有下面的等式。

\[\begin{aligned} g_i &= \sum_{j = i}^{m} \binom{m}{j} f_j \\ &= \binom{m}{i} \binom{n - (i + m)k}{m} \end{aligned} \]

继续化简答案

\[\begin{aligned} res &= \sum_{i = 0}^{m}\sum_{j = i}^{m} (-1)^j \binom{j}{i} g_j \\ &= \sum_{j = 0}^{m} g_j \sum_{i = 0}^{j} 2^{m - j} (-1)^{i - j} \binom{j}{i} \\ &= \sum_{j = 0}^{m} (-1)^{j} 2^{m - j} g_j \end{aligned} \]

于是可以 \(\Theta(m)\) 直接计算了。

其实这个玩意没有这么复杂。可以有一个非常优美的 GF 做法，可惜我不会 /kk

CF1651F

高妙题，第一眼看上去是对塔分块，有一个比较暴力的 \(\Theta(n \sqrt{n})\) 的做法能冲过去。

正解就很神了，首先需要观察，一个怪兽能造成的贡献可以拆分成两种方式，第一种是一段区间直接推平，第二种是对于某一个塔削弱血量。考虑颜色段均摊，维护场上的若干个连续段 \([l, r]\)。

如果遇到 \(l=r\)，直接暴力算。遇到 \(l<r\)，这代表被以前的询问推平的一段区间，问题成了给定初始生命 \(hp\)，时间差 \(T\)，左右端点 \([l,r]\) ，问是否能再次推平这个区间，或者是在这个区间停下。

比较关键的步骤是将塔的回血操作看成分段的一次函数，具体是

\[\begin{cases} r_i t, & t \le \lceil \frac{c_i}{r_i} \rceil \\ c_i, & t > \lceil \frac{c_i}{r_i} \rceil \end{cases} \]

以位置为下标，可以上可持久化线段树，合并一次函数就行了。于是得到了一个主席树上二分的单 \(log\) 做法。

CF1657F

明显是 2-sat 首先把路经抠下来，路经上第 \(i\) 个点可以是 \(str_{i}\) 或 \(str_{len - i + 1}\) ，为表述方便，记为 \(a, b\) ，将 \((a, b, x, y)\) 视为一个限制。

现在考虑如何合并两个限制，记另外一个限制为 \((c, d, x, y)\) ，讨论一下。

\(a \not = c\) ：如果选 \(a\) ，则强制另外一个限制路径用 \(y \rightarrow x\) 满足限制，如果选了 \(x \rightarrow y\)，则只能选 \(b\)
\(b \not = c\) ：如果选 \(b\) ，则强制另外一个限制路径用 \(x \rightarrow y\) 满足限制，如果选了 \(y \rightarrow x\)，则只能选 \(c\)
对于 \(d\) ，同理，不写了

于是这是个点数为 \(2 \times nm\) 的做法。

CF1661F

令 \(dp_{len, x}\) 表示该区间长度为 \(len\) ，增加 \(x\) 个传送器后的代价。

观察一下，这个是个均值，所以每段最好分得尽量平均，有

\[\begin{aligned} dp_{len, x} = (x - len \ \mathrm{mod} \ {(x + 1)}(\lfloor \frac{len}{x + 1} \rfloor)^2) + len \ \mathrm{mod} \ (x + 1)(\lceil \frac{len}{x + 1} \rceil)^2 \end{aligned} \]

再观察一下，发现 \(dp_{len, x} - dp_{len, x}\) 有单调性，可以瞪眼大法知道是不增。然后可以直接二分这个减少的量记为 \(\Delta\) ，于是对每一段都求出来最大满足 \(dp_{len, x} - dp_{len, x + 1}\) 的 \(x\) ，于是增加 \(\Delta\) 个传送器的代价可以求得记为 \(cost_{\Delta}\)。

似乎直接去求最大满足 \(cost_{\Delta} \le m\) 的 \(\Delta\) 即可，但是这个 \(\Delta\) 不一定最优，我们可以在 \(\Delta + 1\) 的基础上继续增加，因为每增加 \(1\) 个传送器，代价就会减少 \(\Delta\) ，所以算出来最少增加 \(\lceil \frac{cost_{\Delta + 1} - m}{d} \rceil\) 个。

CF1809F

首先看到 \(b_i \in [1, 2]\) ，这明显是一个值得去发现性质的点。因为油箱容量不变（废话），所以遇到 \(1\) 能加满就加满，只有在实在没油的情况下才会去加 \(2\) 。发现这个合并并不是那么优美，因为每次剩下的油量都不一样，那么考虑每次都在油箱空了的时候去合并。

如果当前 \(b_i = 1\)
- 并且 \(b_{i + 1} \not = 2\) ，直接交完当前需要的油钱，移动到下一个位置。
- 否则后面将会有 \(len\) 个连续的 \(2\) ，对于这一段区间记为 \([i + 1, i + len]\) ，记 \(a_i\) 的前缀和数组为 \(sum\) ，需要二分出第一个 \(pos\) ，使得 \(sum[i + 1 \dots pos] \le k\) ，那么这一段区间的所有油都应该在 \(i\) 处只花 \(1\) 的代价加上，这是就会出现后面一段 \([pos + 1, i + len]\) 的油不够，那么这一段只能花 \(2\) 的代价买油。
如果当前 \(b_i = 2\) ，直接交 \(2 \times a_i\) ，往下移动。

于是得到了从每一个点出发走一步在最优情况下能够到达的位置记为 \(nxt_{pos, 0}\) ，显然这是一个倍增数组。

最后会发现一个小问题，在倍增完之后有可能到不了终点，并且这一段是连续的 \(1\) ，那么直接计算两者之间的距离就能解决了。

CF1697F

又是 2-sat ，首先建出来 \(a_i \rightarrow v\) 的边表示 \(a_i\) 是否大于等于 \(v\) ，有下面几个限制

\(a_i \le a_{i + 1}\) ， \(\forall v\) ，\(a_i \ge v \Rightarrow a_{i + 1} \ge v\)
\(a_i \not = x\) ， \(a_i \ge x \Rightarrow a_{i} \ge x + 1\)
\(a_i + a_j \le x\) ， \(a_i \ge v \Rightarrow \neg (a_j \ge v - a_i)\)
\(a_i + a_j \ge x\) ， \(\neg(a_i \ge v) \Rightarrow a_j \ge v - a_i\)

注意到不能忘记去建逆否命题的边，以及 \(a_i \ge v \Rightarrow a_i \ge (v - 1)\) 。

CF1680F

首先二分图一定满足题目要求，否则该图中有奇环，删去的边一定要一键干掉所有的奇环，那么树上差分维护经过每个点的奇环就可以了。

CF1716 F

就是要求下面这个式子，开始吟唱

\[\begin{aligned} & \sum_{i = 0}^{n} i^k \binom{n}{i} \left( \lceil \frac{m}{2} \rceil \right)^i \left( \lfloor \frac{m}{2} \rfloor \right)^{n - i} \\ =& \sum_{i = 0}^{n} \sum_{j = 0}^{k} j! \begin{Bmatrix} k \\ j \end{Bmatrix} \binom{i}{j} \left( \lceil \frac{m}{2} \rceil \right)^i \left( \lfloor \frac{m}{2} \rfloor \right)^{n - i} \\ =& \sum_{j = 0}^{k} j! \begin{Bmatrix} k \\ j \end{Bmatrix} \sum_{i = 0}^{n} \binom{i}{j} \left( \lceil \frac{m}{2} \rceil \right)^i \left( \lfloor \frac{m}{2} \rfloor \right)^{n - i} \\ =& \sum_{j = 0}^{k} j! \begin{Bmatrix} k \\ j \end{Bmatrix} n^{\underline{j}} \left( \lceil \frac{m}{2} \rceil \right)^j m^{n - j} \end{aligned} \]

CF1709F

好吧，根本没读懂题，所以给一个看到的正常翻译。

一棵高度为 \(n\) 的满二叉树（共 \(2^{n + 1}\) 个点，\(2^{n + 1} - 2\) 条边），边从父亲指向儿子。

每条边的最大流量为 \([0, k]\) 内的整数，求有几种赋最大流量方案，使得以根为源点，所有叶子为汇点，最大流恰好为 \(f\) 。

令 \(dp_{x, f}\) 表示现在从下往上流回第 \(x\) 层，最大流量是 \(f\) 的总方案数，因为每一层的 \(dp\) 值是一样的，所以说只需要对 \(n\) 个点进行计算就可以了。那么往上计算，对于两个子结点 \(u, v\) 往 \(fa\) 转移的时候，限制的因素要么是 \(fa\) 处的流量，要么是 \(u\) 和 \(v\) 的流量和。

写出转移方程

\[\begin{aligned} dp_{fa, c} = \sum_{i + j > c} (dp_{u, i} \cdot dp_{v, j}) + \sum_{i + j = c} (k - c + 1) (dp_{u, i} \cdot dp_{v, j}) \end{aligned} \]

注意到 \(dp_{u, \dots}\) 和 \(dp_{v, \dots}\) 是一个东西，于是 \(dp_{u, i} \cdot dp_{v, j} = dp_{u, i + j}\) 。于是调整一下这个式子变成

\[\begin{aligned} &dp_{fa, c} = \sum_{i = c + 1}^{2k} dp_{u, i} + (k - c + 1) dp_{u, c} \end{aligned} \]

因为 \(dp_{u, i} \cdot dp_{v, j} = dp_{u, i + j}\) 是个卷积形式。

那么令 \(G\) 是上一层的生成函数， \(F\) 是这一层的生成函数，那么 \(G = F^2\) ，直接 NTT 解决即可。

CF1795F

考虑对于一个固定的步数，构造出来一个唯一的方案。

操作是有顺序的，必须按照 \(1, 2, 3, \dots, k\) 的顺序走，那么在总步数为 \(s\) 的约束下，每一个棋子的步数可以确定，记为 \(cnt_i\) ，于是递归去处理这个问题，记每一个位置目前能够往下（深度更大）走的最大距离为 \(tot_u\) 对于当前位置的 \(u\) ，如果 \(tot_u \ge cnt_i\) ，直接把它放下去，否则往上挪，如果父结点也有棋子或者它本身是根，那么无法完成要求。于是二分即可。

CF1809G

每次在末尾添加一个元素的时候，关心的只有前面所有元素的最大值，因为 \(n \in [1, 1e6]\) ，并且不可能去记录现在剩下来的最大值，所以猜测这个计数往后添加时一定是有一个明确的顺序的。

考虑到这个状态只能一维地去定义，那么就必须保证每一步填完之后这个数列都合法，就是说 要让当前数列开头的数和剩下的数无论怎么填都合法 ，定义 \(dp_{i}\) 表示已经填了前面第 \(i\) 大的元素，那么第 \(i + 1\) 大的元素有两种填法。

不成为第一个数， \(dp_{i + 1} := dp_{i + 1} + dp_{i} \times i\)
成为第一个数，这样会有冲突，是 \([i+2 \cdots to[i]-1]\) 连续的一段应该也一起放，这样保证状态还是合法的。 \(dp_{to[i+1]-1} := dp_i \times (i \times \cdots \times to[i+1]-3)\)

CF1814F

线段树分治。判断是否和 \(1\) 联通，直接在并查集上打标记就可以了，注意下传的时候撤销。

CF997C

考虑容斥，定义 \(f(x, y)\) 表示至少有 \(x\) 行，\(y\) 列被染成了同样的颜色的方案数。
分类讨论一下，得到

\[\begin{aligned} f(x, y) = \begin{cases} \binom{n}{x + y} 3^{(n - x - y)n + x + y}, & xy = 0, x + y \not= 0 \\ \binom{n}{x} \binom{n}{y} 3^{(n - x)(n - y) + 1} & xy \not= 0,x + y \not= 0 \\ 3^{n^2} & xy = 0,x + y = 0\\ \end{cases} \end{aligned} \]

进行一个二维的反演，定义 \(g(x, y)\) 表示恰好有 \(x\) 行，\(y\) 列被染成了同样的颜色的方案数。

\[\begin{aligned} &f(x, y) = \sum_{i = 0}^{n} \sum_{j = 0}^{n} \binom{n}{i} \binom{n}{j} g(i, j) \\ \Leftrightarrow & g(x, y)= \sum_{i = x}^{n} \sum_{j = y}^{n} \binom{x}{i} \binom{y}{j} (-1)^{(i + j) - (x + y)} f(i, j) \end{aligned} \]

用总方案数减去 \(g(0, 0)\) 就是答案，现在来求 \(g(0, 0)\)。

\[\begin{aligned} g(0, 0) &= \sum_{i = 0}^{n} \sum_{j = 0}^{n} (-1)^{i + j} f(i, j) \\ &= f(0, 0) + \left(\sum_{i = 1}^{n} f(0, i) + f(i, 0)\right) + \sum_{i = 1}^{n} \sum_{j = 1}^{n} (-1)^{i + j} f(i, j) \\ &\sum_{i = 1}^{n} \sum_{j = 1}^{n} (-1)^{i + j} f(i, j) \\ =&\sum_{i = 1}^{n} \sum_{j = 1}^{n} (-1)^{i + j} \binom{n}{i} \binom{n}{j} 3^{(n - i)(n - j) + 1} \\ =&3\sum_{i = 1}^{n} (-1)^i \binom{n}{i} \sum_{j = 1}^{n} (-1)^{j} \binom{n}{n - j} \left(3^{n - i}\right)^{(n - j)} \\ =&3\sum_{i = 1}^{n} (-1)^i \binom{n}{i} (3^{n - i} - 1)^{n} \end{aligned} \]

于是可以 \(\Theta(n)\) 计算了。

CF1383E

CF1743E

\(dp\) 阶段很关键，当两发激光炮同时发射之后这个问题就会回到最开始的状态，但是 \(h\) 会变小。

这就启发我们去利用这样的状态 \(dp\) ，具体而言，可以预处理出来从初始状态到产生 \(x\) 的伤害时最小要花费的时间，这个计算能够用二分处理，因为一个比较明显的性质是，这两门激光炮中伤害更大的那一门会一直不停的发射。

于是后续的 \(dp\) 就非常平凡了，复杂度为 \(\Theta(h^2)\) 。

板刷题解round educational