题解归档 - cf2231D

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

• 本地编号：cf2231D
• 本地来源：problems/cf2231D/idea.md
• 题目链接：https://codeforces.com/contest/2231/problem/D
• 原始标题：cf2231D Maximum Prefix Sums

思路

cf2231D Maximum Prefix Sums

数学记录

• pattern: prefix transform / interval feasibility.
• claim: 令 b_i=sum(a_1..a_i)。必须有 b_i<=c_i；如果 i=1 或 c_i>c_{i-1}，还必须有 b_i=c_i。
• necessary: c 非降；所有已知位置的前缀增量必须能保持上述等式/不等式。
• sufficient: 对每段“一个未知位置 + 后面连续已知位置”选择未知后的前缀值 x，只要满足所有 forced equality 和 upper bounds，就能构造该段。
• brute/check: 区间 DP 判断是否存在；checker 重算输出数组的 prefix maximum。

做法

顺序扫描。遇到已知位置，直接更新当前前缀并检查：

• 当前前缀不能超过 c_i。
• 若 c_i 是新的前缀最大，则当前前缀必须等于 c_i。

遇到未知位置 l，把它和后面连续已知位置组成一段 [l,r]。设未知位置之后的前缀是 x，后面已知增量贡献为 off。整段给出：

• x+off <= c_k；
• 若 c_k 新增，则 x+off = c_k。

若存在 forced value，则 x 必须等于它；否则取可行上界。最后把 a_l=x-prev 写回。

验证

• python tools/run_exe.py cf2231D 通过官方样例。
• python tools/stress2.py cf2231D -n 500 --keep-fail 通过，使用 check.cpp 验证构造。
• 旧 fail.in 通过 checker。
• n=200000 随机合法大输入冒烟通过。

代码

来源：problems/cf2231D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll INF=4000000000000000000LL;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        string s;
        cin>>s;
        vector<ll>a(n+1),c(n+1),ans(n+1),b(n+1);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
        bool ok=true;
        for(int i=2;i<=n;i++) if(c[i]<c[i-1]) ok=false;
        ll prev=0;
        for(int i=1;i<=n && ok;){
            if(s[i-1]=='1'){
                ll cur=prev+a[i];
                if(cur>c[i]) ok=false;
                if((i==1 || c[i]>c[i-1]) && cur!=c[i]) ok=false;
                ans[i]=a[i];
                b[i]=cur;
                prev=cur;
                i++;
                continue;
            }
            int l=i,r=i;
            while(r+1<=n && s[r]=='1') r++;
            ll off=0,upper=INF,need=0;
            bool has=false;
            for(int k=l;k<=r;k++){
                if(k>l) off+=a[k];
                upper=min(upper,c[k]-off);
                if(k==1 || c[k]>c[k-1]){
                    ll val=c[k]-off;
                    if(has && val!=need) ok=false;
                    has=true;
                    need=val;
                }
            }
            if(!ok) break;
            ll x=has?need:upper;
            if(x>upper) ok=false;
            if(!ok) break;
            ll lost=x-prev;
            if(lost<-1000000000000000000LL || lost>1000000000000000000LL) ok=false;
            ans[l]=lost;
            off=0;
            for(int k=l;k<=r;k++){
                if(k>l){
                    off+=a[k];
                    ans[k]=a[k];
                }
                ll cur=x+off;
                b[k]=cur;
                if(cur>c[k]) ok=false;
                if((k==1 || c[k]>c[k-1]) && cur!=c[k]) ok=false;
            }
            prev=b[r];
            i=r+1;
        }
        if(!ok){
            printf("No\n");
        }else{
            printf("Yes\n");
            for(int i=1;i<=n;i++) printf("%lld%c",ans[i],i==n?'\n':' ');
        }
    }
    return 0;
}