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

刷题记录:牛客NC17193简单瞎搞题

news 来源：原创 2024/5/3 17:24:30

传送门;牛客

题目描述:
一共有 n个数，第 i 个数是 xi
xi 可以取 $[l i, r i]$ 中任意的一个值。
设 $\sum{{x_i}^2}$
，求 S 种类数。
输入:
5
1 2
2 3
3 4
4 5
5 6
输出:
26

这道题目还是挺有意思的.首先我们看到这道题目想到的应该是区间dp的想法

想法一:

我们使用 $d p [i] [j]$ 来记录枚举完前 $i$ 个数字能否组成 $j$ 的值.我们使用bool来存储
这样的话我们就有一种比较简单的转移方案,我们可以判断前面的已经可以组成的数字来加上我们此时的可以加上的 $x i$ 的值来进行转移.具体代码如下

for(int i=1;i<=n;i++){scanf("%d%d",&l,&r);for(int j=r;j>=l;j--){for(int k=sum;k>=0;k--){f[i][k+j*j]=f[i-1][k];   }    }sum+=r*r;
}

但是我们发现如果这样进行转移的话需要的复杂度将是 $N^4$ ,这样子的话肯定是会超时的,所以我们需要将此代码进行一个优化.我们发现我们主要的判断是否能组成一个数字时是可以使用二进制来进行优化的.也就是当我们的当前的数字进行加法时,就将我们记录状态的01串进行左移.这样的话我们就将原本的每一个可行的数字进行一个简单的记录了.然后我们再将移动后的01串和我们原来的01串进行异或操作来合并即可(异或可以解决重复的问题),但是我们发现这样的话我们又需要 $100 * 100 * 100 * 100$ 的长度的01串,那么我们就不能使用bool类型的数组来记录状态了,因为此时肯定会爆内存.
但是c++中的 $s tl$ 为我们提供了 $bi t se t$ 这样的巧妙的类型.这个类的作用就是给你一个长度更长的01串,并且这个类型存储的内存只占 $b oo l$ 类型的 $1/8$ ,这样的话我们就可以通过这道题了
对于bitset,我们此题涉及以下函数

$b t i se t < l e n g t h > d p [100]$
$d p [0] . se t (0) : 代表将我们的第一个 01 串的第 0 个位置置为 1$
(注意我们的bitset是从右往左进行移动的)
$d p [n] . co u n t (), 用来输出我们的 01 串中的 1 的个数$ 在本题中就是不同数字的是否可行性

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
#include <bitset>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000010
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;
bitset<maxn>dp[110];
int main() {n=read();int l,r;dp[0].set(0);for(int i=1;i<=n;i++) {l=read();r=read();for(int j=l;j<=r;j++) {dp[i]|=(dp[i-1]<<(j*j));}}cout<<dp[n].count()<<endl;return 0;
}

01_导论

第1章导论什么是计量经济学计量经济学定义运用概率统计方法对经济变量之间的（因果）关系进行定量分析的科学。经济问题没法实验，计量经济学不足以确定变量间的因果；但实证的目的恰恰就是要去确定变量间的因果。因果关系如果只是对数据进行预测，那相关关系就足够了。但…...

编程日记 2024/5/3 21:50:51

Akamai 分布式“云+边缘”，打造下一代数字化基座

当下，数字化基础设施正逐步向分布式部署演化，云计算与边缘计算正在成为两大技术支柱。Gartner 数据显示，云服务占 IT 整体支出比例连年上涨，在过去一年已增长至12.1%；IDC 报告显示，截至2021年已有超过500亿…...

编程日记 2024/5/3 19:49:21

DataFrame删除复合索引

index2 和 reasons_id 数据显示重复，可以删除列reasons_id，如果强迫症必须删除索引，可以用下面的方法 # reasons_id total_price ... total_price_统计 people_num_统计 # index1 index2 ... …...

编程日记 2024/5/3 18:59:57

数据集市与数据仓库

一、概念数据仓库（Data Warehouse）和数据集市（Data Mart）是企业中用于存储和管理数据的两种常见架构。它们在设计和应用上有一些区别，下面我简要介绍一下： 数据仓库（Data Warehouse&#xff0…...

编程日记 2024/5/3 16:51:46

【算法基础实验】图论-深度优先搜索和深度优先路径

深度优先(DFS) 理论基础深度优先搜索（DFS, Depth-First Search）是图和树的遍历算法中的一种，它从一个节点开始，沿着树的边走到尽可能深的分支，直到节点没有子节点为止，然后回溯继续搜索下一个分支。DFS …...

