【ABC301D】题解

fengxiaoyi / 2023-05-17 / 原文

本文章同步发表于洛谷

思路

算法：贪心。

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

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

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

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

最后，将 \(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;
}

如果对你有帮助，点赞关注一下吧qwq。
这对我有很大的鼓励qwq。
如果有什么疑问或错误的地方，欢迎讨论区指出，谢谢qwq。