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题库 一开始想到的用前缀和来做,时间复杂度为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
系统:Anolis8(离线) 目录 1、步骤2、make过程中的错误错误1:error: xdr_u_int64_t undeclared (first use in this function) 3、make install的错误错误1:/usr/bin/mkdir -p ""/usr/local/etc/libvirt/nwf…...
Jenkins插件使用问题总结
Git Push插件 插件介绍 主要是用于git推送代码到远程仓库中使用,插件地址 pipeline中使用 官方说明中只有一句代码gitPush(gitScm: scm, targetBranch: env.BRANCH_NAME, targetRepo: origin) 流水线语法中也做的不齐全所以一开始我老是设置错,导致代…...
u盘怎么重装电脑系统_u盘重装电脑系统步骤和详细教程【新手宝典】
u盘怎么重装电脑系统?一个u盘怎么重装电脑系统呢,需要将u盘制作成u盘启动盘pe,然后通过U盘启动盘进入pe进行安装系统,下面小编就教大家u盘重装电脑系统步骤和详细教程。 u盘启动是什么意思? 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(RedHat Package Manager)用于互联网下载包的打包及安装工具,它包含在某些Linux分发版中。他生成具有.RPM扩展名的文件。RPM类似Windows的setup.exe,这一文件格式虽然打上了RedHat的标志,但理念…...
15分钟学 Go 第 41 天:中间件的使用
第41天:中间件的使用 目标:学习如何在Go语言的Web服务中使用中间件 中间件(Middleware)是Web开发中的一种常见设计模式,通常用于处理请求和响应过程中的一些共通功能。比如:日志记录、认证授权、请求处理…...
《Python 与 SQLite:强大的数据库组合》
《Python 与 SQLite:强大的数据库组合》 一、Python 与 SQLite 的结合二、安装与连接(一)安装 SQLite 模块(二)连接到数据库 三、数据库操作(一)创建表格(二)插入数据&am…...
Golang | Leetcode Golang题解之第552题学生出勤记录II
题目: 题解: 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中,可以使用模板元编程和类型特性(type traits)来判断一个结构体是否包含特定类型的成员变量。这通常通过std::is_member_object_pointer类型特性来实现,它可以用来检查给定的成员指针是否指…...
堆排序与链式二叉树:数据结构与排序算法的双重探索
大家好,我是小卡皮巴拉 文章目录 目录 引言 一.堆排序 1.1 版本一 核心概念 堆排序过程 1.2 版本二 堆排序函数 HeapSort 向下调整算法 AdjustDown 向上调整算法 AdjustUp 二.链式二叉树 2.1 前中后序遍历 链式二叉树的结构 创建链式二叉树 前序遍历…...
用 Python 从零开始创建神经网络(四):激活函数(Activation Functions)
激活函数(Activation Functions) 引言1. 激活函数的种类a. 阶跃激活功能b. 线性激活函数c. Sigmoid激活函数d. ReLU 激活函数e. more 2. 为什么使用激活函数3. 隐藏层的线性激活4. 一对神经元的 ReLU 激活5. 在隐蔽层中激活 ReLU6. ReLU 激活函数代码7. …...
使用 Flask 和 ONLYOFFICE 实现文档在线编辑功能
提示:CSDN 博主测评ONLYOFFICE 文章目录 引言技术栈环境准备安装 ONLYOFFICE 文档服务器获取 API 密钥安装 Flask 和 Requests 创建 Flask 应用项目结构编写 app.py创建模板 templates/index.html 运行应用功能详解文档上传生成编辑器 URL显示编辑器回调处理 安全性…...
【C++】【算法基础】序列编辑距离
编辑距离 题目 给定 n n n个长度不超过 10 10 10 的字符串以及 m m m 次询问,每次询问给出一个字符串和一个操作次数上限。 对于每次询问,请你求出给定的 n n n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。 每个…...
【Android】轮播图——Banner
引言 Banner轮播图是一种在网页和移动应用界面设计中常见的元素,主要用于在一个固定的区域内自动或手动切换一系列图片,以展示不同的内容或信息。这个控件在软件当中经常看到,商品促销、热门歌单、头像新闻等等。它不同于ViewPgaer在于无需手…...
学SQL,要安装什么软件?
先上结论,推荐MySQLDbeaver的组合。 学SQL需要安装软件吗? 记得几年前我学习SQL的时候,以为像Java、Python一样需要安装SQL软件包,后来知道并没有所谓SQL软件,因为SQL是一种查询语言,它用来对数据库进行操…...
webstorm 设置总结
编辑器-》文件类型-》忽略的文件和文件夹-》加上node_modules 修改WebStorm 内存有两种方式。 1. 点击菜单中的Help -> change memory settings 弹出设置内存窗口,修改最大内存大小。然后点击Save and Restart 即可。 2. 点击菜单中的Help -> Edit Custom V…...
基于Spring Boot的养老保险管理系统的设计与实现,LW+源码+讲解
摘 要 如今社会上各行各业,都喜欢用自己行业的专属软件工作,互联网发展到这个时候,人们已经发现离不开了互联网。新技术的产生,往往能解决一些老技术的弊端问题。因为传统养老保险管理系统信息管理难度大,容错率低&a…...
Java | Leetcode Java题解之第541题反转字符串II
题目: 题解: 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…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