编程日记 2024/5/3 13:09:35

整合文本和知识图谱嵌入提升RAG的性能

我们以前的文章中介绍过将知识图谱与RAG结合的示例，在本篇文章中我们将文本和知识图谱结合，来提升我们RAG的性能https://avoid.overfit.cn/post/5782ca7c4695427b8c0299ad0887c564...

编程日记 2024/5/3 11:21:26

刷题记录:牛客NC17193简单瞎搞题

传送门;牛客题目描述: 一共有 n个数，第 i 个数是 xi xi 可以取[li,ri][li , ri][li,ri] 中任意的一个值。设 S∑xi2S \sum{{x_i}^2}S∑xi2 ，求 S 种类数。输入: 5 1 2 2 3 3 4 4 5 5 6 输出: 26 这道题目还是挺有意思的.首先我们看到这道题目想到…...

编程日记 2024/5/3 17:24:30

C++笔记 16 （STL常用容器 - deque）

三. STL常用容器 3.deque容器 3.1 deque容器基本概念双端数组，可以对头端进行插入删除操作。 deque和vector区别： 1）vector对于头部的插入删除效率低，数据量越大，效率越低； 2）deque相对而言…...

编程日记 2024/5/1 23:59:23

python:基础知识

环境： window11python 3.10.6vscodejavascript、c/c/java/c#基础（与这些语言对比） 注释一、数据类型基础六大数据类型，可以使用 type()查看，如下图： 1.1 数字（Number） 支持整…...

编程日记 2024/5/1 11:46:46

智工教育：每年必考！教师编制这些考点必背！

夸美纽斯的教育思想 （1）著作：《大教学论》，是近代最早的一部教育学著作，是近代独立形态教育学的开端，标志着教育学开始成为一门独立学科。 （2）观点： 对学年制、班级授…...

编程日记 2024/4/30 4:28:49

C++基础——输入输出和缺省参数讲解

上篇文章中，我们学习了C的域名空间，这次继续来学习C的基础知识。目录一.C的输入输出总结： 二.缺省参数全缺省案例： 部分缺省案例： 一.C的输入输出例： #include<iostream> using std::co…...

编程日记 2024/5/3 7:21:01

Git使用详细教程

1. cmd面板的常用命令 clear：清屏cd 文件夹名称----进入文件夹cd … 进入上一级目录(两个点)dir 查看当前目录下的文件和文件夹(全拼:directory)Is 查看当前目录下的文件和文件夹touch 文件名----创建文件echo 内容 > 创建文件名----创建文件并写入内容rm 文件名…...

编程日记 2024/5/4 5:56:26

11月新书预告——GNN、深度学习和元宇宙

11月的新书聚焦AI的前沿主题——GNN，另外，还有两本重磅的深度学习好书，也不乏元宇宙、智能驾驶和硬件产品经理等全新技术主题的好书。 1. 图神经网络：基础、前沿与应用吴凌飞崔鹏裴健赵亮编著张钹、韩家炜、…...

编程日记 2024/4/29 22:39:30

YOLOv5 PyQt5 | PyQt5快速入门 | 2/3

YOLOv5 PyQt5 快速入门 2/3 文章目录 YOLOv5 PyQt5 快速入门 2/31. 设计页面2. PyQt5 打开图片3. PyQt5 打开视频4. PyQt5 打开摄像头源码1. 设计页面首先我们利用QtDesigner来设计一个页面。这个页面比较简单，包含三个PushButton、两个GroupBox、两个Textlabel。设计好后我…...

编程日记 2024/5/1 10:31:34

Java为什么吧String设计为不可变类？

文章目录那么为什么要这么设计呢？防止被篡改，保证信息数据的安全性不变的对象和值是线程安全的哈希值的唯一性来挺好性能提高常量池的可用性在Java中String类由final修饰，所以不能被继承。被final修饰主要是为了让String成为一个不可变类因为…...

编程日记 2024/4/27 1:46:42

【javaEE】多线程进阶（Part1 锁策略、CAS、synchronized ）

目录前言/补充4. 描述一下线程池的执行流程和拒绝策略有哪些？【面试题！】一、常见锁策略一）乐观锁VS悲观锁二）读写锁VS普通互斥锁三）重量级锁VS轻量级锁四）自旋锁VS挂起等待锁五）公平锁VS非公平…...

编程日记 2024/5/1 7:45:26

