link.
A. Mystic Permutation
link
Solution
可以发现最终字典序最小的排列一定是由\({1,2,3,...,n-1,n}\)临项交换而来。
考虑贪心,计答案序列为\(a\)。
若\(p[i]\neq a[i]\)，则一切安好；
否则考虑临项交换：
若\(a[i-1]<a[i]\)，则将\(a[i]\)与\(a[i+1]\)交换；
否则交换\(a[i]\)与\(a[i-1]\)。
时间复杂度：\(O(n)\).
B. Huge Pile
link
Solution
可以发现每次除以 2 的操作后至多会存在 2 堆数量不同（相差 1 ）的苹果。
在\(n\)一直为偶数时，除以 2 后只会有以对苹果，数量为\(\frac{n}{2}\).
只要出现过\(n\)为奇数，之后的操作都会出现两堆苹果。
直接模拟即可。
时间复杂度：单组\(O(logn)\).
C. Informatics in MAC
link
Solution
计两个子段分别为\(A,B\)，\(mex(A)=x\)且\(mex(B)=x\)，则\(mex(AB)=x\).
所以对于所有\(mex\)相等的子段都可以合并成一个子段。
所以只需要找 2 个子段令他们的\(mex\)值相等即可。
考虑枚举分界点。
时间复杂度：\(O(n)\).
D. Fishingprince Plays With Array
link
Solution
两个操作本质上是互逆的，但是第 2 个合并操作并不好做。
所以考虑将\(a\)序列和\(b\)序列都展开到不能展开的地步。
再判断展开后的\(a,b\)序列是否相等即可。
实现上需要记录每个元素的次数，不能直接展开。
E. awoo's Favorite Problem
link
Solution
可以发现\(a\)序列中的\(a\)只能想右移动，\(c\)只能向左移动。
但他们的移动都要以\(b\)为媒介。
而\(b\)的移动不好刻画，但如果两个字符串的\(a\)和\(c\)都能够匹配上，那么\(b\)也自然能够匹配上。
所以判断\(a\)和\(c\)字符能否互相匹配即可。
判断\(a\)字符时，从后向前匹配；
判断\(b\)字符时，从前向后匹配。
实现时如何快速判断区间内是否没有某个元素？
可以对三个字符分别做前缀和即可。
F. Keshi Is Throwing a Party
link
Solution
发现答案具有单调性，可以二分答案，计二分的答案为\(k\)。
对于第\(i\)个人，计他在被选中的人中的排名为\(pos_i\)。
则\(pos_i\)需要满足\(a_i \geq k-pos_i\)且\(b_i \geq pos_i-1\).
移项得\(k-a_i \leq pos_i \leq b_i+1\).
那么\(check\)时，贪心判断当前能否找出一个排名从 1 到 \(k\) 的序列即可。
时间复杂度：\(O(nlogn)\)。
G. Zero Path
link
Solution
dp.
可以设\(f_{i,j,k}\)表示从\((1,1)\)走到\((i,j)\)是否存在一条和为\(k\)的路径。
但是这样做只能\(O(n^3)\)转移，显然无法通过。
当然，其实可以用\(bitset\)实现，时间复杂度：\(O(\frac{n^3}{w})\)，可以跑过去。
考虑如果从一条确定的路径上选一个点用其他的点来替换，那么这条路径的值要么不变，要么 +2 或 -2 。
所以记录从\((1,1)\)到\((n,m)\)的路径最小值和最大值，只要 0 包含在这个区间内且路径长度是偶数，就一定可以得到和为 0 的路径。
对于最大值和最小值，dp即可。
时间复杂度：\(O(n^3)\)。
H. Exquisite Array
link
Solution
考虑枚举\(k\)，如果直接计算，复杂度为\(O(n^2)\)。
正序枚举\(k\)，相当与不断分裂区间，是不好做的。
与[JSOI2008] 星球大战类似的，直接倒序枚举\(k\)。
对于当前的\(k\)，用并查集维护合并，每次合并差值等于\(k\)的两个数，计算贡献即可。
I. Maximum AND
link
Solution
贪心，位运算。
由于\(2^n= \sum_{i=0}^{n-1} 2^i\)，所以要想让答案尽可能的大，那么高位要尽可能为 1 。
倒序枚举第\(i\)位。
对于第\(i\)位，如何判断这一位是否能为 1 呢？
由题意得：一定要能找出一种分组，值得每一组的\(a_i\)和\(b_i\)均不相同。
推式子，可以得到满足条件：\((a_i \& x) \oplus (b_i \& x)=x\)。
而\(x\)为当前期望答案。
对于\(a_i \& x\)开一个\(map\)记录数量，对于每一个\((b_i \& x) \oplus x\)查找是否有与之匹配的\(a_i \& x\)即可。
注意考虑第\(i\)位时不能只考虑\(2^i\)，而是要在当前的最大答案上加上\(2^i\)，观察是否合法，非法在减掉\(2^i\)。
因为要优先满足高位的 1 ，再考虑低位。
J. Fibonacci Strings
link
Solution
首先\(\sum_{i=1}^{k} c_i\)一定要是斐波那契数列的某个前缀和的值。
那么我们就可以知道它可以凑出的数列的长度了，记为\(n\)。
一个比较自然的想法：肯定要让当前剩余的最大值来充当最大的字符。
而事实上，这是对的。
可以证明：当考虑到\(F_i\)时，如果有一个\(c_i > F_{i+1}\)，那么一定无解。
这个实现过程可以用堆维护，最后看对是否为空即可。
注意实现时，不能连续使用两次同一个元素。
时间复杂度：\(O(nlogn)\)。