题解归档 - cf2229C1

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

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

思路

cf2229C1

pattern: prefix flips as decreasing binary masks.

claim: Encode the signs as a binary number M, where bit i is 1 iff a_i is positive. One operation at i is allowed exactly when bit i is 1, and then toggles all lower bits 1..i. This always decreases the number, and every mask from 0 to M is reachable in at most n operations.

necessary: If the i-th bit is 1, toggling the low i bits replaces that low block by its complement. Since the top bit of this block was 1, the numeric value strictly decreases.

sufficient: To reach zero, repeatedly take the highest current 1 bit and apply that operation. After applying it, the lower block is complemented; maintaining a lazy complement flag lets us find the next highest current 1 in O(1) by prefix last-position arrays. This uses at most one operation per bit.

brute/check: For small n, BFS all reachable sign masks and verify the produced operations are legal and reach the minimum sum.

edge: If there is no positive bit, output zero operations.

代码

来源：problems/cf2229C1/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];
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;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        las[0][0]=las[1][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;
        }
        ans.clear();
        go(n,0);
        printf("%lld\n",(ll)ans.size());
        for(i=0;i<ans.size();i++){
            if(i) printf(" ");
            printf("%lld",ans[i]);
        }
        printf("\n");
    }
    return 0;
}