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

From EOJ Wiki
Jump to navigation Jump to search
Line 54: Line 54:
  
 
Solved by zerol.
 
Solved by zerol.
 +
 +
题意:求某个积性函数的前缀和。
 +
 +
题解:上个板子就好了。
  
 
== Problem K ==
 
== Problem K ==

Revision as of 09:13, 1 September 2018

ECNU Foreigners

Problem A

Solved by Mathematica.

Problem B

Solved by ultmaster.

Problem C

Solved by ultmaster.

Problem D

Solved by ultmaster.

Problem E

Solved by ultmaster.

Problem F

Solved by zerol.

Problem G

Solved by kblack.

Problem H

Solved by zerol.

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

1. 合并两个集合

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

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

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

Problem I

Solved by zerol.

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

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

Problem J

Solved by zerol.

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

题解:上个板子就好了。

Problem K

Solved by kblack.

Problem L

Solved by ultmaster.