The 2022 ICPC Asia Regionals Online Contest (I)-D题题解(DFS暴搜+剪枝+打表去重+二分)_杭州2022icpc题解-程序员宅基地
这次比赛很好，题也很好，就是下午人不太清醒，没做出来太菜了，回去才写出来的。
比赛原题已经上架到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的数的数量，我搜出来差不多有这么多
智能推荐
【WebApi】————.net WebApi开发（一）_webapi .net-程序员宅基地
文章浏览阅读8.5k次。【1】.部署环境.net4及以上版本。【2】.vs2010 开发需单独安装vs2010 sp1和mvc4mvc4：http://www.asp.net/mvc/mvc4【3】.开发1.新建项目选择ASP.net MVC 4 Web应用程序2.选择Web API 3.在新建立的项目里面有已经生成的webapi模版其中App_Start文件夹下WebApiCo..._webapi .net
几招教你阻止百度搜索自动跳转百度APP（其他网站也适用）！_百度自动跳转app怎么解决-程序员宅基地
文章浏览阅读10w+次，点赞15次，收藏33次。最近阿虚看到个消息说「百度」发布了新政策，禁止网站通过搜索引擎打开后折叠内容强迫下载APP客户端听起来似乎是百度难得良心一回？但实际上该政策仅限于手机百度APP内如果你是通过浏览器用百度搜索则与新政策完全没关系正好前不久不少粉丝来问过我这样一个问题：怎么屏蔽手机浏览器上的「跳转某某APP打开查看」提示那今天阿虚就来教一下怎么解决吧，毕竟这东西的确是有点烦人…屏蔽「跳转某某APP打开查看」这个问题我细看了下，还得分俩类：文章只能显示部分，然后提示你需要安装APP才能查看的，这种应该是大_百度自动跳转app怎么解决
PHP快速入门12-异常处理，自定义异常、抛出异常、断言异常等示例_php 抛出异常-程序员宅基地
文章浏览阅读843次。PHP的异常处理机制可以帮助我们在程序运行时遇到错误或异常情况时，及时发出警告并停止程序继续运行。下面是10个例子，分别展示了PHP异常处理的不同用法。_php 抛出异常
linux 清空docker容器日志_linux清理docker容器log-程序员宅基地
文章浏览阅读221次。【代码】linux 清空docker容器日志。_linux清理docker容器log
青岛大学开源OJ平台搭建_github oj开源-程序员宅基地
文章浏览阅读7.3k次，点赞3次，收藏15次。源码地址为:https://github.com/QingdaoU/OnlineJudge可参考的文档为:https://github.com/QingdaoU/OnlineJudgeDeploy/tree/2.0一、安装所依赖的环境sudo apt-get update && sudo apt-get install -y vim python-pip curl g..._github oj开源
浅谈数据安全-程序员宅基地
文章浏览阅读4.4k次。在《网络安全法》中，虽然已经明确了要求保障网络数据的完整性、保密性、可用性的能力，但随着近些年数据安全热点事件的出现，如数据泄露事件、个人信息滥用事件。表明对数据保护的要求仅依赖《网络安全法》中的几款条例是不足以支撑的。因此2021年9月1日《中华人民共和国数据安全法》便正式诞生，从此数据安全也被推上了风口浪尖。那么数据安全如何定义？与传统网络安全有何区别？数据安全体系又应该如何建立？..._数据安全
随便推点
联想笔记本G510升级固态硬盘(SSD)血泪教程!!!_联想g510更换固态硬盘-程序员宅基地
文章浏览阅读8.5w次，点赞23次，收藏55次。#联想笔记本G510升级固态硬盘(SSD)血泪教程!!!用了5年的联想笔记本G510,经过了四年的游戏历程,然后四年后还老当益壮的挣扎在我工作的战斗一线,是我并肩作战多年,比兄弟还要亲的兄弟,虽然此时已经身躯残破,反应迟缓我依旧不舍得抛弃它(主要是没钱!)然后为了我个人的用户体验决定花少量的票子,让它多挣扎一会,最好是能坚持到我度过贫困期. 下面是我升级的悲催历程! - 首先为了提升运行速..._联想g510更换固态硬盘
问题记录——正则表达式匹配控制符_正则表达式匹配控制字符-程序员宅基地
文章浏览阅读910次。问题前端用xterm.js通过websocket连接docker虚拟终端，返回的字符中包括如下字符串，其中有两个控制字符，“ESC"和"BEL” ，想通过正则表达式匹配这一段字符，然后去掉这段字符:参考文档控制字符编码表转义符对照表通过上面查询得知，"ESC"和"BEL"这两个控制符的ASCII码分别为：十进制为27和7，十六进制为0x1B和0x07，转义符分别为：\e和\a代码**注意：**直接使用ASCII码匹配是不行的，一定要用转义符才行。如下测试代码中，只有regex3才能匹_正则表达式匹配控制字符
Android RIL框架分析-程序员宅基地
文章浏览阅读1.5k次。1.RIL框架 RIL，Radio Interface Layer。本层为一个协议转换层，提供Android Telephony与无线通信设备之间的抽象层。 Android RIL位于Telephony Frameworks之下，Modem之上的，根据源码，RIL可以分为两个部分:Frameworks 框架层中的java程序，简称RILJ。HAL层中C/C++程序，简称RILC，RILC具体的又包括LibRIL、Rild和Reference-RIL这三个部分。 Andr..._ril框架
Python编程基础：第六节 math包的基础使用Math Functions_ps math function-程序员宅基地
文章浏览阅读565次。第六节 math包的基础使用前言实践前言我们通常会对数值型变量进行计算，这里我们给出一些常用的函数用于辅助你的计算过程。常用的数学计算函数均在math包。实践首先我们导入math包，并定义一个浮点型变量pi将其赋值为3.14：import mathpi = 3.14如果我们需要计算浮点型变量四舍五入后的计算结果，用函数round()即可：print(round(pi))>>> 3如果我们需要向上取整，那就需要函数math.ceil()：print(math.cei_ps math function
canal异常 Could not find first log file name in binary log index file_canal could not find first log file name in binary-程序员宅基地
文章浏览阅读4.4k次，点赞3次，收藏2次。Could not find first log file name in binary log index file问题解决解决过程问题最近在使用canal来监测数据库的变化，处理变动的数据。由于有一段时间没有用了，这次启动在日志文件中看到这个异常 Could not find first log file name in binary log index file，详细信息如下：2020-12-16 19:14:42.053 [destination = tradeAndRefund , addr_canal could not find first log file name in binary log index file
【练习】生成10个1到20之间的不重复的随机数并降序输出-程序员宅基地
文章浏览阅读960次。分析：1.创建一个Random对象；2.创建一个hashset的集合对象；3.循环生成10个1-20的随机数4.输出。package edu.xalead;import java.util.*;public class Test { public static void main(String[] args) { Random r...