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

K倍区间 C++

1230. K倍区间 - AcWing题库

一开始想到的用前缀和来做,时间复杂度为O(n^2),Time Limit Exceeded

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 100010;int n,k;
int s[N],a[N];int main() {cin >> n >> k;for (int i = 1;i <= n;i++) {scanf("%d",&a[i]);s[i] = s[i-1] + a[i];}int res = 0;for (int r = 1;r <= n;r++) {for (int l = 1;l <= r;l++) {int sum = s[r] - s[l-1];if (sum % k == 0) res++;}}cout << res << endl;
}

for (int l = 1;l <= r;l++) {
            int sum = s[r] - s[l-1];
            if (sum % k == 0) res++;
        }

这段代码中(s[r] - s[l-1])% k == 0    ==>  s[r] %k == s[l-1]%k

当r固定时,我们只需要在1-r中找到有多少个是s[l-1]%k 的值和s[r] %k相等即可

将l-r =>0-(r-1),那么只需要在0-r中找到有多少个是s[l]%k 的值和s[r] %k相等即可

定义一个数组cnt用来存储对应s[l]%k余数的个数

即cnt[s[l]%k]的值为余数为s[l]%k的l个数(l为左端点)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;typedef long long LL;const int N = 100010;int n,k;
LL s[N],cnt[N];int main() {cin >> n >> k;for (int i = 1;i <= n;i++) {scanf("%lld",&s[i]);s[i] += s[i-1];}LL res = 0;cnt[0] = 1;for (int r = 1;r <= n;r++) {res += cnt[s[r]%k];cnt[s[r]%k]++;}cout << res << endl;
}

为什么cnt[0]要设为1

因为如果不需要左端点,该区间即可符合条件,那么res应该+1

相关文章:

K倍区间 C++

1230. K倍区间 - AcWing题库 一开始想到的用前缀和来做&#xff0c;时间复杂度为O(n^2),Time Limit Exceeded #include <iostream> #include <cstring> #include <algorithm> #include <cstdio>using namespace std;const int N 100010;int n,k; in…...

Linux - 弯路系列3:安装和编译libvirt-4.5.0

系统&#xff1a;Anolis8&#xff08;离线&#xff09; 目录 1、步骤2、make过程中的错误错误1&#xff1a;error: xdr_u_int64_t undeclared (first use in this function) 3、make install的错误错误1&#xff1a;/usr/bin/mkdir -p ""/usr/local/etc/libvirt/nwf…...

Jenkins插件使用问题总结

Git Push插件 插件介绍 主要是用于git推送代码到远程仓库中使用&#xff0c;插件地址 pipeline中使用 官方说明中只有一句代码gitPush(gitScm: scm, targetBranch: env.BRANCH_NAME, targetRepo: origin) 流水线语法中也做的不齐全所以一开始我老是设置错&#xff0c;导致代…...

u盘怎么重装电脑系统_u盘重装电脑系统步骤和详细教程【新手宝典】

u盘怎么重装电脑系统&#xff1f;一个u盘怎么重装电脑系统呢&#xff0c;需要将u盘制作成u盘启动盘pe&#xff0c;然后通过U盘启动盘进入pe进行安装系统&#xff0c;下面小编就教大家u盘重装电脑系统步骤和详细教程。 u盘启动是什么意思&#xff1f; U盘启动盘是一种具有特殊功…...

Sql server查询数据库表的数量

SELECT count(*) FROM sys.objects WHERE typeU --统计表数量 SELECT NAME FROM sys.objects WHERE typeU --列出表名称 或者 SELECT COUNT(*) FROM SysObjects Where XTypeU --统计表数量 SELECT Name FROM SysObjects Where XTypeU --列出表名称 --判断字…...

Linux学习笔记之软件包管理RPM与YUM

RPM包的管理 介绍 RPM&#xff08;RedHat Package Manager&#xff09;用于互联网下载包的打包及安装工具&#xff0c;它包含在某些Linux分发版中。他生成具有.RPM扩展名的文件。RPM类似Windows的setup.exe&#xff0c;这一文件格式虽然打上了RedHat的标志&#xff0c;但理念…...

15分钟学 Go 第 41 天:中间件的使用

第41天&#xff1a;中间件的使用 目标&#xff1a;学习如何在Go语言的Web服务中使用中间件 中间件&#xff08;Middleware&#xff09;是Web开发中的一种常见设计模式&#xff0c;通常用于处理请求和响应过程中的一些共通功能。比如&#xff1a;日志记录、认证授权、请求处理…...

《Python 与 SQLite:强大的数据库组合》

《Python 与 SQLite&#xff1a;强大的数据库组合》 一、Python 与 SQLite 的结合二、安装与连接&#xff08;一&#xff09;安装 SQLite 模块&#xff08;二&#xff09;连接到数据库 三、数据库操作&#xff08;一&#xff09;创建表格&#xff08;二&#xff09;插入数据&am…...

Golang | Leetcode Golang题解之第552题学生出勤记录II

