AHOI/HNOI
- D1T1 单旋
不会哦，感觉这题最难。
- D1T2 影魔
考虑计算每个位置作为 \([l+1,r-1]\) 中的最大值时的贡献，一定是有一端取到了左边第一个比自己大的或者右边第一个比自己大的，可以用单调栈求出所有的有效点对，是线性的，然后做一遍二维数点即可。
- D1T3 礼物
首先考虑不做修改，只做轮换的情况。将第二个序列断环成链，我们假设每个 \(i\) 都匹配了 \(i+k\)，那么要求的就是 \(\sum\limits_{i=1}^{n}f_ig_{i+k}\)，翻转一个序列，就变成了卷积的形式，用 FFT 计算。
发现两个序列都加是无意义的，因此可以枚举一个序列加，再利用刚刚 FFT 完的信息计算。时间复杂度 \(\mathcal O(n\log n+nm)\)。
- D2
GZOI
- D1T1 取石子游戏
游戏指的就是 Nim，因此选择 \((i,S)\) 的合法条件就是 \(S\) 中所有数异或和 \(\ge a_i\)，直接 dp 即可。
- D1T2 小z玩游戏
问题即求连边后每个点所在强连通分量大小是否 \(\ge 2\)，直接建图是 \(\mathcal O(n^2)\) 的。优化的方法是对于每个数建立两个虚点，分别表示进入和出去，然后调和级数地连边，时间复杂度 \(\mathcal O(n\log n)\)。
- D1T3 配对统计
发现有效的点对只有 \(\mathcal O(n)\) 个，直接求出来之后二维数点即可。
- D2T1 河神
矩阵快速幂板子。
- D2T2 等差子序列
枚举中间值，现在相当于判断两边有没有 \(a_i-k\) 和 \(a_i+k\)，bitset 就行了。多简单。
标签：省选,FFT,ge,做题,序列,mathcal,2017 From： https://www.cnblogs.com/petitsouris/p/18095476