CF

战况： 别的不说，这个 B1 WA 3发是真的精髓。 A 略 B 我们设此时在第一队队尾的为 las0，在第二队队尾的为 las1，要放的数为 x。 先考虑 B1： 显然有：如果 las0 等于 x，放在第二队，如果 las1 等于 x，放在第一队。 考虑两边都不同的情况，我们想要这个 x 后面尽快 ......

讲真，有点谔谔。 首先考虑若 $a+b=x$ 那么 $|a|,|b|,|x|$ 满足什么样的关系。不妨设 $|a|\ge b$，不难发现 $|x|\ge |a|\ge |x|-1$。 那么分类讨论一下： $|a|=|x-1|$，则 $|b|=|x-1|$。 $|a|=|x|$，设 $\operato ......

题面 将 $a,b,c,d$ 分别用 $a_1,a_2,a_3,a_4$ 表示。 令与第 $i$ 类食物中的第 $j$ 个冲突的第 $i-1$ 类食物的集合为 $S_{i,j}$。 首先是是人都能看出来的 DP： 令 $f_{i,j}$ 为选择第 $i$ 类食物的第 $j$ 个时所需的最小费用，显然 ......

题面 如果我们将 $a$ 数组从大到小排序，那么显然的，前 $k$ 个数就对应着长度为 $k$ 的元素和最大的子序列中各元素的值。 由于要求字典序最小，所以我们将 $a$ 数组中的元素下标进行排序，在排序时以对应的元素值为第一关键字，以元素下标为第二关键字（排序后对应的元素值从大到小，大小相等的元素 ......

