D
这道题被卡了很久。。。惭愧。。。
题意
给你一个由\([0, 1, ?]\)组成的字符串\(S\)和一个数\(N\)（\(N \leq 10^{18}\)），你可以把一个 \(?\) 变成 0 或者 1，问\(S\)最大能表示的不超过\(N\)的数是多少。
正解
先判断 -1 的情况：S能表示的最小的数是所有❓都填0所表示的数字，如果这个数都大于\(N\)，肯定是无解的，否则有解
策略：如果某一位❓填1仍然\(\leq N\)，就填1，否则填0
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
string s, t;
ll n, ans;
int main() {
cin >> s >> n;
int len = s.length();
for(int i = 0; i < len; i++) {
if(s[i] == '1') ans |= (1ll << (len - 1 - i));
}
if(ans > n) {
puts("-1");
return 0;
}
for(int i = 0; i < len; i++) {
if(s[i] == '?') {
if((ans | (1ll << (len - 1 - i))) <= n) ans |= (1ll << (len - 1 - i));
}
}
printf("%lld\n", ans);
return 0;
}
我的错解
我的思路不是比较数值大小，是比较字符串（没过脑。。。。）
错的点在于考虑漏了一种情况（悲，修改后即可ac
debug超久总算ac的shishan代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
string s, t;
ll n;
int main() {
cin >> s >> n;
int len = s.length(); // 2 ^ [len - 1, ... ,0]
// n转字符串
for(int i = 0; i <= 60; i++) {
if((n & (1ll << i)) != 0) t.push_back('1'), n -= (1ll << i);
else t.push_back('0');
if(!n) break;
}
reverse(t.begin(), t.end());
// cout << "t : " << t << endl; ///
// t更长 直接输出
if(t.length() > len) {
ll ans = 0;
for(int i = 0; i < len; i++) {
if(s[i] != '0') ans = ans * 2 + 1;
else ans *= 2;
}
cout << ans << endl;
return 0;
}
// t短 补全
if(t.length() < len) {
int times = len - t.length();
for(int i = 1; i <= times; i++) t = "0" + t;
// cout << "t : " << t << endl; ///
}
// 找 最初的上1下0 并看是否能补救 !!!!!!WA的原因：10之前可能已经有01了,修改后即可ac
int flag = -1;
bool occur = 0;
for(int i = 0; i < len; i++) {
if(s[i] == '1' && t[i] == '0' && !occur) {
flag = i;
break;
}
if(s[i] == '0' && t[i] == '1') {
occur = 1;
break;
}
}
if(flag != -1) {
bool ok = 0;
for(int i = flag - 1; i >= 0; i--) {
if(t[i] == '1' && (s[i] == '0' || s[i] == '?')) {
ok = 1;
s[i] = '0';
break;
}
}
if(!ok) {
puts("-1");
return 0;
}
}
// 照搬 or 可以全1
bool f = 0;
for(int i = 0; i < len; i++) {
if(s[i] == '?') {
if(!f) s[i] = t[i];
else s[i] = '1';
}
else {
if(s[i] == '0') {
if(!f && t[i] == '1') f = 1;
}
}
}
ll ans = 0;
for(int i = 0; i < len; i++) {
if(s[i] == '1') ans = ans * 2 + 1;
else ans *= 2;
}
cout << ans << endl;
return 0;
}
总结
这次的D题让我想到了以前的很多时刻。
我总是这样，常常出现在写模拟题的时候，在思路还不明晰的时候匆忙开始，然后一直一直debug，最后还不保证能解决问题。
我把它总结为因为一时的懒惰而要花费巨大的代价（比如这次还用Mac对拍了，虽说这也是必备技能）去弥补。
得 不 偿 失 。
以后再遇到类似的情况，我一定要先在纸上写下清晰的过程，再开始做。
谢谢trq让我意识到这个问题，看来我还有很大的上升空间呀（
标签：思维,ABC,int,301,ll,len,++,long,ans From： https://www.cnblogs.com/re0acm/p/17398921.html