2019 Multi-University,HDU Day 1

Problem A

Upsolved by Xiejiadong.

题意：给长度为 $N$ 的空格染色，有一些限制要求一些区间中出现的颜色数量，求方案数。

题意：谁能想到，$O(T\cdot n^4)$ 的复杂度稍微优化一下卡卡常就能进去。

用 $f[i][j][k][l]$ 分别表示四种颜色出现最后的位置，已知这四个信息，我们只需要查询限制的右端点是 $max\{i,j,k,l\}$ 的是否满足要求就好了。

这样开数组是会 MLE 的，我们要强行滚动一下，不妨假设 $i>j>k>l$ 即可，用维度 $i$ 滚动。

Problem B

Upsolved by Weaver_zhu. (-1)

Problem C

Unsolved.

Problem D

Solved by Xiejiadong. 01:55:24 (+)

题意：给出每个小车距离终点的距离、车的长度和车的最快速度。求最后一辆车头到达终点的最少时间。要求本来排在后面的车不能冲到前面去。

题解：二分答案。考虑在时间 $mid$ 的时候，车最多能到达的地方。

显然第一辆车全速开，如果后面的车在时间 $mid$ 的时候冲到了前面的车的后面，说明在某个时刻这辆车已经追上了前车，那么这辆车肯定和前辆车连续排布。

如此考虑最后一辆车是否超过了终点即可。

Problem E

Solved by Kilo_5723. 01:45:39 (+1)

Problem F

Upsolved by Xiejiadong. (-1)

题意：要输出目标串，有两个选择，可以花费 $p$ 在字符串末尾输出任意字符，或者花费 $q$ 复制一段已经输出的子串到末尾，求输出目标串的最小代价。

题解：考虑如果以 $i$ 结尾字符串可以通过复制得到，那么一定存在一个或者多个 $j$ 满足 $s[1\cdots j]$ 中存在子串 $s[j+1\cdots i]$ ，显然，我们需要的是这样的 $j$ 中最小的来转移，我们令这样的 $j=g[i]$。

于是可以得到 dp 方程就是两部分构成， $dp[i]=min\{dp[i-1]+p,dp[g[i]]+q\}$ 。

问题关键就是怎么快速的得到 $g[i]$ ，考虑用 SAM 来维护， SAM 的维护都是通过增量构造的。

假设当前已经得到了 $s[1\cdots j]$ 中存在子串 $s[j+1\cdots i]$ ，现在新加入字符 $s[i+1]$ ：

• 如果从当前状态直接能够转移到 $s[i+1]$ ，直接转移即可，此时 $g[i+1]=g[i]=j$ ；

• 如果不能直接转移，也就是 $s[1\cdots j]$ 中不存在子串 $s[j+1\cdots i+1]$ ，我们需要从字符 $s[j+1]$ 开始不断地向 SAM 插入字符，以获得子串 $s[j+1\cdots i+1]$ ，每次插入新字符以后，状态通过 link 跳到当前状态，判断能够转移即可。

Problem G

Unsolved.

Problem H

Solved by Xiejiadong. 04:15:04 (+1)

题意：求长度为 $K$ 的 $26$ 个字母出现次数在规定的区间内的字典序最小的子序列。

题解：贪心地按位确定。

按照字典序判断这一位是否可以放，如果可以放一定放最前面的一个字母。

判断的方法是，不能超过这个字母出现次数的上限，在这个字母之后的其他字母数量能够满足剩余需要满足的数量（这部分可以先预处理）。

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Unsolved.

Problem M

Unsolved. (-19)