Difference between revisions of "2019 ICPC World Finals"

From EOJ Wiki
Jump to navigation Jump to search
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Replay ==
 
== Replay ==
 +
 +
U:
 +
 +
* 上来先看 F,觉得是 DP 但是很难处理,跳;看了一眼 G,没什么思路,跳;期间有人爆交了 A,看了一眼 A 猜了一个假的不行的结论,交上去 WA 了。期间队友上机开始抢 J 的一血。
 +
* UoW 过了 E,跟 Z 一起看 E。Z 觉得是边双,打开板子一看大吃一惊:边双的板子不知道为什么不见了。心态崩了。我接着想 A,Z 发现 E 不用边双准备上机。K 还在抢 J 的一血。
 +
* 我上去把 A 敲了好在一遍过了。很快 J 有队伍过了,一血凉凉。遂开始写 E。
 +
* E 题写了无数个 bug,期间还修正了题意。我 D 和 G 都有算法了,G 一看就不怎么能过,而 D 是稳的,决定先写 D。
 +
* 这时我预言这场比赛四题才能有名次,一看现在才只有两题形势有点严峻。自我安慰说一个小时过一题就能有五题了。
 +
* E 题过了以后,我 D WA 了。让队友写了 H 和 J,双(三)双(三)自闭。三人卡三题。同时我们三个小时没有过题,感觉要冰了,心想能把手上的都过掉就不错了。
 +
* 三个半小时后,我 D 自救成功。K 的 H 经过对拍也爬出来了。只剩 Z 的 J 从 WA 变成了 T。本着『题数要紧,罚时没有』的心态开始大力优化。最后把一个 50 优化成了 log 50 卡着过了。
 +
* 这时比赛还剩下一小时,我开始写那个看起来就不怎么能过的 G,复杂度是 $O(n \sqrt{n} \log n)$。K 说 F 能做,试图抢机。
 +
* 我 G 很快就写完了,返回 WA。看了一会觉得没啥毛病,觉得可能是自然溢出哈希被卡了。试图改成模质数的哈希,返回 T 了。这时感觉已经没救了。
 +
* 最后半小时就是不知所措看队友敲代码。然而 F 到最后都没写完,我最后五分钟上去表演了一下改哈希参数爆交,比赛就结束了。
 +
 +
Z:
 +
 +
* 一开始看了 H,觉得能做,就是有点麻烦,而且刚好是 KBlack 比较擅长的题。KBlack 上机先开始写 J。
 +
* 出全场一血之后,我和 ultmaster 开始看 E,我觉得是边双,树的情况特判就好了。然后摸出板子,惊喜来了,Tarjan 那块(就是求割点和桥那块)全没了,反复确认,真没了,心态崩了,我还犹豫了一下要不要告诉正在上机的 KBlack。
 +
* 此时 ultmaster 表示 A 有个猜想,反正大家都过了,于是上去写,WA 了。一看题目和代码,发现假的不行,好在想出了真算法。有点麻烦,好在 ultmaster 稳健,过了。
 +
* 在写 A 的时候,我发现 E 可以不用边双,心态没那么崩了。之后上 E,样例过不了,发现还可能不连通,又套了个并查集,交上去 WA 了。然后发现题目的输出完全没注意,没排序,也没注意顺序,而且树的情况特判错了,WA 了一通会后过了。
 +
* 让 KBlack 写 H 去了,然后自闭了,期间 ultmaster 写了 D,也自闭了,然后我去重写 J 也自闭了。中途 KBlack 表示会 K(当时没人过),但是已经没有余地去尝试了。
 +
* 相继走出自闭。U 去写字符串了,很可能 T 的字符串,其实这题我应该会的,应该会的。期间 KBlack 写很可能写不完的 F,很遗憾。
 +
 +
K:
 +
 +
* 没了,没了。
  
 
== Problem A ==
 
== Problem A ==
Line 20: Line 46:
  
 
Solved by ultmaster. 03:36 (+3)
 
Solved by ultmaster. 03:36 (+3)
 +
 +
题意:有一个环,环上是很多种不同的颜色的左括号和右括号。要求一种切法使得有尽可能多的颜色满足是一个合法的括号序列。
 +
 +
题解:签到题 II,15 分钟写完,WA 了一年。对于每种颜色,使用 +1, -1 扫描,最低点就是合法的切割点。然后把合法的切割区间加进去汇总扫描线一下就好了。
 +
 +
