MIPT 2016 Warsaw U Contest (ITMO Day 1)

Problem A

Upsolved by kblack.

题意：用光线打砖块，问全部打掉的时间。

题解：如果没有砖块，光线在墙上会反射 $O(N)$ 次，把每段的开头和方向都模拟出来备用，光线的 $(位置, 反向)$ 作为序号。每个砖块一共有 $8$ 种光线可以打到，求出每种的序号扔进 set 里面备用。模拟光线，注意正反方向，从 set 里面慢慢删。

其实从第二发开始就是对的，数组开小天知道第三组就是大数据，assert 了 $20$ 多发随便改改 $N$ $^{tm}$ 才发现。

Problem B

Upsolved by ultmaster. 04:59 (-8)

题意：求能通过正向边达到的点的集合和通过反向边达到的点的集合的并集是所有点集的，有哪些点。

题解：先缩点，然后转换成拓补序上的问题。对于一个点只考虑拓补序比它小的点是否能都到达它（另外一边是对称的问题）。这个判断的充要条件是，删去所有指向右边（拓补序比它大）的点的边后，左边的点出度都大于 0。这样，左边的点总能通过一定的路径达到这个点。

比赛的时候过度纠结能达到的点的数量，而没有考虑这个题实际上不是问数量，而是问「是不是」。

Problem C

Unsolved.

Problem D

Upsolved by ultmaster | zerol.

题意：将所有子集以子集和为第一关键字，子集内的下标的字典序为第二关键字排序，求第 $k$ 大的。

题解：

ultmaster: 按照一定顺序生成所有子集，然后 Dijkstra。生成的方法是：对当前的集合：

• 将当前的集合的最后一个（最大的）元素删除，加上更大（紧接着）的一个；
• 直接加上更大的一个。

zerol: 参考了标程，实在是炫酷。

• 生成的方式同上。但是只记录：价值，最大元素，最小下标，除去最后一个的最小下标。
• 其中除去最后一个的最小下标是为了方便转移。（因为可能会把最后一个元素删除）
• 然后利用优先队列得到前 $k$ 大的信息。但是不能直接知道第 $k$ 大的包含了哪些元素。
• 每次输出下标最小的，然后需要得到剩下的是第几大。
• 设原来价值为 $C$，最小下标为 $i$，去掉下标最小的之后价值为 $C'$。那么当前在所有价值为 $C$，最小下标为 $i$ 中的排名和剩下的在价值为 $C'$ 最小下标为 $i +1$ 的排名是一致的，将 $k$ 减去两者起始位置的差值即可。

Problem E

Unsolved.

Problem F

Upsolved by ultmaster.

题意：取出一些元素，元素的个数是 $d$ 的倍数，使得剩下的元素异或和为 $0$ 。问有多少种取法。

题解：先从小到大排序，$dp(i,j,k)$ 表示对于前 $i$ 个，取出的元素数量 $\bmod d = j$ ，异或和为 $k$ 的方案数，显然答案就是 $dp(n,0,0)$。对于第一维做滚动，对于第三维，这样的做法的正确性基于所有数的和不会太大，均摊下来是正确的。

Problem G

Solved by zerol. 01:19 (+)

题意：给定一颗树，求一条链使得 $2+\sum (d(u)-2)$ 最大（$d(u)$ 为结点 $u$ 的度数），输出这个值。

题解：很常规的树形 dp。但是要注意某个点只有一个儿子或者没有儿子的情况。

Problem H

Upsolved by zerol.

题意：求一个点到另一个点不经过起点和终点，中间的点和边可以经过任意多次的，一定长度的路径的方案数。询问特别多。

题解：

$allPath(u,v,l)=\sum_{i=1}^{n} allPath(u,i,d-1) hasEdge(i, v)$, $startNoCircle(u,v,l) = allPath(u,v,l) - \sum_{i=1}^{l-1} allPath(u,u,i) startNoCircle(u,v,l-i)$, $circleOfUWithoutV(u,v,l) = allPath(u,u,l)-\sum_{i=1}^{l-1} allPath(u,v,i) circleOfUWithoutV(v, u, l - i)$, $ans(u,v,l) = startNoCircle(u,v,l) - \sum_{i=1}^{l-1} ans(u,v,i) circleOfUWithoutV(v,u,l-i)$.

Problem I

Solved by zerol. 02:26 (+)

题意：从 1~n 的最小排列到当前排列依次变化，求每一步需要的最小交换次数之和。

题解：打表找规律。设当前是第 $k$ 个排列，那么答案为 $\sum_{i=0}^\infty \lfloor \frac{k}{(2i)!} \rfloor$。

Problem J

Unsolved.

题意：有一系列的堆对（每一对有两个堆）。先手可以从任意一堆中移除任意多的石子，后手可以在同一对石子中将一堆中的某一些移到另一堆中。先手希望尽快结束，后手希望进行尽可能长的时间。问轮数。

Problem K

Solved by ultmaster. 03:20 (+3)

题意：求一个最长的子序列，形如 $(a_1,a_1,a_2,a_2,\ldots)$。

题解：如果没有内存限制 32 MB 的话，显然有状态转移方程：$dp(i,j)=\max\{dp(i-1,j),dp(i,j-1),dp(back(i)-1,back(j)-1)+2\}$。但这样的状态显然是存不下的。我们考虑对于每一个状态在转移时所需要的状态。注意第三个状态，对于每一列，由于这一列上的数字是固定的，所以在经过多行之后，只要不遇到这个数，这个状态就不会改变。当更新时，从大往小刷新就好了。注意 $dp(i,j-1)$ 转移时要从小往大刷新。