一道模拟题。 模拟题重在如何实现，接下来挑出几个难以实现的地方说一说： 判断死活。 对于一块棋，有「气」就能活，没有「气」就会死。下面的 bool live(int, int, char) 处理了这个过程： 从一块棋的某个点开始找联通快，只有与自己相同的点才能相连。 另外，如果超出边界，按照围棋规则不算「气」；如果碰到不同色棋子，按照围棋规则同样也不算「气」。 如果碰到 . 就代表找到了至少一口气，就是暂时活棋。 落子。 考虑到围棋还有一个落子问题，也就是说不一定是落子之后自己没有「气」就会死，而是对方有「气」并且自己没有才会死。 这里采用的判断方法也很巧妙： 首先落下这颗子； ...

解题思路 首先澄清一点，不「重要」的边可以是亮着的，也可以是灭着的，这个题目里没说，只能通过样例 #1 去理解，希望后续有人来修复一下。 考虑从所有的叶子结点开始向上考虑。 对于一个点到自己父亲的边，(u,fau)(u,fa_u)(u,fau​)，我们考虑： 如果这条边不「重要」，我们不需要管它的状态； 如果这条边「重要」，并且目前它是灭着的，我们就需要翻转这条边的状态。 另外，考虑一些相连的边可以放在一起翻转，下面以样例 #2 为例： 首先我们考虑到结点 666，它和它父亲之间的边「重要」，所以需要翻转，那么我们标记一下这条链需要翻转。 另外我们发现例如 (1,4)(1,4)(1,4)...

感觉题意挺意识流。所以解法也应该是意识流解法。 首先根据题意，手上有 aaa 元钱，每 bbb 元钱买一个面包，所以原价能买 ⌊ab⌋\left\lfloor\dfrac{a}{b}\right\rfloor⌊ba​⌋ 个面包。 然后是原价购买的面包中，每 ccc 个面包能换 ddd 个面包，所以能换到的面包数是 ⌊⌊ab⌋c⌋×d\left\lfloor\dfrac{\left\lfloor\dfrac{a}{b}\right\rfloor}{c}\right\rfloor\times d⎣⎢⎢⎢​c⌊ba​⌋​⎦⎥⎥⎥​×d 个面包。 代码如下： #include<cstdio&gt...

题意：给定 TTT 组询问，每组询问给出两个正整数 L,RL,RL,R，求 x=L(L+1)(L+2)⋯R‾x=\overline{L(L+1)(L+2)\cdots R}x=L(L+1)(L+2)⋯R​ 是否是 333 的倍数。 首先是一个广为人知的结论：判断一个数 xxx 是否是 333 的倍数，只需要将它所有数位相加判断是否是 333 的倍数即可。 根据这个结论，本题转化为求 L+(L+1)+(L+2)+⋯+RL+(L+1)+(L+2)+\cdots+RL+(L+1)+(L+2)+⋯+R 的和是否是 333 的倍数。 考虑 L+(L+1)+(L+2)+⋯+R=(L+R)(R−L+1)2L...

