2022 暑期集训补题题解【简版】

又是无休止的坐牢和自我批判。

Training 1

B

题意：

选一个点染色，然后自动把所有跳了一格子的点染色，问能否把整个图染色完。

思路：

对于一个连通图，只要有两个点之前存在一条偶数长路径和一条奇数长路径，即可把整个图染色。
这个可以用黑白染色法进行判断，如果一个点即是0又是1即可。

然后无向图求一下连通块个数，把他们之间加一条边即可。

D

题意：

将一个环分为若干区域，区域内进行或运算，区域外与运算，求结果最大值。

思路：

提到位运算优先考虑按位贪心，异或考虑线性基啥的。
破环成链，贪心地找最小的、使当前位凑出1的区域，看划分出这些区域的数量能否 >=2k-1
（切多了没事，可以合并，反正是或运算）
之所以2k-1，是你想，环的话你要凑k段，双倍环你要凑2k段，破环成链了你至少要切2k-1刀.

F

题意：

找一对最小的（A,B），使存在{A,B,A,B}的子序列

思路：

应该先固定一个元素，再找另一个元素，时间复杂度O(nlogn)
我们预处理出每一位的下一个元素出现的位置nex，然后就这样枚举B…B的区间。
然后就是求区间最小值，把它当成A更新答案就行。

重要的是维护这棵线段树时，每经过一个点，就把这个点的nex处插到线段树里，
这样可以保证在线段树搜到点，前面肯定也出现了。

K

题意：

太长了不写。

思路：

就是你看到了一个周期啥的，应该想想分层图。

然后主要就是建图，按时间节点建k层，每层有n个节点，连边的话你就往下一时间点连边，如果是第n层就循环往第一层连边。

超源连所有的起始点，超汇连所有时间节点的n号节点。跑dinic就行。

Training 2

A

题意：

两条线从上往下扫，看两者一共能截取多少给定区间。

思路：

典中典之控制变量，先O(n)枚举一条线在不同点上能截多少区间，再想个方法在O(logn)中找到另一条线应该的位置。

暴力的想法就是枚举的时候被截到的区间就扔了，离开之后再加回来，可以用线段树维护，维护区间最大值，支持区间+/-1。

离散化之后可以开个桶，在每个区间的端点处丢入区间的编号，起始点区间-1，终点+1；

K

题意：

给你若干个猜灯组合，让你调整n个灯的0/1状态使得每个组合至多错一个。

思路：

每个灯就两状态，妥妥 2-sat。
一个组合若某个猜测是错误的，可推得其他两个必然是对的。就这样建个图跑缩点即可。

Training 3

是之前打过的比赛，笑啦。

Training 4

在长沙摸鱼。

Training 5

B

题意

该公司有n名员工和k个团队。该公司雇佣了一辆班车，这辆班车将会往返多次承载员工去参加宴会，每一次可以承载1个团队或者2个团队。 这辆车可以承载s个员工，s可以为任意选定值，假设通过r次运输所有的员工都到达宴会，计算 r∗s 的最小值。

分析

根据贪心策略，$a_1$ 配 $a_n$ 比较优秀，这样枚举 S ；

给定 S，问如何安排使得 r 最小。本来想着对于 a_r 用二分找另一个队来匹配，但后来发现尺取法就行了。给定 S 对于两边都是单调的。

C

题意

您估计了一下自己每天必然要花费 k 元食宿费。共有 n 份工作，每份工作从 L_i 工作到 r_i 天，可获得报酬 p_i 元。 选定 L, R 区间使得 $p=\sum_{s \in S}p_s - k*(R-L+1)$ 最大。

分析：

典中典之控制变量。 枚举结束节点 R，考虑一个最优的 L 使得 p 最大。

维护一个线段树，食宿费每天在 [1,i] 区间加 -k ; 如果某个工作 r_i < i，则在 [1,l_i] 区间加上 p_i（因为当 L 选在这上面时候工作才会产生贡献）。

