Difference between revisions of "2012 ACM-ICPC World Finals"

From EOJ Wiki
Jump to navigation Jump to search
Line 24: Line 24:
  
 
Solved by zerol & ultmaster. 04:18 (+2)
 
Solved by zerol & ultmaster. 04:18 (+2)
 +
 +
题意:给一个有向图,对于其中的任意两个结点 AB,要么 A 连向 B,要么 B 连向 A。问最少选几个点使得它们以及直接相连的点包括了所有点。
 +
 +
题解:可以证明点的个数很少(因为一定能够通过选择出度最多的点,使得一次选中超过一半的点),所以直接迭代加深搜索就好了。
  
 
== Problem F ==
 
== Problem F ==

Revision as of 13:29, 9 March 2019

Problem A

Unsolved.

Problem B

Solved by zerol. 01:36 (+)

这个才是签到。

Problem C

Solved by ultmaster. 02:20 (+)

Problem D

Solved by kblack. 01:16 (+)

题意:一个类似斐波那契的 01 串构造序列 F,求第 n 项包含多少次指定串。

题解:先对目标串建 kmp 自动机,状态 $(i,j)$ 表示现在是 j 状态,接受一个 $F_i$ 后,会转移到 $f_{i,j}$,同时匹配到 $g_{i,j}$ 次,对于 $F_0$ 和 $F_1$ 显然,之后就可以递推出所有值了。

Problem E

Solved by zerol & ultmaster. 04:18 (+2)

题意:给一个有向图,对于其中的任意两个结点 AB,要么 A 连向 B,要么 B 连向 A。问最少选几个点使得它们以及直接相连的点包括了所有点。

题解:可以证明点的个数很少(因为一定能够通过选择出度最多的点,使得一次选中超过一半的点),所以直接迭代加深搜索就好了。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by kblack. 03:04 (+)

题意:若干堆从小到大的的碟子,拆开和重新叠上,最少的步数整理成一堆。

题解:先分析答案的计算,假装原始堆是颜色,那么使用的步数等于 $2*(C+1)-n-1$,其实 $C$ 是从上到下颜色的变化次数。对于同一种大小的碟子,变化数已经固定了,关键是不同的大小之间是否能减少变化数,相邻每对长度都有一些可以用,除了一种大小全是同一种颜色外,两边的颜色都要不同(相同并不会更好),对于可以用的颜色序列正反搞一搞(超过三种的一定好),还剩能用的都是好的。

Problem L

Unsolved.