题解归档 - cf2229C2

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2229C2
• 本地来源：problems/cf2229C2/idea.md
• 题目链接：https://codeforces.com/contest/2229/problem/C2
• 原始标题：cf2229C2

思路

cf2229C2

pattern: best weighted mask under an upper bound.

claim: The reachable final sign masks are exactly all binary masks T with 0 <= T <= M, where M is the initial positive-sign mask. To maximize the sum, either keep T=M, or choose the first high bit where T becomes smaller than M: that bit must be an original 1 changed to 0, and all lower bits should be 1.

necessary: Once T is already smaller than M at bit i, every lower bit is unconstrained by the upper bound and should be positive because all absolute values are positive weights.

sufficient: For a chosen bit i, first use the C1 zero-construction on the lower i-1 bits, making them all negative while not touching bit i. Then apply operation i, which turns bit i negative and all lower bits positive. Higher bits stay equal to M.

brute/check: For small n, BFS all reachable sign masks and compare the produced sequence with the maximum reachable sum.

edge: If the original mask itself is best, output zero operations.

代码

来源：problems/cf2229C2/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll s[maxn+5],las[2][maxn+5],pre[maxn+5],suf[maxn+5];
vector<ll>ans;
void go(ll r,ll zc){
    ll x;
    if(r<=0) return;
    x=las[zc^1][r];
    if(x==0) return;
    ans.push_back(x);
    go(x-1,zc^1);
}
int main(){
    ll t,n,i,best,cur,pos;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        las[0][0]=las[1][0]=pre[0]=0;
        for(i=1;i<=n;i++){
            scanf("%lld",&s[i]);
            las[0][i]=las[0][i-1];
            las[1][i]=las[1][i-1];
            if(s[i]>0) las[1][i]=i;
            else las[0][i]=i;
            pre[i]=pre[i-1]+llabs(s[i]);
        }
        suf[n+1]=0;
        for(i=n;i>=1;i--){
            suf[i]=suf[i+1]+s[i];
        }
        best=suf[1];
        pos=0;
        for(i=1;i<=n;i++){
            if(s[i]>0){
                cur=suf[i+1]-llabs(s[i])+pre[i-1];
                if(cur>best){
                    best=cur;
                    pos=i;
                }
            }
        }
        ans.clear();
        if(pos){
            go(pos-1,0);
            ans.push_back(pos);
        }
        printf("%lld\n",(ll)ans.size());
        for(i=0;i<ans.size();i++){
            if(i) printf(" ");
            printf("%lld",ans[i]);
        }
        printf("\n");
    }
    return 0;
}