AT_arc210_e [ARC210E] Subset Sum Gaps 题解

· · 题解

紫题！？？班上同学场紫？！！

显然没有紫啊 /lengh 一定是虚高了。主观难度青。

这也放模拟赛 T1 啊，要我命啊。

首先考察有没有什么方法可以生成出来这 2^n 个和。最容易想到的是直接枚举，但是这样绝对会炸，因为你中途没有任何可以优化的步骤。

思考 2^n 的来源，可以看作 n 次 \times 2（废话）。考虑依次加入每个 a_i，并令集合里当前有的和复制一遍并全部加上 a_i，这样就成功实现了集合大小 \times 2 这样的操作。

中途如果完全不做优化的话，最终肯定还是 O(2^n)，还是爆炸。

注意到最终需要判断的是相邻两个的间隔要比某个值大。那么，很显然的，在我们不断 \times 2 处理的这个的过程中，如果已经存在当前的相邻两个的间隔已经比那个值小了，那么这个值肯定不会贡献答案了。

嗯，或者这么说吧，当前处理了一部分，相邻的两个数为 x 和 y，且 x \le y。那么最终与 x 相邻的 y' 一定不超过 y，即有关系式 x \le y' \le y。如果目前已经有 1.01 x > y，那么一定有 1.01 x > y \ge y'，最终 x 也不会对答案做出贡献。

好，那么既然这个时候已经不会做出任何贡献了，维护它们之间的差值已经没有任何意义，将其看作段并合并。对于一个段，维护三个值 (l,r,sum)，其中 l 和 r 表示段对应的左右端点所对应的 S 值，sum 为当前段内的 k 数量。（这么说应该能听懂吧 qwq）

于是每次对原集合做翻倍的过程中，再合并一下新产生出来的段。最终得到的段，就是我们的答案，对于相邻的两个段就可以做输出了。

到这里我们已经做完了，但还有一个问题：时间复杂度。这个时间复杂度只是做了一个合并而已，看起来还是 O(2^n) 的，那能过吗？能，因为千万不要低估指数的增长级别。就这样一个一个套下去，最终能合并出来的段也不过 O(\log_{1.01} n) 个。n 只有 5000 欸，1.01^{1000} 都已经有了两万多了，校内考的 n 是 1 \times 10^5 都轻松过。所以时间复杂度是稳的。

代码非常好写。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 1e5+5;
const LL MOD = 998244353;
struct node{LL l,r,sum;};
LL n,a[N];
vector<node> dp,f;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool cmp(node d1,node d2){
    return (d1.l<d2.l)||(d1.l==d2.l&&d1.r<d2.r);
}
int main(){
    //freopen("subset.in","r",stdin);
    //freopen("subset.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    dp.pb({0,0,1});
    for(int i=1;i<=n;i++){
        f=dp;
        for(node x:dp)f.pb({x.l+a[i],x.r+a[i],x.sum});
        sort(f.begin(),f.end(),cmp);
        dp.clear();
        for(node x:f){
            if(dp.empty()||dp.back().r+(dp.back().r+99)/100<=x.l)
                dp.pb(x);//新开一段
            else{
                dp.back().r=max(dp.back().r,x.r);
                dp.back().sum=(dp.back().sum+x.sum)%MOD;
                //合并段 
            } 
        }
    }
    cout<<dp.size()-1<<"\n";
    node lst;LL now=0;
    for(node x:dp){
        if(now)cout<<lst.r<<" "<<x.l<<" "<<now<<"\n";
        now=(now+x.sum)%MOD,lst=x;
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！