然后跑就行了，线段树还得多维护一个取到最小值的位置信息，但也还挺好写。

E

题意

对于每一组测试样例，会给你 n 个长为 m 的 01 组成的字符串，和一个整数 k。

我们规定两个字符串是相似的，当且仅当两者有 k 个或以上的位置值对应相同。你可以将一些字符串翻转，使得所有字符串两两相似。请求出最少的翻转字符串的数量，并输出翻转的字符串的编号。

分析

将 当前串是否翻转 作为图上节点，套 2-sat 连边跑就完事了。

连边依据以下策略：

• 两个本来就能匹配，反转后不能匹配了，则 i -> j
• 两个本来不能匹配，翻转后能匹配，则 i -> j+n
• 两个本来不能匹配，反转后也不能匹配，则 i -> n+i（无解）

建的是双向边。最后求的是最少翻转字符串数量，首先你建的图里边肯定有若干个支，每个支表示一套操作策略。即如果 $A\in V_1$ 反转了，那 $B\in V_1$ 也要反转。

为了让反转次数最小，我们在缩点的时候就维护一个支里边反转节点（即 i+n）的数量 size，在最后判断答案时，如果反转 A 所在支的 size 小于不反转支的 size，那么就把 A 反了并把这个支打上标记，之后把同一个支里面的反转节点也都反了。就是这么一个贪心，感觉有问题但还是过了居然。

Training 6

这场摆烂。

Training 7（Nowcoder）

J

题意

有一张 n 个点 m 条边的无重边无自环的有向图，初始时可以选择一个点染黑；若某个点所有入边的起点均为黑点，则该点可以被染黑，最大化图中黑点数量。

分析

开始想着上拓扑，但是拓扑肯定得在 DAG 上啊于是还套了缩点。无端把问题变复杂。

马同学说的好，你就直接对每一个没搜到的点 BFS 就行了，题解里证明了每个点最后得到的染色点集合是一个树，且树两两不想交。

怕的是他构造数据来卡你。但我们把所有点打乱（随机化），时间复杂度是 O(nlgn) 的就可以直接过了。这个想法很简单，代码也很好写。

Training 8（HDU）

C.

题意

有一个容量为 m 的背包。有 n 个物品，第 i 个物品的体积为 vi，价值为 wi。

找到一种方案，恰好装满大小为 m 的背包，且价值的 异或和 最大。若找不到恰好装满大小为 m 的背包，则输出 -1。

分析

猜到了 DP 两维分别是异或和与背包容量，但是明显 N^3 会寄就扔了这个 idea.

结果最后把背包容量那维度压到 bitset 里面就过了。。bitset[i] 对应的是背包容量为 i 是否能够达到。

那么，j-v[i] 在 bitset 里面就代表了 j<<v[i]。

Training 9（HDU）

A

题意

一棵树给你三个点集A,B,C，问点集D使得存在点 x,y 属于 A,B ，可以到达C中某个点。

分析

找出 A,B 向上可到达的所有点（链），C 向下可到达的所有点，求一个并即可。

最恶心人的居然是每次询问后的初始化，一开始想的把所有加进去的边在删掉，但可能有pushdown的没删；后来还得在求答案时候顺手删了才不会超时。。。

H

题意

给你一个字符串 s 和若干次操作 (ch, x) 得到的字符串 t，表示 ch 连续打 x 次，若 ch='-' 则连续删 x 次，问能否有某一时刻 t 中包含 s 的子串。

分析

字符串匹配优先还是可以考虑 hash 的，这题骚操作挺多但是字符串哈希还是 yyds.

以相同字符为一个块，加一连串字符可以视作一个等比数列，直接加到块儿的贡献里。

删除字符和匹配可以通过二分找到对应的起始块儿，然后把三个部分（起始块儿，中间那段和最后部分块儿）加起来，算算 hash 值（得动动脑子

