1st Universal Cup, Stage 4: Ukraine
思维题很多，赛中要大胆猜结论，证明可以用程序
| ID | Difficulty (0-5) | Topic | Status | Code |
|---|---|---|---|---|
| A | 0 | Greedy | Solved | A.cpp |
| B | 3 | Counting | Solved | B.cpp |
| C | ||||
| D | 1 | Constructive Algorithms, Shortest Path | Solved | D.cpp |
| E | 1 | Constructive Algorithms | Solved | E.cpp |
| F | 2 | Constructive Algorithms, Brute Force | Solved | F.cpp |
| G | 4 | Bitmasks, DP | Upsolved | G.cpp |
| H | ||||
| I | 2 | Counting, DP | Solved | I.cpp |
| J | 3 | Inversions | Solved | J.cpp |
| K | 0 | DFS | Solved | K.cpp |
| L | ||||
| M | ||||
| N |
A. Adjacent Product Sum
重排一个环形数列，最大化重排后的相邻两数乘积之和。
由排序不等式，感性理解一下应该是大的挨在一起，小的挨在一起。
所以排序之后左右交替放就行了，复杂度 $O(n\log n)$ 。
*B. Binary Arrays and Sliding Sums
给定 $n,k$ , 考虑所有长度为 $n$ 的二进制序列 $a_0,a_2,\dots,a_{n-1}$ :
令 $f_i=\sum_{j=0}^{k-1}a_{(i+j)\mod n}$ 得到序列 $f_0,f_1,\dots,f_{n-1}$ ，求有多少个本质不同的 $f$ 。
$T\ (T\le 10^5)$ 组询问，每次问一对 $n,k\ (2 \le k < n \le 10^6 )$ 。
下述过程中，所有下标均在模 $n$ 意义下。
有 $a_i-a_{i-k}=f_i-f_{i-1}\in[-1,1]$ ，当不为 $0$ 时一定能确定 $a_i$ 和 $a_{i-k}$ 的取值，否则两者可能同为 $0$ 或同为 $1$ 。
按照间隔为 $k$ 分组，会分成 $g=gcd(n,k)$ 个“环”，每个环长为 $n/g$ 。
每个环中只要有一个位置能确定（有一个 $f_i-f_{i-1}\neq 0$ ），整个环的取值都能确定。
考虑每个环对 $f$ 的贡献，容易发现对于每连续 $k$ 个位置，每个环都恰好占走了 $k/g$ 个位置。
因此对于某个 $a$ 数列，我们去考虑和他 $f$ 数组一致（冲突）的数列的特征，按照环考虑：
- 对于可以从 $f$ 唯一确定的环，显然这些位置必须和 $a$ 保持一致。
- 否则是全 $0$ / 全 $1$ 环（称作特殊环），由于每个环对 $f$ 的贡献位置个数一致，所以只要全 $1$ 环的“环个数”一致即可。
因此我们按 $f$ 划分出等价类：特殊环位置的集合一致（个数+下标），全 $1$ 环的个数一致，非特殊环对应位置完全一致。
因此对应特征计数：枚举特殊环数 $k$ ，特殊环下标集选法 ${g\choose k}$，全 $1$ 环个数选法 $(k+1)$ ，非特殊环方案数 $(2^{n/g}-2)^{g-k}$ 。
$$
\begin{array}{ll}
ans &= \sum_{k=0}^g(k+1){g\choose k}(2^{n/g}-2)^{g-k}\\
&= \sum_{k=0}^g{g\choose k}(2^{n/g}-2)^{g-k}+ \sum_{k=0}^g k\times \frac{g!}{k!(g-k)!}\times (2^{n/g}-2)^{g-k}\\
&= \sum_{k=0}^g{g\choose k}(2^{n/g}-2)^{g-k}+ g\sum_{k=1}^g {g-1\choose k-1}\times (2^{n/g}-2)^{g-k}\\
&=((2^{n/g}-2) + 1)^g + g\times ((2^{n/g}-2) + 1)^{g-1}
\end{array}
$$
快速幂计算即可，复杂度 $O(T\log n)$ 。
D. Distance Parities
一个 $n\ (n\le 500)$ 个点的无向图，给定任意两点最短路奇偶性，构造一个图符合要求。
构造一个图 $G$ ：对于任意两点，给定性质中如果要求是奇数距离就给两点间加一条边，否则不加。
证明：这个图 $G$ 符合要求 $\Leftrightarrow$ 存在一个图 $G’$ 符合要求。
左推右显然，证明右推左，若 $G’$ 符合要求，那么对于任意点对 $u,v$ ：
- 若距离为奇数，则在 $G$ 中两点距离为 $1$ 符合要求；
- 若距离为偶数，则必然存在一个点 $w$ ，在 $G’$ 中到两个点距离为奇数（例如 $u\to v$ 最短路上，除掉 $u,v$ 的第一个点），则在 $G$ 中 $w$ 和两个点都有一条边，因此 $G$ 中两点距离为 $2$ 符合要求。
因此判断 $G$ 是否合法即可，Floyd-Warshall 复杂度 $O(n^3)$ 。
E. Excellent XOR Problem
长度为 $n\ (n\le 10^5)$ 的数列 $a_i\ (0\le a_i< 2^{30})$ ，将数列划分成多于一段，使得每段异或和两两不同。
如果全部异或和不为 $0$ ，任意切分两段异或和不同。
否则考虑从左往右第一个不为 $0$ 的数字 $a_x$ ：
- 对于某个 $p\in[x+1,n-1]$ ，如果 $[x+1,p]$ 异或和不为 $0$ 也不为 $a_x$ ，那么找到了一种分三段的方法。
- 否则，数列中除了 $0$ 以外，是偶数个 $a_x$ ，这种情况一定无解。
所以找到 $a_x$ 之后扫一遍就可以了，复杂度 $O(n)$ 。
F. F*** 3-Colorable Graphs
给一个连通二分图 $K_{n,m}\ (2\le n,m\le 10^4)$，问最少加多少边使得这个图不能三染色。
不加边，二分图可以二染色。
加一条边，随便把这条边的一个端点染成第三种颜色就保证了相邻不同，此时可以三染色。
加两条边，如果有公共点，把一个公共点染成第三种颜色；否则四个不同的端点如果构成了 $K_4$ ，则需要四染色，否则四个点中至少有一对点没有边相连，把这两个点都染成第三种颜色后，其他维持二分图染色不变，依然可以三染色。
加三条边，因为是连通二分图且两侧都有至少两个点，必定存在长度为 $3$ 的链，必能补成 $K_4$ ，需要四染色。
因此如果能加两条边补出 $K_4$ 答案就是 $2$ ，否则答案是 $3$ 。
因为二分图中不能有奇环，因此唯一的情况是图中存在四元环。
考虑暴力，枚举左侧点 $u$ ，枚举 $u$ 的邻居 $v$ ，枚举 $v$ 的邻居 $u’$ ，当 $u’\neq u$ 时对 $u’$ 累加计数器。
当遇到一个 $u’$ 被累计了两次的时候，就找到了答案。否则不存在四元环。
暴力复杂度是对的，对于每个 $u$ ，每个 $u’$ 只会枚举到 $O(1)$ 次，否则找到答案结束，因此复杂度是 $O(n^2)$ 的。
当然也可以直接上四元环计数，复杂度 $O(m\sqrt{m})$ 。
*G. Graph Problem With Small n
给一个 $n\ (2\le n\le 24)$ 个点的无向图，判断是否任意点对间存在从一个出发另一个结束的哈密顿路径。
设 $dp[S][u][v]=0/1$ 表示经过的点集为 $S$ ，起点为 $u$ 终点为 $v$ 的路径是否存在，这个dp是 $O(n^32^n)$ 的。
进一步设 $dp[S][u]$ 表示经过点击为 $S$ ，起点为 $u$ 的可能的终点集合，新 dp 的值相当于之前 dp 的值的状压。
初始化 $dp[{u}][u] = {u}$ ，求 $dp[S][u]$ 时考虑第一步走 $u\to v$ ，那么方程是：
$$
dp[S][u] = \bigcup_{v\in S} dp[S/{u}][v]
$$
枚举 $S,u$ 之后枚举 $u$ 邻居 $v$ ，现在复杂度降低到了 $O(n^22^n)$ 。
换个思路，直接考虑有哪些 $v$ 在 $dp[S][u]$ 中，我们考虑路径的最后一步 $w\to v$ ，需要保证 $w$ 在 $S/{v}$ 对应状态的可能终点中（即 $dp[S/{v}][u]$ 中），并且 $w$ 和 $v$ 有边相连。
预处理每个人的邻居集 $N_i$ ，条件等价于 $dp[S/{v}][u]$ 和 $N_v$ 有交，即方程是：
$$
dp[S][u] = \bigcup_{dp[S/{v}][u]\ \cap\ N_v\neq \emptyset} {v}
$$
枚举 $S,u,v$ 判断是 $O(1)$ 的，因此这个转移的思路复杂度也是 $O(n^22^n)$ 的。
这个转移的好处是 $dp[S][u]$ 的值只依赖于 $dp[*][u]$ ，换句话说，可以 $O(n2^n)$ 求出对某个特定 $u$ 的所有 dp 值。
考虑 $O(n2^n)$ 求出所有的 $dp[*][0]$ ，即从 $0$ 出发的所有可能的集合的可能的终点。
考虑一条 $u$ 开始 $v$ 结束的哈密顿路径，必定经过 $0$ ，点集可以拆成两段 $S$ 和 $U/S \cup {0}$ （互补集合都加上 $0$ ）。
因此对于 $dp[S][0]$ 中的每个点 $u$ ，都可以和 $dp[U/S\cup{0}][u]$ 中的每个点 $v$ 匹配。
再次使用状压的思路，设 $ans[u]$ 表示 $u$ 出发可能的哈密顿路径终点集合。
枚举 $S$ ，枚举 $S$ 中的点 $u$ ，令 $ans[u] = ans[u] \operatorname{or} dp[U/S\cup{0}]$ 即可。
这样总复杂度神奇的降到了 $O(n2^n)$ ，空间复杂度 $O(2^n)$ 。
由于 1s 需要的计算量达到了 2e8 所以需要比较精细的实现，实测不同的实现方法常数甚至有 5 倍的差距。
可能的卡常方法：
$S$ 不包含 $0$ 的状态是没有用的，所以可以删去一半的集合，$2^n\to 2^{n-1}$ 卡掉一半的常数。
多使用位运算及
__builtin系列函数加快枚举集合内元素，而不直接 $O(n)$ 枚举：
for (int ts = S, v; ts; ts &= ~-ts) v = __builtin_ffs(ts) - 1;
I. Increasing Grid
一个 $n\times m\ (1\le n\times m\le 2\times 10^5)$ 的矩阵，每个位置的数字在 $1\sim n+m$ 之间。
现给定一些位置的取值，问其他位置有多少种不同的合法填法，使得每行从左往右递增，每列从上到下递增。
观察发现 $A_{ij}$ 的值只能是 $i+j-1$ 或 $i+j$ ，选了 $i+j-1$ 左上角的所有数字就确定了，否则右下角所有数字都确定了。
因此所有数字分成两类，一类能推出所有左上角，一类能推出所有右下角，先把冲突无解的情况判掉。
因此存在一个从左下到右上的分界线，每次向上或向右，计数矩阵填法等价于计数分界线选法。
处理出来每个位置是必定在左上/必定在右下/都可以，然后从左下向右上dp分界线方案数，复杂度 $O(n\times m)$ 。
注意一个位置如果上方必须是边界就不能往右延伸了。
*J. Jewel of Data Structure Problems
给定一个排列 $(1\le n,q \le 2\times 10^5)$，支持交换两个位置，查询最长的子序列，其逆序对数为奇数。
结论大杂烩。
整体逆序数为 $0$ 的情况（排列为 $1,2,\dots,n$ ），答案为 $-1$ 。
如果整个排列逆序对数为奇数，答案是 $n$ 。
否则考虑每个数 $p_i$ 产生的逆序对数 $c_i$ （前面比他大的个数+后面比他小的个数），如果存在一个 $c_i$ 是奇数，删掉对应的 $p_i$ 即可，答案是 $n-1$ 。
否则所有 $c_i$ 都是偶数，考虑序列中的任意一个逆序对 $(p_i,p_j)$ ，这个逆序对在 $c_i,c_j$ 中都被考虑了一次，所以把这两个位置删掉，逆序对的减少量一定是奇数，所以答案最差 $n-2$ 。
于是只需要维护：
当前逆序数是否为 $0$ （排列是否为 $1,2,\dots,n$ ）：维护 $p_i\neq i$ 的个数，交换两个操作下可以 $O(1)$ 维护。
总逆序数奇偶性：考虑交换 $p_i,p_j$ ，容易发现 $p_k\ (k\in (i,j))$ 参与的逆序对数奇偶性不会发生变化（按值和 $p_i,p_j$ 的关系分三段讨论），而 $p_i,p_j$ 的交换必然导致增加/删除了一个由 $p_i,p_j$ 构成的逆序对，因此每次操作总逆序数奇偶性一定改变，即交换两个元素排列的奇偶性一定改变。而一个排列可以通过 $n-$ 环数次交换变成 $1,2,\dots,n$ ，所以其逆序对数的奇偶性与 $n-$ 环数相同，初始化复杂度 $O(n)$ 。
是否有一个 $c_i$ 为奇数（所有的 $c_i$ 的奇偶性）：考虑 $c_i$ 的计算方法，假设 $i$ 前面比 $p_i$ 大的数字有 $x$ 个，那么 $c_i=x+[p_i-1-(i - 1 - x)]=2x+p_i-i$ ，所以 $c_i$ 的奇偶性只和 $i,p_i$ 有关，只有交换两个的操作可以 $O(1)$ 维护。
总复杂度 $O(n+q)$ ，不需要任何数据结构，实在优雅。
K. King of Swapping
对于 $n$ 的排列，给定 $m$ 个操作 $a_i,b_i$ 代表如果 $p_{a_i}>p_{b_i}$ 则可以交换这两个数。
问使用给定的操作任意多次，是否能把任意一个 $n$ 的排列变成任意另一个 $n$ 的排列。
其实是问能否交换任意两个位置（反证即可），把操作看成有向边，也就是要判断图是否强连通。
判一下原图和反图 $1$ 是否都能到所有点即可（这是整个图强连通的等价命题），复杂度 $O(n)$ 。
1st Universal Cup, Stage 4: Ukraine