Jagiellonian U Contest (ITMO Day 3)

Problem A

Solved by kblack. Upsolved by ultmaster. 02:33 (+1)

题意：将一个多重集分成两个集合，使得两个集合异或和的差的绝对值尽可能小。

题解：如果全体异或和为 $0$，那么显然答案就是 $0$。否则让较大的那个集合的异或和在全体异或和非零的位尽量保持 $100000\cdots$ 的形状。方法是求出所有数的异或线性基，从高位往低位贪心即可。如果某一位全体异或和为 $0$，那么直接将该位 ignore 掉。

比赛的时候只有 kblack 会线性基。不过现在我也会了（误）。

Problem B

Solved by ultmaster. 00:25 (+3)

题意：已知所有子集和，将原序列还原出来。

题解：选出最小的，一定是最小的元素，然后其余元素就能两两配成差为最小的元素的对，然后长度减半，迭代解决。

多校的时候有一道完全一样的题目。然而这道题还是三发。

Problem C

Solved by zerol. 01:45 (+)

题意：序列 $i_1<i_2<\ldots<i_k$ 满足 $a_{i_1} < a_{i_2} < \ldots < a_{i_k}, b_{i_1} < b_{i_2} < \ldots < b_{i_k}$，求最大的 $k$。

题解：树套树，查询的是左下方的一块区域内的最大值。但这样做空间复杂度是 $O(n \log^2 n)$，据说过不了（但是我们突然过了）。有空间复杂度 $O(n)$ 的做法待补。

zerol: 空间一手抖开小了，所以没爆内存。（所以是数据造弱了，还是代码写得好？）所以 CDQ 分治好，也更加好写，最重要的是线性内存。[伪题解]

Problem D

Unsolved.

Problem E

Solved by zerol. 03:08 (+2)

题意：有 $k$ 个长度为 $n$ 的 01 串等待鉴别。每次可以询问某一个位置上是 0 还是 1，可以根据上一次的答案进行追问。求全部鉴别出来的最小询问次数。

题解：由于 $n$ 不大，直接对每一位置三种状态：未知、已知 0、已知 1。每一种状态组合都恰好对应了一个子集。如果子集中元素恰好为 1 个，那么就需要 0 次。难点在于还有一种子集中没有元素的情况需要另外判断。

ultmaster 写错了，虽然赛后调了一会就过了。然而 zerol TLE 的程序 long long 改 int 突然 AC 了，于是，摊手。。。

Problem F

Solved by zerol. 00:15 (+)

签到。

Problem G

Upsolved by kblack.

题意：有一个 $2^n$ 个顶点的完全图，顶点标号为 $0$ 到 $2^n-1$。两个顶点之间边权是两个顶点标号位异或的二进制中 1 的个数。现求该图的最小生成树。

题解：考虑 Prim 算法的过程。每次新加进来一个点，就用广搜将这个点到所有点的距离进行更新。由于距离变化次数不超过 $n$ 次，所以总的复杂度是 $O(n 2^n)$ （均摊）。优先队列会超时，需要对每个距离开桶。

比赛的时候一直在想 Kruskal 的过程。据说 Kruskal 也能做？

Problem H

Upsolved by ultmaster.

题意：从左上走到右下，只能向右向下走；再回到左上，只能向左向上走，经过的格子被染色。现在已知每行每列的染色格子个数，求方案数。

题解：知道了格子个数之后，形状是唯一的。构造出来就好了。两个点从左上角开始向右向下走，分两种情况讨论：

• 如果两个点在同一行内，动靠左的点，优先向下动。
• 如果两个点不在同一行内，动靠右的点，优先向右动。

实际上这两种是同一种情况，只是旋转了而已。动的时候要判断这个点以前有没有走过等等。用 set 似乎很容易超时（虽然有一次提交不小心卡过去了），需要 hash 以后加 unordered_set。似乎有 $O(n)$ 的做法，但不想去想。时限是玄学。需要读入优化和优秀的常数。

Problem I

签到。

Problem J

Upsolved by kblack.

题意：给出了一个组合数 $n \choose k$ 的质因数分解，求 $n,k$。

题解：枚举 $n$，然后二分出 $k$ 可能的范围（通过对数计算），然后用随机数取模验证成立。

已经有好几题用到随机质数取模了。这个思想一定要注意。这个题刚开始从数论的角度考虑，只能说题目太有迷惑性了。

Problem K

Upsolved by zerol.

题意：问树上有多少无序三元组对使得两两距离相等。

题解：

• 标程给的是在 bzoj3522 的基础上加了强力剪枝，将递归深度限制在子节点深度的第 3 大，复杂度还是 $O(n^2)$ ，但是常数很小。（kblack 造了个菊花图把它卡掉了。）这个优秀的假算法把 bzoj4543 和 这道题过都掉了。
• 真算法的 dp 和复杂度分析参照网上 bzoj4543 题解，dp 的过程相当于将子节点的 dp 结果合并，然后这里使用启发式合并，将其他的 dp 合并到下标范围最大的 dp 上（也就是深度最大的子节点）。

Problem L

Solved by ultmaster. 01:36 (+2)

题意：求两个字符串允许有 $k$ 个位置不同的最长公共子串。

题解：平移一个字符串，然后将相邻的相同的位置合并为一个区间，然后就是经典的滑动窗口。

写错了好几次，差点对了拍，在 kblack 的帮助下艰难地过了。