Difference between revisions of "2019 Multi-University,HDU Day 1"

From EOJ Wiki
Jump to navigation Jump to search
Line 1: Line 1:
 
== Problem A ==
 
== Problem A ==
  
Unsolved.
+
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 ==
 
== Problem B ==

Revision as of 05:35, 23 July 2019

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

Unsolved. (-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

Unsolved. (-1)

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)