题解「EZEC-9」进位

· · 题解

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

\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);
}