Training 10（Nowcoder）

SPFA 判环坐大牢，请认准如下代码：

还得注意精度问题。

bool spfa(long double wei)
{
    queue<int> q;
    for (int i=1;i<=n;i++) q.push(i), v[i]=1, d[i]=1, cnt[i] = 0;
    while (!q.empty()) {
        int k = q.front();
        q.pop(), v[k] = 0;
        for (int u: g[k]) {
            if (eps < d[k]*wei*w[k][u] - d[u]) {
                d[u] = d[k]*wei*w[k][u];
                cnt[u] = cnt[k]+1;
                if(cnt[u] >= n) return 0;
                if (!v[u]) {
                    q.push(u), v[u]=1;
                }
            }
        }
    }
    return 1;
}

Training 11（Nowcoder）

F

题意：

给你一个无向图并在上面选 2 个点 x 和 y，让你构造一个数组，第一个元素是 x、最后一个是 y。中间插入其他所有的点；使得这个构造的数组对于任意 k <=n，前 k 个 x 连通，后 n-k 个也连通。

分析：

易知点双是两两互达的，怎么划分都没事；点双缩点之后会形成一个树，任何度为 1 超过 3 个节点的树都是不行的。大概思路就是先缩个点双，然后判断是不是链。

但也有一个割点属于两个点双的情况，这种要特判 x, y 不是割点才行。

H：

题意：

给出长度为n的小写字符串 A 和k个长度为m的小写字符串 $B_i$ ，$B_i$ 的每个位置拥有统一的权值 $v_i$，对于每个 $B_i$ 求最大和区间满足该区间构成的字符串是 A 的子串（空区间合法）

分析：

先给 A 建一个 SAM，对于每个 $B_i$ 从左往右地固定右端点 $r_i$，找出以 $r_i$ 结束的最长子串（这个可以直接在 SAM 上 $O(n)$ 的跑出来，SAM 你好强大！）。对于该最长子串的每一个后缀也是 A 的子串，于是维护一个 ST 表求最大子段和即可（即 $sum_{r_i} - \min_{i\in(l,r)}\left \{sum_i\right\}$。)

Training 12（HDU）

这场坐牢，签到没过。

Training 13（HDU）

B 题分析：

先 dij 求出最短路上的边集，建好图后在上面跑最长路。

注意到边权可以为 0，于是可能有 0 环，缩个点就是 DAG，跑个拓扑 DP 就行了。

一直 MLE，可能是 kosaraju 炸空间了。

Training 14（Nowcoder）

A

题意：

从 n 个任务中选 m 个 $(a_1,a_2,......,a_m)$ 并任意排列，收益是 $\sum_{i=1}^m w_{a_i} \prod _{j=0}^{i-1} p_{a_j}$，求最大收益。

分析：

考试都没时间想，调签到题去了，应该把签到扔了来想想这题。这题之前做过的，甚至还写过题解。

他说你选 m 个数后任意排列，那我们先找一种排列方式，使得任意取一个子序列，他都是满足最大收益。假设交换其中任意两位置的元素（下标 x, y）导致的收益变化是 $R_x-R_y$，算一算可知：

$R_x-R_y = (w_{a_x}-w_{a_x}*p_{a_y}) - (w_{a_y}-w_{a_y}*p_{a_y}) \ge 0$

此时满足最优解，我们把这个当做排序的 cmp 即可，然后上 DP 求一个最大子序列和。我超，这么简单的题我居然没去想。

哦，貌似不是严格的最大子序列和，由于之前的元素会产生贡献，还得倒着求。

Training 15（Nowcoder）

考试出大锅，摆了。
其实 A 题也能写，但还是摆了。

Training 16（HDU）

好像没啥能补的，还得学 NTT 摆了。

Training 17（HDU）

王炸，以后在写 hash 我是狗。
费马小定理求逆元的常数很大，不可忽略！！

