XX Open Cup named after E.V. Pankratiev. Grand Prix of Kazan, Division 1.

Problem A

Unsolved.

Problem B

Solved by Xiejiadong. 0:34 (+)

题意：要在给出的 $n$ 个数中选择 $k$ 个数，满足这些选出来的数两两异或的结果 $\ge x$ ，求能选出的方案数。

题解：对于一些数，两两异或的结果一定会出现在排序之后相邻的数之间，于是就可以考虑 dp 了。

我们用 $f[i]$ 表示以 $i$ 为结尾的满足要求的子序列个数，显然对于所有满足 $a_i\oplus a_j (j < i)$ 的所有 $j$ 都可以转移到 $i$ ，最后的答案显然是 $\sum f_i$ 。

对于满足要求的可以一起转移，用 Trie 维护即可。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by Weaver_zhu. 4:15 (+5)

Problem F

Unsolved.

Problem G

Solved by Kilo_5723. 1:02 (+)

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 2:08 (+2)

题意：给出一棵树，树中有一个结点 $x$ 为关键节点，你要通过训练来得到关键节点。询问的方式是，你每次询问 $u$ 和 $v_1,v_2,\cdots ,v_k$ ，会返回 $min_{1\le i\le k}\{dist(x,v_i)\ge dist(x,u)\}$ 是否成立。

题解：考虑每次找出重心，然后判断关键点是否是重心，或者在某一棵子树里面。

• 如果重心，显然满足到重心的距离都小于到重心的孩子的距离；
• 如果在某一棵子树，显然满足到子树根节点的距离小于到重心的距离。

对于第二部分，可以二分，保证每次都能砍掉至少一半节点数量的子树。每次找到那棵子树以后，在当前的子树中继续找重心，重复上述操作即可。

Problem J

Unsolved.

Problem K

Unsolved.