CF1779

前半场打的稀烂。

还好没掉分。

A. Hall of Fame

出现 RL 即满足题意。

B. MKnez’s ConstructiveForces Task

只有 时无解。

手推一下可以发现序列一定是 的形式。

为偶数是平凡的，令 即可。

为奇数时可以令 。

C. Least Prefix Sum

原条件等价于

• 。
• 。

贪心，不满足条件时操作最大或最小数即可。

D. Boris and His Amazing Haircut

先离散化。没在 中出现的 显然没用。

从大到小剪一定是不劣的。每次操作形如选出若干区间覆盖 的点，不能覆盖 的点。

树状数组记录限制即可。

E. Anya’s Simultaneous Exhibition

很像 1498E。

缩点，可以获胜的点一定在入度为 的点双内。因为是竞赛图，这样的点双只有 个。

反证法容易证明，出度最大的点一定在这个点双内。

1498E 的结论，按出度从大到小排序后每个点双一定是一个区间。

按顺序询问每个点到当前点集是否有出边。若有则把一整个区间加入。

也可以采用 1498E 不询问的方式在 次询问内解决。

F. Xorcerer’s Stones

对于 为偶数的情况，我们只需要对 操作两次即可。

考虑扩展这一结论。若点 子树大小为偶数，可以通过对 进行一次操作使得 子树异或和变成 。

对于子树大小为奇数的 ，只有当前子树内异或和为 时可以清空。

原问题也就转化为：选出若干没有父子关系且子树大小为偶数的节点，使得它们子树的异或和恰好等于所有节点的异或和。

维护异或卷积状物即可做到 。

G. The Game of the Century

考察外侧大三角形。记三个顶点分别为 ，若形成 的形式则已经满足条件。

否则一定是 的形式。沿原方向边权为 ，反方向边权为 ， 的最短路即为答案。

发现只有最靠外且与 外侧方向相反的边可能被经过。01bfs 即可。