另一个签到题是按编号从大到小排序后求生成树，没想到，我是个寄吧。

Training 18（Nowcoder）

这次比赛居然没坐牢。

C

题意：

求给定图边集的所有子集的最小生成森林边权和之和。

分析：

注意是边集而非点集，虽然都不会写。

考虑每一条边在多少个边子集中产生贡献。 根据 Kruskal 算法的思想按大小把边排序，这样一条边 (u,v) 在某个边子集产生贡献当且仅当 u 和 v 不能通过较小边连通。令 $S_1$ 为所有边集的集合，那么为了计算这条边造成的贡献，我们先只需考虑在 $S_1 / T$ 边集的集合中所造成贡献即可，T 是包含了较小边使 u, v 连通的边集集合。

其中，边分为比它小和比它大两种，比它大的边可以任取而不影响 u, v 的连通性；而对于比他小的边外加上 (u,v) 可形成一个连通块 S，我们将 (u1, v1) 分成三类：

• u1, v1 都在 S 之外的边：可以任取，贡献是 2 的幂；

• u1 或 v1 中一个点在 S 的边：必须不取（否则是至少包含一个其他顶点的连通块），贡献 1；

• 对于u1, v1都在 S 内的边：需要取出一些边满足能让 S 连通即可，贡献设为 f[S]；

可以维护一个状压 DP ，枚举其中的所有点集 T 合并转移即可。

Training 19（Nowcoder）

K

题意：

给 n 堆石子，两人轮流进行以下操作：

• 从非空石子堆中取出若干石子
• 要么保持不变，要么将两堆非空石子堆合并

给定若干询问区间，问该区间内使得先手必胜的子区间个数？

分析：

博弈论如果推不出来可以打表。 结论就是奇数堆石子先手必胜，偶数堆的 $a_i-1$ 异或和不为 0 先手必胜。可以归纳假设证明，但感觉不如打表》》》

等价于询问是否存在偶数段子区间，使得异或和为0（或两端点的前缀异或和相同）。问题很古怪又看到询问可以离线，考虑用莫队做。分奇偶维护各端点的前缀异或和，把他们丢进桶里，套一个莫队就行。

Training 20（HDU）

笑死了，博弈论打表打出来了。

B

题意：

给一个图有n个点，每个点都有权值，图初始是由三个顶点组成1 , 2 , 3 和三个边( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 1 ) 组成的一个三元环，之后会再给出 n − 3 行，每行给出两个点u ， v 表示连接$( i + 3 , u )$ 和 $( i + 3 , v )$ 的两条边。让你将这个图分成一个独立集，其他点构成森林，且独立集中顶点的权值之后最大。

分析：

考试时候被唬住了，概念啥的都知道但就是被唬住了。事后分析，可能是对这些名字有一种无名的敬畏感，导致分析时候大闹宕机，挺sb的。

图中每个点都形成至少一个三元组，那么显然在独立集中选择一个点后，其链接的省下若干点对都是不能选的，否则不构成独立集；若存在一个三元组，其中一个点都不选，那就成环了、破坏树形结构。综上，每个三元组都必须选出一个点放进独立集中。

其实这个图进行三染色后，染色方案是确定的，找个权值最大的就行了。

Training 21（HDU）

签到题小细节没注意，导致罚时爆炸从而在手速场垫底的我真是千古罪人。

E

题意：

给出n个城市，这些城市排成一条长链，相邻两城市间有边权bi，每个城市有一个点权ai，当处在一个城市时可以将ai的质因子装入背包，当要经过具有边权bi的边时必须背包中存在bi，背包中的质因子不会被消耗，之后有q组询问，每次询问给出起点和终点，问能否从起点走到终点。

分析：

考场想了能不能把询问离线处理之类的做法，想过一秒的预处理全部但没有深入。

