Difference between revisions of "ACM-ICPC 2018 Qingdao Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 115: Line 115:
 
== Problem J ==
 
== Problem J ==
  
Solved by .
+
Solved by oxx1108 && Xiejiadong. 02:00(+5)
  
 
== Problem K ==
 
== Problem K ==
  
 
Solved by Xiejiadong. 00:15(+)
 
Solved by Xiejiadong. 00:15(+)

Revision as of 11:42, 16 September 2018

ECNU Foreigners

代码

ultmaster: 题目比较。。正常的比赛。

Problem A

Solved by zerol. 00:12 (+)

温暖的签到。

Problem B

Solved by ultmaster. 02:14 (+)

题意:给一棵黑白树,定义白节点代价为 0,黑节点代价为到最近的白节点祖先的距离。每次询问一个点集,允许修改一个黑节点为白节点,求点集中代价最大的东西的最小值。

题解:二分答案,然后求超过答案的部分的 LCA。然后将这个点染白,检查超过答案的部分是不是被卡进答案范围内了。

Problem C

Solved by zerol. 00:35 (+)

题意:给一些指令,问是否有限步内结束。

题解:状态数很少,直接模拟,如果遇到重复状态就不停机了。

Problem D

Solved by kblack. 04:10 (+4)

题意:$n \times m$ 的棋盘上,水彩笔涂了 $k$ 条不相交的线,求前 $i$ 行的黑块和黑联通块数量。

题解:将每条线记在左上角处,没对交点会在 “较低” 的线计算。这样就只需要记录上一行的横线和能影响到这两行的竖线,然后大力讨论接上的情况。讨论有点烦,不是特别好写,贡献不少罚时,浪费不少机时。

Problem E

Problem F

Unsolved. 04:59 (-5)

Problem G

Solved by zerol. 02:50 (+)

题意:给一个数列,每次删除其中一个数,求出每一段的逆序对数量的最大值。强制在线。

题解:考虑新分裂出的两段,短的那段暴力计算,长的那段把短的那段以及删除掉的数的贡献从中扣除,复杂度 $O(n \log^2 n)$。

zerol: 自闭了近两小时,两度做成另一道题,所以根本过不了样例。背锅

Problem H

Solved by ultmaster. 00:55 (+)

题意:直线上红绿灯每秒变换,求所有点对的旅行代价。

题解:应该瞎 DP 一下就好了。奇偶搞错了自闭了好一会儿。

Problem I

Problem J

Solved by kblack. 01:04 (+)

题意:周期性按按钮,求亮着的情况按下的次数。

题解:周期 $a \times c$,周期只有 $a+c$ 个关键点,周期内乘系数再加上最后一段。

Problem K

Solved by kblack. 00:14 (+)

温暖的签到。

One,Two,Three,AK

Problem A

Solved by oxx1108. 00:10(+)

Problem B

Unsolved.

Problem C

Solved by Xiejiadong. 00:53(+1)

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 03:21(+2)

Problem H

Solved by . 00:48(+)

Problem I

Solved by .

Problem J

Solved by oxx1108 && Xiejiadong. 02:00(+5)

Problem K

Solved by Xiejiadong. 00:15(+)