无数个错误:
 +
 +
* 有可能这种颜色根本不可能合法(这个过不了样例)。
 +
* 有可能没有颜色合法。
 +
* 最终的最佳答案有可能不在扫描线的关键点上取到(不过按照 Z 说的那个方法写就不会有这个问题了,不知道为什么要执着地开两倍)。
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by zerol. 01:49 (+1)
 
Solved by zerol. 01:49 (+1)
 +
 +
题意:有些复杂。有一个无向图,要求在一些路口装死路的标志,问最少装几个。
 +
 +
题解:类似于拓扑排序,把度为 1 的点和边不断去掉,然后在那些去掉和没被去掉的点之间的边上装牌子。树的情况特判,就是把度为 1 的点相邻的边上装。
  
 
== Problem F ==
 
== Problem F ==
Line 36: Line 76:
  
 
Solved by kblack. 03:49 (+3)
 
Solved by kblack. 03:49 (+3)
 +
 +
题意:有向基环外向森林,求到每个点距离小于 K 的点数。
 +
 +
题解:分为环上的点和树上的点:树上的点用 dfs 和树状数组统计;环上的先处理出树上某个距离的点数,然后转两圈,错位加在树状数组上维护每个距离的点数;不连通连带导致大量傻逼问题。
  
 
== Problem I ==
 
== Problem I ==
Line 44: Line 88:
  
 
Solved by zerol. 04:09 (+8)
 
Solved by zerol. 04:09 (+8)
 +
 +
题意:每个人都有 k 个数字,排名就是数字和小于自己的人数 +1。问对所有数字取 min 后,每个人的排名最高是多少。
 +
 +
题解:对于每两个人,求出两者之间的相对排名变化的时间点(这部分有点麻烦,反正就是枚举相邻两个数字,然后解方程)。然后对于每个人,和其他所有人的排名变化的事件按时间排序,然后扫一遍。
 +
 +
zerol: 我也不知道重写 KBlack 的代码是不是正确的选择。我牺牲了时间复杂度换来了代码复杂度,然后 T 的生活不能自理,把一个 50 换成了 log50,然后常数优化了一通才过。
  
 
== Problem K ==
 
== Problem K ==
  
 
Unsolved.
 
Unsolved.

Latest revision as of 14:56, 6 April 2019

Replay

U:

  • 上来先看 F,觉得是 DP 但是很难处理,跳;看了一眼 G,没什么思路,跳;期间有人爆交了 A,看了一眼 A 猜了一个假的不行的结论,交上去 WA 了。期间队友上机开始抢 J 的一血。
  • UoW 过了 E,跟 Z 一起看 E。Z 觉得是边双,打开板子一看大吃一惊:边双的板子不知道为什么不见了。心态崩了。我接着想 A,Z 发现 E 不用边双准备上机。K 还在抢 J 的一血。
  • 我上去把 A 敲了好在一遍过了。很快 J 有队伍过了,一血凉凉。遂开始写 E。
  • E 题写了无数个 bug,期间还修正了题意。我 D 和 G 都有算法了,G 一看就不怎么能过,而 D 是稳的,决定先写 D。
  • 这时我预言这场比赛四题才能有名次,一看现在才只有两题形势有点严峻。自我安慰说一个小时过一题就能有五题了。
  • E 题过了以后,我 D WA 了。让队友写了 H 和 J,双(三)双(三)自闭。三人卡三题。同时我们三个小时没有过题,感觉要冰了,心想能把手上的都过掉就不错了。
  • 三个半小时后,我 D 自救成功。K 的 H 经过对拍也爬出来了。只剩 Z 的 J 从 WA 变成了 T。本着『题数要紧,罚时没有』的心态开始大力优化。最后把一个 50 优化成了 log 50 卡着过了。
  • 这时比赛还剩下一小时,我开始写那个看起来就不怎么能过的 G,复杂度是 $O(n \sqrt{n} \log n)$。K 说 F 能做,试图抢机。
  • 我 G 很快就写完了,返回 WA。看了一会觉得没啥毛病,觉得可能是自然溢出哈希被卡了。试图改成模质数的哈希,返回 T 了。这时感觉已经没救了。
  • 最后半小时就是不知所措看队友敲代码。然而 F 到最后都没写完,我最后五分钟上去表演了一下改哈希参数爆交,比赛就结束了。