题面 ~~我来水题解啦！！~~ 首先这题和素数有关，我们就先需要一个线性筛： int prm[1000005],tot; bool vis[1000005]; void init(){ vis[1]=vis[0]=1; for(int i=2;i<=b;i++){ if(!vis[i])prm[++ ......

题面 设 $f(s,t)$ 表示串 $s$ 在 $t$ 中出现的次数。 首先把询问 $\sum\limits_{i=l}^rf(s_i,s_k)$ 拆成 $\sum\limits_{i=1}^rf(s_i,s_k)-\sum\limits_{i=1}^{l-1}f(s_i,s_k)$，然后考虑如何算 ......

题面 这题这么水怎么还是蓝啊（恼 ~~即使这么水我还是脑子抽风交了好几遍~~ 其实很简单： 不妨设正确密码长度为 $len$ ，根据题意，在试到正确密码前都要先把长度小于 $len$ 的密码全部试一遍，则最优情况就是试长度为 $len$ 的密码时一遍试对，最劣情况就是把长度为 $len$ 的所有密码 ......

题意： 维护一个可重集 $S$，支持以下两种操作： 插入一个数，保证插入的数不降。 找出 $S$ 的一个子集 $s$，使 $\max(s) - \operatorname{mean}(s)$ 最大，输出这个最大值。其中 $\max(s)$ 表示 $s$ 中元素的最大值，$\operatorname{ ......

题面 $Update 2021.10.8:$使用了$\LaTeX$ 分析题意： 字符串 $S$ 中只有 $A$ $B$ $C$ 三种字符 删除 $A$ 时必须同时删除 $B$ 删除 $C$ 时也必须同时删除 $B$ 因此，删除 $A$ 和 $C$ 的总个数就等于删除 $B$ 的个数 解法： 想要让字 ......

题面 简单分析容易发现，若 $s=rev(s)$，则无论 $rev(s)$ 放在前面还是后面，生成的新串都相同，只有一种情况。 相反，如果 $s\neq rev(s)$，则一次操作后可以出现两种情况。而无论是哪种情况，生成的新串都是回文串，即 $s'=rev(s')$，根据乘法原理，后面的情况数都是 ......

考虑这样一种贪心策略： 按序号遍历 $a$，如果 $a_i=i$ 则继续，否则暴力向下找到一个 $a_j=i$，暴力翻转区间 $[i,j]$，然后退出。 正确性证明： 当遍历到 $a_i$ 时，$a_1$ 到 $a_{i-1}$ 一定已经是不需要翻转就已经字典序最小，因为如果不是的话程序在这之前就已 ......

蒟蒻有一种用 set 的乱搞（？）做法。 将题目中的连边要求反着说一遍：$i>j$ 且 $a_i<a_j$。 考虑遍历 $a$ 时，遍历到的 $a_i$ 编号一定要比它前面的大，只需要将前面比它大的元素都和它连起来。 将每个连通块看作一个整体，只要 $a_i$ 比其中任意一个小，$a_i$ 就可以加 ......

题意 有一些蛋糕，最开始只有一块。每次可以选择质量为 $x(x\ge2)$ 的一块，将其切成 $\left\lfloor\frac x2\right\rfloor$ 和 $\left\lceil\frac x2\right\rceil$ 两块。现在给定切 $n-1$ 次后的结果，判断能否通过最开始的 ......

题面 观察题面：$n\le10^4$，询问次数 $\le15$，因此考虑二分。 用 $x$ 表示没有被交换过的那个元素。 考虑当询问区间 $[l,r]$ 时，得到的序列满足什么条件，才能确定 $x$ 在这个区间内。 考虑一个在交换前的序列的 $[l,r]$ 区间内的元素 $y$，由题意 $a_y=y ......

题面 前排提醒：这是本题最烂的做法，代码长达 91 行。 由于题里提到了 $\operatorname{MEX}$，所以考虑该怎么求 $\operatorname{MEX}$。 我们使用主席树。由于主席树难以直接处理下标为 $0$ 的情况，所以给数组中的每个值都加上一个偏移量 $1$，同时下文提到的 ......

题面 看起来是个 DS 题，事实上是个乱搞题，做法挺多的。由于它给的这个结构看起来就不好优化，所以考虑随机化。 由于两个点到达 LCA 后剩下的贡献就是 LCA 到根的每个点权值的平方，这部分可以 $O(n)$ 预处理，所以只需要考虑两个点之间的路径所产生的贡献。 在树上随机撒 $\sqrt n$ ......

题面 形式化题意： 给出长为 $n$ 的两个序列 ${a}$ 和 ${b}$，定义序列 ${c}$ 满足：$c_i=d_ib_i$，其中 $d_i\mid a_i$。求 ${c}$ 最少能被分成多少个连续段，使得每个连续段内的值相同。 首先对于一个 $i$，如果 $c_i$ 能和 $c_{i-1}$ ......

题面 看到要求每一位的答案，首先考虑倒着扫，因为加数一般都比删数好做。 对于任意长为 $m$ 的的序列 ${b}$，我们都可以通过将 $b_1$ 改成 $1$，将 $b_2$ 改成 $m-2$ 使得 ${b}$ 成为一个 multitest，因此操作数不会超过 $2$。 现在讨论答案的三种情况： 答 ......

~~我来水题解啦！！~~ 首先这题和素数有关，我们就先需要一个线性筛： int prm[1000005],tot; bool vis[1000005]; void init(){ vis[1]=vis[0]=1; for(int i=2;i<=b;i++){ if(!vis[i])prm[++tot ......

题面 设 $f(s,t)$ 表示串 $s$ 在 $t$ 中出现的次数。 首先把询问 $\sum\limits_{i=l}^rf(s_i,s_k)$ 拆成 $\sum\limits_{i=1}^rf(s_i,s_k)-\sum\limits_{i=1}^{l-1}f(s_i,s_k)$，然后考虑如何算 ......

这题这么水怎么还是蓝啊（恼 ~~即使这么水我还是脑子抽风交了好几遍~~ 其实很简单： 不妨设正确密码长度为 $len$ ，根据题意，在试到正确密码前都要先把长度小于 $len$ 的密码全部试一遍，则最优情况就是试长度为 $len$ 的密码时一遍试对，最劣情况就是把长度为 $len$ 的所有密码试到最 ......

题意： 维护一个可重集 $S$，支持以下两种操作： 插入一个数，保证插入的数不降。 找出 $S$ 的一个子集 $s$，使 $\max(s) - \operatorname{mean}(s)$ 最大，输出这个最大值。其中 $\max(s)$ 表示 $s$ 中元素的最大值，$\operatorname{ ......

将 $a,b,c,d$ 分别用 $a_1,a_2,a_3,a_4$ 表示。 令与第 $i$ 类食物中的第 $j$ 个冲突的第 $i-1$ 类食物的集合为 $S_{i,j}$。 首先是是人都能看出来的 DP： 令 $f_{i,j}$ 为选择第 $i$ 类食物的第 $j$ 个时所需的最小费用，显然有 $ ......

$Update 2021.10.8:$使用了$\LaTeX$ 分析题意： 字符串 $S$ 中只有 $A$ $B$ $C$ 三种字符 删除 $A$ 时必须同时删除 $B$ 删除 $C$ 时也必须同时删除 $B$ 因此，删除 $A$ 和 $C$ 的总个数就等于删除 $B$ 的个数 解法： 想要让字符串为 ......

简单分析容易发现，若 $s=rev(s)$，则无论 $rev(s)$ 放在前面还是后面，生成的新串都相同，只有一种情况。 相反，如果 $s\neq rev(s)$，则一次操作后可以出现两种情况。而无论是哪种情况，生成的新串都是回文串，即 $s'=rev(s')$，根据乘法原理，后面的情况数都是前一个 ......

考虑这样一种贪心策略： 按序号遍历 $a$，如果 $a_i=i$ 则继续，否则暴力向下找到一个 $a_j=i$，暴力翻转区间 $[i,j]$，然后退出。 正确性证明： 当遍历到 $a_i$ 时，$a_1$ 到 $a_{i-1}$ 一定已经是不需要翻转就已经字典序最小，因为如果不是的话程序在这之前就已 ......

蒟蒻有一种用 set 的乱搞（？）做法。 将题目中的连边要求反着说一遍：$i>j$ 且 $a_i<a_j$。 考虑遍历 $a$ 时，遍历到的 $a_i$ 编号一定要比它前面的大，只需要将前面比它大的元素都和它连起来。 将每个连通块看作一个整体，只要 $a_i$ 比其中任意一个小，$a_i$ 就可以加 ......

题意 有一些蛋糕，最开始只有一块。每次可以选择质量为 $x(x\ge2)$ 的一块，将其切成 $\left\lfloor\frac x2\right\rfloor$ 和 $\left\lceil\frac x2\right\rceil$ 两块。现在给定切 $n-1$ 次后的结果，判断能否通过最开始的 ......

观察题面：$n\le10^4$，询问次数 $\le15$，因此考虑二分。 用 $x$ 表示没有被交换过的那个元素。 考虑当询问区间 $[l,r]$ 时，得到的序列满足什么条件，才能确定 $x$ 在这个区间内。 考虑一个在交换前的序列的 $[l,r]$ 区间内的元素 $y$，由题意 $a_y=y$。设 ......

题面 看起来是个 DS 题，事实上是个乱搞题，做法挺多的。由于它给的这个结构看起来就不好优化，所以考虑随机化。 由于两个点到达 LCA 后剩下的贡献就是 LCA 到根的每个点权值的平方，这部分可以 $O(n)$ 预处理，所以只需要考虑两个点之间的路径所产生的贡献。 在树上随机撒 $\sqrt n$ ......