杂题选做 [S-C1]

· · 个人记录

【S-C1】是啥意思？？

01. CF1858E2 Rollbacks (Hard Version)

维护一个初始为空的序列 a，支持以下操作：

有 q 次操作，强制在线，1\le q,x\le 10^6，询问操作不超过 10^5。

解法

垃圾 *2600。

经典地，我们用 set 维护所有数字的出现的所有位置，更新时只需要查询其首位即可。

这样我们可以轻松实现 \texttt + 操作。

为了实现 \texttt - 操作，我们引入序列 A，使得序列 A 的前 l 位恰好为序列 a（l 为序列 a 此时的长度）。这样一来，我们更新时直接将 l 更改为 l-k 即可。

这样做同样是为了方便进行 \texttt ! 操作。因为我们实际上保留了 1\sim l_{\max} 的所有信息，足以进行回溯。

对于 \texttt ! 操作，我们使用 stack 存储所有操作，并尝试逆向地进行还原，具体情况与上面的 \texttt +/\texttt - 操作思路一致。

特别地，对于 \texttt + 操作，我们需要存储原来的 A_{l'} 而不是 x。这是容易理解的。

至于答案的更新，我们在所有元素第一次出现的位置标记为 1，这个是已经维护过的。

那么 \texttt ? 操作只需要输出该数组在 [1,l] 上的区间和即可。

至此，我们需要一个可以支持单点修改、查询区间和的数据结构。拉一个树状数组即可。

时间复杂度 O(q\log q)。

https://codeforces.com/contest/1858/submission/219045104

考虑优化，逐个解决瓶颈：

据此，我们得到时间复杂度 O(q) 的做法。代码从略。

02. CF1804F Approximate Diameter

给定一个 n 个点 m 条边的初始无向图，有 q 次更新，每次更新向图中添加一条边。设 d(G_i) 代表加入 i 条边后的图中两点之间的最大距离，你需要输出 q+1 个整数 a_0,a_1,\dots,a_q，满足 \Bigl\lceil\dfrac{d(G_i)}{2}\Bigr\rceil\le a_i\le 2\cdot d(G_i)。

### 解法 牛逼 \*2700。 考虑一个性质，以某个点为端点的最长路径长度 $s$ 满足 $$ \Bigl\lceil\dfrac{d(G_i)}2\Bigr\rceil\le s\le d(G_i) $$ 证明从略。 但是发现这个比要求的更紧。考虑怎么利用这个 $2\cdot d(G_i)$。 显然地，我们考虑二分某个答案什么时候失效，此时我们将该答案除以 $2$ 即可。这是可行的，因为这个一眼单调。 二分枚举端点再套枚举答案即可，时间复杂度 $O(n\log^2 n)$。 <https://codeforces.com/contest/1804/submission/219393324> 注意我们钦点的 dijkstra 算法别写丑，不然无法通过。 ## _03._ CF992E Nastya and King-Shamans 给定序列 $a$，维护两种操作： - 单点将 $a_i\to x$； - 查询 $\sum_{i=1}^n\Bigl[\Bigl(\sum_{j=1}^{i-1}a_j\Bigr)=a_i\Bigr]$。 $1\le n,q\le 2\times10^5$，$0\le a\le 10^9$。 ### 解法 还不错的 \*2500。 考虑一个性质：答案最多为 $\log n$。 证明从略。我们考虑直接拉线段树维护然后暴力遍历即可找到答案。 时间复杂度 $O(q\log^2 n)$。 <https://codeforces.com/contest/992/submission/219414380> ## _04._ CF825G Tree Queries 一棵树有 $n$ 个节点，初始均为白色，有两种操作： - $\texttt{1 } x$：把节点 $x$ 染为黑色； - $\texttt{2 } x$：查询 $x$ 到树上任意一个黑色节点的简单路径上的编号最小的节点的编号。 保证第一个操作为染色操作，强制在线。$3\le n\le 10^6$，$1\le q\le 10^6$。 ### 解法 小清新 \*2500！ 首先，显然地，为了方便维护，我们以第一次染色的节点 $t$ 为根 dfs 一遍以求出所有节点到 $t$ 的简单路径上的编号最小的节点的编号，即数组 $a$。 然后画个图可以理解： - 对于染色操作，将目前维护的一个答案 $ans\gets \min(ans,a_x)$，可以证明这是正确的； - 对于询问操作，我们输出 $\min(ans,a_x)$ 即可。 这是因为，我们的对于不同 $t$ 的子树间的路径 $u\to v$，有 $u\to t\to v$ 即为其简单路径。而对于子树内的路径，可以用 $u\to t,v\to t$ 覆盖整个路径。 至此问题得到 $O(n)$ 解决。 <https://codeforces.com/contest/825/submission/219512635> ## _05._ CF1503D Flip the Cards 你有 $n$ 张牌，第 $i$ 张牌的正面有整数 $a_i$，背面有整数 $b_i$。所有 $1$ 到 $2n$ 的整数都出现过正好一次。 我们认为这 $n$ 张牌是好的当且仅当 $a_i$ 升序，$b_i$ 降序。 可以进行下面的操作： - 交换 $a_i,b_i$。 - 随意重排这 $n$ 张牌。 求如果要使这 $n$ 张牌变成好的最少需要**翻几次牌**，或报告无解。 ### 解法 牛逼 \*2600。可惜放了 $\log$ 过。 我们考虑到，若存在一个 $i$ 使得 $a_i,b_i\le n$，则必然无解。 于是考虑将所有牌变成 $a_i<b_i$ 的情况，则必然有 $a_i\le n,b_i>n$。于是设 $f(a_i)=b_i$。 下面研究 $f(i)$。发现当且仅当 $f(1\ldots n)$ 可以被分为两个单调递减子序列使有解。 在 $\min_{j=1}^i\{a_j\}>\max_{j=i+1}^n\{a_j\}$ 处断点分段处理最小值即可。 时间复杂度 $O(n)$，远超 $\log$ 且更巧妙。 同时注意到没必要管顺序。 <https://codeforces.com/contest/1503/submission/219536981> ## _06._ CF1646F Playing Around the Table 有 $n$ 个人坐成一个圈，每个人手上有 $n$ 张麻将，麻将上是 $1$ 萬到 $n$ 萬，每次可以让每个人同时掏出一张麻将给下一个人，构造一组方案使得第 $i$ 个人能够做成「$i$ 萬一色」。 要求，操作次数不超过 $n^2-n$；$1\le n\le 100$。 ### 解法 萌萌 \*2900。 我们考虑到，为了方便处理，设计一个过渡态「一气通贯」使所有情况达到统一。 可以证明，初态 $\to$「一气通贯」$\to$「$i$ 萬一色」这一变换中，第一步的操作次数不超过 $n(n-1)/2$，第二步的操作次数为 $n(n-1)/2$。 下面，我们证明第一个。发现离「一气通贯」最远的状态是每个人均有一个「$j$ 萬一色」，证毕。 <https://codeforces.com/contest/1646/submission/219623330> 感觉还是比较难想的，所以场上才仅 3 人通过。 ## _07._ CF802H Fake News (medium) 构造字符串 $s,p$，使字符串 $s$ 的为 $p$ 的子串恰有 $n\ (1\le n\le 10^6)$ 个。 ### 解法 萌萌 \*2200！感觉思路比较牛逼。 我首先想到了 [CF1368B Codeforces Subsequences](https://codeforces.com/contest/1368/problem/B)，不同的是，这道题是**至少** $n$ 个。 一个朴素的想法是，对于恰好有 $k$ 个子串的情况 $(s,p)$，我们可以实现 $k\to 2 k$。 具体地，任取一个**新字符** $c$，令 $s'=scc$，$p'=pc$ 即可（这里直接用字符串拼接表示了）。 但是我们不能实现 $k\to k+1$。这是很困难的。否则我们可以直接二进制拆分 $n$ 解决。 考虑另一个思路，假设对于恰好有 $k$ 个子串的情况 $(s,p)$，$s$ 可以被表示为 $pu$（$u$ 也是一个字符串），任取一个新字符 $c$，那么我们可以实现 - $k\to 2 k+1$：令 $s'=pcucc$，$p'=pc$ 即可； - $k\to 2 k+2$：令 $s'=pccucc$，$p'=pc$ 即可。 这之后我们均直接可以更新 $u'$。 于是我们递归地解决这个问题即可。考虑每次处理 $x$ 时，先解决 $\left\lfloor\frac{x-1}2\right\rfloor$ 时的情况，再回溯解决。容易发现这是合理的。 边界是 $x=1,2$。这个也是平凡的，只需要使 $p=\texttt a$ 即可。 这个是很对的，不考虑 string 类的复杂度是 $O(\log n)$。由于 $2^{26}>10^6$，我们可以仅用小写字母解决本题。 <https://codeforces.com/contest/802/submission/219735685> ## _08._ CF1363F Rotating Substrings 给定两个长度为 $n$ 的字符串 $s,t$。定义一次操作为选择 $s$ 的一个子串 $s_{l, l +1, \dots, r}$，然后将其修改为 $s_{r, l, l + 1, l + 2, \dots, r - 1 }$。请求出使 $s$ 与 $t$ 相等的最小操作次数或判定无解。 多组数据，$\sum n \leq 2000$，$s, t$ 中只有小写字母。 ### 解法 很好 \*2600。 我们考虑设 $dp_{i,j}$ 表示 $s$ 长度为 $i$ 的前缀插入 $i$ 后的**若干**个字符后，等于 $t$ 长度为 $j$ 的前缀的最小花费。显然这里有 $i\le j$。我们分情况转移： 1. 如果 $s_i=t_j$，可以直接匹配，也即 $dp_{i,j}=dp_{i-1,j-1}$； 2. 如果 $s_{r+1,n}$ 中存在 $t_j$，我们可以直接拉过来匹配，也即 $dp_{i,j}=dp_{i,j-1}$。**我们这里暂时不计算贡献，具体原因见下**； 3. 直接把 $s_i$ 拉到前面去，也即 $dp_{i,j}=dp_{i-1,j}+1$。这样的目的在于，我们保证了 2 中必定将会有某个 $t_j$ 被拉到前面去并计算了其贡献。 于是就可以转移了。 感觉这个**假借字符**的思路比较巧妙。