题目&#xff1a; 题解&#xff1a; const mod int 1e9 7type matrix [6][6]intfunc (a matrix) mul(b matrix) matrix {c : matrix{}for i, row : range a {for j : range b[0] {for k, v : range row {c[i][j] (c[i][j] v*b[k][j]) % mod}}}return c }func (a matrix) p…...

Vue3 常用代码指南手抄,超详细 cheatsheet

一、Vue3 基础 1.1 创建 Vue3 项目 使用 Vite 创建 npm create vitelatest my-vue-app -- --template vue cd my-vue-app npm install npm run dev使用 Vue CLI 创建 npm install -g vue/cli vue create my-vue-app1.2 项目结构 my-vue-app ├── node_modules ├── pu…...

结构体是否包含特定类型的成员变量

结构体是否包含特定类型的成员变量 在C中&#xff0c;可以使用模板元编程和类型特性&#xff08;type traits&#xff09;来判断一个结构体是否包含特定类型的成员变量。这通常通过std::is_member_object_pointer类型特性来实现&#xff0c;它可以用来检查给定的成员指针是否指…...

堆排序与链式二叉树:数据结构与排序算法的双重探索

大家好&#xff0c;我是小卡皮巴拉 文章目录 目录 引言 一.堆排序 1.1 版本一 核心概念 堆排序过程 1.2 版本二 堆排序函数 HeapSort 向下调整算法 AdjustDown 向上调整算法 AdjustUp 二.链式二叉树 2.1 前中后序遍历 链式二叉树的结构 创建链式二叉树 前序遍历…...

用 Python 从零开始创建神经网络(四):激活函数(Activation Functions)

激活函数&#xff08;Activation Functions&#xff09; 引言1. 激活函数的种类a. 阶跃激活功能b. 线性激活函数c. Sigmoid激活函数d. ReLU 激活函数e. more 2. 为什么使用激活函数3. 隐藏层的线性激活4. 一对神经元的 ReLU 激活5. 在隐蔽层中激活 ReLU6. ReLU 激活函数代码7. …...

使用 Flask 和 ONLYOFFICE 实现文档在线编辑功能

提示&#xff1a;CSDN 博主测评ONLYOFFICE 文章目录 引言技术栈环境准备安装 ONLYOFFICE 文档服务器获取 API 密钥安装 Flask 和 Requests 创建 Flask 应用项目结构编写 app.py创建模板 templates/index.html 运行应用功能详解文档上传生成编辑器 URL显示编辑器回调处理 安全性…...

【C++】【算法基础】序列编辑距离

编辑距离 题目 给定 n n n个长度不超过 10 10 10 的字符串以及 m m m 次询问&#xff0c;每次询问给出一个字符串和一个操作次数上限。 对于每次询问&#xff0c;请你求出给定的 n n n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。 每个…...

【Android】轮播图——Banner

引言 Banner轮播图是一种在网页和移动应用界面设计中常见的元素&#xff0c;主要用于在一个固定的区域内自动或手动切换一系列图片&#xff0c;以展示不同的内容或信息。这个控件在软件当中经常看到&#xff0c;商品促销、热门歌单、头像新闻等等。它不同于ViewPgaer在于无需手…...

学SQL,要安装什么软件?

先上结论&#xff0c;推荐MySQLDbeaver的组合。 学SQL需要安装软件吗&#xff1f; 记得几年前我学习SQL的时候&#xff0c;以为像Java、Python一样需要安装SQL软件包&#xff0c;后来知道并没有所谓SQL软件&#xff0c;因为SQL是一种查询语言&#xff0c;它用来对数据库进行操…...

webstorm 设置总结

编辑器-》文件类型-》忽略的文件和文件夹-》加上node_modules 修改WebStorm 内存有两种方式。 1. 点击菜单中的Help -> change memory settings 弹出设置内存窗口&#xff0c;修改最大内存大小。然后点击Save and Restart 即可。 2. 点击菜单中的Help -> Edit Custom V…...

基于Spring Boot的养老保险管理系统的设计与实现,LW+源码+讲解

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统养老保险管理系统信息管理难度大&#xff0c;容错率低&a…...

Java | Leetcode Java题解之第541题反转字符串II

题目&#xff1a; 题解&#xff1a; class Solution {public String reverseStr(String s, int k) {int n s.length();char[] arr s.toCharArray();for (int i 0; i < n; i 2 * k) {reverse(arr, i, Math.min(i k, n) - 1);}return new String(arr);}public void reve…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

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 提…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

JS红宝书笔记 - 3.3 变量

要定义变量&#xff0c;可以使用var操作符&#xff0c;后跟变量名 ES实现变量初始化&#xff0c;因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符&#xff0c;可以创建一个全局变量 如果需要定义…...

python读取SQLite表个并生成pdf文件

代码用于创建含50列的SQLite数据库并插入500行随机浮点数据&#xff0c;随后读取数据&#xff0c;通过ReportLab生成横向PDF表格&#xff0c;包含格式化&#xff08;两位小数&#xff09;及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...

java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟

众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了&#xff0c;延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp &#xff0c;边缘服务器拉流推送到云服务器 …...