CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 HDUMUTC2020-03 LAYOUT”
学业稍微有点重,趁着假期和几个朋友打打比赛复健一下。
不是很在状态,所以难题这里基本上都不会有,基本上都是签到题。
http://acm.hdu.edu.cn/contests/contest_show.php?cid=881
给定一个数列 $A_n$,你可以把相邻的数任意合并成它们的和,要使得若干次操作后数列中出现尽量多 $p$ 的倍数。
贪心。
等价于选出尽量多不交的区间,使得和是 $p$ 的倍数。
经过前缀和处理后等价于 mod $p$ 相等的两个数匹配。
从左到右贪心即可。
n 个人,每个人是 fpd 或者 oscar。
每个人对应一个点,每次操作会在某两个点之间连边。图初始为空。
一个 ACM 队定义如下:
求每次操作完,在 n 个人中选出一个 ACM 队的方案数。
维护信息的并查集。
不知道这个题谁出的,就繁琐,一大堆无聊分类讨论
感谢队友排雷
懒 癌 得 治
给一个 n 个点的完全图,边权在同一个值域内随机。
现在删去 k 条边,求删完之后最短路的最大可能值。
$ 3 \leq n \leq 50, 1 \leq k \leq \min(n - 2, 5), T \leq 100 $
边权随机,最短路包含边数就那么点,枚举删一条变成子问题。暴力搜搜搜!
复杂度 $ O(n^2) + e^{k\epsilon} $,其中 $\epsilon$ 为最短路边数自然对数的期望。
写个 n^2 Dijkstra 把 j 写成 i 卡了 10 分钟丢了两发罚时
给一个球在正三角形边框里,可视为质点,有个初速度。球和边框发生完全弹性碰撞。保证球不会到达正三角形的任意一个角。
事实上不用算碰撞反射角度,这样比较麻烦
正三角形在平面空间可以密铺的。“反射”过去就行。
二分答案,看对应时间内和多少条边界相交即可。
给一个带通配符的括号序列。通配符可以换成左括号,右括号,或空字符。
你需要把所有通配符换成字符,换完之后要是一个合法的括号序列,字符最少。
相同字符的情况下字典序最小。无结果输出”No solution!”。
$\sum n \leq 5 \times 10^6$
贪心。
括号序列合法的充分必要条件是:对任意一个前缀,其左括号数不少于右括号数;且对于任意一个后缀,其右括号数不少于左括号数。
依据这个条件设计算法。对于字典序的要求,我们把左括号的位置尽量提前。遇到一个通配符,将其入队;遇到一个不满足要求的前缀,从队首取出一个空位放上左括号。右括号的位置则尽量靠后。
待补题列表:
http://acm.hdu.edu.cn/showproblem.php?pid=6793
http://acm.hdu.edu.cn/showproblem.php?pid=6796
http://acm.hdu.edu.cn/showproblem.php?pid=6800