ICPC 2022 网络赛 d ( 数位dp + 二分
#include<bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using ll = long long;
const int mod = 998244353;ll n;
int d[100];
int dp[60][40][40][2];
set<int> s;
//枚举数位,枚举这一位余数是几
//每一位的限制,
int dfs(int pos , int ct1 , int h0 , int lead0 , int limit){if(pos == -1){if(ct1 == h0 && ct1) return 1;else return 0;}auto x = dp[pos][ct1][h0][lead0];if(x != -1 && !limit) return x;x = 0;int up = limit ? d[pos] : 1;for(int i = 0 ; i <= up ; i++){int t = ct1 + (i == 1);int h;if(!lead0 && i == 0) h = h0 + 1;else h = 0;x += dfs(pos - 1 , t , h , lead0 && i == 0 , limit && i == up); }if(!limit) dp[pos][ct1][h0][lead0] = x;return x;}
int work(int x){int idx = -1;while(x){d[++idx] = x % 2;x/=2;}//memset(dp , -1 , sizeof dp);return dfs(idx , 0 , 0 ,1, 1);
}void solve(){int l,r;cin>>l>>r;if(s.size()){int t = * s.lower_bound(l);if(t >= l && t <= r){cout<<t<<"\n";return;}}int ct = work(l-1);if(work(r) - ct == 0){cout<<-1<<"\n";return;}//cout<<work(68) - work(67)<<"\n";//int ll = l , rr = r;while(l < r){int mid = (l + r) >> 1;if(work(mid) - ct > 0){r = mid;}else{l = mid + 1;}}cout<<l<<"\n";s.insert(l);} int main(){memset(dp , -1 , sizeof dp);int t;cin>>t;while(t--){solve();}
}
考虑到各个数的状态 , 可能会存在一些共同的,因此不一定每次都要memset
每个数的limit状态不一定相同 , 把这个作为搜索的内容,其他的都可以设计再dp状态里面
相关文章:
ICPC 2022 网络赛 d ( 数位dp + 二分
#include<bits/stdc.h> using namespace std; using VI vector<int>; using ll long long; const int mod 998244353;ll n; int d[100]; int dp[60][40][40][2]; set<int> s; //枚举数位,枚举这一位余数是几 //每一位的限制, int d…...
透视俄乌网络战之二:Conti勒索软件集团(下)
透视俄乌网络战之一:数据擦除软件 透视俄乌网络战之二:Conti勒索软件集团(上) Conti勒索软件集团(下) 1. 管理面板源代码2. Pony凭证窃取恶意软件3. TTPs4. Conti Locker v2源代码5. Conti团伙培训材料6. T…...
网络安全深入学习第一课——热门框架漏洞(RCE-命令执行)
文章目录 一、RCE二、命令执行/注入-概述三、命令执行-常见函数四、PHP命令执行-常见函数1、exec:2、system3、passthru4、shell_exec5、反引号 backquote 五、PHP命令执行-常见函数总结六、命令执行漏洞成因七、命令执行漏洞利用条件八、命令执行漏洞分类1、代码层…...
应用在电子体温计中的国产温度传感芯片
电子体温计由温度传感芯片,液晶显示器,纽扣电池,专用集成电路及其他电子元器件组成。能快速准确地测量人体体温,与传统的水银玻璃体温计相比,具有读数方便,测量时间短,测量精度高,能…...
JVM 虚拟机 ----> Java 内存模型(JMM)
文章目录 Java 内存模型(JMM)一、运行时数据区域划分二、程序计数器(Program Counter Register)计数器的作用 三、Java 虚拟机栈(VM Stack)四、本地方法栈(Native Method Stack)五、…...
指针-字符串替换
任务描述 从标准输入读入数据,每行中最多包含一个字符串 “_xy_”,且除了字符串“_xy_”外,输入数据中不包括下划线字符,请将输入行中的 “_xy_” 替换为 “_ab_”, 在标准输出上输出替换后的结果;若没有进行过满足条…...
docker 网络(单机环境)
文章目录 深入理解 Namespace什么是NamespaceNamespace当中的 Network Namespace Libcontainerdocker 网络基础创建两个命名空间创建网络接口 veth pair命名空间添加 veth 接口为 veth 接口分配 IP启动 veth 接口相互 ping bridge 网络搭建网络环境查看docker0 网桥创建网桥 br…...
14、二叉树的morris遍历等
统计热词 有一个包含100亿个URL的大文件,假设每个URL占用64B,请找出其中所有重复的URL 【补充】 某搜索公司一天的用户搜索词汇是海量的(百亿数据量),请设计一种求出每天热门Top100 词汇的可行办法 多个小文件的大根堆,然后把每…...
BeanFactory与ApplicationContext
BeanFactory与ApplicationContext的区别 使用Alt Ctrl U查看java类图 什么是BeanFactory接口 他是ApplicationContext的父接口他才是Spring 的核心容器,主要的ApplicationContext功能的实现都间接通过BeanFactory接口来实现 在ApplicationContext类中方法的实现是…...
【计算机网络】 粘包问题
文章目录 为什么会产生粘包问题?解决办法先发包大小再发包内容代码示例 为什么会产生粘包问题? tcp是数据流传输,是一种没有边界的,可以合并的传输数据方式。合并就要能拆开,拆不开就是粘包。 解决办法 设置标志位&a…...
valgrind massif 详解(内存分配释放分析)
参考 https://valgrind.org/docs/manual/ms-manual.html 使用格式 valgrind --toolmassif [--massif-opts] prog [prog-args]目的 记录每一次的malloc, free; 概念: malloc申请内存, 实际分配内存(字节对齐, 分配器的记录头, 等等原因) 对内存进行分析, 优化, 以达到资源…...
使用命令行创建一个vue项目卡住不动如何解决
问题 在使用命令去创建一个vue项目, 出现下面卡住不动的一个状态。 解决方案一 首先先ctrlc停止进入创建好的项目文件手动输入npm install 、npm run dev如果npm run dev 的时候 出现 ‘vite’ 相关的错误查看node版本是否是最新的稳定版本node -v查看安装源是否…...
七天学会C语言-第一天(C语言基本语句)
一、固定格式 这个是C程序的基本框架,需要记住!!! #include<stdio.h>int main(){return 0; }二、printf 语句 简单输出一句C程序: #include<stdio.h> int main(){printf("大家好,&quo…...
vue项目部署,出现两个ip的原因
我宁愿靠自己的力量打开我的前途,而不愿求有力者的垂青。——雨果 tags: 篇首语:本文由小常识网(cha138.com)小编为大家整理,主要介绍了vue项目部署,出现两个ip的原因相关的知识,希望对你有一定的参考价值。 参考技术A 在部署v…...
无涯教程-JavaScript - ASIN函数
描述 ASIN函数返回给定数字的反正弦或反正弦,并返回以弧度表示的Angular,介于-π/2和π/2之间。 语法 ASIN (number)争论 Argument描述Required/OptionalNumberThe sine of the angle you want and must be from -1 to 1.Required Notes 如果您希望ASIN函数返回的Angular以…...
MYSQL的SQL优化
insert语句 开启事务 手动控制事务 start transaction; insert into tb_test values(1,Tom),(2,Cat),(3,Jerry); insert into tb_test values(4,Tom),(5,Cat),(6,Jerry); insert into tb_test values(7,Tom),(8,Cat),(9,Jerry); commit; 内存插入 load命令中用 fields te…...
lintcode 553 · 炸弹袭击【中等 数组+bfs+模拟】
题目 https://www.lintcode.com/problem/553 给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 0), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固,所以墙不会被摧毁.你只…...
第一章 计算机系统概述 八、虚拟机
目录 一、传统虚拟机的结构 二、两类虚拟机管理程序 (1)定义: (2)区别:(考点) 一、传统虚拟机的结构 二、两类虚拟机管理程序 (1)定义: &…...
桶装水送水多水站送水员公众号h5开发
桶装水送水多水站送水员公众号h5开发 界面简洁易懂用户容易接受。 独家一户一码全家都能订水。 多个水站运营可按距离选择绑定。 三种支付方式水票、微信、到付。 强大员工系统老板坐享其成。 自由跑跑模式可招兼职送水员接单。 一户一码、全家享用 一户一码,精准…...
【JavaEE】多线程(二)
多线程(二) 文章目录 多线程(二)第一个多线程程序观察线程sleep创建线程继承Thread类,重写run方法实现Runnable, 重写run继承Thread,重写run实现Runnable,重写run基于lambda表达式 T…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
