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

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by one other user not shown)
Line 35: Line 35:
 
== Problem F ==
 
== Problem F ==
  
Unsolved. (-3)
+
Upsolved by zerol. (-3)
 +
 
 +
明明做过这道题,但为什么没过呢?
 +
 
 +
题意&题解:https://zerol.me/2018/05/09/HDU-3842/
  
 
== Problem G ==
 
== Problem G ==
Line 44: Line 48:
  
 
Solved by zerol. 04:39 (+1)
 
Solved by zerol. 04:39 (+1)
 +
 +
题意:给一个连通无向图,要求选择一些点,使得删除图中任意一个点之后,所有点都可以由点集中的某个点到达。
 +
 +
题解:考虑每个点双,如果这个点双上有两个及以上割点,那么这个点双内不用选任何点。否则如果只有一个割点,那么在除了那个割点的其他点中随便选一个。如果整个图本身就是一个点双那么就特判。
 +
 +
Z: 解法有些魔幻,评测机表示对。这个算法是不断找反例,打补丁之后得出的,似乎,还挺逼真的。
  
 
== Problem I ==
 
== Problem I ==
  
 
Solved by kblack. 04:06 (+1)
 
Solved by kblack. 04:06 (+1)
 +
 +
题意:八方向跑路,多个木乃伊按最优距离追你,问能活几秒。
 +
 +
题解:时间显然具有二分性(一旦追上就一直可以追上),对于一个时间,我们检查所有木乃伊范围(矩形)的并是否完全包含了自己的移动范围,全包含了就没了,否则就还有命。
  
 
== Problem J ==
 
== Problem J ==

Latest revision as of 10:58, 3 March 2019

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by zerol. 00:46 (+)

签到

题意:图像识别

题解:数内部联通块个数

Problem D

Unsolved.

Problem E

Solved by ultmaster. 03:53 (+)

曼哈顿距离转切比雪夫距离签到。

U: 题目本身非常傻逼,没什么好说的。但是:

  • 我读错了题。两次。
  • kblack 搞出了某些非常玄幻的做法,导致一度不会做这个题。
  • 好在稳健的 Z 给出了这题是签到题的指导性意见,然后就过了。

Problem F

Upsolved by zerol. (-3)

明明做过这道题,但为什么没过呢?

题意&题解:https://zerol.me/2018/05/09/HDU-3842/

Problem G

Unsolved.

Problem H

Solved by zerol. 04:39 (+1)

题意:给一个连通无向图,要求选择一些点,使得删除图中任意一个点之后,所有点都可以由点集中的某个点到达。

题解:考虑每个点双,如果这个点双上有两个及以上割点,那么这个点双内不用选任何点。否则如果只有一个割点,那么在除了那个割点的其他点中随便选一个。如果整个图本身就是一个点双那么就特判。

Z: 解法有些魔幻,评测机表示对。这个算法是不断找反例,打补丁之后得出的,似乎,还挺逼真的。

Problem I

Solved by kblack. 04:06 (+1)

题意:八方向跑路,多个木乃伊按最优距离追你,问能活几秒。

题解:时间显然具有二分性(一旦追上就一直可以追上),对于一个时间,我们检查所有木乃伊范围(矩形)的并是否完全包含了自己的移动范围,全包含了就没了,否则就还有命。

Problem J

Solved by ultmaster. 02:53 (+3)

题意:300 * 1000000 的 01 背包,求方案,要物品数量尽量少,同时字典序最大。

题解:发明了若干种假算法之后,直接开了个 300*1000000 的数组存储所有点的最短路径。

Problem K

Solved by ultmaster. 01:28 (+)

题意:求一个最小的间距使得多边形刚好能卡过。

题解:求完凸包,旋转卡壳。但是数据范围太小了根本不需要。