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

Upsolved by ultmaster.

题意：比较复杂。举个例子可能会比较明白。$n=5,a=2$ 的时候，有一个棋盘长这样：

其中 1 表示禁手，0 表示可以放车（横竖攻击）。求共有多少种方法可以放互不攻击的车。

题解：方法似乎很多。我的方法似乎稍微优于题解的方法，复杂度是 $O(a^2 + a \log n)$，做法如下：

考虑左下角的三角形多出来的一块 $a-1$ 的上三角形，这一块的方案数可以用 $dp(i,j)$，$i$ 表示列数（从左往右，因为左边的行数少，所以知道了左边放几个可以逐步往右推），$j$ 表示放了几个车。转移方程是 $dp(i,j)=dp(i-1,j)+dp(i-1,j-1) (i-j+1), dp(i,0)=1$。

枚举左下角那个三角形里放了几个东西，然后左下角就不能放东西了，于是变成了这样：

如果左下角放了若干个东西，那么就要删掉若干行若干列，因为那些行和列已经没有用了。比如放了 1 个，就会变成这样：

最后计算剩下的方案数，对于左下角禁手区放的东西个数运用容斥（因为一个都不能放，把放的情况减掉就好了）。具体推导过程不想再说明，式子如下：

$ax = \sum_{i=0}^b (-1)^i (b-i)^{n-a} (b-i)! (\binom{b}{i} ^2 i!)$, where $b=a-taken$.

$\binom{b}{i} ^2 i!$ 是左下角的放错的东西的方案数。式子写错了一个地方 ($n-a$ or $n-b$)，调了好久。标程的方法不一样，也很难看懂，也没法拍。最后手算出来了。

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 的帮助下艰难地过了。