deepin（深度）系统下qt5.12.0的程序打包发布到linux云服务器上

做项目时要求，要求做一个用于QT客户端更新提供更新的服务器，服务器弄好啦，要测试一下，在发布时，发现了一些问题，在此记录一下。这个打包和我的前一篇博客步骤一样，打包可参考https://blog.csd…...

编程日记 2024/5/2 19:49:42

精读大型网站架构：前端架构模块化的方法及困境，自研框架Trick

模块化的方法网页和网页之间有很多相似或者相同的模块，模块化就是把这些模块抽离并独立管理。而模块化的方法，就是把模块的HTML、CSS和JavaScript文件独立出来，然后通过某种方法关联到使用这些模块的网页上。在介绍模块化的具体方法之前&…...

编程日记 2024/4/30 14:09:22

用Python实现的这五个小游戏，你真的学会了嘛？

游戏名称1、五子棋 2、雷霆战机 3、贪吃蛇 4、坦克大战 5、俄罗斯方块开发环境 Python版本：3.6.4 相关模块： pygame模块； 以及一些Python自带的模块。环境搭建安装Python并添加到环境变量，pip安装需要的相关模块即可。一&am…...

编程日记 2024/4/30 1:56:16

linux环境下查询主板、CPU、内存等硬件信息

文章目录前言dmidecode常用参数-t参数测试-q参数测试-s参数测试总结前言如果是在windows系统下，查询电脑硬件会容易的多，可以通过电脑属性、计算机管理等多种图形化界面中查到，如果安装了各种电脑管家，那查询这类信息就更方便了…...

编程日记 2024/4/30 2:05:51

查看日志.

如果查看比较小的日志文件：cat xxx.log 一般常用：view xxx.log/vi xxx.log查找关键字，如“木叶”：编辑，/木叶，确定，然后按“n”键就能往下找。如果想往上找，输入:$到最后一行&#…...

编程日记 2024/5/4 0:49:31

vue3 生命周期函数，都改了啥？

