这次比赛很好，题也很好，就是下午人不太清醒，没做出来太菜了，回去才写出来的。
比赛原题已经上架到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<bits/stdc++.h> #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; }
复杂度分析
- 时间复杂度：O(227 + nlog(n) + T * log(n))，227是DFS打表的时间，nlog(n)是vertor排序的时间，T*log(n)是询问次数和二分搜答案的时间。(如果算错了，评论或者私信指出谢谢)
- 空间复杂度：O(n)，n表示good的数的数量，我搜出来差不多有这么多
