题解

A 气球谜题

签到，输出 ACD 即可。

B 猪猪狗狗

简单鸡兔同笼问题。设 w,o,f 的数量分别为 ,,

那么可得：

解得

C 1v树

题目要求对给定序列多次查询前 个元素的最大值。预处理前缀最大值数组 ，其中 表示 ，递推关系为：

对每个查询 ，直接输出 即可，单次查询 ，总复杂度 。

D 战士的防守抉择

本题是比较简单的模拟问题，对每次伤害计算三种选择方式的效果并选择掉血最少的方式即可。 值得注意的是Colossus的伤害变成50%是向上取整的（），所以实际原始伤害应该这样计算。

E 构造与异或

已知需要构造的两个二进制串和等长。由二进制数的性质可知，要让与的按位异或运算结果最大，应当尽可能让异或结果的高位出现1，低位出现0。而由异或运算的性质可知，当与的对应位为01组合或者10组合时，该位的异或结果为1，否则为0.

所以，想让异或结果尽可能大，就要让和的高位尽可能为01组合或者10组合。换言之，需要将给定的0和1尽可能多的配出01组合或者10组合放在与的高位，剩余的00组合或11组合放在低位，即可使得与的按位异或运算结果最大。

一种构造方式是，从的高位到低位开始，依次填充数字1，直到所有的1填充完。若使用1填充完数字1后，1仍有剩余，则将剩余的1从的低位到高位依次填充，直到用完所有的1。随后，使用0填充其他空余位置。

F 你怎么知道我一个版本八个金

设提升 的词条数为 ，求目标函数 最大时的解 。注意到 是一个二次函数，对称轴表达式可直接解出，因此无需使用二分或三分查找。复杂度 。

此题难度集中在多个注意事项上，下面是易错点：

1. 数据范围超过 C++ int 上限；
2. 时，需要特判，输出 0 ；
3. 非零时不影响 的最优值，需要从 对称轴表达式中删去，否则数据范围超过 C++ long long 上限；
4. 若 （即全部词条用于提升 ，也不能让 为正数），需要特判，输出 0 ；
5. 计算对称轴的位置时，C++ 的 float 精度不够，至少需要 double 的精度；
6. 若 最优解的小数部分为 ，对应最优整数解需向下取整。

G Alice和Bob的三维棋盘游戏

判断 是否为偶数，是则 Bob 获胜，否则 Alice 获胜。

证明：如果 为偶数，那么 至少存在一个偶数，那么长方体的对称中心就不在格子内，当 Alice 放置棋子时，Bob 在其中心对称的位置放置一枚相同颜色的棋子即可，这样 Bob 放置的位置永远合法，只有 Alice 会无法放置，所以 Bob 赢。

如果 为奇数，那么 Alice 开局抢占最中心的位置，之后 Alice 跟着 Bob 在中心对称的位置放棋子，是Alice 赢。

H 扔鸡蛋

分块思想。

本题设计的目标询问次数为 300 次，321 次纯属拍脑子想出来的。

即，如果将 看作 100 进制下的数，那么这个数共有 3 位，每 100 次询问可以确定 1 位，即可在 300 次询问内完成。

考虑求 h-1，也就是最大安全高度。

如何在 100 次询问内确定 1 位？按 1,2,3,...,100 逐个询问即可，如果在 H 收到了 >= 那么安全高度这一位最高就是 H-1。

最后我们会求出 h-1，最后记得输出 h。

I 战士的攻击抉择

本题操作的选择时机是核心的难点。 首先，我们按照怪物血量从低到高排序，这里用到贪心思路：优先攻击血量少的怪物显然更优，越早让怪物减员，我们受到的总伤害就越低。 其次，我们考虑未使用操作的阶段，我们发现持续使用操作（打击）是稳赚不亏的，这说明在使用操作之前，全程使用操作是最优策略。 然后，考虑使用操作之后的情况:操作+ 操作+ 操作的组合能打出点伤害。对于血量较高的敌人，可先用该组合消耗大部分血量，剩余少量血量再针对性收尾。 收尾策略：若剩余血量对取模后≤，用次操作解决；若≤，用次操作解决；否则仍用操作+操作+操作解决。 关键在于操作的使用时机：首先，攻击某个怪物的过程中不应使用操作（因为不如先使用操作再攻击该怪物）；其次，我们可以暴力枚举操作的使用时机。 该解法的时间复杂度为。 本题也可通过简单优化将时间复杂度降至，或从贪心角度推导另一种的解法。 本题的数据规模允许的解法通过。

