2023-12-13 23:10 已编辑成都信息工程大学技术美术发布于四川

关注

题解 | #欢迎来到算法世界#

第十届CUIT - ACM程序设计竞赛 - 题解

本题解为官方题解，题号按照现场赛写的。

注意同步赛与现场赛的题号、顺序不一样。

[TOC]

$1.$ 标签预览

$A$ 怎么走啊（拓扑 $\$ 缩边 $\$ $Dijkstra$ ）

$B$ 我来组成头部（构造）

$C$ 欢迎来到算法世界（签到）

$D$ 娇の礼帽（思维 $\$ 策略）

$E$ 区间异或（前缀异或 $\$ 排序）

$F$ 不存在的子串（二维数点：树状数组）

$G$ 三人成行（排序）

$H$ 若你来到南京是否想起我的梧桐（离散化 $\$ 线段树优化 $DP$ ）

$I$ 参加算法竞赛（二分优化 $LIS$ ）

$J$ 我上面有人儿（并查集）

$K$ 这是回文吗（贪心 $\$ 哈希）

$L$ 更待西湖彻底干此间应有再生缘 （思维 $\$ 策略）

预期难度定位： 简单 $BCDGJL$ ，中档 $EIK$ ，较难 $AFH$ 。

现场赛排行榜效果： 简单 $CGLDJ$ ，过度 $B$ ，中档 $I$ ，中难 $KE$ ，较难 $AFH$ 。

下文按照现场赛排行榜效果排序。

$2.$ 思路讲解：

$C$ 欢迎来到算法世界

输出即可，注意转义。

$G$ 三人成行

发现排序后直接三人一组即可使得差异最小。

简易理解：

一个组内差异是最大减最小，我们将其描述为一条线段，就有（意会一下）

alt

$L$ 更待西湖彻底干此间应有再生缘

答案 $n-1$ 次。

首先因为一个人不可能抱自己和伴侣，所以次数只可能为 $[0,2n-2]$ ；

其次除开小林的 $2n-1$ 人又各不相同，那只能是 $[0,2n-2]$ ；

我们考虑某人抱了 $2n-2$ 次，那么意味着他抱了除开他和伴侣之外所有人，所以被抱的人已经至少算一次了， 那么 $0$ 次的人只能是 $2n-2$ 次的人的伴侣。

把 $n$ 对情侣画出来（此时并不知道小林小雅是哪一对），先把 $2n-2$ 次的写最边上。

又从剩余的最大值 $2n-3$ 来考虑，同理可得他与 $1$ 次的人为情侣。

以此类推，发现最后一对情侣次数相同，都是 $n-1$ 次。

又因为题设除开小林其他人都不一样，那小林只能是最后一对之一，所以其伴侣小雅自然也是 $n-1$ 。

alt

$D$ 娇の礼帽

答案 $n-0.5$ 。

每个人帽子只有黑白两种可能，我们令白色为 $0$ ，黑色为 $1$ ，令第 $i$ 个人帽子颜色是 $a_i$ 。

我们策划回答顺序为 $n->1$ 倒着来，第 $n$ 个人最先回答 $[1,n-1]$ 的颜色异或值，简单记为 $F(n-1)$ 。

那么第 $n-1$ 个人可以看到前 $n-2$ 人，得到前面的异或值 $F(n-2)$ ，由于他听到了 $n$ 号曝出的 $F(n-1)$ ，所以第 $n-1$ 就知道自己头上就是 $F(n-1) \bigoplus F(n-2)$ 。

同理，第 $n-2$ 看得到 $F(n-3)$ ，又已经听到了 $F(n-1)$ 和 $a_{n-1}$ , 可以得到 $a_{n-2}=F(n-1) \bigoplus a_{n-1} \bigoplus F(n-3)$ 。

其他人以此类推，所以这种方案只有第 $n$ 个人 $50%$ 概率答对，其他 $n-1$ 人必对，则期望为 $100\%*(n-1) 50\%*1=n-0.5$ 。

$J$ 我上面有人儿

并查集模板，出此题是教学意义。

使用题面的伪代码可以查询到老大，只需要开个数组记录老大名下的人数，遍历每个人，查询其老大，然后给老大的计数加一。

再重新遍历每个人，查询其老大，然后输出老大对应的名下人数即可。

另外，并查集可以用 $while$ 循环写法，就不需要担心递归深度了。

还有“路径压缩”技巧，即在找老大的过程中把路径上所有人的“领导”都直接修改成老大，那么下次查询的路径长度就只有 $1$ 了，这样更快。

$B$ 我来组成头部

构造题答案不唯一，题解做法是 $(\lfloor \frac{1}{n} \rfloor (n-1))*2-(n-2)$ 。

$I$ 参加算法竞赛

观察发现，选出来的序列可以理解成两个上升子序列(简称 $LIS$ )拼起来的。

可以做一遍1到n的最长上升子序列 $f_1[]$ ，再做一遍 $n$ 到 $1$ 的最长下降子序列 $f_2[]$ ；

