IOI2020国家集训队作业试题乱做 Part 1

难度标签：$\color{red}\texttt{[HARD]}$，$\color{blue}\texttt{[NORMAL]}$，$\color{green}\texttt{[EASY]}$。

CF505E Mr. Kitayuta vs. Bamboos

$\color{green}\texttt{[EASY]}$

看到最大值最小，考虑二分答案。

二分一个最后高度的 $\max$，再考虑倒推。倒推则每次每个位置减少 $a_i$，然后你可以选择一些位置让他 $+p$。直接用堆贪心，取出将会最快被减到 $<0$ 的位置，$+p$。最后判断一下是不是每个位置都不低于初始高度 $h_i$ 即可。

时间复杂度 $\mathcal{O}((n+mk)\log n\log \text{maxv})$。

二分答案是十分套路的东西了，但是如果考虑正推的话，可能很难选择要给哪个位置 $-p$。若倒推，则遇到一个即将变为负数的位置，你不得不将其抬高。因此，有很多题目，你具有过多的选择权反而不是什么好事，可以考虑倒推等方法使得你的权力变小，只去做你不得不做的那些操作，反而可能更好地求解问题。

CF521D Shop

$\color{green}\texttt{[EASY]}$

十分显然的，操作顺序一定按照赋值->加法->乘法来进行，同时由于最后求乘积的最大值，所以乘法实际上是全局的。

考虑加法，对于一个位置，其加法一定按照从大到小地来加，那么可以把一个加法操作转变为乘法 $\times\dfrac{b_i}{a_i+\text{sum}}$，其中 $\text{sum}$ 是之前进行的加法操作的和。这样就将加法转变为乘法，因为无论怎么取，最后都可以把加法调整到最前面，然后使其最优。

考虑赋值，再将其转变为加法。显然的是，一个位置最多赋值一次，且一定在第一个执行。那么直接把赋值为 $b$ 转变为加 $b-a$，则转变为普通的加法操作。若最后没有选择到这个操作，则显然无影响；若选到了，只需要将其调整到最前面即可。

时间复杂度 $\mathcal{O}((n+k)\log n)$。

本题中有三种操作，首先需要发现前两个性质：操作顺序以及乘法的无序性。接着基于乘法的无序性，考虑将其他操作转变为乘法操作。这体现了一种化繁为简的思想，通过贪心策略等方法，将不同的操作转变为相同的操作，从而使得求解变得更简单。

CF512D Fox And Travelling

$\color{blue}\texttt{[NORMAL]}$

对于一个环，显然上面所有点都选不到。若两个环之间连接有一条路径，路径上的点也选不到。

那么删掉环和环之间的路径之后，图就会变成一个森林。森林中的树分为两类：有根树与无根树。其中有根树表示，这棵树中有一个节点连接着一个已经删除的点，这代表着只有这个节点的所有树上的儿子被删除了，这个节点才可以被删除（因为他连接的已经被删除的点已经占用了那一个可以不删除的节点）。无根树表示没有这样的限制，实际上就是这个联通块在原图中就是一棵树。

先考虑对于有根树的情形。考虑 $\text{dp}$。令这棵树的节点个数为 $s$，那么如果需要贡献一个长度为 $s$ 的选择序列，那么根必然是最后选择的。因此可以设计状态：$\text{dp}_{i,j}$ 表示在 $i$ 的子树中选择 $j$ 个节点的方案数。那么这就是一个树形背包，更确切的，这个背包类似一个 $\text{EGF}$ 的卷积，也就是乘了一个组合数。由于当前子树的根节点必然在所有节点都被选择了才可以被选择，所以 $\text{dp}_{\text{root},s}=\text{dp}_{\text{root},s-1}$。

再考虑无根树。考虑类似上述关于有根树的做法，由于在有根树中必然最后才能选择根节点，所以不妨直接暴力枚举一个点为根，然后进行上述 $\text{dp}$。同时，一个选择了 $c$ 个数字的合法序列会被计算 $s-c$ 次，也就是这棵树中任意未被选中的点为根，都将计算到这种方案，因此直接除掉即可。当然需要特判 $s=c$ 的情况，或者说认为 $0$ 的逆元为 $1$。

现在得到了每个联通块，每一种长度的序列个数。接着就是一个类似的带组合数的背包，组合一下即可。

时间复杂度 $\mathcal{O}(n^3)$。

本题关键在于发现环上节点、环之间路径上的节点无法被选择。这同样是一种方法简化图上边数——此处直接简化到树的形态，也就是根据题目要求的性质进行边数缩减，将图简化为树。因此本题同样可以先套路地思考树的情形，然后通过观察题目性质进行转化。

