自动搬运

查看原文

来自洛谷，原作者为

	gyh20 orz Feecle6418

搬运于2025-08-24 22:33:40，当前版本为作者最后更新于2021-09-07 20:30:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

令"前"表示二进制数位值小的一边，"后"表示大的一边。

$\textrm{Subtask~1}$

可以 $m!$ 枚举，再检查答案。

$\textrm{Solution~1}$

对于第一问，我们有结论，无论顺序如何，答案不会改变。

证明可以按位考虑，对于第 $i$ 位，无论怎样操作，前 $i-1$ 位对之 $i$ 之后二进制的贡献都要经过第 $i$ 位进位，且每次进 $1$，所以第 $i$ 位的变化次数是固定的，直接模拟即可。

复杂度证明

比较经典，令 $a_i$ 表示加在 $i$ 位置的操作个数，一个位置进位的次数 $f_i=\lfloor \frac{f_{i-1}}{2}\rfloor+a_i$，直接看作 $f_i=\frac{f_{i-1}}{2}+a_i$ 可以看出每个 $a_i$ 对答案的贡献是 $O(a_i)$ 量级的，所以直接模拟复杂度是 $O(n+m)$ 的。

$\textrm{Subtask~2,3}$

考虑枚举得到最大值的加操作，假设位置为 $x$，每次尽量让 $x$ 向后进位的多，即每一次能进位就进位，即从 $x$ 向后枚举，枚举到某一位时用上这一位所有加操作，判断最后能加到哪一位即可，时间复杂度 $O(n(n+m))$。

在 $\textrm{Subtask~3}$ 中，可以发现这个位置 $x$ 一定是最靠前的存在进位的位置，时间复杂度 $O(n+m)$。

$\textrm{Solution~2.1}$

基于对 $O(nm)$ 直接的优化，从后往前枚举 $x$，每次贪心进位，但是在位值为 $2$ 时不进位，等到位值为 $3$ 时变为 $1$，并进一次位，这样可以保证最后一次操作能进位尽量多，使用数据结构维护最长的连续非 $0$ 段，根据方法不同，使用性质多少可以做到 $O(n+m)\sim O(n+m\log^2 n)$ 不等，如果复杂度过高只能无法通过 $\textrm{Subtask~6}$。

这里提供了一个 $O(n+m)$ 的并查集实现 。

$\textrm{Solution~2.2}$

在 $O(nm)$ 的基础上继续找性质，直接以任意顺序模拟整个操作，得到每个位置是否出现过进位，发现答案即为出现过的最长出现进位的连续段，最后一次加法可以看做加在这个连续段最前面的一个位置，然后依次影响了这些存在进位的位置，可以发现答案不可能更优，因为下一个位置不可能存在进位，简单来说，就是这是上界，但是可以取到的。

一些常见的错误可以见这个帖子。

#include<cstdio>
char s[1000032];
int n,m,a[1000032],ans,len,x,ans1;
int main(){
	scanf("%d%d%s",&n,&m,s);
	for(int i=0;i<n;++i)s[i]-='0';n+=30;
	while(m--){
		scanf("%d",&x),++s[x],++ans1;
		while(s[x]>=2)a[x]=1,++s[x+1],s[x]-=2,++x,++ans1;
	}
	for(int i=0;i<n;++i)
		if(a[i]){++len;if(len>ans)ans=len;}
		else len=0;
	printf("%d\n%d",ans1,ans+1);
}