九月算法竞赛选题（二）

[[ slider_text ]]

[[ item.c ]]

九月算法竞赛选题（二）

发布时间 2025-09-18 作者：秋千月 来源：算法小站

拓扑排序

## Educational Codeforces Round 182
### D
**[D. Price Tags](https://codeforces.com/contest/2144/problem/D)**
给定`n`件商品，价格是`a[1...n]`，现在要打折，可以选一个`x`，使得每件商品的价格变成$$\lceil \dfrac{a_i}{x} \rceil$$
但是重新贴标签，每个标签需要$$y$$的额外代价，但是呢，假设说你新的标签是`val`
你发现如果原来有商品标价是`val`，那么你就可以不要重新贴标签了
形式化地说，`y * max(0, need[val] - has[val])`，是你需要贴标签的代价
现在要最大化利润

**算法分析**
很明显的可以根号分治，如果$$x \leqslant \sqrt{V}$$，直接暴力

如果$$x > \sqrt{V}$$呢？注意到，此时新价格$$p = \lceil \dfrac{V}{x} \rceil$$就很小了，$$p \in \sqrt{V}$$
暴力枚举$$x$$仍然可行，但是`for i = 1 to n`肯定不行了，这个时候枚举新的价值
并且计算**每一个新价值的贡献**

> 怎么算呢？对于新价值$$p$$，可能的新价值$$p \in [1\cdots \lceil \dfrac{V}{x} \rceil]$$
关键在于，只需要知道有多少个**原来的$$a_i$$**，会改成这个新价值$$p$$？其中`x`我们枚举了，是已知的

注意到$$p = \lceil \dfrac{a_i}{x} \rceil$$，那么$$p, x$$已知的情况下，$$a_i \in [(p-1)x+1, px]$$

那么每个$$p, x$$，都可以搞出这样的区间$$[l, r]$$，只需要记一下有多少个**初始的**$$a_i \in [l, r]$$即可
这一步，可以用前缀和预处理，$$needp = S[r] - S[l-1]$$得到

那么$$p$$对答案的贡献就是，`sum += p * needp`，同时令`del = max(0, needp - has[p])`
然后`sum -= 1Ll * y * del`，这部分就维护好了

## Hello 2023
### C
**[C. Least Prefix Sum](https://codeforces.com/contest/1779/problem/C)**
给定一个序列，你可以执行若干次操作，每次选择一个下标$$i$$，令$$a_i = -a_i$$
现在给定$$m$$，要求任意的非空前缀和，满足$$a_1 + a_2 + \cdots + a_m$$总是最小的
即$$a_1 + a_2 + \cdots + a_m \leqslant a_1 + a_2 + \cdots + a_k$$对任意$$k$$恒成立
问最少要多少次操作

**算法分析**
首先对于$$i \geqslant [m+1\cdots n]$$，以`m`为基准，令$$sum = 0$$，遍历$$i$$，`sum += a[i]`
如果$$sum \geqslant 0$$，那么什么都不用做，否则的话，就一定要修改
修改一个下标，`sum`会怎么变化呢？$$sum = sum - a_i + (-a_i)$$，即有$$sum \leftarrow sum - 2a_i$$
而$$sum < 0$$才需要修改，我们要将$$sum$$改的尽可能大，这时候取$$a_i < 0$$并且$$|a_i|$$最大的数
只要不满足$$sum \geqslant 0$$，那么就取$$[m+1\cdots i]$$中，**最小的数**改，同时维护`sum`
这部分就统计完了

那么怎么考虑$$i \in [1, m)$$呢？**可以考虑倒着扫描**，如果$$S_i < S_m$$，那么此时改$$[1, i]$$肯定是没有用的
换句话说，我们此时只能改$$[i+1, m]$$中的数，并且只能**减小**$$S_m$$，怎么做呢？
注意到，因为我们倒着扫描，所以后面的修改并不会影响前面的前缀和，所以只需要维护$$sm$$的值即可
修改操作，$$sm \leftarrow sm - 2a_j$$，往小了改，如果发现$$s_i < sm$$，那么取**扫描过的最大的数**
假设说是$$maxv$$，然后`sm -= 2maxv`即可

扫描过的最大最小 + 修改，可以优先队列或者`set`来实现

### D
**[D. Boris and His Amazing Haircut](https://codeforces.com/contest/1779/problem/D)**
理头发，当前的头发用序列`a`表示，目标头发用序列`b`来表示，`m`把剃刀，每一把剃刀的尺寸假设为$$x$$
并且没把剃刀最多只能用一次，如果多把尺寸相同，假设有`sz`个，那么只能用$$\leqslant sz$$次
在一次操作中，选择一把剃刀并且修建头发，如下描述
选择一把没有使用过的剃刀，假设尺寸是$$x$$，选择一个区间$$[l, r]$$，对每个$$i \in [l. r]$$
令$$a_i = \min(a_i, x)$$
可以任意次操作，判断最后理发师能否把头发修剪成想要的样子

**算法分析**
还是很容易写出来了，如果$$b_i > a_i$$，无解，因为所有操作都只能减小$$a$$
其次，**从大到小考虑**，如果考虑减少到$$b_i$$，`b`左边$$> b_i$$的数肯定不能操作，右边$$> b_i$$的数也不能操作
所以可以单调栈预处理出每一个$$b_i$$对应的若干区间$$[L, R]$$，然后取这些不相交的区间
有多少个`（假设 num 个）`就需要多少把剃刀，对应地，维护`cnt[val] -= num`，如果`cnt < 0`就不合法

坑点，在于如果$$a_i = b_i$$是不需要操作的，对上面的过程，预处理不相交区间的时候，只考虑$$a_i \neq b_i$$的位置

### E
**[E. Anya's Simultaneous Exhibition](https://codeforces.com/contest/1779/problem/E)**
交互题，有$$n$$位象棋高手，编号从`1-n`，并且满足以下性质
对于任意一个选手，不会出现平局，总是有一方能够战胜对方
但不一定满足传递性，比如`A 战胜 B, B 战胜 C，但是 C 可以战胜 A`

一开始并不知道谁能战胜谁，举办`n-1`场比赛，每场比赛其中一人获胜并且留下，另一个人淘汰
所有比赛之后只剩下一名选手，若某位选手可能赢得比赛，那么就是 master
注意，根据$$n-1$$场比赛中，选择的对手的不同，可能会有不同的胜者

现在最多组织$$2n$$场同时博弈，在每一轮博弈中，选择一名选手，和其他$$\geqslant 1$$选手对弈
被选中的选手会赢下所有他能够赢得局，输掉他会输的局，同时博弈就意味着在进行期间，没有人会被淘汰
现在对弈结束后，我可以知道，我选的这个人，赢了多少场，但是不知道具体赢了谁

询问用`? i s1s2...sn`给出，`sn`是一个`01 串`，如果要让$$(i, j)$$博弈，必须$$s_j = 1$$，否则是$$0$$
另外$$s_i = 0$$恒成立

**算法分析**
首先，如果$$u$$能够战胜$$v$$，就建一条有向边$$u \to v$$，这样就构成了**竞赛图**，它是个特殊有向图

来看几个性质
> 关于它的 scc

对于竞赛图的 SCC，在这个问题下，SCC 中的任意一个点，都可能在这个 SCC 中胜出
为什么呢？因为竞赛图的 SCC 构成一个**哈密顿回路**（经过每个点恰好一次的回路）
而哈密顿回路，断掉任何一条边，选择一个起点，都会产生一个不同的胜者，一共$$|SCC|$$个 winner

> 性质一，竞赛图进行强连通分量缩点之后形成了一个 DAG，这个 DAG 中，每个点都会向自己后面的节点连边
并且存在一条最长链

如下图所示
![](/media/content_img/Hello2023-e.png)

> 性质二，如果一个点（原图）有着最高的出度，那么它就是**可能的胜利者**

有一个结论，**任意的另外的点**，都可以从这个度数最高的点$$s$$出发，经过**最多两次**到达
假设说一次能到的点集设为$$S_1$$，两次能到的设为$$S_2$$，那么假设$$x \notin S_1, S_2$$
因为竞赛图是完全图，这也意味着连边只能是$$x \to \\{S_1\\}$$`中所有的点`，$$x \to s$$
这也就意味着，$$x$$的出度是$$|S_1| + 1$$，而最大出度的点是$$s$$，它的出度也才$$|S_1|$$
这就矛盾了

> 性质三，竞赛图缩点后，链顶的 SCC 中任意一个点的出度，都大于之后的 SCC 中**所有点**的出度（针对原图，而非缩点之后的图）
更进一步的，前面强连通分量的点的出度，严格大于后继强连通分量的点的出度

经过上面的分析，我们不难得出结论，缩点之后的 DAG，入度为`0`的点（代表 SCC）
它里面所有实际的节点，就是答案

> 一种是缩点之后，找 DAG 中拓扑排序最小的 SCC 中的点，另一种是按每个节点的出度排序，找出度最大的点、

原图实际连边情况，在交互题中是不可知的，所以没法缩点，只能从出度的角度来考虑
我们可以询问$$(i, 111\cdots 1)$$，来知道每个点$$i$$的出度，那么在出度已知的情况下，怎么求答案呢？

首先可以对出度，**从大到小排序**，最后的答案一定是**一段前缀**
> 接下来的问题是，怎么根据出度，判断一段前缀是不是构成**极大的 SCC**？

首先，在$$2n$$次询问的前提下，可以很自然地，先用$$n$$次查询，得到每个点的出度
然后对出度从大到小排序，其中`map[deg] = {v1, v2, ...}`，把出度为`deg`的点用一个桶维护起来
这样，只要出度`deg = mx`的点，一定在**第一个 SCC 中**（以下 SCC 特指第一个 SCC）

> 有没有漏网之鱼呢？

出度$$deg \neq mx$$的点，有没有可能在第一个`SCC`中？我们需要最多$$n$$次查询来 check
已知第一个`SCC`中的所有点，都存在到后面 SCC 中的点的连边

那我们只需要维护第一个`SCC`中的点，然后考虑`check 其他 SCC`中的点
如果存在`query( 其他 SCC 中的点 u，第一个 SCC 中的点 ) != 0`，那么$$u$$就可以到达第一个`SCC`
而`SCC`中肯定有点能够到达`u`，从而$$u$$和第一个`SCC`中的点是**强连通的**
此时我们把`u`加入`SCC`，然后接着考虑即可

如果这个点可以加入`SCC`，根据**性质一，性质三**，只要$$deg_v \geqslant deg(u)$$的点$$v$$
也都可以到达`SCC`，为什么呢？

因为`deg >= deg(u)`的点，它所在的$$SCC'$$一定在$$SCC(u)$$的前面，根据性质三
存在连边$$SCC1 \to SCC' \to SCC(u)$$，而$$u$$可以到达`SCC1`，所以他们是强连通的

所以算法设计就比较简单了
如果我们判断，`deg != mx`的点$$u$$，能否加入`SCC1`呢？针对`query(u, SCC1 中的所有点)`做一次查询
如果可以加入，那么把`deg(j) >= deg(u)`的所有`j`都加入`SCC1`即可

### E hard
> 现在如果只给你$$n$$次询问的机会，要怎么做

那么考虑**出度和 SCC**有什么关系，注意到`SCC`中连出去的边，都是由`出度 deg(u)`**贡献的**
同时竞赛图是完全图，如果按度数从大到小排序，前$$i$$个点，有多少条边呢？
不难算出是$$\sum_i deg_i$$

> 现在问题来了，如果从一个`SCC`到另一个`SCC`连边，会发生什么？$$SCC_1 \to SCC_2$$

假设说$$SCC_1 \to SCC_2$$，如果考虑$$SCC$$中所有的点，构成的边的数量

恰好是$$|SCC_1| \cdot |SCC_2|$$，等价于$$\displaystyle\binom{|SCC_1|}{1} \binom{|SCC_2|}{1}$$

说明了什么？说明了此时$$|SCC_1|, |SCC_2|$$**不能合并**，只能由$$SCC_1$$连向$$SCC_2$$
而不能够合并之后，边内部消化

> 考虑必要条件

不难推出必要性，按照度数从大到小排序，第一个`SCC`一定是一段前缀

那么考虑前$$i$$个点，那么$$\sum_i deg_i$$肯定包括了$$\displaystyle \binom{i}{2}$$条边
（因为前`i`个点属于同一个`SCC`，又因为竞赛图是完全图，任意两个点都可以相互到达）
起点和终点都可以任意选

那么$$\sum deg_i$$会不会包含其他的，连到**后继 SCC 的边**呢？可能有，也能没有
什么时候构成了一个极大`SCC`呢？

因为竞赛图是完全图，缩点之后，每个点都会和后面的所有`SCC`连边，那么我们要尝试找到，
所点之后，和后面点有连边的，有用的点，怎么找？

> 这里有个前提，竞赛图按照`deg`从大到小排序后，缩点后的连通分量，拓扑序最小的`SCC1`一定是排序后的**一段前缀**

假设第一个`SCC`恰好包含了$$1 \sim i$$，实际上也就意味着第一个`SCC1`包含$$i$$个节点
它有多少条边呢？注意，竞赛图是一个完全图
首先，`SCC1`内部肯定两两有边（方向不确定），边数是$$\displaystyle \binom{i}{2} = \dfrac{i(i-1)}{2}$$

另外，`SCC1`中的点都会连向之后的`SCC`，那么从`SCC`中选一个点，方案数是$$\binom{i}{1}$$

从$$[i+1\cdots n]$$后面的点中，任选一个，方案数是$$\binom{n - i}{1}$$

综上所述，`SCC`中的出边一共有$$\dfrac{i(i-1)}{2} + n(n - i)$$，这些出边都是由$$deg$$贡献的

所以必要条件是，`SCC`是找到第一个满足$$\displaystyle \sum deg_i = \binom{i}{2} + i(n - i)$$
其中$$[1\sim i]$$构成了第一个`SCC`

> 再证充分性

不难发现，这个条件也是充分的，否则的话，假设说有一个$$j < i$$也满足$$\sum deg = \dfrac{j(j-1)}{2} + j(n - j)$$
其中有$$j(n - j)$$的贡献，说明了什么？

说明`j`和`[j+1...i]`**不能合并**，只能是$$j$$中选一个点，$$n - j$$中选一个点
这个和$$j, i$$属于同一个连通分量是矛盾的

> 更优的做法

还需要`n`次询问，确定每一个点的出度，然后从大到小排序，求`deg`的前缀和`sumdeg`
找到第一个满足$$\sum = \dfrac{i(i-1)}{2} + i(n - i)$$的点$$i$$，输出$$[1\sim i]$$即可

### F
**[F. Xorcerer's Stones](https://codeforces.com/contest/1779/problem/F)**
**问题描述**
给定一个有根树，`1`是根，节点$$i$$有$$a_i$$个石头，每次操作如下
选择一个节点$$i$$，计算$$i$$所有的子树节点$$j$$（包括$$i$$）的 xor 和$$x$$
然后将所有属于$$i$$的子树的节点$$j$$，令$$a_j \leftarrow x$$

最多可以执行$$2n$$次操作，他想要把树上所有节点的$$i$$都有$$a_i = 0$$，请给出方案
不存在输出`-1`，否则输出长度为$$q$$的序列，`ans[i]`表示第`i`次操作，处理`v = ans[i]`及其子树

**算法分析**
根据数据范围，$$a_i \leqslant 31$$，不难发现可以设计状态$$dp(u, val) = 0/1$$
表示当前节点$$u$$，考虑以`u`为根的子树，其 xor 和为`val`，状态是否合法

考虑$$u$$及其子树，如果$$|u|$$（表示子树大小）是**偶数**，那么一定可以
可以考虑**自底向上**选择，假设说选择$$(a, b)$$，`b`是叶子
可以通过一次操作，把$$(a, b) \to (a \oplus b, a \oplus b)$$，这样下来子树中所有节点的权值，
都变成了$$\bigoplus_v a_v$$，再一次操作，即可把子树所有节点都变成`0`，而变成`0`就意味着把这些点都删掉

如果存在$$sz(u)$$是偶数的点，就可以这样操作把子树删掉

状态转移并不难写，按照`u`的**每一个分支子树**作为 dp 阶段
```bash
dfs(u):
	for v : G[u]:
		auto ndp = array<int, 32>;
		for x = 0 to 31, y = 0 to 31
			ndp[x ^ y] |= (dp(u, x) & dp(v, y))
			
		dp = ndp
		
	if sz[u] 是偶数, dp[u][0] = 1
```

> 奇数呢？

奇数的情况，可以按照上面的方法`dp`，如果`dp[root][0] = 0`，那么就不合法

> 怎么输出方案？这是一个难点

考虑到$$n$$是奇数的时候，最后一步操作必然是针对根节点的，于是整个**操作过程中的状态**
差不多是$$dp(?, 0) \to dp(root, 0)$$

在第一步的时候，要记一下状态是从哪里转移过来的，比如$$\textbf{for } v \in G(u)$$
存在转移，$$|u| = v \cup |u|$$，即`v 和 u 及其已经考虑过的子树分支合并`
`dp(v)`维护了当前`v`所有可能合法的 xor 值，`pre(v)`维护`v 合并前`所有可能合法的 xor 值

一个合法的方案，xor 和`sum`的`dfs`状态，一定是从$$0 \to \cdots \to 0$$，考虑`dfs(u, sum)`
什么样的**中间状态**是合法的呢？

根据第一步的`dfs`过程，一个状态`sta`合法，考虑$$v \to u$$合并的过程
我们有$$pre(v, sta) \textbf{ and } dp(v, sta \oplus ?)$$，其中`?`表示`v`所有子树可能的合法 xor 和状态

那么输出方案，可以倒过来，因为终点状态`val = 0`是已知的，`dfs(u, val)`
考虑** 倒着 for **`u 的儿子`，尝试去找到一个合法的转移状态`?`，假设说考虑儿子$$v$$
注意到$$dp(u, oldsta), dp(v, ?)$$，我们有`oldsta ^ ? = val`

尝试确定`?`的值，最多就`31`个，令`? = can = 0`，那么`oldsta = val ^ can`
其中`oldsta`对应的就是`v 和 u 合并前，可能的异或和状态`
那么要求就是`dp(v, can) 合法，并且 pre(v, oldsta) 也合法`，如果不满足，就`can++`

这样继续下去，直到找到`val = 0, 并且 size(u) == 0`，那么把`ans.push_back(u)`，回溯回去即可

> 更进一步地理解

**观察一**
合法序列，如果我们操作了`x`使得`x 及其子树`合法，那么就不会操作`x 子树中任何节点了`
因为$$x$$已经合法了，此时一次操作，使得$$x$$子树所有点的权值都是`xorsum`
再操作任何子树中的节点，效果都是使得**其中偶数个点的子集**，它们的权值都是`0`

换句话说，如果操作`x`使得`x 及其子树权值都是 0`，可以把`x 及其子树删掉`

**观察二**
我们知道如果子树合法，那么可以把子树立刻删掉
基于此，操作序列，两两点对**不存在祖先关系，只有分支关系**
需要找到若干个，（1）子树大小为偶数的点，（2）并且两两之间只有分支关系，没有祖先关系

记$$i$$的子树的异或和为$$b_i = \bigoplus_j a_j$$，还必须满足$$(\bigoplus b) \oplus other = 0$$
注意到最后一次一定要对$$b_1$$进行操作，而`b[1] = 所有节点的 xorsum 和`
换句话说，$$other = b_1 \oplus (\bigoplus b)$$，考虑以下几种情况

（1）$$(\bigoplus b) \oplus b_1 \oplus (\bigoplus b) = b_1 = 0$$，也就是$$b_1 = 0$$
这种情况，只需要对`root = 1`进行一次操作就可以了

（2）或者就是$$other = 0$$，这种情况，要求$$(\bigoplus b) \oplus b_1 = 0$$
也就是说，我们选若干个分支，使得这些分支的$$\bigoplus b = b_1$$
这个时候最多只需要`2n`次操作即可
对每个子树分别操作（因为子树大小为偶数），可以将每个子树都删掉（点权变成`0`）
然后只有根节点有权值了，对根节点一次操作，把所有点的权值都变成`a[1]`
最后再对根节点操作，使得整棵树的权值变成`0`

> 具体实现

具体实现，输出方案的时候，实际上是找到权值从$$0 \to 0$$的一条路径
类似做一个**树上分支的前缀和**，记一下`sum = 树上前缀分支，所有节点的权值 xor 和`

当`dfs`发现`sum = 0`，并且`sz[u] 是偶数`的时候，说明`u`及其子树，是一个合法的分支
`ans.push_back(u)`，此时对应之前的分析，`other = 0`

整个`dfs`的过程，需要枚举当前`v`对应的，合法的$$b_v$$到底是多少？
根据第一次`dp`的结果，枚举`bv`，找到`dp(v, bv)`合法的状态，并且呢，还需要保证`v`能够作为分支被合并
这就需要`pre(v, ?)`，`? ^ bv == val`，换句话说，`? = (val ^ bv)`，即`pre(v, val ^ bv)`也要合法

之后呢，前缀和就变成了`val ^ bv`，`dfs(v, v ^ bv)`继续下去

#### 算法实现
```bash
void solve(int cas) {
    int n;
    cin >> n;

vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

vector<vector<int> > g(n+1);
    for (int i = 2; i <= n; i++) {
        int pi;
        cin >> pi;

g[i].emplace_back(pi);
        g[pi].emplace_back(i);
    }

vector<int> sz(n+1, 0);
    using arr = array<int, 32>;
    vector<arr> dp(n+1, array<int, 32>{}), pre(n+1, array<int, 32>{});

auto dfs = [&](auto &dfs, int u, int fa) -> void {
        sz[u] = 1;
        for (auto v : g[u]) {
            if (v == fa) continue;
            dfs(dfs, v, u);
            sz[u] += sz[v];
        }

dp[u][a[u]] = 1;

for (auto v : g[u]) {
            if (v == fa) continue;

arr ndp{};
            for (int x = 0; x < 32; x++) for (int y = 0; y < 32; y++) {
                ndp[x ^ y] |= dp[u][x] & dp[v][y];
            }

pre[v] = dp[u];
            dp[u] = ndp;
        }

if (sz[u] % 2 == 0) dp[u][0] = 1;
    };

dfs(dfs, 1, 0);
    if (dp[1][0] == 0) {
        cout << "-1\n";
        return;
    }

vector<int> ans;
    auto dfs2 = [&](auto &dfs2, int u, int fa, int val) -> void {
        if (val == 0 && sz[u] % 2 == 0) {
            ans.emplace_back(u);
            return;
        }

assert(dp[u][val]);
        for (auto v : g[u] | views::reverse) {
            if (v == fa) continue;

int sta = 0;
            while (!dp[v][sta] || !pre[v][val^sta]) sta += 1;

val ^= sta;
            dfs2(dfs2, v, u, sta);
        }

assert(val == a[u]);
    };

dfs2(dfs2, 1, 0, 0);

ans.emplace_back(1);
    cout << ans.size() << "\n";
    for (auto x : ans) cout << x << "\n";
}
```

## leetcode 戳印序列
**[戳印序列](https://leetcode.cn/problems/stamping-the-sequence/description/)**
给定两个串`stamp`和`target`，每个回合可以将`stamp`放在`target`上面，并且将对应位置的字符
替换成`stamp`上的相应字符，最多只能进行`10 * target.length`个回合
一开始序列是`length`个`? ? ... ?`，问最后能不能打印出`target`

**算法分析**
考虑倒着做，考虑从`[i, i+m-1]`这样一段，如果有**字符可以匹配**，比如`stamp[j] == target[i+j]`
那么这个位置可以还原成`?`，还原成`?`之后的位置，不能再继续`stamp`操作了

而`stamp[j] != target[i + j]`，即**不匹配的位置**，是可以重复去覆盖的，直到匹配，变成`?`
这样存在**覆盖的先后顺序**，可以考虑**拓扑排序**

假设当前考虑对`[i, i+m-1]`这个窗口进行操作
1）如果`stamp[j] != target[i + j]`，那么要还原回去，就需要**覆盖**，如果需要覆盖
那么之前的字符可以是任意的，**只要不能改成`?`的都可以**
所以考虑顺序，`[i+j 的窗口] --> [i 的窗口]`进行`stamp`，连边$$(i+j \to i)$$

2）否则呢？你通过对`i`进行`stamp`操作，可以将`target[i+j]`位置改成`?`
我们考虑每个位置的`deg[i]`，初始化，一开始`deg[i] = m`，表示有`m`个位置未经修改成`?`
如果`target[i+j] == stamp[j]`，说明可以将一个位置改出想要的`?`，`--deg[i]`
如果`--deg[i] == 0`，那么就说明，这个位置`i`可以一开始就被操作，将其进队列

然后就是进行拓扑排序的过程，值得注意的是，拓扑排序的时候
从`i`位置出发的所有边，**因为印章是可以覆盖的**，也就是说，$$(i \to j)$$
换句话说，$$j$$可以是任意的我们想要的字符，当然也可以是`stamp`中的任何位置的字符
也就是说，考虑完`i`之后，只要`i -> j`有边，就意味着`target[i+j] != stamp[j]`
换句话说，经过上一轮的操作，`target[i+j]`这个位置**改不出`?`**
而改不出`?`，就意味着这个位置可以替换成任意的字符，那么它是可以在接下来的过程中改成`?`的

> 这个问题的核心在于说，每一个位置的数，都必须由`stamp`中的字符提供
而一旦可以改出`?`，之后就不能动它了，没改成`?`的位置可以随便动，可以是任意字符
也就是说，这个位置可以在下一轮操作中，被还原成`?`

```bash
vector<int> ans, seen(n, 0);
while (que.size()) {
	auto i = que.front(); que.pop();
	ans.emplace_back(i);

for (int j = 0; j < m; j++) {
		auto u = i + j;
		if (seen[u]) continue;
		seen[u] = 1;
		
		// 如果 |g[u]| > 0，说明 u->v 有边，也就是说字符不匹配
		// 而不匹配的位置，v 可以是任何字符
		// 换句话说，这个位置一定可以在下一轮操作中，被还原成 ？
		
		for (auto v : g[u]) {
			if (--deg[v] == 0) que.push(v);
		}
	}
}
```

上一篇：九月算法竞赛选题（一）下一篇：九月算法竞赛选题（三）

看完文章有啥想法