同时需要注意，原图中的树联通块与删除若干点之后得到的树联通块的区别。也就是关于上述是否有根的分类讨论。关于有根树与无根树之间的讨论，比较常见的方法是将无根树转化为有根树，其代价一般在于枚举根。同时关于有根树的根节点最后删除，需要一定的观察，同时根据这一性质设计 $\text{dp}$。

在得到有根树的解法之后，由于无根树可以较好地向有根树转化，因此应该朝着此方向设计做法。

CF516D Drazil and Morning Exercise

$\color{blue}\texttt{[NORMAL]}$

首先显然 $f_x$ 就是距离树两个直径的端点的距离的最大值。

考虑到 $q$ 只有 $50$，因此我们可以认为每次询问可以十分暴力。注意到题中需要保证求出的是一个联通块，因此考虑要如何才能只考虑联通块。

发现由于联通块的限制，答案要么包含直径中点，要么在直径中点的左侧/右侧。在和直径相关的问题中，可以考虑直径中点的一些性质：显然直径中点是 $f$ 值最小的点（之一）。考虑利用这个东西：不妨令直径中点为根，根据边权均为正，可以得到：若把 $f$ 看做节点的权值，那么若 $y$ 是 $x$ 的父亲，则 $f_y\le f_x$。

那么对于一个节点 $x$，其祖先的 $f$ 都不小于他自己的 $f_x$，因此可以二分向上跳，找到那个最远的，且与 $x$ 距离不超过给定的 $\text{lim}$ 的祖先。然后进行一个树上差分即可，也就是若这个祖先是 $a$，那么记录一个数组 $\text{sum}$，则 $\text{sum}_{x}\leftarrow 1$，$\text{sum}_{a}\leftarrow \text{sum}_{a}-1$。那么只需要同时维护 $\text{sum}$ 的子树和，然后对每个点的子树和取 $\max$ 即可。

时间复杂度 $\mathcal{O}(nq\log n)$。

本题是直径相关，且由于和距离的平衡相关，所以应该要想到直径的中点。然后根据上述的性质，考虑将直径中点作为树根，从而得到优秀的性质。考虑为什么我们会需要这个性质：由于需要求联通块，而如果联通块中两个点的 $f$ 跨度过大，这对我们可能是不够有利的，这会让我们不知道什么点应该选。

如果可以找到一种方法，给每一个点一个限制，表示要满足什么条件，这个点才可能被选择，那么问题就会变得简单很多。因此在本题中，这个限制的实现就是通过将直径中点变为根，使得 $f$ 随着深度不降，然后给予每一个点关于其祖先的限制，然后进行树上差分、子树和来求解问题。

所以本题同样可以看做，经过一些等价的变换之后，使得问题满足更多的限制。这和之前所做的一些 $\text{dp}$ 的状态顺序处理有着相似的思想。更广泛的，当一个问题过于自由的时候，往往容易无从下手，因此一个很好的方向是通过观察性质，变换其顺序、角度，从而使其具有更紧的限制，以求得更容易讨论的解法。

CF521E Cycling City

$\color{green}\texttt{[EASY]}$

画画图就可以发现，只要一个环上有一条弦，就必然可行，否则必然不可行。

直接考虑 $\text{DFS}$ 树，上面这个结论等价于存在一条树边被两条返祖边覆盖。那么对于一条返祖边，暴力向上跳来覆盖每一条树边，如果存在一条已经被覆盖过的，直接画画图输出答案即可。

看似很暴力，但是每条树边实际上最多被遍历 $2$ 次，所以时间复杂度 $\mathcal{O}(n+m)$。

本题中考虑到了解决图上问题的神仙方法：$\text{DFS}$ 树。在图上关于环的一些问题，转化到 $\text{DFS}$ 树上变为返祖边。仅有返祖边的性质使得我们可以快速地得到这些环，从而快速地计算这些相关的问题。

CF527E Data Center Drama

$\color{blue}\texttt{[NORMAL]}$

要求入度、出度都是偶数。关于度数不难想到欧拉回路。

因此，将所有边视作无向边，然后把度数为奇数的点之间连边。这样就得到了一张有欧拉回路的图。考虑找到欧拉回路，在欧拉回路上构造。实际上，只需要在欧拉回路上走，把边交替定向即可。即对于边 $x\rightarrow y\rightarrow z$，构造：

x to y
z to y

若边有奇数条，说明最后回到出发点的时候，出发点度数有问题。则在出发点上加一个自环即可。