我们设 $l_i,r_i$ 为 i 号城市左右可扩展的最大范围。先倒着搜一遍初，始化出从 i 走向 i+1 的 $r_i$ 。

再正着搜，如果 i+1 和 i 可互达，那么两点有共同范围；否则就用数组维护第 i 条边的质数出现的范围，二分判定是否合法，暴力的跳就完事儿了。。。

暴力跳的代码如下，以后大模拟可供参考：

bool check(int _p, int l, int r) // 当前检测 _p 是否出现，范围 [l,r]
{
    auto pos = lower_bound(pri[_p].begin(), pri[_p].end(), l);
    if (pos == pri[_p].end()) return 0;
    else return (*pos <= r);
}

while (1) {  // 暴力的向左右扩展，但均摊O(n)
    bool flag = 1;
    for (int j=l[i]-1;j>=1;j--) 
        if (check(b[j],l[i],r[i])) { j=l[j], l[i]=j, flag=0; }
        else break;
    for (int j=r[i]+1;j<=n;j++) 
        if (check(b[j-1],l[i],r[i])) { j=r[j], r[i]=j, flag=0; }
        else break;
    if (flag) break;  // 无法扩展时退出
}

G

题意：

给定若干个点，每个点的点权是 n 排列 $p_i$ 的值。连接 i,j 点的代价是 $|j-i|*|p_j-p_i|$ ，问这些点的最小生成树。

分析：

如果把所有边列出来排序，那数量级是 $O(n^2)$ 的，因此考虑通过压缩生成树的边权上限来对边进行筛选。注意到边权 $p_i$ 是一个n排列，如果我们顺着连成一条链的话，那这棵树的最大边权是小于 n 的，因此只需要保证 $|j-i|$ 或 $|p_j-p_i|$ 小于 $\sqrt n$ 就行了。

对于 Kruskal 算法也有一个限制，如果用快排的话会多一个 log，又注意到数组范围不大，因此直接用桶排即可，恁强啊。

Training 22（Nowcoder）

签到题坐牢，我真™是个铸币。

没啥意思了。

Training 23（Nowcoder）

E

题意：

构造一个 n 的排列，使其恰好有 m 个不同的最长上升子序列。

分析：

考场想到了做二进制拆分，但拆的方向好像不太对。

考试的想法是通过 2 1 , 4 3 ... 的方式构造 $2^{p_i}$ ，再通过 将高进制位向前放 来运用加法原理。但为了维持 LIS 的长度相同，还得使得不同进制位构造出来的子序列长度一致。

比如对于 $m=5=(101)_2$，就是 (5, 6) , (2 1, 4 3) , 7 ： 前面是那个 001，后头是 100.

但这样构造，如果 1 的数量很多的话长度就会炸。题解给的想法如下：

• 先确定最高位 $k$，构造 $2,1,4,3...,2k,2k-1$.

• 对于每一个二进制位是 1 的地方，往后插一个大于 $2k$ 的序列 $p_i$，从而实现加法原理；

• 同时，为了保证 LIS 长度是 $k+1$， 在每一个 $p_i$ 后边插入 m 的二进制表示下第 i 位往上连续0的个数。重新调整 $p_i$ 的大小即可。

比如对于 $m=101=(0110 0101)_2$，只需构造（保证 LIS 长度为 k+1）

$13, 14,(2~1, 4~3) ~15, 16, 17, (6~5, 8~7, 10~9),18, (12~11), 19$

这样构造就很短了。

Training 24（HDU）

G (07)

今日比赛我开的两题被畅联杀疯了，睿宁最后攻速提交流过了 03，只有我最后摸了一手鱼。

题意：

题目描述. 有𝑛个套娃，大小为 $a_1 ≤ a_2 ≤ ... ≤ 𝑎_𝑛$，现在要将这些套娃分成 𝑘 组，每组套娃按 照大小排序后相邻两个套娃之间的大小差距要求大于 r，求方案数。