首先选择的是子序列，考虑对原序列排序没有影响。 理由是选择子序列相当于可以任意选数，所以排序之后从大到小取可以双向规约。 另外考虑对于不同的 kkk，首先对排序后的攻击序列做一遍前缀和，便于查询它们的区间和。 如果我们直接枚举不同的 kkk，然后考虑每一个长度为 kkk 的区间： 实际上这个区间的直接贡献是：（假如护盾效果用 mmm 表示） sum[l…r]−msum[l\dots r]-msum[l…r]−m 另外这个区间的贡献不会是负数，原理和【最大子段和】相似，考虑证明复杂度： O(∑k=1nnk)=O(nln⁡n)O\left(\sum\limits_{k=1}^{n}\dfrac{n...

首先扔一个结论： 原序列奇数位置上的 1 有 1 个单位贡献，最后贡献为奇数则 T 否则 X。 考虑证明，首先任意一个偶数位置上的 1 没有意义，因为你对这个位置 iii 操作完了之后，对手继续操作位置 i−1i-1i−1，就相当于： 翻转 iii、翻转 i−1i-1i−1 翻转 i−1i-1i−1、翻转 i−2i-2i−2 相当于把影响连续传递了 222 位，与阶梯博弈类似，该影响没有意义可以直接扔掉。 对于奇数位置，每个奇数位置都会有一个单位的贡献（多余的通过类似分析将贡献也扔掉）就可以了。 最后两个人能连续操作的“有意义”步数，如果是奇数代表最后一步是先手操作，如果是偶数代表最后...

这里给出一些琢喵博客上的小提示。 一、公开题目题解资源 (solution) 这部分一般会直接公开，直接通过「搜索」功能找到对应题目的题解即可。 二、游记或算法总结等 (note) 这部分一般会设置密码，直接私信琢喵申请访问密码即可，注意要告诉琢喵是哪篇博文哦 \(\sim\) 三、非公开的一些资源 (private) 这部分资源一般是用于自己整理自己的心得体会等，原则上不对外公开。

\(1~\text{树的直径}\) Subtask5 满足 \(n\le10^3\)，因此可以 \(O(n^2)\) 模拟建树。 以 \(u\) 为根的子树中，\(u\) 必选时树的直径为 \(d_1+d_2-1\)。 其中 \(d_1,d_2\) 分别表示以 \(u\) 为根最大、次大深度。 \(2~\text{森林直径}\) 引理：森林直径必由树的直径扩展而来。 证明：一条边 \((u,v)\) 若存在于树的直径中，必在森林中有一对应子树存在。 此时该对应子树对应的最长链一定是森林的最长链。 设 \(d_1[u],d_2[u]\) 分别表示以 \(u\) 为根最大、次大深度...

首先二分 \(d\)，对每一个点 \(i\)，考虑找到一个区间 \([L_i,R_i]\) 满足： 当且仅当 \(k\in[L_i,R_i]\)，直线 \(y=kx\) 能够覆盖点 \(i\)。 原问题转化为一个经典问题：\(N\) 条线段，最少点数覆盖它们。 考虑直接贪心解决，按照结束时间从小到大排序，每次选择一个区间的右端点即可。 Author 的 std 复杂度是 \(O(\log\times N\times\log)\)，第一个是二分的 \(\log\)，第二个是求斜率区间的 \(\log\)。

\[\rm C~\text{魔力滋生} \] 部分分提示正解：前两个 Subtask 一个满足 \(x=0\) 另一个满足 \(x=1\)，提示了分类讨论。 \(n\) 个点的树，每个点的度不超过 \(2\)，也就是说这是一条 链。 首先考虑 \(x=0\)：显然此时给出的树 \(T'\) 即原来的树 \(T\)，直接读入什么就输出什么即可。 其次考虑 \(x=1\)：此时每个点连接了一个新建点，但事实上不难发现，这 \(n\) 个新建点的度均为 \(1\)，原来 链 中的点的度至少为 \(2\)。据此亦不难将所有度为 \(1\) 的点从原来的 链 上剥离。 满分做法：树的直径 ...

证明 这里出题人补充一种较为理性的证法。 证明：考虑设我们以此种方式遍历到的数依次为 \[a_1,a_2,\dots,a_K \] 我们将序列 \(a\) 进行分类，分为位于倒数第二行的序列 \(b_{K/2}\) 和位于倒数第一行的序列 \(c_{K-K/2}\)。 其中： \[\begin{aligned}b_i&=a_{2i}\\c_i&=a_{2i-1}\end{aligned} \] 以上的设法和考虑都是显而易见的。 我们考虑反证，假如我们遍历到一个更优的序列 \(d\)： \[d_1,d_2,\dots,d_K \] 将它...

出题人题解。 E 黄牛の争 数学模型 考虑优化 Special Judge 中 win 函数部分的暴力，首先记 \(\alpha=\left\lceil\dfrac{B}{a}\right\rceil\) 表示 \(\tt A\) 击败 \(\tt B\) 所需回合数； \(\beta=\left\lceil\dfrac{A}{b}\right\rceil\) 表示 \(\tt B\) 击败 \(\tt A\) 所需回合数。 那么： 如果 \(\tt B\) 是先手，仅需 \(\beta\le\alpha\) 即可击败 \(\tt A\)； 如...

出题人题解。 D 火烧の云 Sol 考虑最短路，设一个三元组 \(dis(i,j,k)\) 表示到达位置 \((i,j)\) 且方向状态为 \(k\) 时所需最少步数。 初始化：所有点位置字符导致的连边、权值更新；\(dis(S_i,S_j,\{0,1,2,3\})=0\)，最终答案：\(\min\{dis(E_i,E_j,\{0,1,2,3\})\}\)。 注意多个起点多个终点的情况需要灵活地处理，考虑将所有起点和终点吊起来导向同一个虚拟根节点即可。 实现 设一个三元组 \[(i,j,0)\text{表示到达点}(i,j)\text{，}\color{red}{\tex...

出题人题解。 C 兜心の顶 按道理边做这题边点开 P7238、P7807，应该通过率 100% 吧。 下文中「唯一性」代指直径、重心、直径重心三个「唯一」，「不等性」代指树的重心不等于直径重心。 一、直径的长度讨论 首先直径 不会是偶数。 否则设直径的长度是 \(2k\)，由 \(1\cdots 2k\) 这 \(2k\) 个结点组成。 那么结点 \(k\) 和结点 \(k+1\) 必然都是直径重心，与唯一性不符，舍去。 然后直径不可能是 \(1\)：显然。 直径不可能是 \(3,5\)：此时重心只能出现在中间的点（否则与唯一性不符），与不等性不符。 综上，直径长度至少为 ...