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

From EOJ Wiki
Jump to navigation Jump to search
Line 76: Line 76:
  
 
Solved by ultmaster. 01:26 (+5)
 
Solved by ultmaster. 01:26 (+5)
 +
 +
= One,Two,Three,AK =
 +
 +
== Problem A ==
 +
 +
Solved by oxx1108. 0:04:35(+)
 +
 +
== Problem B ==
 +
 +
Solved by dreamcloud. 1:40:13(+)
 +
 +
== Problem C ==
 +
 +
Upsolved by oxx1108. 4:59:46(-7)
 +
 +
== Problem D ==
 +
 +
Solved by oxx1108. 3:23:04(+2)
 +
 +
== Problem E ==
 +
 +
Solved by Xiejiadong. 3:29:38(+5)
 +
 +
== Problem F ==
 +
 +
Unsolved.
 +
 +
== Problem G ==
 +
 +
Solved by dreamcloud. 4:08:09(+1)
 +
 +
== Problem H ==
 +
 +
Unsolved.
 +
 +
== Problem I ==
 +
 +
Solved by Xiejiadong. 2:56:25(+)
 +
 +
== Problem J ==
 +
 +
Solved by dreamcloud. 0:26:57(+)
 +
 +
== Problem K ==
 +
 +
Unsolved.
 +
 +
== Problem L ==
 +
 +
Solved by oxx1108. 13:36:03(+4)
 +
 +
罚时是Xiejiadong贡献的。SPFA被卡了。

Revision as of 09:55, 1 September 2018

ECNU Foreigners

Problem A

Solved by Mathematica. 00:13 (+)

Problem B

Solved by ultmaster. 01:04 (+)

Problem C

Solved by ultmaster. 03:24 (+4)

Problem D

Solved by ultmaster. 04:17 (+2)

Problem E

Solved by ultmaster. 00:35 (+)

Problem F

Solved by zerol. 03:48 (+5)

题意:给一棵树,要求支持以下操作:

1. u v 连边

2. 以 u 为根,把 v 和它父亲的边切开

3. 询问以 u 为根,一个生物在 u,以等概率移动到相邻结点,问最后回到 u 的经过边数的期望。

题解:蒙特卡洛可以发现询问就是求 (sz[u]-1)/d[u]*2,其中 sz[u] 是联通块大小,d[u] 是度数。然后就是一个很经典的维护子树大小的 lct 了。

Problem G

Solved by kblack. 02:58 (+)

Problem H

Solved by zerol. 04:47 (+3)

题意:一开始每个集合里有一个数。要求支持操作:

1. 合并两个集合

2. 把一个集合里的数都 +1

3. 询问一个集合里满足 $x \equiv a \pmod {2^k}$ 的 $x$ 的个数。

题解:首先发现询问 3 就是相当于求把所有数字倒过来插入一个 trie 以后某个节点上的和。把一个 trie 上的数字 +1,相当于交换 0/1 然后在左子树(0) 下递归交换。集合合并就是类似于动态开点的线段树的合并。当然这里的数据结构像是介于 trie 和 主席树之间的东西。

Problem I

Solved by zerol. 02:26 (+)

题意:求一个数字串中所有本质不同的回文子串之和。

题解:建回文自动机,在转移边上 dfs 统计一下。

Problem J

Solved by zerol. 00:17 (+)

题意:求某个积性函数的前缀和。

题解:上个板子就好了。(这里我用了 min_25 筛,但感觉数据范围有点小)

Problem K

Solved by kblack. 01:53 (+)

Problem L

Solved by ultmaster. 01:26 (+5)

One,Two,Three,AK

Problem A

Solved by oxx1108. 0:04:35(+)

Problem B

Solved by dreamcloud. 1:40:13(+)

Problem C

Upsolved by oxx1108. 4:59:46(-7)

Problem D

Solved by oxx1108. 3:23:04(+2)

Problem E

Solved by Xiejiadong. 3:29:38(+5)

Problem F

Unsolved.

Problem G

Solved by dreamcloud. 4:08:09(+1)

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 2:56:25(+)

Problem J

Solved by dreamcloud. 0:26:57(+)

Problem K

Unsolved.

Problem L

Solved by oxx1108. 13:36:03(+4)

罚时是Xiejiadong贡献的。SPFA被卡了。