分析：

开头就想到 DP，设 $f[n][k]$ 为前 n 个分成 k 份的方案数，转移方程即为：

$f[n][k] = f[n-1][k-1] + f[n-1][k]*\phi(n,k)$

前者指第 n 个数单独分成一组，后者指放在已有的 k 队里，$\phi(n,k)$ 表示第 n 个可以放的堆数。

考试自己想的时候在 $\phi(n,k)$ 这里卡了半天，畅联是这样构造的：考虑对于有多少个 $a_j$ 是和 $a_i$ 套不起来的，那他们互相肯定也套不起来（因为间隔肯定也是小于 r），因此他们的划分肯定是相互独立的。于是维护可以套进去的边界 pos，则 $\phi(n,k) = k - (n-pos).$

H

题意：

给定 𝑛 个点的完全图，两个点之间距离为它们的 $gcd$，𝑞 次询问两个点之间的最短路以及方案数。

分析：

首先题目显然可以转化成：对于给定的 $u,v$ 求 1~n 范围内与二者都互质的个数。

一开始还以为是欧拉函数，但欧拉函数是求小于自身与其互质的个数，因此得用质因数分解+容斥。特别地，对于两个数 $u,v$ 只需把他们质因数的并集丢进去就行了。

在 $n\leq 10^9$ 范围内，质因数的数量是不超过 12 个的 ？因此可以用状压这类的方法进行一个容斥过程：奇数个就加 n/cur，偶数个就减 n/cur. 如果是按位枚举常数会很大，用 lowbit 加速一下就可以了。

有机会可以补一下加赛的字符串

Training 24（HDU）

没印象了，好像也是坐牢场。

A

题意：

n 个队打比赛，分最高的共同获胜。问一号队伍有无赢的可能性？

分析：

首先一号的比赛都得赢，只需要其他队伍使得均摊胜负最大化就有机会赢。感觉像是一个最大流/最大匹配问题，一开始还不敢写，结果畅联翻到原题了））

扔掉一号队伍及其比赛，把其他所有队伍向各自的比赛连流量为 两队比赛场次 的边，超源向队伍连流量为 一号队伍胜利场次 - 各队伍已胜利场次 的边，比赛向超汇连流量为 比赛场次 的边。如果最大流量等于所有比赛数量之和，则存在一个方案，输出 YES。

Training 25（Nowcoder）

**最后一次是校内第四。**再见了，所有的多校比赛。

A

题意：

定义 $f(s)$ 表示 s 所有的循环周期之和。求 s 所有子串的 $f(s)$ 之和。

考虑所有的循环区间 $i$，并把整个字符串分割成长度为 i 的段落。可以想象得到，中间一定有若干段是一模一样的，比如（k=3）：xxa | bca | bca | bcx . 但也注意到前后会有多余的段落会拼接上去，组成一个大的循环节。

如此，我们考虑对于每一个段落可以向前后扩展的范围：这个可以利用后缀数组求得 LCP（最长公共前缀）以及 LCS（最长公共后缀）。这至多可以扩出来一个循环两次的，把这个向前连接看能接多远，可以用线段树维护。

总结：

暑假结束了，比赛也结束了。过程中想了很多事，每每比赛时坐牢亦或是考完试看到垫底的排名总会自我怀疑：打这么多比赛也没啥进步的感觉，看样子估计铁进不了前十，那做这些的事情的意义是什么？

有一个我高中安慰到现在的借口：我所做的事情都是人生之动态规划转移的必要，短期的失利在长期一定会转化成更高的利益，所以不必担心——我如是安慰自己。

如今我也不得不开始反思：我的回报是否值得我在上面花费的时间？我的努力是否能弥补天赋的缺失？我是否能用这些时间做更有意思的事？

虽然但是，在想明白这些问题之前，我打算再犯一会儿蠢 — — 应该至少还能允许我犯一个学期吧。