ACGO 巅峰赛#16 题解
写在前面
本场排位赛的所有题目的难度评级为：
题目编号 题目标题 难度 A. 美丽数 入门 B. 环形回文串 入门 C. 无重复字符的子串 普及- D. 统计满足条件的子串个数 普及+/提高 E. 考拉兹猜想 普及+/提高 F. 帕罗蒂克 普及+/提高
非常感谢大家参加本场巅峰赛！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解简述
以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。
A - 美丽数
模拟
我们可以使用一个数组 cnt 来统计 NNN 中各个数字出现的次数。
然后枚举 [1,9][1, 9][1,9] 中每个数字进行检查，若 NNN 中存在数字 iii，且 cnti≠icnt_i \ne icnti =i，那么说明不是 美丽数，直接输出 No，并结束程序；否则循环结束后，没有退出程序，则输出 Yes。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 环形回文串
枚举
我们考虑将 222 个原字符串 SSS，前后拼接起来构造为字符串 S′S'S′。
然后枚举下标 i(1≤i≤∣S∣)i (1 \le i \le \vert S \vert)i(1≤i≤∣S∣)。检查在字符串 S′S'S′ 中，以 iii 开头的长度为 ∣S∣\vert S \vert∣S∣ 的子串是否为回文串即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 无重复字符的子串
模拟；枚举
由于不含重复字符的字符串最长为 262626，所以我们可以暴力枚举每个起点为 i(1≤i≤∣S∣)i (1 \le i \le \vert S \vert)i(1≤i≤∣S∣) 的子串，并使用数组 cnt 来统计每一个字符出现的次数，若在向后遍历的过程中，发现某个字符已经出现过，则停止向后遍历。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 统计满足条件的子串个数
数据结构（树状数组，线段树，平衡树）；
使用「树状数组」等数据结构，ft[i][j] 维护字符串 SSS 中字符 iii 在前 jjj 个字符中出现的次数。
使用树状数组，预处理 cnt[i][j] 数组，表示字符串 S 中，以 iii 开头，以 jjj 结尾的子串的个数。
对于每次修改操作，我们考虑删除字符 SXS_XSX 对以 iii 开头以 SXS_XSX 结尾和以 SXS_XSX 开头以 iii 结尾的子串数量，即 cnti,SXcnt_{i, S_X}cnti,SX 和 cntSX,icnt_{S_X, i}cntSX ,i 的影响。
那么我们直接枚举 iii：
1. 对于 cnti,SXcnt_{i, S_X}cnti,SX ，查询前 X−1X - 1X−1 个字符中，字符 iii 出现的次数，并将其从 cnti,SXcnt_{i, S_X}cnti,SX 减去。
2. 对于 cntSX,icnt_{S_X, i}cntSX ,i ，查询第 XXX 个及以后的字符中，字符 iii 出现的次数，并将其从 cntSX,icnt_{S_X, i}cntSX ,i 减去。
同时修改树状数组。
然后将 SXS_XSX 修改为字符 CCC，使用与计算删除的影响相同的做法，即可得到修改后对 cnt 数组的影响。
对于每个查询，我们可以以 O(1)\mathrm{O}(1)O(1) 的时间从 cnt 数组中得到答案。
令 NNN 为字符串 SSS 的长度，MMM 为字符集的大小，整个算法，预处理 cnt 数组的时间复杂度为 O(NMlog2N)\mathrm{O}(NM\log_2{N})O(NMlog2 N)。处理每个查询的时间复杂度为 O(Mlog2N)\mathrm{O}(M\log_2{N})O(Mlog2 N)，整个算法时间复杂度为 O((N+Q)×(Mlog2N)\mathrm{O}((N + Q) \times (M\log_2{N})O((N+Q)×(Mlog2 N)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 考拉兹猜想
数据结构（平方分割，等）；
编写程序计算，10510^5105 内变为 111，需要操作次数最多的数为 770317703177031，经过 350350350 次操作后变为 111。这意味着，数组中的每个元素最多经过 350350350 次操作后，后续的操作对其失效。
我们考虑将数组分割为 N\sqrt{N}N 个部分，对于每个块，我们维护一个容器，存储块内不为 111 的元素的下标，另外维护一个变量维护块内为 111 的元素数量。每次修改操作，[L,R][L, R][L,R]：
1. 对于未整体出现在同一个块内的元素，暴力更新。
2. 对于整体出现在同一个块内的元素，只修改块内不为 111 的元素，同时将修改后所有的变为 111 的元素下标，从块内容器中删除，同时令块内为 111 的元素数量增加。
由于每个元素最多被修改 350350350 次后，变为 111，上述操作，第一部分时间复杂度为 O(N)\mathrm{O}(\sqrt{N})O(N )，第二部分同样为 O(N)\mathrm{O}(\sqrt{{N}})O(N )。
对于每个查询 [L,R][L, R][L,R]，也分为两个部分：
1. 对于未整体出现在同一个块内的元素，暴力统计。
2. 对于整体出现在同一个块内的元素，查询块内维护的块内为 111 的元素数量。
两部分操作时间复杂度皆为 O(NN)\mathrm{O}(N\sqrt{N})O(NN )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 帕罗蒂克
状态压缩动态规划
定义 dp[i][mask][j]dp[i][mask][j]dp[i][mask][j] 为第 iii 位朋友，已经经过的站点集合为 maskmaskmask，此时位于车站 jjj 的可行性。
那么我们就可以对每一位朋友分开考虑，并使用状态压缩动态规划，在 O(KN22N)\mathrm{O}(KN^22^N)O(KN22N) 的时间复杂度内，计算出上述 DPDPDP 数组。
然后我们定义 turn[step][i]turn[step][i]turn[step][i] 表示，经过 stepstepstep 次移动，位于车站 iii 的朋友的集合。根据已经得出的 dpdpdp 数组，我们可以很容易计算出 turnturnturn 数组。
最后根据 turn[step][i]turn[step][i]turn[step][i] 中的存储的集合是否为所有朋友的全集，来判断，是否可以在站点 iii 汇合即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
