Difference between revisions of "ACM-ICPC 2015 Asia Tsukuba Regional"

From EOJ Wiki
Jump to navigation Jump to search
Line 46: Line 46:
  
 
Solved by zerol. 03:31 (+)
 
Solved by zerol. 03:31 (+)
 +
 +
题意:给一个字符串 s,求所有 s 是其子序列的最短回文串中第 k 大的。
 +
 +
题解:首先用 dp 求出每个区间扩展成回文的最小代价和方案。然后按位枚举求出第 k 大。

Revision as of 11:04, 7 October 2018

Problem A

Solved by zerol. 00:15 (+)

温暖的签到。

Problem B

Solved by zerol & ultmaster. 00:24 (+)

题意:求最小距离,使得两块板之间可以塞下题给的所有木棍(不能交换顺序)。

题解:贪心往左放即可。依次计算每根木棍最左可以放到哪儿。

Problem C

Solved by ultmaster. 01:39 (+4)

题意:你在一个图上走。每次老大哥会从预先准备好的三个数中挑一个,然后你必须要走这么多步,你只能决定怎么走。你走投无路或者死循环了就输了。求你从起点到终点,在最坏情况下,要几轮?

题解:典型的博弈 DP。然而会有出现环的情况,在某些情况下某些点会算不对。不知道怎么搞……(其实是因为之前有个题没补)

在尝试了若干假算法之后,ultmaster 提出要不把这个东西迭代 1000 轮。然后就……顺利地 AC 了?

Problem D

Solved by kblack. 01:42 (+)

题意:在一个矩形内,每个人有一个直角的视野,在墙上挂钟使得每个人都能至少看到一个钟。

题解:直角视野对应周长上的一个区间,然后就是一个在环上丽娃河装路灯的问题。我们枚举第一个钟的位置,之后贪心地尽量靠后安装。

Problem E

Solved by ultmaster. 03:50 (+)

Problem F

Solved by kblack. 04:22 (+9)

题意:$p$ 个进程,$r$ 种资源,判断从哪一次资源分配后无法靠安排之后的顺序解决死锁。

题解:无法避免死锁的点存在二分性,因为能跑完的进程一定先跑完更好,通过类似 [1] 的方式贪心判断是否能全部跑完,需要注意一些边界情况。

Problem G

Solved by zerol. 03:31 (+)

题意:给一个字符串 s,求所有 s 是其子序列的最短回文串中第 k 大的。

题解:首先用 dp 求出每个区间扩展成回文的最小代价和方案。然后按位枚举求出第 k 大。