2019 Multi-University,HDU Day 8

Problem A

Upsolved by Kilo_5723.

题意：判断一个图是否可以是正方体的展开图。

题解：首先根据面积算出可能是正方体的边长，再以每一个方格作为正方体上特定的一个位置尝试把图铺在正方体上。按 dfs 序模拟在正方体上移动的过程，注意方向。如果没有冲突就可以是正方体的展开图。

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 04:20:32 (+3)

Problem D

Solved by Xiejiadong. 03:50:43 (+)

题意：要求不重不漏的走完 $n\times m$ 的所有格子，每一次的步长必须满足 $>1$ 且 $<3$ 。

题解：对于 $n>m$ 的 swap 一下，我们就只需要处理 $n\le m$ 的情况。

显然，$n<2$ 或者 $m<3$ 的时候无解，有一个坑点是 $n=1,m=1$ 的时候有解。

分两部分进行。

第一次从最后一行进行到第三行，偶数行走 $2,4,6,\cdots $ ，奇数行走 $\cdots 5,3,1$ ，在行与行交接的地方，显然步长为 $\sqrt{2}$ ，满足要求；

然后直接走到 $(1,1)$ ，在继续走第二行的偶数位置，返回第一行走奇数位置，在 $(1,3)$ 处结束；

从 $(2,1)$ 出发，步长 $\sqrt{5}$ ；

依次走前两行剩下的位置 $(1,2),(2,3),(3,4),\cdots $ ，每次步长都是 $\sqrt{2}$ ；

剩下的，奇数行从大到小走偶数位置，偶数行从小到大走奇数位置就好了。

Problem E

Solved by Xiejiadong. 02:55:46 (+2)

题意：求字符串中有多少子串满足均分成 $k$ 段以后，每一个子段都相同。

题解：如果一个字符串是最短循环节长度为 $x$ ，长度为 $len$ ，显然这一段的答案就是 $len-kx+1$ 。

所以我们只要找到所有的长度 $\ge kx$ 的循环串即可。

考虑枚举 $x$ ，每一次从一个位置 $i$ 开始向两边拓展，为了保证不重不漏，向前拓展的长度不能超过 $x$ ，每一次拓展的位置 $i$ 一定要与前一次距离至少 $x$ 。

这样直接枚举的复杂度是 $O(\frac{|s|}{1}+\frac{|s|}{2}+\cdots +\frac{|s|}{|s|/k})$ ，复杂度近似 $O(nlogn)$ 。

向右最多的拓展长度，显然就是求 $lcp(i,i+x)$ ，向左的就是在反串上类似的求。

F0RE1GNERS 的 SA 板子狂 TLE 不止，被演了 2h 。

Problem F

Solved by Kilo_5723 && Xiejiadong. 03:06:21 (+2)

题意：在一棵树上，A 决定棋子的初始位置，两个玩家轮流移动棋子在树上移动且不能经过走过的点，玩家 A 把棋子移动到第 $i$ 个点时获得 $a_i$ 的权值，B 移动时则会获得 $b_i$ 的权值，若两名玩家都选择最佳策略，求两名玩家获得权值的差。

题解：首先考虑以 $1$ 为根，从每个点只能往子节点移动时 A,B 分别能获得的权值差，这一部分可以用树形 DP 求解。我们发现，我们可以 $O(1)$ 从以结点 $u$ 为根的答案推到以 $u$ 的子节点 $v$ 为根的答案。按 dfs 序从 $1$ 节点推出每一个节点出发时的权值差，对所有节点让 A 出发的答案取最大值。

Problem G

Unsolved.

Problem H

Solved by Kilo_5723. 04:26:28 (+2)

题意：给定一个有边权的有向图，求其中边权和最小的长度为 $k$ ($1 \le k \le 5$) 的链。

题解：如果这是一个 DAG，我们可以在 $O(n*k)$ 的时间里算出答案。但由于 $k$ 很小，我们发现，如果我们每次都对所有点随机排序，那么假设最短链存在，最短链在这个图上是顺序的概率是 $\frac{1}{720}$，我们只要随机排序 $3000$ 次就基本能保证最短链上的点一定在其中某次是顺序排列的，而如果是顺序排列，那么 dp 一定能给出正确答案。所以对所有点的顺序随机排列 $3000$ 次，把其中所有的逆序边删除，计算每一次的答案，对所有答案取最小值就是最终答案。

Problem I

Solved by Kilo_5723. 01:38:27 (+2)

题意：给出两个平面上的矩形，求矩形将平面分成了多少区域。

题解：开始的时候尝试枚举情况，但是枚举情况太复杂了，所以放弃，转为离散化 BFS。

Problem J

Solved by Xiejiadong. 00:07:46 (+)

温暖的签到。靠着开题直觉和手速，抢了一血。

Problem K

Solved by Kilo_5723. 00:26:03 (+)

题意：$n$ 个班级，第 $i$ 个班有 $a_i$ 个学生和 $b_i$ 杯奶茶，学生不能喝自己班级的奶茶，求最多有多少学生能喝到奶茶。

题解：考虑限制条件在什么时候会生效，那么肯定是 $n$ 个班级只剩下某个班级既有学生没喝奶茶，又有奶茶没被喝掉。枚举每一个班作为这个班级的可能性，再加上一般情况就是答案。