The 2022 ICPC Asia Regionals Online Contest (I)-D题题解(DFS暴搜+剪枝+打表去重+二分)

这次比赛很好，题也很好，就是下午人不太清醒，没做出来太菜了，回去才写出来的。
比赛原题已经上架到PTA了：点击跳转

题目

解释

题目意思其实很简单，就是给你一个[l, r]的区间你去找一个数，满足他后缀连续的0的个数等于前面的1的个数，举个例子68：二进制形式1000100，后缀连续的零的个数ctz(68)=2，前面1的个数popcount(68)=2，刚好相等所以他就是一个good的数。

思路

方法：DFS暴搜+剪枝+打表去重+二分

题目的意思不就是让你怎么去排列后缀零前面的1的位置和个数，直接用dfs暴搜出所有的good数，因为x只有1e9的范围，二进制也就是30位，我们从高往低去搜，当前位选1或者0，用两层for循环，外面那层我们用来枚举位数，里面枚举后缀0的个数。

dfs传递的是我们枚举的后缀0的个数now(需要多个1)，当前到dfs哪一位step以及用了几个1(one)。

剪枝：我们当前位超过了后缀0的个数就return。

我们搜出now == one的时候就是good的数，用unordered_map和vector用来去重和保存。

dfs搜完后，把vector的数sort一下，后面求区间内的数用lowwer_bound(l)找就行。

代码

#include
#define CL(a,b)  memset(a,b,sizeof(a))
using namespace std;
const int maxn = 1e5+10;
const int mod  = 1e9+7;

int T, l, r;
vector<int>num;
unordered_map<int,int>nums;
int tot;
void dfs(int now,int step,int need) {
	if(now==need) {
		if(!nums[tot])num.push_back(tot);
		nums[tot]=1;
		return;
	}
	if(step==now)return;
	for(int i=1; i>=0; i--) {
		if(i)need++, tot += 1 << step;
		step--;
		dfs(now,step,need);
		step++;
		if(i)need--, tot -= 1 << step;
	}
	return;
}

void solve() {
	for(int len = 30 ; len >= 2; len--) //构造的数的长度
		for(int p = 1; p <= len / 2 ; p++) { //构造末尾0
			tot = 1 << p;
			dfs(p,len-1,1);
		}
}

int getnum(int l) {
	return lower_bound(num.begin(),num.end(),l)-num.begin();
}

int main() {
	solve();
	sort(num.begin(),num.end());
	scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d",&l,&r);
        int ans = num[getnum(l)];
        if(ans <= r)printf("%d\n", ans);
        else printf("-1\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

复杂度分析

• 时间复杂度：O(2²⁷ + nlog(n) + T * log(n))，2²⁷是DFS打表的时间，nlog(n)是vertor排序的时间，T*log(n)是询问次数和二分搜答案的时间。(如果算错了，评论或者私信指出谢谢)
• 空间复杂度：O(n)，n表示good的数的数量，我搜出来差不多有这么多