然后枚举 $[1,n]$ 作为拼接点，用 $f_1[i] f_2[i]-1$ 更新答案即可。

注意到数据规模较大，所以求 $LIS$ 不能用 $n^2$ 做法，需要优化。

思考下标、 $LIS$ 长度、 $LIS$ 最后一个数字的值三者的两两映射关系。

我们想要的是下标 $->$ $LIS$ 长度，转移时是找其 $LIS$ 末尾值小于自己的最大 $LIS$ 长度；

第一种，也比较自然的优化是：遍历下标过程中维护映射 $LIS$ 末尾值 $->$ $LIS$ 长度，用树状数组做前缀最值查询。

第二种，也是 $std$ 写法的优化是：遍历下标过程中维护映射 $LIS$ 长度 $->$ $LIS$ 最小末尾值，这个数组显然有单调性，每次可以二分找到 $a_i$ 最多能接在多长的上升子序列末尾，即求出了以 $a_i$ 结尾的 $LIS$ 长度。

$K$ 这是回文吗

第一步贪心的想，先双指针从 $A$ 的头部和 $B$ 的尾部开始尽量选一个最长的前后缀满足两个拼起来是回文；

第二步假设两个指针最后停在 $i$ 和 $j$ 位置，现在再求出 $A$ 中以 $i$ 为起始的最长回文串，求出以 $j$ 为结尾的最长回文串，选两者更长的保留下来。

则答案就是双指针跑过的长度第二步保留的更长回文串长度。

其中第二步的实现是多样的；

第一种，可以用马拉车做预处理

第二种，也是 $std$ 的做法，可以预处理前后缀哈希，在枚举以i开始的所有字符串长度 $len$ 的过程中，用哈希对比字符串 $s[i,i \frac{len}{2}-1]$ 和 $s[i \frac{len 1}{2},i len-1]$ 即可。

第三种，回文自动机....（高手自便）

另外，第一步贪心的简易证明：

反证法，我们假设最优解在没有选满前后缀的地方，我们看如果强行选满会不会让答案更小；

如图，最优解如果在不选满的地方，再强行选满，这个过程一定满足 $a=反b，b=c$ ，则可以把 $c$ 补到 $b$ 的地方，此时答案和选满的答案是一样的，所以选满并不会使得解变得比最优解小，即贪心选满前后缀可以得到最优解之一。

alt

$E$ 区间异或

首先考虑 $k=0$ 的情况，小于 $2^0=1$ ，即求异或值为 $0$ 的区间个数。

先做前缀异或，显然前缀异或值相同的两个位置所成区间异或值为 $0$ ；

于是只需要对前缀异或相同的值计数，两两配对的组合数为 $\frac{cnt(cnt-1)}{2}$ ，累加组合数则为答案。

现在考虑 $k>0$ 的情况，其实只需要把所有数字右移 $k$ 位，就转换成了区间异或为 $0$ 的问题。

但若对每个 $k$ 单独处理前缀异或再用 $map$ 计数是 $nlog^2n$ 的复杂度，不足以通过本题，需要考虑优化。

第一种，很自然的做法是手写写哈希表计数，写得好就能过本题。

第二种，用字典树储存前缀异或的所有值，遍历过程中累加答案，深度对应 $k$ ，子树叶子个数对应 $cnt$ ，做到 $nlogW$ 预处理， $O(1)$ 询问。

第三种，也是 $std$ 的做法，只需要把前缀异或排序，用双指针来实现 $O(n)$ 的相同数字计数；在右移 $k$ 之后并不会影响有序性，所以可以直接跑 $O(n)$ 的双指针。因为只需要排序一次，复杂度 $nlogn$ ，对于每种询问需要 $O(n)$ 计数，复杂度 $qn$ ，所以综合复杂度 $nlogW$ ，且很好写。

$A$ 怎么走啊

关键点：所有点连通、边数不超过点数 $100$ 、起点终点固定、没有负权边。

于是可以理解为在一棵树上添加了不超过 $100$ 条边，起点终点又是固定的，其实可以想到核心的点不会太多。

其 $std$ 的做法是：

第一步，先拓扑排序，把除开 $1$ 和 $n$ 之外的所有叶子一层层删掉直到删不掉为止，因为这些删掉的点是完全不可能成为答案的点。（这一步基于起点终点固定、没有负权边）；

第二步，将除开 $1$ 和 $n$ 之外度数为 $2$ 的点收缩掉（即把一条长链收缩为单独一条边），用一条新的双属性边来描述这条路。（双属性是指，原本一条边只有一个正向的权值，但如果把一条链全部收缩，则需要分别记录正向权值和反向权值）

可以想到，这样做之后剩下的点数只会在 $200$ 左右，因为最开始保证了连通，所以边数也只有 $800$ 左右。

那么对于每次询问，只需要在“缩略图”中直接跑 $Dijkstra$ 就可以了。预处理复杂度线性，询问一次 $200log800$ 大约 $2000$ ，对于 $1e5$ 次询问已经足够了。

