题目描述

难度分:$885$

输入长度$\leq 60$的字符串$s$，只包含0，1和?。

输入$n(1 \leq n \leq 10^{18})$。

你需要把$s$中的?替换成0或1，从而得到一个二进制数$x$。

问：不超过$n$的最大$x$是多少？以十进制形式输出这个最大值。如果不存在这样的$x$，输出$-1$。

输入样例$1$

?0?
2

输出样例$1$

1

输入样例$2$

101
4

输出样例$2$

-1

输入样例$3$

?0?
1000000000000000000

输出样例$3$

5

算法

DFS+剪枝

定义递归函数$dfs(i,sum)$，其中$i$是当前需要填数的数位，$sum$是数位$[0,i)$填完之后的结果。设字符串$s$的长度为$len$，索引从$0$（高位）开始，从高位开始填：

1. 如果$s[i] \neq$?，那就填数字$s[i]$，继续递归$dfs(i+1,sum+s[i] \times 2^{len-i-1})$。

2. 如果$s[i]=$?，那就可以填数了。这里做个贪心，优化一下搜索顺序，为了结果尽可能大，先填$1$，若后续$dfs(i+1,sum+2^{len-i-1})$能得到合法答案，就没有必要填$0$了，否则还需要在当前数位填$0$试试。

如果在DFS的过程中发现$sum \gt n$成立，就不用再往深搜了，这条分支肯定搜不到答案。只要到底了，即$i \geq len$，说明中间没有发生过与题目要求冲突的地方，产生一个合法解$sum$。

复杂度分析

时间复杂度

每个?的位置可以选填$0$和$1$，最差情况下$s$串全是问号，时间复杂度在$O(2^n)$级别，但由于做了剪枝、并优化了搜索顺序，因此时间复杂度远远低于这个理论的复杂度。

空间复杂度

空间复杂度为递归树的高度，最差情况下应该是$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL n, ans;
int len;
string s;

void dfs(int i, LL sum) {
    if(sum > n) return;
    if(i >= len) {
        ans = sum;
        return;
    }
    if(s[i] == '?') {
        dfs(i + 1, sum + (1ll<<(len - i - 1)));
        if(ans != -1) return;
        dfs(i + 1, sum);
    }else {
        int d = s[i] - '0';
        dfs(i + 1, sum + (1ll<<(len - i - 1))*d);
    }
}

int main() {
    cin >> s;
    len = s.size();
    scanf("%lld", &n);
    ans = -1;
    dfs(0, 0);
    printf("%lld\n", ans);
    return 0;
}