感觉题意挺意识流。所以解法也应该是意识流解法。 首先根据题意，手上有 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\)：此时重心只能出现在中间的点（否则与唯一性不符），与不等性不符。 综上，直径长度至少为 ...