目录
错题集 1
1、Fake Maxpooling
题意
给定一个 $n\times m$ 矩阵，$a_{i,j}=\text{lcm}(i,j)$，设 $f(i,j)=\{\max a_{x,y}|i\le x\lt i+k,j\le y\lt j+k\}$，求
\begin{equation}\sum_{i=1}^{n-k+1}\sum_{j=1}^{m-k+1}f(i,j)\end{equation}
题解
记忆化搜索求 $\text{gcd}$，两次单调队列维护最大值。
第一次单调队列维护每行长度为 $k$ 的区间的最大值，第二次单调队利用 $k$ 列每行长度为 $k$ 的区间的最大值。
时间复杂度 $O(nm)$。
2、Columns Swaps
题意
给定一个 $2\times n$ 的表格，定义一次操作为交换同一列的上下两个元素。
问至少要经过多少次操作才能使表格两行均为 $1\sim n$ 的全排列。(如果无解，输出 $-1$)
题解
首先如果某个数字在表格中出现次数不为 $2$ 必无解。
否则记录每个数的两次出现的行号和列号。
建图，每个列代表一个点。对图进行某种染色，若一个点染黑色代表该列要交换，若一个点染白色代表该列不要交换。
考虑每对相同数的行号。如果行号相同，则两个数所在列必须有一个交换，一个不交换，两列所代表点连一条黑边，代表这两点颜色不同。
如果行号不相同，则两个数所在列要么都交换，要么都不交换，两列所代表点连一条白边，代表这两点颜色相同。
对每个连通块进行染色，初始点颜色设为 $0$，与初始点不同的颜色设为 $1$。最后如果 $0$ 色点多则 $0$ 色为白色，否则 $1$ 色为白色。
由于染色过程遇到已标记点会跳过，所以最后需要在染色后枚举边集确定每条边的两个点颜色是否满足条件。
3、Columns Swaps
一道简单 $\text{dp}$ 题，比赛时犯蠢当成只能由一个长度为 $6$ 的组了，其实可以好几个。
4、Just Shuffle
题意
已知某个置换对初始排列 $1,2,\cdots n$ 连续迭代 $k$ 次的置换，求原置换(保证 $k$ 为大质数)。
题解
首先对任意一个置换的循环节，设其长度为 $m$，该循环节对初始排列连续迭代 $t$ 次等价与对初始排列连续迭代 $t\bmod m$ 次。
已知某个循环节是对初始排列连续迭代 $k$ 次的结果，将当前结果对初始排列连续迭代 $k^{-1}\bmod m$ 次。
这等效于将原置换对初始排列连续迭代 $k\ast k^{-1}\equiv 1\bmod m$ 次，即结果仍为原置换。
5、Hard Gcd Problem
题意
给定一个 $n$，要求找出最大的集合 $A,B$，使得 $A,B\subset \{1,2,\cdots n\}$，且 $|A|=|B|,A\cap B=\emptyset$。
同时设 $A=\{x_1,x_2,\cdots x_m\}$，$B=\{y_1,y_2,\cdots y_m\}$，有 $(x_i,y_i)\gt 1$。
题解
显然答案不大于 $\frac {n-1-|C|}2,C=\{p|p\gt \frac n2\}$。
现在构造满足该上界的解。
然后从 $3$ 开始枚举不属于 $C$ 的质因子 $p$，把之前未访问的质因子的倍数丢掉桶里，显然这个桶里一定会有 $2p$，因为 $2p$ 不可能在之前被访问。
如果桶里有偶数个数，直接两两配对，否则剩下一个 $2p$。
最后只剩下偶数，直接两两配对。
