当前位置: 首页 > news >正文

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; //枚举数位&#xff0c;枚举这一位余数是几 //每一位的限制&#xff0c; int d…...

透视俄乌网络战之二:Conti勒索软件集团(下)

透视俄乌网络战之一&#xff1a;数据擦除软件 透视俄乌网络战之二&#xff1a;Conti勒索软件集团&#xff08;上&#xff09; Conti勒索软件集团&#xff08;下&#xff09; 1. 管理面板源代码2. Pony凭证窃取恶意软件3. TTPs4. Conti Locker v2源代码5. Conti团伙培训材料6. T…...

网络安全深入学习第一课——热门框架漏洞(RCE-命令执行)

文章目录 一、RCE二、命令执行/注入-概述三、命令执行-常见函数四、PHP命令执行-常见函数1、exec&#xff1a;2、system3、passthru4、shell_exec5、反引号 backquote 五、PHP命令执行-常见函数总结六、命令执行漏洞成因七、命令执行漏洞利用条件八、命令执行漏洞分类1、代码层…...

应用在电子体温计中的国产温度传感芯片

电子体温计由温度传感芯片&#xff0c;液晶显示器&#xff0c;纽扣电池&#xff0c;专用集成电路及其他电子元器件组成。能快速准确地测量人体体温&#xff0c;与传统的水银玻璃体温计相比&#xff0c;具有读数方便&#xff0c;测量时间短&#xff0c;测量精度高&#xff0c;能…...

JVM 虚拟机 ----> Java 内存模型(JMM)

文章目录 Java 内存模型&#xff08;JMM&#xff09;一、运行时数据区域划分二、程序计数器&#xff08;Program Counter Register&#xff09;计数器的作用 三、Java 虚拟机栈&#xff08;VM Stack&#xff09;四、本地方法栈&#xff08;Native Method Stack&#xff09;五、…...

指针-字符串替换

任务描述 从标准输入读入数据&#xff0c;每行中最多包含一个字符串 “_xy_”&#xff0c;且除了字符串“_xy_”外&#xff0c;输入数据中不包括下划线字符&#xff0c;请将输入行中的 “_xy_” 替换为 “_ab_”, 在标准输出上输出替换后的结果&#xff1b;若没有进行过满足条…...

docker 网络(单机环境)

文章目录 深入理解 Namespace什么是NamespaceNamespace当中的 Network Namespace Libcontainerdocker 网络基础创建两个命名空间创建网络接口 veth pair命名空间添加 veth 接口为 veth 接口分配 IP启动 veth 接口相互 ping bridge 网络搭建网络环境查看docker0 网桥创建网桥 br…...

14、二叉树的morris遍历等

统计热词 有一个包含100亿个URL的大文件&#xff0c;假设每个URL占用64B&#xff0c;请找出其中所有重复的URL 【补充】 某搜索公司一天的用户搜索词汇是海量的(百亿数据量)&#xff0c;请设计一种求出每天热门Top100 词汇的可行办法 多个小文件的大根堆&#xff0c;然后把每…...

BeanFactory与ApplicationContext

BeanFactory与ApplicationContext的区别 使用Alt Ctrl U查看java类图 什么是BeanFactory接口 他是ApplicationContext的父接口他才是Spring 的核心容器&#xff0c;主要的ApplicationContext功能的实现都间接通过BeanFactory接口来实现 在ApplicationContext类中方法的实现是…...

【计算机网络】 粘包问题

文章目录 为什么会产生粘包问题&#xff1f;解决办法先发包大小再发包内容代码示例 为什么会产生粘包问题&#xff1f; tcp是数据流传输&#xff0c;是一种没有边界的&#xff0c;可以合并的传输数据方式。合并就要能拆开&#xff0c;拆不开就是粘包。 解决办法 设置标志位&a…...

valgrind massif 详解(内存分配释放分析)

参考 https://valgrind.org/docs/manual/ms-manual.html 使用格式 valgrind --toolmassif [--massif-opts] prog [prog-args]目的 记录每一次的malloc, free; 概念: malloc申请内存, 实际分配内存(字节对齐, 分配器的记录头, 等等原因) 对内存进行分析, 优化, 以达到资源…...

使用命令行创建一个vue项目卡住不动如何解决

问题 在使用命令去创建一个vue项目&#xff0c; 出现下面卡住不动的一个状态。 解决方案一 首先先ctrlc停止进入创建好的项目文件手动输入npm install 、npm run dev如果npm run dev 的时候 出现 ‘vite’ 相关的错误查看node版本是否是最新的稳定版本node -v查看安装源是否…...

七天学会C语言-第一天(C语言基本语句)

一、固定格式 这个是C程序的基本框架&#xff0c;需要记住&#xff01;&#xff01;&#xff01; #include<stdio.h>int main(){return 0; }二、printf 语句 简单输出一句C程序&#xff1a; #include<stdio.h> int main(){printf("大家好&#xff0c;&quo…...

vue项目部署,出现两个ip的原因

我宁愿靠自己的力量打开我的前途,而不愿求有力者的垂青。——雨果 tags: 篇首语&#xff1a;本文由小常识网(cha138.com)小编为大家整理&#xff0c;主要介绍了vue项目部署&#xff0c;出现两个ip的原因相关的知识&#xff0c;希望对你有一定的参考价值。 参考技术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), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固&#xff0c;所以墙不会被摧毁.你只…...

第一章 计算机系统概述 八、虚拟机

目录 一、传统虚拟机的结构 二、两类虚拟机管理程序 &#xff08;1&#xff09;定义&#xff1a; &#xff08;2&#xff09;区别&#xff1a;&#xff08;考点&#xff09; 一、传统虚拟机的结构 二、两类虚拟机管理程序 &#xff08;1&#xff09;定义&#xff1a; &…...

桶装水送水多水站送水员公众号h5开发

桶装水送水多水站送水员公众号h5开发 界面简洁易懂用户容易接受。 独家一户一码全家都能订水。 多个水站运营可按距离选择绑定。 三种支付方式水票、微信、到付。 强大员工系统老板坐享其成。 自由跑跑模式可招兼职送水员接单。 一户一码、全家享用 一户一码&#xff0c;精准…...

【JavaEE】多线程(二)

多线程&#xff08;二&#xff09; 文章目录 多线程&#xff08;二&#xff09;第一个多线程程序观察线程sleep创建线程继承Thread类&#xff0c;重写run方法实现Runnable&#xff0c; 重写run继承Thread&#xff0c;重写run实现Runnable&#xff0c;重写run基于lambda表达式 T…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...