2018 Multi-University, HDU Day 1

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by ultmaster. 00:41 (+2)

题意:求 $a$, $b$, $c$ 满足都是 $n$ 的因数也和为 $n$。

题解:各种筛各种暴力发现都布星。过了好久才开始考虑数学性质,好像只能分成 1/3 * 3 或者 1/2 + 1/4 + 1/4 其它都布星。

Problem B

Solved by ultmaster. 04:33 (+3)

题意:给若干个字符串,求一个排列使得最长可匹配括号子序列最长。

题解:先把每个字符串贪心匹配下,形成若干个形如 )))((( 的字符串,并分别记为二元组 $(a,b)$。接下来类似七月月赛大鱼吃小鱼。对 $b-a$ 正负性不同的分别排。对于 $b$ 比 $a$ 大的,按 $a$ 从小到大排;对于 $b$ 比 $a$ 小的,按 $b$ 从大到小排。不能证明。

ultmaster: 很早就开了这道题,在如何排序上产生了争执,卡了好久。尝试了好几种不同的排序,都不能顺利地通过对拍。最后 zerol 指出这个 $a$ 和 $b$ 其实就是需求和获利情况。在括号的泥沼中陷了太久的 ultmaster 终于领悟到此题方法可能与月赛题神似,终于通过了对拍。其实如果叫 kblack 来做的话,可能几小时前就过了。(可惜 kblack 在写 F。。。)

Problem C

Solved by zerol. 00:19 (+)

Problem D

Solved by kblack. 00:56 (+1)

Problem F

Unsolved. 04:50 (-1)

Problem G

Solved by zerol. 03:25 (+1)

Problem K

Solved by kblack. 00:28 (+4)