ABC301D题解

· · 题解

本文章同步发表于博客园

思路

算法：贪心。

我们可以将 s 想象成一个二进制数，每一位都有它对应的权值。

我们将 N 依次减去已经确定的位的权值，如果减完后 N\lt0，则 ? 即使都填 0，值也大于 N，输出 -1 即可。

接下来，我们就贪心的从第一位（二进制数下的最高位）开始枚举，如果当前位置为 ?，那么：

最后，将 s 转化成 10 进制数，输出即可。

贪心的正确性证明

如果将当前位置改为 1，最后的值仍然小于等于 N，则贪心的这个位置改为 1。

反证法，如果当前位置不选 1，那么由于在二进制下，第一个为值不同时，值为 1 的一定最大，则后面不管怎么选，都不是最大的答案。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long n,now,ans;
char s[100];
int si; 
int main(){
    scanf("%s",s+1);
    scanf("%lld",&n);
    si=strlen(s+1);
    now=1ll<<(si-1);
    for(int i=1;i<=si&&n>=0;i++){
        if(s[i]=='1') n-=now;
        now>>=1;
    }
    if(n<0) return !printf("-1");
    now=1ll<<(si-1);
    for(int i=1;i<=si;i++){
        if(s[i]=='?'){
            if(now<=n) s[i]='1',n-=now;
            else s[i]='0';
        }
        now>>=1;
    }
    for(int i=1;i<=si;i++) ans=(ans<<1ll)+1ll*s[i]-'0';
    printf("%lld",ans);
    return 0;
}