专栏文章

题解：P13832 【MX-X18-T4】「FAOI-R6」绿茶

HHim_shu
P13832题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio4x512
此快照首次捕获于
2025/12/02 13:25
3 个月前
此快照最后确认于
2025/12/02 13:25
3 个月前
查看原文

背景

考场会做，调到现在，因为小错误浪费三个小时，劝大家错了用对拍调试。
这题我认为应该凭绿更恰当一点。

题意

你有两个 nn 位二进制数 A,BA,B（可能有前导 0）和一个序列 c0,c1,…,cn−1c_0, c_1, \ldots, c_{n - 1}。
花费 ckc_k 的代价让 AA 或上 A+2KA+2^K 或 A−2KA-2^K。
求 AA 变成 BB 的最小代价，不行就输出 −1-1。

分析

因为 AA 每次只能变大，二进制包含 AA 的肯定可以达到，所以当存在 kk 有 Ak>BkA_k>B_k 则输出 −1-1，否则肯定可以达到。
代码CPP
for(int i=0;i<n;i++)
    if(s1[i]>s2[i]){puts("-1");return;}

先考虑 BB 是全 11 的情况。

之后我们考虑如何变 AA。
问题1：一开始我们想是不是每一位空的加上 ckc^k 解决，就是最优呢？
回答1：
其实不一定，样例
CPP
6
001001
111111
8 4 7 3 6 2
就是反例，明显从小到大，有空的直接加上 11，考虑进位所以每一位都能或上。 想这样做：
CPP
001001+1=001010
相或=001011
001011+1=001100
相或=001111
这样子对于前面的明显更优。
问题2：难道这个已经是答案了吗？
回答2：NoNo！我们都没有考虑花费 ckc_k 的代价让 AA 或上 A−2KA-2^K 的情况。
那么如何解决？玩一下样例便知
CPP
10
0000000000
1111111111
1 1 4 5 1 4 1 9 1 9
一位一位的操作明显不优，是不是可以对最高位加个 11 再对 最低位减个 11 实现用两个操作实现对整个的修改，具体可以看下面。
CPP
0000000000+1000000000=1000000000
相或=1000000000
1000000000-1=0111111111
相或=1111111111
考虑到低位不好被高位修改，所以可以从低往高走，可以考虑 DPDP。
状态：dpidp_i 表示前 ii 位已经复原的最小代价。
转移：分两种情况：
  • 从 i−1i-1 通过回答1的方式转移 dpi=dpi−1+mincdp_i=dp_{i-1}+minc
  • 从 j<ij<i 通过回答2的方式转移 dpi=min⁡(dpj+cj+1+c[i])dp_i=\min(dp_j+c_{j+1}+c[i])，jj 到 ii 没有 11 在 AA 中。
前面说是先考虑 BB 是全 11 的情况。
BB 当不是全 11 的情况下，可以按 00 分段就解决了。

Code

暴力：
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353,inf=1e14;
int n;
int c[N];
string s1,s2;
int dp[N];
void work(){
    cin>>n;
    cin>>s1>>s2;
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());//方便从低到高，当然不变也可以
    s1[n]=s2[n]='0';//在最后分段
    for(int i=n-1;i>=0;i--)
        cin>>c[i];

    for(int i=0;i<n;i++)
        if(s1[i]>s2[i]){puts("-1");return;}//判-1

    int ans=0;
    memset(dp,0,sizeof(dp));
    dp[0]=(s1[0]!=s2[0])*c[0];
    for(int i=1;i<=n;i++){
        if(s2[i]=='0'){
            ans+=dp[i-1];
            dp[i]=0;
            continue;
        }//分段
        if(s1[i]=='0'){
            int mi=inf;
            for(int j=i;j>=0&&s2[j]=='1';j--)
                mi=min(mi,c[j]);
            dp[i]=dp[i-1]+mi;//通过回答1的方式转移
            for(int j=i-2;j>=-1&&s2[j+1]=='1'&&s1[j+1]=='0';j--)
                dp[i]=min(dp[i],(j<0?0:dp[j])+c[j+1]+c[i]);
            //通过回答2的方式转移
        }
        else{
            dp[i]=dp[i-1];//已经相同回答1的方式转移可以继承上一个
            for(int j=i-2;j>=-1&&s2[j+1]=='1'&&s1[j+1]=='0';j--)
                dp[i]=min(dp[i],(j<0?0:dp[j])+c[j+1]);//同理
        }
    }
    cout<<ans<<"\n";
}
signed main(){
    int _;
    cin>>_;
    while(_--)work();
    return 0;
}
考虑到都是连续的所以可以用变量一遍枚举位的时候，一遍统计，遇到分段要从新搞。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353,inf=1e14;
int n;
int c[N];
string s1,s2;
int dp[N];
void work(){
    cin>>n;
    cin>>s1>>s2;
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());
    s1[n]=s2[n]='0';
    for(int i=n-1;i>=0;i--)
        cin>>c[i];
    
    for(int i=0;i<n;i++)
        if(s1[i]>s2[i]){puts("-1");return;}
    
    int ans=0;
    memset(dp,0,sizeof(dp));
    
    
    int mi=c[0],mi_dp=(s1[0]=='0'?c[0]:inf);
    //mi对于回答1的方式转移做统计
    //mi_dp对于回答2的方式转移做统计
    //下面同理
    for(int i=0;i<=n;i++){
        if(s2[i]=='0'){
            ans+=(i<1?0:dp[i-1]),
            mi=inf,mi_dp=c[i+1];
            continue;
        }
        
        mi=min(mi,c[i]);
        
        if(s1[i]=='0')
            dp[i]=min(mi_dp+c[i],dp[i-1]+mi),
            mi_dp=min(mi_dp,dp[i-1]+c[i]);
        
        else
            dp[i]=min(dp[i-1],mi_dp),
            mi_dp=inf;
    }
    // for(int i=0;i<n;i++)cout<<dp[i]<<' ';
    cout<<ans<<"\n";
}
signed main(){
    int _;
    cin>>_;
    while(_--)work();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...