首先 $a$ 的值域很小只有 $20$，可以支持 $2^{20}$，考虑用状压 dp。 状态 $s$，当 $s$ 二进制下后面第 $i$ 为 $1$ 时，表示 $i$ 计算在答案中。$s$ 的贡献为 $2\times \lvert s\rvert$。 设 $f(s)$ 表示状态为 $s$ 时，右端点的最小值。当 $f(…

首先处理 `1`，`2`，`/` 的前缀数量，并记录所有 `/` 的位置，用 $p$ 记录。对于 $l$ 和 $r$，找到位于 $[l,r]$ 的所有 `/` 的位置。$l \le p_{L} \le p_{R} \le r$。对于所有 $i \in [L,R]$，设 $id=p_i$，计算 $[l,p_i-1]$ 中…

将数组 $a$ 变成元素加个数的形式，元素数组为 $b$，个数为 $c$，如 $\mathtt{1,1,2,2,3,3,3}$，$b$ 就是 $\mathtt{1,2,3}$，$c$ 就是 ${2,2,3}$。用双指针来做。用 $v$ 统计是否出现，$j$ 表示左指针，$i$ 表示右指针。统计答案就是 $i-j+1$。…

# Cut the Sequence [P10977 Cut the Sequence](https://www.luogu.com.cn/problem/P10977) ## 前言 单调队列优化 dp 的好题，思维难度大细节多。因为觉得自己看不懂其他题解，在看完 y 总的讲解后豁然开朗，所以写这篇题解来巩固一下。包括…

交互题，记得用 `endl` 或者 `cout.flush()` 清空缓存区。 询问次数最大为 $n$，设 $k_i=f(1,i)$ $(2 \le i \le n)$。 先考虑无解的情况，显然是 $k_n=0$ 时不能确定答案。 然后遍历 $k$，考虑如果 $s_i=0$，则一定有 $k_i=k_{i-1}$。所以当…

dp 加容斥。 逐步推导，设 $f_i$ 为从 $1$ 到 $i$ 的方案数，按题意模拟就有： $$ f_1=1 $$ $$ f_i=f_i+f_j (1 \le j #include #include #include #include #include #include #include #include usin…

二分答案，设攻击了 $k$ 次。 因为只能是在同一个位置 $p$ 攻击，所以第 $i$ 个敌人每次攻击需要受到至少 $t_i=\lceil\frac{h_i}{k}\rceil$ 的伤害，因此 $p$ 的范围就是 $[x_i-(m-t[i]),x_i+(m-t[i])]$，若 $m #include #include…

## D 赛时的清奇想法。 首先发现能跳跃的两个位置是逆序对，因此考虑用并查集维护，并记录集合内最大值与最小值。 再考虑这样一种做法，先遍历一遍数组，目前遇到的最大值为 $x$，下标为 $id$，加入一个数 $a_i$。 * 若 $a_i>=x$ 更新 $x$ 和 $id$。 * 若 $a_i mi_j$，就说明这两个…

在讨论《感觉思路是对的但为啥不行？（样例过）》回复：

题目意思理解错了。

初始化 dis 数组时要初始化为 2147483647，因为数据随机，会出现无法到达的情况，由数据来看正无穷为2147483647。

此题用并查集必须使用路径压缩进行优化（递归写法），否则会超时。

在讨论《过了，但有疑问，求dalao解答》回复：

--i 是先减一再用 i ，而 i-- 是先用 i 再减一。

在讨论《求助，全是wa，看不出来哪里错了aa》回复：

读入错了。第一个 scanf 最后一个 "%d" 改为 "%c".

在讨论《RERERE!!!!!!!!!》回复：

这样改 ```cpp #include #include int main(){ int sum=0,cnt=0; char a[99]; for(int i=1;i<=13;i++){ scanf("%c",&a[i]);//格式要正确 } for(int i=1;i<=12;i++){ if(a[i]!='-'){…

在讨论《RERERE!!!!!!!!!》回复：

RE 是因为第7行的 printf 少了 & ，而且不应该用 %s 要用 %c 。 这样交上去还是错的，因为你直接用字符进行计算了，就是 a[i] ,char 型对应的数是该字符的 ASCII值，如 '0' 对应的是48，计算就会出错。

在讨论《有谁知道怎么把几个变量搞到一个新建结构体里啊》回复：

```cpp struct node { int a,b,c; }; vector g; ```

在讨论《90分，玄关求调》回复：

十年 OI 一场空，不开 long long 见祖宗。

在讨论《求助，请帮忙看一下为什么会0分，都是RE》回复：

数组开小了，注意看数据范围。

在讨论《凭什么这份代码能过？！！》回复：

~~洛谷数据比较水~~，洛谷比较人性。

在讨论《0分求助》回复：

换行输出多了，$a=1$ 时和 $a=2$ ，$q$ 不为空时输出了换行

在讨论《BFS wa7求助》回复：

图里是有环的，所以要用vis数组来记录访问过的点。