vue2到3常用生命周期钩子函数的变化 Ⅰ. 实例化和数据初始化 （beforeCreate，created > setup） 1. new Vue 从开始 > 结束 [vue2和3 、两版本区别处] vue2的写法> export default {beforeCreate(){console.log(vue的实例还没ne…...

编程日记 2024/5/4 5:39:02

基于springboot的医院管理系统

项目描述临近学期结束，还是毕业设计，你还在做java程序网络编程，期末作业，老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里，你想解决的问题&#xff0…...

编程日记 2024/5/4 1:06:59

Django + Nginx https部署实战（第一辑）

WebServer和WebAPP 之前对于nginx的了解都只是听说，根本就不知道nginx对于整个网站的作用。经历了数个项目之后，我本人逐渐对nginx有了更深入的了解，也希望把这段经历拿出来分享给大家！ 由于我本人之前接触的都是Python的Django…...

编程日记 2024/4/28 9:33:06

Pycharm+服务器运行代码

Pycharm服务器运行代码服务器的连接与Anaconda环境配置ssh连接安装Anaconda创建虚拟环境安装代码所需的库Pycharm上传代码到服务器服务器的连接与Anaconda环境配置 ssh连接我使用的是MobaXterm，新建一个会话，选择SSH，输入主机IP地址自己的…...

编程日记 2024/5/3 10:11:08

【Spring】IDEAspring-mybatis的整合----关于配置文件的整合

文章目录spring-mybatis的整合过程步骤1.导包，spring的jar包，mybatis的jar包2.mybatis.xml配置3.spring-mybatis.xml配置4.dao、service层、代码测试spring-mybatis的整合过程步骤 1.导包，spring的jar包，mybatis的jar包 <!--统…...

编程日记 2024/4/30 4:07:05

ssm技术

ssm ssm框架配置 maven项目–》webquickstart pom文件 <?xml version"1.0" encoding"UTF-8"?><project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLo…...

编程日记 2024/5/4 6:09:20

MQ消息队列

MQ消息队列消息队列（Message Queue，简称MQ），指保存消息的一个容器，本质是个队列消息队列是大型分布式系统不可缺少的中间件，也是高并发系统的基石中间件使用消息队列还可以实现异步处理下图便是消息…...

编程日记 2024/4/29 10:53:56

【JVM技术专题】精心准备了一套JVM分析工具的锦囊「JConsole补充篇」

前提概要本篇文章主要针对于之前本系列文章的补充版，之前落下了Jconsole分析工具，所以为了了却这个遗憾，所以小编又开了这篇文章，主要针对于Jconsole工具进行相关的应用性能分析。初识JConsole 【Jconsole（Java Moni…...

编程日记 2024/5/3 13:31:13

基于PHP的高效协同办公管理系统

有需要请私信或看评论链接哦可远程调试基于PHP高效协同办公管理系统一介绍高效协同办公管理系统基于Yii框架开发，数据库mysql，可以稳定用于商业以及门户级的开发和使用。二系统功能用户 1 办公门户(邮件/日志/汇报/日程/信息中心/通知公告/微博…...

编程日记 2024/5/1 23:24:53

第十四届蓝桥杯（Web应用开发）模拟赛1期-大学组

数据类型检测请看这篇数据类型检测渐变色背景生成器 html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><meta name&…...

编程日记 2024/4/26 13:05:17

【遥感科学】遥感科学绪论

第一章绪论本系列适用于梅安新老师的遥感导论复习，也可以作为遥感领域的快速入门文章一、遥感的基本概念啥子是遥感？借用童庆禧院士的理解，那就是欲穷千里目，更上一层楼，遥感可以看做人的眼睛或者感知的延伸&…...

编程日记 2024/5/4 1:18:19

Tensorflow图像识别 Tensorflow手写体识别（二）

资源介绍我们从 MNIST handwritten digit database, Yann LeCun, Corinna Cortes and Chris Burges 这条链接（MNIST官网）中下载好数据集，如下： 下载下来以后整理成包含四个压缩包的文件MNIST_data（不要解压&#x…...

编程日记 2024/5/2 16:20:41

盘点上海IB国际学校，你会选哪一所呢？

之前，小编给大家盘点了上海热门的AP学校和Alevel学校，同时也介绍了国际课程的具体情况；今天就和大家聊聊上海的IB国际学校。IB即是国际文凭组织IBO(International Baccalaureate Organisation)为全球学生开设从幼儿园到大学预科的课程&#x…...

编程日记 2024/4/29 18:12:39

windows远程访问树莓派ubuntu22.04 桌面 - NoMachine

通过nomachine 实现 windows 安装 nomachine 下载：链接：https://pan.baidu.com/s/10rGBREs-AnwRz7D7QbLQ1A?pwd8651 提取码：8651 安装：下一步下一步使用： 下一步下一步 ubuntu 安装 nomachine服务下载&#…...

编程日记 2024/5/2 14:25:39

聚醚醚酮（Polyether Ether Ketone）PEEK在粘接使用时可以使用UV胶水吗？要注意哪些事项？

一般情况下，聚醚醚酮（Polyether Ether Ketone，PEEK）是一种难以黏附的高性能工程塑料，而UV胶水通常不是与PEEK进行粘接的首选方法。PEEK表面的化学性质和高温性能使得它对常规胶水的附着性较低。然而，有一些…...

编程日记 2024/5/2 14:07:34

mysql基础知识汇总

本文自行整理，只做学习记忆之用，若有不当之处请指出一、数据库三层结构 （1）所谓安装Mysql数据库，就是在主机安装一个数据库管理系统(DBMS),这个管理程序可以管理多个数据库。DBMS(database manage system) &#xf…...

编程日记 2024/5/4 3:12:14

1、下载安装 pip install paddlehub -i https://pypi.tuna.tsinghua.edu.cn/simple 报错： Collecting onnx<1.9.0 (from paddle2onnx>0.5.1->paddlehub)Using cached https://pypi.tuna.tsinghua.edu.cn/packages/73/e9/5b953497c0e36df589fc60cc6c6b35…...

编程日记 2024/5/2 13:10:10

分布式与一致性协议之Raft算法(一)

Raft算法概述 Raft算法属于Multi-Paxos算法，它在兰伯特Multi-Paxos思想的基础上做了一些简化和限制，比如日志必须是连续的，只支持领导者(Leader)、跟随者(Follwer)和候选人(Candidate)3种状态。在理解和算法实现上，Raft算法相对…...

编程日记 2024/5/4 4:56:04

Linux专栏04：Linux基本指令之用户管理指令

博客主页：Duck Bro 博客主页系列专栏：Linux专栏关注博主，后期持续更新系列文章如果有错误感谢请大家批评指出，及时修改感谢大家点赞👍收藏⭐评论✍ Linux基本指令之用户管理指令编号：04 文章目录 Linux基…...

编程日记 2024/5/2 5:40:34

想法一:

相关文章：