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

Problem A

Solved by Xiejiadong. 1:06 (+)

题意：给出一个 $d$ 的多项式，但你不知道多项式也不知道次数，要求通过不超过 $d+3$ 次询问，确定次数。

题解：一开始询问 $d+1$ 次 $d$ 的情况下函数的值，插值得到函数，可以额外判断两个 $x$ 的时候是否满足这个解析式。

如果不满足的话，继续向后询问确定函数即可。

Problem B

Solved by Xiejiadong. 0:50 (+2)

题意：有一个包含 $64$ 个二进制位的信息板，每次要求修改一个数，能够唯一地表示出 $[1,64]$ 内的所有书。

题解：考虑对于每一个位置的权重都为当前位置的编号，通过所有 $1$ 位置的异或得到最终的数。

对于得到的信息板，我们可以得到与最终结果每一位的差异，如果不同，则那一位为 $1$ （为了调整回来），否则为 $0$ ，对于得到的这个数所在的位置进行修改即可。

Problem C

Solved by Kilo_5723. 2:23 (+2)

题意：随机生成一个 $n$ 个节点 $m$ 条边的无向图，每次可以询问一个点有没有未被提到的边与其相连，在 $2n$ 次询问中判断图是否联通。

题解：可以发现，如果是随机产生的图，那么已有的联通块越大，随机加边之后它与其他联通块不连通的概率就越小。

因此，维护所有联通块的大小，每次从最小的联通块里找一个点询问，如果没有新边与其联通则舍弃这个点，如果有某个联通块每个点都不与其他联通块联通则图不联通，反之则联通。

Problem D

Solved by Weaver_zhu. 4:58 (+5)

Problem E

Solved by Xiejiadong. 0:12 (+1)

题意：对于两个 unsigned int 存储的两个数，能够从 $x$ 变成 $y$ 。

题解：显然对于 $y$ 去掉前导 $0$ 和后导 $0$ 以后，判断在 $x$ 中是否作为子串即可。

注意特判 $x=0$ 或者 $y=0$ 的情况。

Problem F

Solved by Xiejiadong && Kilo_5723. 2:36 (+)

题意：每个节点有限制其子树所挂的装饰品数量，每个装饰品的价值不同，要求获得最大的价值。

题解：因为每个装饰品的重量相同，于是可以考虑贪心。

对于一个节点上的装饰品，显然它可以挂的最多数量就是从当前节点到根结点的路径上所有节点的限制的最小值。

于是我们考虑从大到小依次摆放每个装饰品，这个装饰品的数量就是从当前节点到根结点限制的最小值，然后路径上涉及到的节点需要减小已经用掉的限制。

而对于不同的数，可以考虑连出一个新的节点 $0$ ，且他的限制为 $t$ ，即全局的限制。

Problem G

Unsolved.

Problem H

Solved by Weaver_zhu. 1:57 (+2)

Problem I

Solved by Weaver_zhu. 0:37 (+1)

Problem J

Solved by Weaver_zhu. 0:17 (+1)

Problem K

Solved by Kilo_5723. 0:34 (+1)

题意：有两个模具分别能把蛋糕 $a,b$ 等分，求分割出 $a+b$ 块蛋糕时，最小块和最大块之间的差最小是多少。

题解：先将蛋糕 $2ab$ 等分，再枚举较大的模具第一条切割边的位置。