CF1753A Make Nonzero Sum 题解

· · 题解

可能更好的阅读体验

题目传送门

给定一个长度为 n 的，仅由 -1，0 或 1 组成的序列 a。你需要把它划分成若干个连续段，设这些连续段分别为 [l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]，那么这样划分的代价是

\sum_{i=1}^k\sum_{j=l_i}^{r_i}(-1)^{j-l_i}a_i

现在你需要确定任意一种划分方式让总代价为零，或者报告无解。

题目解析

显然 1 和 -1 个数为奇数的时候肯定无解。
这样只需要保证相邻的两个非零数字都可以消掉就可以了。

如果相邻的两个非零数字不一样，那么只需要这两个都是正的，显然这两个都作为一个新的区间的开头即可。
如果相邻的两个非零数字一样，那么这两个就要一正一负。如果前面的一个是正的，那么后面的一个就是负的。这样就有两种可能：如果两个相邻，那么就直接分到一组，否则就前面的作为一组的第一个、后面的作为一组的第二个。

非常丑的赛时代码

int n,a[maxn],p[maxn],cnt;
struct JTZ{
    int l,r;
}ans[maxn]; int tmp;
void work(){
    n=read(); cnt=0; int i; for(i=1;i<=n;i++){ a[i]=read(); if(a[i]) p[++cnt]=i; }
    if(cnt&1){ puts("-1"); return; } tmp=0;
    if(cnt==0){
        pc('1'),pc('\n');
        pc('1'),pc(' '),print(n),pc('\n');
        return;
    }
    if(p[1]>1) tmp++,ans[tmp].l=1,ans[tmp].r=p[1]-1;
    for(i=1;i<=cnt;i+=2){
        if(i>1&&p[i-1]<p[i]-1){ tmp++,ans[tmp].l=p[i-1]+1,ans[tmp].r=p[i]-1; }
        if(a[p[i]]==a[p[i+1]]){
            if(p[i]+1==p[i+1]){
                tmp++; ans[tmp].l=p[i]; ans[tmp].r=p[i+1];
            }
            else{
                tmp++; ans[tmp].l=p[i]; ans[tmp].r=p[i+1]-2;
                tmp++; ans[tmp].l=p[i+1]-1; ans[tmp].r=p[i+1];
            }
        } else {
            if(p[i]+1==p[i+1]){
                tmp++; ans[tmp].l=p[i]; ans[tmp].r=p[i];
                tmp++; ans[tmp].l=p[i+1]; ans[tmp].r=p[i+1];
            } else {
                tmp++; ans[tmp].l=p[i]; ans[tmp].r=p[i+1]-1;
                tmp++; ans[tmp].l=p[i+1]; ans[tmp].r=p[i+1];
            }
        }
    }
    if(p[cnt]!=n){
        tmp++; ans[tmp].l=p[cnt]+1; ans[tmp].r=n;
    }
    print(tmp),pc('\n');
    for(i=1;i<=tmp;i++) print(ans[i].l),pc(' '),print(ans[i].r),pc('\n');
}