简略证明一下正确性。首先由于入度出度都要是偶数，所以在奇数度数上的加边是加边最少的方案使得这个条件可能成立。接着对于是否需要加自环，发现只与加入奇数度数点之间的边之后的边的总数相关，因此也是无法避免的。因此这种构造方式是最小的。

需要注意的是，走欧拉回路的函数如果这么写：

void DFS(int x) {
    for(int i = e.head[x], to; i; i = e.nxt[i]) {
        if(vis[i]) continue;
        vis[i] = vis[i ^ 1] = true, to = e.to[i];
        DFS(to);
        if((++cnt) & 1) printf("%d %d\n", x, to);
        else printf("%d %d\n", to, x);
    }
}

复杂度可以卡到 $\mathcal{O}(nm)$，但是这么写：

void DFS(int x) {
    for(int &i = e.head[x], to; i; i = e.nxt[i]) {
        if(vis[i]) continue;
        vis[i] = vis[i ^ 1] = true, to = e.to[i];
        DFS(to);
        if((++cnt) & 1) printf("%d %d\n", x, to);
        else printf("%d %d\n", to, x);
    }
}

相当于在删除边，复杂度就是 $\mathcal{O}(m)$ 的了。

本题中第一步是根据度数与偶数之间的问题，联系到欧拉回路。本问题的形式与欧拉回路联系及其紧密，尤其是无向图欧拉回路。因此应该朝着这个方向考虑，从无向图欧拉回路，再转化为合法的定向问题。

CF506E Mr. Kitayuta's Gift

$\color{red}\texttt{[HARD]}$

首先考虑 $n+m$ 为偶数的情况，也就是最后字符串长度为偶数。有一个很慢的 $\text{dp}$：

考虑从字符串两侧，每次加入两个相同的字符以保证串一定回文，那么只需要 $s$ 是其子串。设 $f_{i,l,r}$ 表示在两侧分别填了 $i$ 个字符，已经尽量匹配了 $s$ 除了 $[l,r]$ 之外的所有位置的方案数。

设 $g_i$ 为在两侧分别填了 $i$ 个字符的时候，已经匹配了 $s$ 的所有位置的方案数。

那么：

• 若 $s_l=s_r$ 且 $r-l+1\le 2$：

$$ g_{i+1}\gets f_{i,l,r} $$

$$ f_{i+1,l,r}\gets f_{i,l,r}\times 25 $$

• 若 $s_l=s_r$ 且 $r-l+1>2$：

$$ f_{i+1,l+1,r-1}\gets f_{i,l,r} $$

$$ f_{i+1,l,r}\gets f_{i,l,r}\times 25 $$

• 若 $s_l\ne s_r$

$$ f_{i+1,l+1,r}\gets f_{i,l,r} $$

$$ f_{i+1,l,r-1}\gets f_{i,l,r} $$

$$ f_{i+1,l,r}\gets f_{i,l,r}\times 24 $$

• 对于 $g$：

$$ g_{i+1}\gets g_i\times 26 $$

这个东西直接矩阵快速幂优化完全跑不过。

仔细观察，如果我们把 $f_{i,l,r}$ 看做节点 $(i,l,r)$，那么实际上这个 $\text{dp}$ 转移是一个 $\text{DAG}$——或者说是一个有限状态自动机。目前点数有立方级别，考虑优化：

观察发现，如果我们把刚刚删除了左右各一个的点看做绿点，刚刚删除了左右中一个的点看做红点，那么有以下性质：

最后一个节点必然是绿点。
若一条路径中经过了 $x$ 个红点，那么经过 $\left\lceil\dfrac{|s|-x}{2}\right\rceil$ 个绿点。
路径的贡献只与红点、绿点个数有关。

那么可以只关心一条路径经过了多少红点、多少绿点，再算出有多少这样的路径，乘一下。

设 $h_{i,l,r}$ 表示从原点到 $(l,r)$ 对应节点中，经过 $i$ 个红点的路径条数，这个可以记忆化搜索。

接着考虑压缩上面那个自动机。发现只需要挂红点、绿点两条链，然后在适当的红点、绿点之间连边，点数就是 $\mathcal{O}(|s|)$ 的了。然后在这个上面矩阵快速幂就可以做到 $\mathcal{O}(|s|^3\log n)$。

考虑奇数。实际上就是最后一步走的绿点不能删去两个字符，只能删除一个，同时终点的自环要去掉。那么把图上这些地方的权值改成一定删去两个字符，然后再跑一边，减去即可。

时间复杂度 $\mathcal{O}(|s|^3\log n)$。

