挑战赛#15 全题解
前记
太爽了极限 AK。
这里着重会讲万恶的 T5。
正式部分
T1
T1 小特想散步
很简单的一道题啊，字符串输入判断即可。
T2
T2 老猞狸的问题
同样很简单的题，每次遇到不同的贪心性交换后一位，如果不行直接 No，同时统计次数，次数 >1>1>1 时也要 No。
T3
T3 源石虫比赛
这能有黄？
看到数据范围 1≤n≤1041 \le n \le 10^41≤n≤104，直接 O(n2)\mathcal O(n^2)O(n2) 自信过了。
理论上也可以加一个排序和二分，有人有时间打吧。
贪心性很明显，每次选择最小的比两接力位置之差大于或等于的原石虫就可以了。
注意一下它的输出结构。
T4
T4 简单集合之和
总算有点难度的题，不过数据范围 1≤n≤351 \le n \le 351≤n≤35，显然 2352^{35}235 的爆搜会 TLE，同时用背包的话 ai≤109a_i \le 10^9ai ≤109 也得凉。
其实不难让人想到是 折半搜索（meet in the middle） 算法。
该算法主要思路是：
1. 将 nnn 范围的数分成两半；
2. 将两半数 dfs，用两个数组统计其中的答案，两个数组的大小就是 2n2=2182^{\frac{n}{2}} = 2^{18}22n =218 是可以实现的;
3. 将其中一个数组排序（我这里选 ans2ans2ans2），然后遍历另一个数组进行 二分操作（这个后面讲）;
4. 最后统计一下答案就可以了。
对于这道题来讲，由于我们搜出来的答案对 xxx 取模，所以 0≤ansi<x0 \le ans_i < x0≤ansi <x。
同时不难证明，我们我们每次遍历的数 ans1i+ans2jans1_i + ans2_jans1i +ans2j 小于 xxx 的情况一定比大于等于 xxx 的情况模 xxx 要更大，所以二分操作就是选出令 ans1i+ans2j<xans1_i+ans2_j<xans1i +ans2j <x 中最大的 ans2jans2_jans2j ，注意可以重复选，也可以不选（ans20=0ans2_0=0ans20 =0）。
但注意 ans1ans1ans1 也可以不选。
最后时间复杂度是 O(2n2log2n2)\mathcal O( 2^{\frac{n}{2}} \log 2^{\frac{n}{2}})O(22n log22n )，可以通过本题。
T5
T5 聪明图
万万差点没想到原来是线段树。
首先没看到 “保证每次操作后都会满足对于 i<ni<ni<n 存在从 iii 连向 i+1i+1i+1 的边” 的出来罚站，没救了。
那么既然有这个条件，那就说明对于任何 (i,j)∣i<j(i,j) |i<j(i,j)∣i<j，一定能从 iii 到 jjj。
问题到这已经非常线性了。
那么我们要做的就只有维护每个数能到的编号最小的数了，这里我用了一个 map 来记录维护，本质是红黑树，能在稳定 O(nlogn)\mathcal O(n \log n)O(nlogn) 来维护。
那么对于每次加边删边，只有 x<yx<yx<y 的时候要改变，同时发现操作改变了的时候要修改到线段树。
接下来说一下查询，可以知道 xxx 号节点一定能到任何 ≥x\ge x≥x 的节点，所以我们只要知道我们能到的编号最小的节点就行了。第一次只用查询区间 [x,n][x,n][x,n] 中能到的编号最小的数最小值。区间？正好就是线段树的工作（你用树状数组或者 ST 表可能也行）。但是要知道不仅如此，设第一次答案为 ansansans，则它到了这个节点之后还能到区间 [ans,x−1][ans,x-1][ans,x−1]，以此类推，可以到 [ansi,ansi−1−1][ans_i,ans_{i-1}-1][ansi ,ansi−1 −1]，终止条件就是
ansi+1=ansians_{i+1}=ans_iansi+1 =ansi ，这时候能到 [ans,n][ans,n][ans,n] 的任一节点，所以答案就是 n−ansi+1n-ans_i+1n−ansi +1。
补充：
其实这样写有可能会被卡到 O(nq)\mathcal O(nq)O(nq) 的，出题人好心没卡。如果谁有时间可以试试做个记忆化，每次查询后 [ansi,x][ans_i,x][ansi ,x] 的区间可以记忆化，然后在真实修改了某一个数的能到的编号最小的数就覆盖掉。
T6
T6 串串
很明显，前缀长度增大时，答案单调不增，所以二分就可以。
但模式串字符串匹配，那就是 KMP 了，不多讲。
我之前想过 AC 自动机的，不过因为比较聪明不会拓扑建图，所以就算了。
总结
这次挑战赛出的还不错。
