Overview

Links: 补题链接, 题面, 官方题解

Comment: 一堆思维题，证明都非常理性愉悦，赛中要大胆猜结论

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)\)，支持交换两个位置，查询最长的子序列，其逆序对数为奇数。

结论大杂烩。

1. 整体逆序数为 \(0\) 的情况（排列为 \(1,2,\dots,n\) ），答案为 \(-1\) 。

2. 如果整个排列逆序对数为奇数，答案是 \(n\) 。

3. 否则考虑每个数 \(p_i\) 产生的逆序对数 \(c_i\) （前面比他大的个数+后面比他小的个数），如果存在一个 \(c_i\) 是奇数，删掉对应的 \(p_i\) 即可，答案是 \(n-1\) 。

4. 否则所有 \(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)\) 。