在讨论《【LGR-271-Div.3】洛谷基础赛 #31 & 中国新年跨年赛 赛时答疑帖》回复：

@[Ethan0517](luogu://user/1387125) 第五天 $a_{i\bmod n}=a_{5\bmod 5}=a_0$。

在讨论《【LGR-271-Div.3】洛谷基础赛 #31 & 中国新年跨年赛 赛时答疑帖》回复：

@[dread_breaker](luogu://user/1098908) 已修改。

在讨论《大样例过水》回复：

完了，我好像也炸了

不难发现 $a_i$ 中数的顺序是不重要的。因此可以发现，在值域序列 $cnt$ 上，问题就相当于位置 $i$ 上叠着 $cnt_i$ 个方块的柱子，每次操作把所有高度大于 $1$ 的方块往右推，铺平这些方块直到每个柱子的高度都小于等于 $k$。 那么问题的答案显然可以这样计算：对于每一个高度超过 $k$ 的柱子 $i…

将字符串转化为 $01$ 序列 $a$，记 $f_i=a_{i-1}\oplus a_i$，特别地，$f_1=1$，则连通段数即为 $f_i=1$ 的个数，对 $[i,i+k-1]$ 进行区间反转的影响则为 $f_i\leftarrow f_i\oplus 1$，$f_{i+k}\leftarrow f_{i+k}\o…

假设当前最靠右的已被移除的卡牌为 $i$，注意到两个关键性质： * $i$ 之前最多有两个卡牌没有被移除。 * 若 $i$ 之前有两个卡牌没有被移除，那么上一次移除的卡牌一定是 $i$。 证明：第一个性质是因为若 $i$ 之前有三个卡牌没有被移除，$i$ 不可能被移除。第二个性质是因为如果上一次操作选择的是第一张卡牌，…

考虑以下两个性质： * 若区间 $[L,R]$ 包含区间 $[l,r]$，那么区间 $[L,R]$ 的答案一定大于等于区间 $[l,r]$ 的答案； * 对于一个长度为 $n$ 的排列 $p$，区间 $[l,r]$ 的 $\operatorname{MEX}$ 为不在区间 $[l,r]$ 中数的最小值，也就是区间 $[…

提供一个非常复杂做法。 进行一些思考后发现，似乎很难利用 $C$ 的实际意义进行信息传递，不如先把 $C$ 当作任意的 $1$ bit 信息进行传递。既然要传递的信息只有 $1$ bit，第二次运行中比较得到的两个字符串的字典序也许是一种可行的方案。 考虑如何找到 $r,c$ 使得第 $r$ 行的字典序（记为 $s_r…

Hao 希望答案尽量小，Alice 希望答案尽量大，这种问题考虑二分答案 $g$，如果能够判断答案是否小于等于 $g$ 就能完成这道题。 不难发现，Alice 总能在前两轮就锁定她能拿到的 $a_j-a_i$ 最大的 $i,j$（她总可以将前两轮选择的位置换为 $i,j$）。我们考虑这四次操作的位置 $H_1,A_1,…

先考虑美丽的染色方案有什么性质。对于颜色 $k>1$，不难发现颜色为 $k$ 的格子一定占了完整的若干行、若干列，并且最后需要把这些行列**都**涂上颜色 $k$。比如若某一行是颜色 $k$ 且可以不涂，那么一定要把每一列都涂上 $k$ 才行，最终就不会有小于 $k$ 的颜色，不满足性质。 这时把这些颜色是 $k$ 的…

首先考虑如果某种颜色 $c$ 对询问 $(x,y)$ 造成了一次贡献，当且仅当 $x$ 和 $y$ 在颜色 $c$ 的同一连通块内，最终的答案为 $(x,y)$ 有几次在同一连通块内。 考虑对于每一种颜色 $c$ 中的每一个连通块，给每个连通块赋予一个编号，用 $A_p$ 代表节点 $p$ 所在的连通块的编号集合，则询…

先观察什么样的 $f(x)$ 满足 $g(x)=f(x)$。 首先分析 $f(x)$ 和 $g(x)$ 的项数，两者应该相等：我们发现，若 $a_i\not=0$，则 $f(x)$ 总有 $n+1$ 项，而 $g(x)$ 只有最多 $n$ 项，因此可以得到至少有一个 $a_i=0$。在此基础上，每有一个 $a_i=0$…

在讨论《警示后人》回复：

%%%

在讨论《（求解答）20 -> 100 只需要改一个地方！？》回复：

@[江湖午餐票](luogu://user/378069) 首先，`c[++ cnt] = v[p]-cnt;` 好像是 UB，但是 WA 的原因应该是数据问题：[https://www.luogu.com.cn/discuss/1157793](https://www.luogu.com.cn/discuss/115…

本篇题解中没有用到贪心。 首先我们发现，只用 $a$ 和 $r$ 就能表示这个序列的每一项。具体地，这个序列为： $$a,a+r_1,2a+r_1+r_2,4a+2r_1+r_2+r_3,8a+4r_1+2r_2+r_3+r_4,\cdots$$ 不难发现其中的规律，对于 $a$ **之后**的第 $k$ 项（不包括…

在讨论《CZOI Round 7 赛时答疑》回复：

@[CaiZi](luogu://user/728853) T3 括号匹配的定义中是否要求 i 是左括号，j 是右括号？

## CF2050E1 Hidden Single (Version 1) 假设每个数在整个序列中都出现了两次，那么有一个显然的矛盾——区间长度应该是 $2n$，而不是 $2n-1$。这虽然听起来是一句废话，但确实是我们找到这个只出现一次的数的关键。 现在假设每个数在整个序列中都出现了两次。考虑进行递归，递归状态设为目…

## CF2050E1 Hidden Single (Version 1) 假设每个数在整个序列中都出现了两次，那么有一个显然的矛盾——区间长度应该是 $2n$，而不是 $2n-1$。这虽然听起来是一句废话，但确实是我们找到这个只出现一次的数的关键。 现在假设每个数在整个序列中都出现了两次。考虑进行递归，递归状态设为目…

首先枚举 $i$，需要计算出滑块 $i$ 在所有情况下的位置之和。先分析一次操作会对滑块 $i$ 带来什么影响： 对于一次操作 $(p,v)$，不难发现有以下三类影响： * 对于 $i p$ 的滑块 $i$，$a_i\leftarrow\max\{a_i,v+i-p\}$。 由于我们已经钦定滑块 $i$，每次操作都会带…

已申请工单。 数据中没有保证二叉树具有 n 个节点，也就是说，给出的二叉树可能不连通，只考虑 1 所在的二叉树求解才能得出一样的答案。 验证代码如下，若 1 所在的二叉树大小不为 n 则会 RE。[Submission](https://www.luogu.com.cn/record/236558477)，代码附在最后…

## CF2140E1 Prime Gaming (Easy Version) 只考虑 $m=2$ 的情况。将序列中的 $1,2$ 分别映射为 $0,1$，考虑直接进行状压 DP。设 $f_{i,S}$ 为对于长度为 $i$ 的序列，序列状压为 $S$，且 Alice 先手时的答案，$g_{i,S}$ 则为 Bob 先…

## CF2140E1 Prime Gaming (Easy Version) 只考虑 $m=2$ 的情况。将序列中的 $1,2$ 分别映射为 $0,1$，考虑直接进行状压 DP。设 $f_{i,S}$ 为对于长度为 $i$ 的序列，序列状压为 $S$，且 Alice 先手时的答案，$g_{i,S}$ 则为 Bob 先…

首先考虑一个时空复杂度都是 $O(n^2)$ 的做法： 首先求出 $a_i,b_i$ 中的每一个数下一次的出现位置 $nxta_i,nxtb_i$。类似于正常的 LCS，设 $dp_{i,j}$ 为考虑 $a$ 的前 $i$ 项，$b$ 的前 $j$ 项的最长公共口吃序列长度，考虑向后转移，显然有以下转移： * $dp…

## CF2135D1 From the Unknown (Easy Version) 考虑首先询问 $10^5$ 个 $1$，得到 $\left\lceil\dfrac{10^5}{W}\right\rceil$ 的值 $A_1$。考虑计算可能的 $W$ 的范围，你可以选择进行二分，也可以通过数学计算得到（特别地，$…

## CF2135D1 From the Unknown (Easy Version) 考虑首先询问 $10^5$ 个 $1$，得到 $\left\lceil\dfrac{10^5}{W}\right\rceil$ 的值 $A_1$。考虑计算可能的 $W$ 的范围，你可以选择进行二分，也可以通过数学计算得到（特别地，$…

设 $dp_i$ 代表从 $i$ 扔出小球需要跳几次才能到达终点，则若 $a_i=1$，则 $dp_i=dp_{i+1}+1$，否则 $dp_i=dp_{i+2}+1$。这样，若 $dp_{i+1}\not=dp_{i+2}$，我们可以判断出 $a_i$ 的值：若 $dp_i=dp_{i+1}+1$，则 $a_i=1$…

## CF2129C1 Interactive RBS (Easy Version) 由于我们一次询问中可以重复选择某一个下标，不难想到找到一个 $\texttt($ 和一个 $\texttt)$ 的下标参与后续询问是很有必要的。 考虑二分查找。不难发现，若一个串的答案为 $0$，那么它一定形如 $\texttt{))…

## CF2129C1 Interactive RBS (Easy Version) 由于我们一次询问中可以重复选择某一个下标，不难想到找到一个 $\texttt($ 和一个 $\texttt)$ 的下标参与后续询问是很有必要的。 考虑二分查找。不难发现，若一个串的答案为 $0$，那么它一定形如 $\texttt{))…

## CF2129C1 Interactive RBS (Easy Version) 由于我们一次询问中可以重复选择某一个下标，不难想到找到一个 $\texttt($ 和一个 $\texttt)$ 的下标参与后续询问是很有必要的。 考虑二分查找。不难发现，若一个串的答案为 $0$，那么它一定形如 $\texttt{))…

显然 $a$ 中的元素顺序并不重要，因此我们不妨认为 $a$ 单调不降。由于可能多个 $a$ 映射到同一个 $Q$ 上，考虑对于找出有一些特殊性质的代表元方便计数。 注意到 $1$ 的特殊性，不难发现若 $a$ 中含有 $1$，那么除了 $1$ 以外，其余数的重复是没有意义的，重复的数 $x$ 可以变为 $x$ 个 $…