本题为我们提供了一个新的 $\text{dp}$ 优化方向：有时候我们的 $\text{dp}$ 中有很多状态的转移是十分类似的，同时由于需要保证没有后效性所以一般可以认为无环，那么不妨将其描述为一个自动机匹配的类似问题。

一定条件下，这种自动机上的走路问题可以用矩阵乘法优化，同时应该尽量考虑压缩自动机，使得保证其等价性的情况下让点数减下来。

CF547D Mike and Fish

$\color{green}\texttt{[EASY]}$

对于网格图，有两种建边成为二分图的方式：

• 黑白染色后建边。
• 将横坐标、纵坐标看做点，$(x,y)$ 就在横坐标 $x$ 的点，纵坐标 $y$ 的点之间连边。

第一种适合处理在网格上走路的问题，而第二种更适合处理网格上相交相关问题。

本题显然应该用第二种。

建立二分图后，考虑这个条件意味着什么。应该是给边染色，然后每个点连接的边中，两种颜色的边的条数差 $\le 1$。这让我们联想到之前集训队作业中一道题，可以考虑给边定向，然后让一个点的出度、入度之差 $\le 1$。

那么如果所有点度数都为偶数，那么一定存在欧拉回路，直接构造即可。

若存在度数为奇数的点，那么这样的点一定是偶数个。把他们全部连向虚点 $0$，这样就存在欧拉回路了。但是这样的话构造方案会出现一些问题——边不能交替染色，因为其中会经过一些实际上不存在的边。

对于一条边 $(a,b)$，我们按照边是从左部点连向右部点、从右部点连向左部点分类，连向 $0$ 的无所谓。然后按照这种方式染色就必然可行了。

$\text{trick}$：看到图上度数平衡相关构造问题，考虑欧拉回路。

CF547E Mike and Friends

$\color{green}\texttt{[EASY]}$

考虑建立 $\text{fail}$ 树。

把询问差分为两个前缀中出现次数的差。然后每次加入一个字符串的时候，将所有代表其前缀的节点处均 $+1$，然后查询时查询该串在 $\text{fail}$ 树上子树内 $\text{tag}$ 之和即可。

因为跳 $\text{trie}$ 边是在后缀删字符，跳 $\text{fail}$ 边是在前缀删字符，恰好可以找到所有子串。

求子树和，树状数组即可。时间复杂度 $\mathcal{O}((\sum |S|+q)\log \sum |S|)$。

本题使用了两个十分常见的套路，但还是总结一下：

• 子串 $\iff$ 前缀的后缀。因此在自动机上，结合匹配边和失配边来找子串是十分有效的。
• 对于带有可减性的区间询问，若没有快速求解的方法，考虑差分，然后转化为只需要求前缀的情况。

CF526G Spiders Evil Plan

$\color{red}\texttt{[HARD]}$

考虑如果没有强制要求经过点 $x$，可以怎么做。

发现我们选择的路径必然是一些叶子到叶子，可以证明，可以通过 $k$ 条路径覆盖一棵有 $2k$ 个叶子的树，大概思路就是进行调整，如果存在两条路径不相交，则调整为相交。

对于一个询问，总存在一种合法情况，使得其包括直径两个端点中至少一个。那么可以把直径两端分别看做根，然后求解取 $\max$。那么现在在一棵树中，我们就只能选择 $2k-1$ 个叶子了（根也是叶子），并且要使得这 $2k-1$ 个叶子和根联通，并使边权最大。

这就是在树上选择带边权的前 $2k-1$ 条长链，因为一条长链会添加一个叶子，且一条长链顶端节点的父亲所在的长链一定比当前长链优，所以是等价的。

那么考虑求出所有长链，然后匹配一下。如果 $x$ 已经在选择的前 $2y-1$ 条长链中了，那么直接输出即可，否则需要调整。

具体来说，有两种调整方式：

• 把最后加入的长链删除，加入当前长链（从 $x$ 向下的长链和 $x$ 向上直到一条已经被选的长链）。
• 找到 $x$ 上方第一条被选的长链，然后把这条长链修改到 $x$ 的方向来。

这可以树上倍增，时间复杂度 $\mathcal{O}((n+q)\log n)$。

本题着重考察了对于树上各种性质的综合运用。首先，又是通过树的直径的性质，将询问中以不同的 $x$ 作为根转变为以直径端点为根。接着又通过把“连接叶子和根”与“匹配最优的长链”进行连接，那么就可以很快地选择出匹配的长链来。最后再考虑对于不同的 $x$，要如何修改当前方案。

因此，对于一类题目，其中某一个限制特别不好考虑（例如本题的 $x$ 可能需要换根），可以先考虑全局、无限制的情况，然后再通过题目性质来从全局最优解进行调整。