模拟赛游记 #4，#3 被我吃了
这次依旧 OI 赛制。
T1
题面：给定一个数 NNN，你可以进行若干次操作，每次操作交换两个数位。问最少进行多少次操作可以使 NNN 变成 444 的倍数。
N≤109N\le 10^9N≤109？能忍住不搜的是这个 👍
注意到 444 的倍数满足：
* 若倒数第二位为偶数，则最后一位是 444 的倍数；
* 若倒数第二位为奇数，则最后一位是 444 的倍数 +2+2+2。
时间复杂度：O(T∣n∣3)O(T|n|^3)O(T∣n∣3)。
写完后才发现有 T≤105T\le 10^5T≤105 组样例，成 Joker 了
没事，至少我有了一个暴力代码，可以用来攻克一堆特判的正解。
经过特别久的调完改改完调调完改改完调后我终于写出来了以下代码，里面有如下特判：
* 如果初始就是 444 的倍数，则最少交换次数为 000。
* 如果交换了最后两位后是 444 的倍数，则最少交换次数为 111。
* 如果是小于两位并且不符合前面的条件，则无法变成 444 的倍数。
对于剩下的情况，令 a,b,ca,b,ca,b,c 分别为在 NNN 的所有数位中，模 222 为 111 的数，模 444 为 222 的数，模 444 为 000 的数的数量，则：
* 如果 b=0b=0b=0 且 c≤1c\le1c≤1 ，则不能变成 444 的倍数。
* 如果 a=0a=0a=0 且 c=0c=0c=0，则无法变成 444 的倍数。
* 如果最后一位是 444 的倍数，则倒数第二位必不是 222 的倍数，只需将任何一个是 222 的倍数的数移过来即可。
* 如果最后一位模 444 余 222，则倒数第二位必为 222 的倍数，只需将任何一个不是 222 的倍数的数移过来即可。
* 否则，最后一位一定不是 222 的倍数。如果倒数第二位不是 222 的倍数并且有模 444 为 222 的数，只需将任何一个模 444 为 222 的数移到最后一位即可。
* 如果倒是第二位是 222 的倍数并且有除了后两位以外的 444 的倍数，只需将任何一个 444 的倍数移到最后一位即可。
* 如果上述情况都不满足，可以证明最少移动次数为 222。
时间复杂度：O(T∣n∣)O(T|n|)O(T∣n∣)。
T2
题面：有一个数组长度为 NNN 的数列 AAA，小明用它生成了一个数列 FFF，满足 Fi,j=max{Ai,Aj}F_{i,j}=\max\{A_i,A_j\}Fi,j =max{Ai ,Aj }，他把数列 FFF 打乱，又删除了一项。现在他给你这个数列，问你他删除了哪个元素，如果有多种可能输出 Infinite。
唯一没有对拍的一个。
先把 AAA 排序。显然，在原来的 FFF 种，A1A_1A1 会出现 000 次，A2A_2A2 会出现 111 次，A3A_3A3 会出现 222 次，...，ANA_NAN 会出现 N−1N-1N−1 次。
我们只需要找哪个数的出现次数不对。
当然，无数种情况当且仅当删除了 A2A_2A2 。此时删除的可能为任意一个小于等于 A3A_3A3 的数。
实现的时候直接用 map 解决即可。map/set 太好用了你知道吗
时间复杂度：O(n2logn)O(n^2\log n)O(n2logn)。
T3 太史了，先看 T4。
T4
题面：定义请输入文本串如下：
一个字符串可以划分成若干个（一个也行）非回文字串。如 abbba 可以划分成 ab bba 两个子串，所以它是请输入文本串。
现给定一个长度为 NNN 的数组 AAA 和一个正整数 MMM（1≤Ai≤M1\le A_i\le M1≤Ai ≤M 或 Ai=−1A_i=-1Ai =−1），你可以用 AAA 生成一个字符串 BBB，使 BBB 满足：
Bi={AiAi≠−1K(1≤K≤M)Ai=−1B_i= \begin{cases} A_i & A_i\not= -1\\ K(1\le K\le M) & A_i=-1 \end{cases} Bi ={Ai K(1≤K≤M) Ai =−1Ai =−1
求你可以生成多少种不同的请输入文本串 BBB。
首先注意到有 N,M≤7N,M\le 7N,M≤7 的部分分，遇事不决先打暴力：
我们枚举每个 Ai=−1A_i=-1Ai =−1 时 BiB_iBi 的取值，然后再枚举划分点，逐个判断是否是请输入文本串。
暴力最难拿的一集，甚至只占了 101010 分。
时间复杂度：O(Tmn2n)O(Tm^n2^n)O(Tmn2n)，卡不满。
好的，暴力有了，接下来就该想正解了。
显然，绝大多数串都是请输入文本串，所以正难则反，先考虑所有不是请输入文本串的串，再拿总方案数减去这些即可。
经过一番对拍，我找到了所有不是请输入文本串的串：
* 前面一半和后面一半都是同一个字符。如 aaaa，bbbbabbbb。显然如何划分都有一个串全是同一个字符。
* 长度为奇数，并且所有奇数下标的字符均为同一个字符，所有偶数下标的字符均为同一个字符。如 ababababa。显然如何划分都会使得它有一个奇回文串。
注意这两种情况可能有重复，实现的时候注意减去重复的情况。
时间复杂度 O(∑n)O(\sum n)O(∑n)。
T3 就随便打了个暴力，预估 50。
赛后
分出来了，100+100+20+100=320100+100+20+100=320100+100+20+100=320，喜提 rk1。
T3挂了的原因是因为数组开小了？
