2022ICPC网络赛 D Find the Number（子集生成）

D Find the Number（子集生成）

题目：

​ 定义一个01串为好串：其二进制表示的后缀0和其二进制表示中1的个数相同。给出2e5次询问，若\([l,r]\)内存在一个整数的二进制串为好串的话，请输出任意一个在\([l,r]\)中的好串的十进制表示，否则输出-1。

思路：

​ 我们可以想到两种思路，一种是预处理子集后用二分进行查询。第二种是对于每次查询构造一个可行解。通过打表可以发现，子集的个数是5e5，可以通过爆搜剪枝来完成对子集的预处理，而且构造可行解难度过大，于是选择第一种思路。

实现：

​ 枚举每一位，要么填0要么填1，只需要在最后注意一下在结尾填长度为1的个数的0就可以了。其中有一步剪枝操作需要注意，当当前长度+其补零后的长度大于题目限制，就直接return。

#include <bits/stdc++.h>

using namespace std;

vector<int> v;

int to_ten(const vector<int> &a)
{
    int res = 0;
    for(int x : a)
        res = res * 2 + x;
    return res;
}

void dfs(vector<int>& cur, int cnt1)
{
    if(cur.size() + cnt1 > 30) return; //放不了0了
    
    cnt1 ++;
    cur.push_back(1);
    if(cur.size() + cnt1 <= 30)
        v.push_back(to_ten(cur) << cnt1);
    cnt1 --;
    cur.pop_back();
    
    cur.push_back(1);
    dfs(cur, cnt1 + 1);
    cur.pop_back();
    
    if(cur.size())
    {
        cur.push_back(0);
        dfs(cur, cnt1);
        cur.pop_back();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    vector<int> st; st.clear();
    dfs(st, 0);
    
    int q;
    cin >> q;
    sort(v.begin(), v.end());
    while(q --)
    {
        int l, r;   
        cin >> l >> r;
        auto pos = lower_bound(v.begin(), v.end(), l);
        if(pos == v.end())
        {
            cout << "-1\n";
        }
        else 
        {
            if(*pos > r)   
                cout << "-1\n";
            else
                cout << *pos << '\n';
        }
    }   
    return 0;
}