J Terracraft

从原点出发的射线可以用方向角来描述。对于每个正方形，从原点能射中它的方向角构成一段连续区间，问题因此转化为：给定 个区间，求被最多区间同时覆盖的点。

对于左下角 、边长 的正方形，角度区间的最小方向对应右下角 ，最大方向对应左上角 。将每个区间拆成起点 、终点 两个事件（同角度 优先），按角度排序后扫描并维护计数，取最大值即为答案，复杂度 。

为了避免浮点精度问题，而坐标均为整数，我们改用方向向量叉积比较：

C++中，若使用 long double（精度约 ）按斜率排序也可行，但 double 精度仅约 ，不够用。

K 绝密运输行动

此题需在 T 型物体的状态集上建图，跑一次单源最短路即可得到答案。

我们可以使用三元组 描述 T 型物体的状态：

• 表示 T 型物体中心方块的坐标，
• 表示 T 型物体的朝向，

于是可以得到大小上界为 的状态点集。随后在点集上建立有向带权图：

若两点间移动不合法，则不建立边。若移动合法，则建立带权边，具体如下：

• → 边权：
• → 边权：
• → 边权：
• → （）或 → 边权：

建图完成后，跑一次单源最短路即可得到答案。若得到最短路长为无穷（初始化值），则说明最短路径不存在，输出 -1 。

一个小技巧：为了避免额外处理边界，可在迷宫外围围一圈 “1” ，然后用处理墙壁的方式处理边界。

L 战士的路线抉择

本题为动态规划（DP）问题。可将“点的编号”“是否持有红/绿/蓝钥匙”“角色血量”分别作为状态维度：

• 点的编号：对应图的节点；
• 是否持有钥匙：共种状态（红、绿、蓝各有“有/无”两种可能）；
• 角色血量：题目中角色血量数值较低，可直接作为维度（上限约）。 因此状态总数为。

由于图是严格分层的，可先通过BFS求出每个点的层数，再按层数从低到高继承状态；当然，更通用的方法是通过拓扑排序处理状态转移。

M 迭代协议

题目要求

给定一棵有根树，每个点 上有一个二进制字符串 ，两种操作：

• 操作 1：将点 及其子树中所有点 执行更新：；
• 操作 2：查询点 上二进制字符串 后缀 的个数。

期望一个 的算法。

关键词

• 位运算
• 模拟
• 子树转 DFS 序
• RMQ
• 预估难度：cf 1700? 区域赛 铜/银-

考虑每次 操作会带来什么影响：

本质上会将尾部的一串连续的 1 变成 0，并将前面的一个 0 变成 1。对于一个二进制串，最多只会进行 次有效的操作 1，当二进制串变为 的形式后，每次操作 1 只需要在二进制串尾部加一个 0 即可。

于是每次操作 1 都可以模拟上述的操作，直到二进制串变成 的形式。

在每次操作 1 时都遍历子树并进行模拟是不能接受的，这需要 的时间复杂度，其中 为字符串总长度。考虑通过 DFS 序，将子树问题转为序列问题，原问题变为区间 +1，单点查询问题。只需要在操作 2 时进行懒更新，查询时进行模拟。通过树状数组、线段树等方法即可通过。

时间复杂度为 。

一些冷知识

• 本题从题意形成、参考代码编写、数据生成校验、题面润色等环节均使用了 Google Gemini，因此在题目中特意写了 Special thanks to Google Gemini.
• 本题受到 [WC2026] 二进制 的启发而命制。
• 下次再见是什么时候呢？谁知道呢。