当前位置: 首页 > 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…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

三维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;确保相对路径.…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

电脑桌面太单调,用Python写一个桌面小宠物应用。

下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡&#xff0c;可以响应鼠标点击&#xff0c;并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...

python打卡day49@浙大疏锦行

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...