官方题解 | 挑战赛19题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的字符串加密 入门 T2 小午的质因子统计 普及- T3 午枫的字符串移动 普及- T4 午枫的01串翻转 普及/提高- T5 午枫的双向奔赴 普及/提高- T6 午枫的字符串制造 普及/提高-
T1 午枫的字符串加密
题目大意
给了一个 mmm 加密后的字符串，求出加密前的字符串。
解题思路
由于小写英文字母只有 262626 个，所以加密也是 262626 次一个循环。我们可以将 mmm 直接对 262626 取模，可以对每一个字符用循环模拟解密的过程，即将这个字母变成在字母表上循环左移 mmm 位后的字母，时间复杂度 O(m%26)O(m\%26)O(m%26) 。
当然，也可以通过直接计算直接得到加密前的字母，时间复杂度 O(1)O(1)O(1) 。std 给出的是 O(1)O(1)O(1) 的方法。
参考代码
T2 小午的质因子统计
题目大意
求所有数质因数分解后有多少个不同的质因子。
题解思路
可以用埃式筛先预处理出 [1,106][1,10^6][1,106] 所有数的质因子有哪些，然后遍历数组用 setsetset 容器存储所有质因子，因为 setsetset 容器会自动去重，所以最后直接输出 setsetset 容器的 size()size()size() 即可。
参考代码
T3 午枫的字符串移动
题目大意
给定原串和最终串，最终串是通过原串循环右移且丢失若干字符得到的，求出原串最小的循环右移次数。
题解思路
由于 nnn 最大是 100001000010000 ，我们可以考虑 O(n2)O(n^2)O(n2) 的做法。
首先，很容易发现 mmm 最大可能是 n−1n-1n−1 ，所以我们可以通过枚举 s′s's′ 对应原串 sss 的开头位置，类比做了 C(s,m)C(s,m)C(s,m) 的操作，一位一位进行比较判断，如果某一位不匹配，那么就让 sss 的下一位去匹配，如果 sss 的每一位都判断过了还没有匹配到 s′s's′ 的最后一位，那么说明不存在这么一个 mmm 让 sss 变成 s′s's′ 。
我们只要找到最小的 mmm 即可。
参考代码
T4 午枫的01串翻转
题目大意
给定一个 010101 串，可以进行指定操作，求出所有可能的 010101 串中距离最远的两个 000 的距离是多少。
题解思路
我们其实最多只需要操作一次即可得到答案。
一共分三种情况：
* 没有 000 ，直接输出 000 。
* 只有一个 000 ，此时很容易发现不操作的话距离一定是 000 ，所以我们尽量考虑操作。
* 如果这个 000 在最后两个位置，要么无法操作，要么操作了一次也还是只能有一个 000 , 此时答案为 000 .
* 如果不在最后两个位置，考虑到其余位置都为 111 ，我们尽量操作更长的区间，能使两个 000 的距离最大，那么以这个 000 为区间左端点，最后一个 111 为区间右端点，对这段区间进行一次操作，就会将区间内所有的 111 都变为 000 ，此时答案为 翻转区间长度−1翻转区间长度-1翻转区间长度−1 .
* 有两个及以上个 000 ，此时我们可以让最左端的 000 不动，记这个 000 的位置为 pospospos ，用后面的任意 000 最为操作区间的左端点，最后一个 111 最为区间右端点，不难发现，操作后距离最左端的 000 最远的 000 一定是最后一个字符，此时答案为 n−posn-posn−pos .
综上所述，此题只需找到第一个 000 的位置，按照上述情况分类讨论即可。
参考代码
T5 午枫的双向奔赴
题目大意
给定一张图，小午和小枫分别在 111 号节点和 nnn 号节点，求出两人会和的最小时间，并且按照编号从小到大输出所有花费最小时间的节点
题解思路
设 d1id1_id1i 为从 111 号节点出发到达 iii 号节点的最短时间，dnidn_idni 为从 nnn 号节点出发到达 iii 号节点的最短时间。那么他们在 iii 号节点会和花费的时间为 max(d1i,dni)max(d1_i,dn_i)max(d1i ,dni ) 。所以他们会和的最短时间为 mini=1n(max(d1i,dni))\min_{i=1}^{n} (max(d1_i,dn_i))mini=1n (max(d1i ,dni )) 。
分别以 111 号节点和 nnn 号节点为起始节点用 dijkstradijkstradijkstra 求出最短路，即 d1id1_id1i 和 dnidn_idni ，然后再求出他们会和需要的最短时间，最后找出所需最短时间的节点，按照编号从小到大输出。
参考代码
T6 午枫的字符串制造
题目大意
给定一个长度为 nnn 的字符串，求有多少个连续子串可以通过重新排列得到回文串。
题解思路
首先，如果用 O(n2)O(n^2)O(n2) 暴力枚举所有区间肯定是不可行的。于是我们需要考虑优化。
我们如何可以快速判断一个子串能否通过重新排列得到一个回文串？
不难发现，如果这个子串的长度是偶数，那么所有的字母的个数都是偶数就可以排列成回文串；如果这个子串的长度是奇数，那么只能有一个字母的个数是奇数，才可以排列成回文串。
那么我们可以用长度为 262626 的二进制状态表示每一个字母个数的奇偶。
奇偶性可以通过异或来表达。记 StateiState_iStatei 为前 iii 个字母的奇偶状态，定义 State0=0State_0=0State0 =0 ，cntStatecnt_{State}cntState 为 StateStateState 这种状态的数量。我们可以通过枚举区间右端点 iii ，得到 StateiState_iStatei ，那么我们可以考虑分回文串的奇偶长度分两个情况考虑：
* 回文串的长度为偶数，此时有 cntStatejcnt_{State_j}cntStatej 个左端点 jjj 可以形成回文串，其中 0≤j≤i−10\leq j\leq i-10≤j≤i−1 且 Statei=StatejState_i=State_jStatei =Statej 。
* 回文串的长度为奇数，此时我们可以枚举 262626 个字母为奇数状态的情况，设第 kkk 个字母的个数是奇数的状态为 mask=Statei⊕(1<<k)mask=State_i\oplus (1<<k)mask=Statei ⊕(1<<k) ，那么有 cntmaskcnt_{mask}cntmask 个左端点 jjj 可以形成回文串，其中 0≤j≤i−10\leq j\leq i-10≤j≤i−1 且 mask=Statejmask=State_jmask=Statej 。
字符串的长度为 nnn 且每个状态最多延申出 262626 个状态，空间复杂度最大为 O(26n)O(26n)O(26n) ，此题空间限制给了 1GB1GB1GB ，因此是可以通过的。
时间复杂度为 O(26n)O(26n)O(26n) 。
参考代码