alt

另外还有选手使用了十分巧妙的二分做法：

对于一条路线，令反边权值和为 $a$ ，正边权值和为 $b$ ，则其真实路线长度为 $y=ak b$ ，几何意义为一条直线。

众多的路线可以理解为第一象限内的众多直线。

而对于每次询问，也就是确定k的情况下，从众多路线中选择最短路的行为，可以理解为在所有直线中选择最小的函数值。

那么当k从小到大变化起来，会发现其实我们选择的就是众多直线在第一象限内的下凸包表面(或许说是凹包更合理)。

由于图的边数限制，这个凸包表面的线段数量不会很多；

显然k越大所截取的凸包面的斜率越小，于是可以维护一个当前斜率，在确定一个凸包面线段左端点后，通过二分来求右端点， $check$ 方式是跑一遍最短路再看斜率大小。

每求出一段线段就可以把范围内的 $dis$ 直接计算完。于是这样做预处理的复杂度是 $线段数*logn*n*logm$ ，询问是 $O(1)$ 的。

alt

另外还有选手使用了十分巧妙的虚树做法：

但是我不会。

$F$ 不存在的子串

模型可以抽象为HH的项链，不会这个的先去洛谷搜搜做。

给 $1e6$ 的主串， $q$ 次询问求区间内最短的未出现子串。首先答案不会超过 $5$ ，因为长度为 $5$ 的串有 $26^5=11881376$ 种， $1e6$ 的主串不可能包含完。

所以可以考虑枚举答案 $[1,4]$ ，检查区间内长度为k的串是否全都出现过了，即区间内是否有 $26^k$ 种不同的串。

考虑一种特别的哈希，即把字符串按照 $26$ 进制唯一映射为一个数字，那么长度为k的所有串其实对应了 $[26^k,26^{k 1}-1]$ 的数字区间。

我们把字符串的每一个位置开始长度为 $[1,4]$ 的子串都映射为数字保存在新的数组中，那么问题就变成了：求四次在区间内不同的数字种类数是否为 $26^k$ 个。

模型建立完毕，从数据规模判断，莫队并不足以通过本题。

所以可以先离线所有询问，然后遍历数列的过程中用树状数组维护每个数字最后一次出现的位置 $1$ ，处理到第 $i$ 位的同时，处理所有右端点为 $i$ 的询问，即查询此刻树状数组中 $[l,i]$ 的和，直观意义是最后一次出现的数字个数，同时也是区间内不同数字的个数。

以上。当然也可以写主席树维护 $pre[i]$ 的计数（代表上一个 $a[i]$ 出现的位置），直接在线查询对于区间 $[l,r]$ ,满足 $last[i]<l$ 的点的个数。

$H$ 若你来到南京是否想起我的梧桐

$h,w,c$ 分别是树高，存活价值，砍伐代价。

由题意阳光机制可以分析，最终活下来的树一定形成了高度“先上升再下降”的趋势。

于是考虑设计 $f_i$ 表示保证第 $i$ 颗树存活的情况下，前缀树高不下降子序列能产生的最大价值。

其暴力转移方式为，枚举 $[1,i-1]$ ，选一棵不高于自己树j作为上一颗必须存活的树，那么j~i的所有低于j的树都会因为缺乏阳光而自然枯萎，而不低于j的树都需要砍伐掉且消耗对应代价，以此保证j是上一颗树。

于是有转移方程 $f_i = w_i max\{f_j-sum\{c_k|j<k<i,h_j \le h_k\}|j<i,h_j \le h_i\}$ 。

这样的暴力显然 $n^2$ 不行，考虑优化。

如果考虑 $[1,i-1]$ 的情况下维护对映射 树高 $h$ $->$ 最后一棵树高为h的所有决策中能产生的最大价值 建立线段树求区间最值；

那么转移方程中 $max$ 这一步就变成了求线段树中键小于等于 $h_i$ 的最大值。

但不对，这没有体现出砍伐的代价。

思考对于第 $i$ 颗树什么时候会被砍，只有在计算大于 $i$ 的 $dp$ 状态，且选中了一颗高度小于等于自己的树作为“前驱”时，自己必然被砍，且造成负贡献。

所以只需要在处理完第 $i$ 个 $dp$ 值后，先在线段树更新 $h_i$ 的 $dp$ 值为 $f_i$ ，再**把线段树内 $[0,h_i)$ 都减去代价 $c_i$ **即可。

于是做到了 $nlogn$ 复杂度求出 $f_i[]$ ，代表了以 $i$ 结尾的前缀高度不下降最大价值；

同理再倒着求一个 $g_i[]$ ，代表以 $i$ 起始的后缀高度不上升最大价值；

最后枚举第 $i$ 位作为峰点，用 $f_i g_i-w_i$ 更新答案即可。

另外，树高一开始就离散化了更方便处理。

$3.$ 标程代码：