ICPC 2022网络赛(1) - D Find the Number（暴搜预处理）

https://pintia.cn/problem-sets/1571150153619189760/problems/1571150314621562883

题意
定义 $ctz(x)$ 为 $x$ 的二进制表示后缀 $0$ 的个数；$popcount(x)$ 为 $x$ 的二进制表示中 $1$ 的个数。
如果 $ctz(x)=popcount(x)$，则称 $x$ 为一个好数。

一共 T 次询问，每次询问给出一个区间 $[l,r]$，找到区间中的任意一个好数。不存在输出 -1。

$1\le T\le 10^5,1\le l\le r\le 10^9$

思路
一共 1e9 个数，但是满足描述中严格限制的只有 5e5 个数。
一共30位，暴搜+剪枝完全可以求出所有满足的数。所有数预处理出来。
后面对于每个询问，找到第一个大于等于左端点的满足的数，判断是否在区间中。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 2000010, mod = 1e9+7;
int T, n, m;
int a[N], sum;
int ans[N], idx;
vector<int> v;

void dfs(int u)
{
	if(u > 30)
	{
		if(sum) return;
		
		int x, res = 0;
		for(int i=1;i<=30;i++)
		{
			if(i == 1) x = 1;
			else x *= 2;
			
			if(a[i]) res += x;
		}
		v.push_back(res);
		return;
	}
	
	if(sum)
	{
		sum --;
		a[u] = 1;
		dfs(u+1);
		sum ++;
	}
	
	a[u] = 0;
	dfs(u+1);
}

signed main(){
	for(int i=1;i<=16;i++)
	{
		for(int j=1;j<=i;j++) a[j] = 0;
		a[i + 1] = 1;
		sum = i - 1;
		dfs(i+2);
	}
	
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	
	cin >> m;
	while(m--)
	{
		int l, r; cin >> l >> r;
		auto it = lower_bound(v.begin(), v.end(), l);
		
		if(it == v.end()) cout << -1;
		else
		{
			int x = *it;
			if(x > r) cout << -1;
			else cout << x;
		}
		if(m) cout << "\n";
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

经验
多用点野路子，不是它说啥就是啥。不要光跟着它的思路走。
能 a 掉题目的方法都是好方法。