0103abc 的网站

不算太难的题，duel 的时候用了 1h 切掉了。 注意到 $aiaj+t(ai+aj)=(ai+t)(aj+t)-t^2$（恭喜你你做完了这个题最难的一步）。最后的 $t^2$ 是容易省去的，于是问题可以转化为： 对于给定的 $t$ 值，你可以构造一棵 $n$ 个点的完全图，其中两点...

用时：37 分 17 秒 这啥博弈啊！ 我们发现最难的情况是 $n = 3$，且打表发现不存在三种棋盘组合可以稳定地通过所有可能纸带的情况。此时我们发现题目并没有说一次只能用 $3$ 个硬币，而是说 $333$ 次用 $999$ 个硬币，那么直接随机，期望用 $666$ 个硬币。 如果 $n...

用时：1 小时 37 分钟 15 秒。 前置技巧：影跃。 在这道题中，我们发现如果可以提取出 $O(n)$ 个影跃点，然后在这些点上面跑倍增，那么答案就容易求了。 我们考虑这些点的选择： 首先选上从一个箭头出发，第一次碰到其他箭头时所在的位置； 再选上从一个询问点出发，第一次碰到箭头时所在的位置。...

用时：50 分 3 秒。 考虑先简化问题。若 $s$ 和 $t$ 的第一个字符不是 ，那么这两个字符一定匹配，可以把原问题规约为去掉第一个字符的问题。相似的，两个串的末尾也能做这种简化。 然后我们发现，假设 $s$ 的开头和 $t$ 的末尾都是 ，那么一定有解。否则其中一个字符串的首尾都是...

考虑建出 2-SAT 图论模型并各跑一遍 floyd 算法求解有向图闭包传递问题。接下来分类讨论： 假设两张图的有解性不同，对有解的图直接构造一组解即可； 否则假设两张图的可达性完全一致，这两张图等价； 否则假设两张图的已经被确定的变量之间...

尝试刻画题目的条件，不难想到混合操作就是值域在 $[0, 3]$ 中的数的异或。 又由于只有两个数位，我们可以拆开看它们并设为 $2n$ 个布尔变量。不失一般性地，设白、红、黄、蓝分别对应矩阵 $\begin{bmatrix}0 & 0 \...

有点奇怪的题，想到了很多题解需要用到的结论但是就是导不出一个形式化做法... 考虑一颗 $4$ 个节点的虚树 $x-a, x-b, x-c$，假设这三条边对应到原树的长度都不小于蛇的长度，那么蛇头 / 尾一旦到达 $x$ 点，就可以完成掉头。 不难发现可能的 $x$ 点有多个，但是蛇能到达 $x1$...

三千的奥义，巴巴的博弈 拆分方案一定是若干个 $3$ 加上 $O(1)$ 个 $2$ 或者 $4$。不难验证 $n$ 比较小的情况，而对 $n$ 较大的情况，$3 \times 3 > 2 \times 2 \times 2$，则拆出 $3$ 总是更优的。 因此我们可以分类讨论： $n =...

先考虑每个非零数不同的情况，我们有经典结论：选出的 $0$ 一定是前 $k$ 个和后 $k$ 个，且正数第 $i$ 个 $0$ 对应的后面的 $0$ 必然是倒数第 $k + 1 - i$ 个 $0$。 如果知道 $k$，我们便把原问题变成了一些区间和一些点匹配的问题。容易使用贪心判断是否能取到...

在构造答案之前，我们先需要会判断有无解。一个直接的观察是直径只变长不变短，那么如果初始直径长于最终直径，我们直接声称无解，否则在构造的过程中判断有无解。 一些提示和声明： 定义 $p$ 的子树的高度为其内部节点的最大深度（以 $dep_p = 1$ 为标准）。...