Difference between revisions of "XX Open Cup named after E.V. Pankratiev. Grand Prix of Kazan, Division 1."
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== Problem A == Unsolved. == Problem B == Solved by Xiejiadong. 0:34 (+) 题意:要在给出的 $n$ 个数中选择 $k$ 个数,满足这些选出来的数两两异或...") |
(No difference)
|
Revision as of 08:15, 7 March 2020
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
Unsolved.
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.