Difference between revisions of "ACM-ICPC 2018 Nanjing Online Contest"
Jump to navigation
Jump to search
| Line 40: | Line 40: | ||
3. 询问一个集合里满足 $x \equiv a \pmod {2^k}$ 的 $x$ 的个数。 | 3. 询问一个集合里满足 $x \equiv a \pmod {2^k}$ 的 $x$ 的个数。 | ||
| + | |||
| + | 题解：首先发现询问 3 就是相当于把所有数字倒过来插入一个 trie 以后某个节点上的和。把一个 trie 上的数字 +1，相当于交换 0/1 然后在左子树(0) 下递归交换。集合合并就是类似于动态开点的线段树的合并。当然这里的数据结构像是介于 trie 和 主席树的东西。 | ||
== Problem I == | == Problem I == | ||
Revision as of 09:12, 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.
Problem J
Solved by zerol.
Problem K
Solved by kblack.
Problem L
Solved by ultmaster.