Z:

  • 一开始看了 H,觉得能做,就是有点麻烦,而且刚好是 KBlack 比较擅长的题。KBlack 上机先开始写 J。
  • 出全场一血之后,我和 ultmaster 开始看 E,我觉得是边双,树的情况特判就好了。然后摸出板子,惊喜来了,Tarjan 那块(就是求割点和桥那块)全没了,反复确认,真没了,心态崩了,我还犹豫了一下要不要告诉正在上机的 KBlack。
  • 此时 ultmaster 表示 A 有个猜想,反正大家都过了,于是上去写,WA 了。一看题目和代码,发现假的不行,好在想出了真算法。有点麻烦,好在 ultmaster 稳健,过了。
  • 在写 A 的时候,我发现 E 可以不用边双,心态没那么崩了。之后上 E,样例过不了,发现还可能不连通,又套了个并查集,交上去 WA 了。然后发现题目的输出完全没注意,没排序,也没注意顺序,而且树的情况特判错了,WA 了一通会后过了。
  • 让 KBlack 写 H 去了,然后自闭了,期间 ultmaster 写了 D,也自闭了,然后我去重写 J 也自闭了。中途 KBlack 表示会 K(当时没人过),但是已经没有余地去尝试了。
  • 相继走出自闭。U 去写字符串了,很可能 T 的字符串,其实这题我应该会的,应该会的。期间 KBlack 写很可能写不完的 F,很遗憾。

K:

  • 没了,没了。

Problem A

Solved by ultmaster. 01:07 (+1)

题意:给两排物品,每个物品分别有高度和价格两个属性。要求给两排物品分别做排列,使得同一列上后面的物品比前面的物品高;同一行上价格单增。

题解:盲人签到,上来就 WA。还得靠队友拯救。对价格排完序后,切成一段一段,然后从左往右加进去,少的那段在多的那段里面贪心找。代码倍增,没出锅已经很好了。

Problem B

看完口胡了一下觉得有点难写,就扔了。

Problem C

没看过。

Problem D

Solved by ultmaster. 03:36 (+3)

题意:有一个环,环上是很多种不同的颜色的左括号和右括号。要求一种切法使得有尽可能多的颜色满足是一个合法的括号序列。

题解:签到题 II,15 分钟写完,WA 了一年。对于每种颜色,使用 +1, -1 扫描,最低点就是合法的切割点。然后把合法的切割区间加进去汇总扫描线一下就好了。

无数个错误:

  • 有可能这种颜色根本不可能合法(这个过不了样例)。
  • 有可能没有颜色合法。
  • 最终的最佳答案有可能不在扫描线的关键点上取到(不过按照 Z 说的那个方法写就不会有这个问题了,不知道为什么要执着地开两倍)。

Problem E

Solved by zerol. 01:49 (+1)

题意:有些复杂。有一个无向图,要求在一些路口装死路的标志,问最少装几个。

题解:类似于拓扑排序,把度为 1 的点和边不断去掉,然后在那些去掉和没被去掉的点之间的边上装牌子。树的情况特判,就是把度为 1 的点相邻的边上装。

Problem F

Unsolved.

Problem G

Unsolved. (-10)

Problem H

Solved by kblack. 03:49 (+3)

题意:有向基环外向森林,求到每个点距离小于 K 的点数。

题解:分为环上的点和树上的点:树上的点用 dfs 和树状数组统计;环上的先处理出树上某个距离的点数,然后转两圈,错位加在树状数组上维护每个距离的点数;不连通连带导致大量傻逼问题。

Problem I

没看过。

Problem J

Solved by zerol. 04:09 (+8)

题意:每个人都有 k 个数字,排名就是数字和小于自己的人数 +1。问对所有数字取 min 后,每个人的排名最高是多少。

题解:对于每两个人,求出两者之间的相对排名变化的时间点(这部分有点麻烦,反正就是枚举相邻两个数字,然后解方程)。然后对于每个人,和其他所有人的排名变化的事件按时间排序,然后扫一遍。

zerol: 我也不知道重写 KBlack 的代码是不是正确的选择。我牺牲了时间复杂度换来了代码复杂度,然后 T 的生活不能自理,把一个 50 换成了 log50,然后常数优化了一通才过。

Problem K

Unsolved.