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

蓝桥杯复习之前缀和

题目链接:https://www.luogu.com.cn/problem/P8649

思路:
    看到区间和,第一反应肯定是前缀和,我们求出前缀和后对前缀和数组每一个值模k,然后对一个数组的值查看前面有几个相同的,举个例子:

    样例中前缀和数组a取模后为:1    1    0    0    1

    下标依次为1 2 3 4 5

    当题目所求子序列以a5结尾时,已知a5=1且a5前面与a5相同的值有2个,则以a5结尾可以获得2个满足题目要求的区间
    
    如果以a3结尾则是一个,因为实际上有一个a0=0。
 

#include<bits/stdc++.h>using namespace std;using ll = long long;
const ll N = 3e5 + 5;
const ll mod = 1e9 + 7;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}void solve() {int n; cin >> n;ll k; cin >> k;vector<ll>a(n + 1);vector<ll>pre(n + 1);vector<ll>cnt(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];pre[i] = pre[i - 1] + a[i];}ll ans = 0;cnt[0] = 1;for (int i = 1; i <= n; i++) {ans += cnt[pre[i] % k];cnt[pre[i] % k]++;}cout << ans << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(0);std::cout.tie(0);int t1 = 1;//cin >> t1;while (t1--)solve();return 0;
}

相关文章:

蓝桥杯复习之前缀和

题目链接&#xff1a;https://www.luogu.com.cn/problem/P8649 思路&#xff1a; 看到区间和&#xff0c;第一反应肯定是前缀和&#xff0c;我们求出前缀和后对前缀和数组每一个值模k&#xff0c;然后对一个数组的值查看前面有几个相同的&#xff0c;举个例子&#xff1a;…...

动态规划(算法竞赛、蓝桥杯)--背包DP求具体方案

1、B站视频链接&#xff1a;E20 背包DP 求具体方案_哔哩哔哩_bilibili #include <bits/stdc.h> using namespace std; const int N1010; int v[N],w[N]; int f[N][N],p[N][N];int main(){int n,m;cin>>n>>m;for(int i1;i<n;i)cin>>v[i]>>w[i…...

go写mysql取得自增字段值

场景&#xff1a;有多张表&#xff0c;依据其中一张表的自增字段取得 id 值作为对象ID&#xff0c;然后使用这个Id插入到其他它表中。 如下一张 MySQL 的 innodb 表 X&#xff0c;用 go 编写程序&#xff0c;不指定 a 的值&#xff0c;指定 b 和 c 的值&#xff0c;往表 X 插入…...

Vue 3的Composition API和vue2的不同之处

Vue 3的Composition API是Vue.js框架的一个重要更新&#xff0c;它提供了一种新的组件逻辑组织和复用方式。在Vue 2中&#xff0c;我们通常使用Options API&#xff08;data、methods、computed等&#xff09;来组织组件的逻辑&#xff0c;但这种组织方式在处理复杂组件时可能会…...

go语言基础 -- 面向对象编程

go语言面向对象编程思想 面向对象编程离不开封装、继承、多态三个特性&#xff0c;go语言与其他c、java不太一样&#xff0c;没有类的概念&#xff0c;面向对象的实现也有些区别&#xff0c;下面分别描述。 go语言封装 结构体中字段如欲对外隐藏&#xff0c;首字母小写&…...

HarmonyOS—编译构建概述

编译构建是将应用/服务的源代码、资源、第三方库等&#xff0c;通过编译工具转换为可直接在硬件设备上运行的二进制机器码&#xff0c;然后再将二进制机器码封装为HAP/APP软件包&#xff0c;并为HAP/APP包进行签名的过程。其中&#xff0c;HAP是可以直接运行在模拟器或真机设备…...

下载element-ui 资源,图标 element-icons.woff,element-icons.ttf 无法解码文件字体

css下载地址&#xff1a;https://unpkg.com/element-ui2.15.14/lib/theme-chalk/index.css js下载地址&#xff1a;https://unpkg.com/element-ui2.15.14/lib/index.js 图标及文字文件下载地址&#xff1a; element-icons.woff:&#xff1a; ​ https://unpkg.com/element-…...

Flutter整体框架

Flutter整体框架由三部分组成&#xff1a;Framework、Engine和Embedder。 Framework Framework提供了一个用 Dart 语言编写的现代、反应式框架&#xff0c;由许多抽象的层级组成。它包括一套丰富的布局、动画、绘制、手势UI组件及配套代码&#xff0c;以及更基础的异步、文件、…...

JVM堆内存中新生代晋升到老年代的条件

1. 一般年龄判断 当对象在Eden区中经过第一次 Minor GC 后&#xff0c;如果仍然存活&#xff0c;则会被移动到 From Survivor 区&#xff0c;并且对象的年龄设为 1。每经过一次 Minor GC&#xff0c;存活下来的对象年龄加 1&#xff0c;若存活对象在 From Survivor 区的年龄达…...

前端监控为什么采用GIF图片做埋点?

一、什么是埋点监控 前端监控是开发人员用来跟踪和维护应用程序表现层的运行状况的过程和工具。它主要包括三种类型&#xff1a;数据监控、性能监控和异常监控。 1、数据监控 主要是为了收集跟用户相关的数据&#xff0c;例如用户设备类型、浏览器版本、页面浏览量&#xff08;…...

webstorm 创建运行纯Typescript项目

创建一个空项目&#xff0c;在项目根目录创建一个tsconfig.json文件自动配置&#xff1a; 打开终端输入tsc --init&#xff0c;即可自动生成tsconfig.json文件手动配置&#xff1a; 在项目根目录下新建一个tsconfig.json文件,并配置如下内容 具体配置可以直接使用下面的配置&am…...

GO-接口

1. 接口 在Go语言中接口&#xff08;interface&#xff09;是一种类型&#xff0c;一种抽象的类型。 interface是一组method的集合&#xff0c;接口做的事情就像是定义一个协议&#xff08;规则&#xff09;&#xff0c;只要一台机器有洗衣服和甩干的功能&#xff0c;我就称它…...

【C语言】动态内存管理常用函数

前言 我们在之前学习的数组开辟的空间是固定不变的&#xff0c;有时候我们需要的空间⼤⼩在程序运⾏的时候才能知道~ c语言中的动态内存开辟&#xff0c;让程序员⾃⼰可以根据实际需求申请和释放相应空间&#xff0c;这使得空间的开辟变得灵活了许多。 欢迎关注个人主页&#x…...

【OpenGL】(1) 专栏介绍:OpenGL 库 | 3D 计算机图形应用 | GPGPU 计算 | 3D 建模和 3D动画 | 渲染技术介绍

&#x1f517; 《C语言趣味教程》&#x1f448; 猛戳订阅&#xff01;&#xff01;&#xff01; &#x1f4ad; 写在前面&#xff1a;本专栏主要内容是关于 3D 计算机图形技术的学习&#xff0c;重点是学习与此技术相关的 3D 实时渲染 (3D real-time rendering) 技术。我们会以…...

SPI总线知识总结

1 SPI的时钟极性CPOL和时钟相位CPHA的设置 1.1 SPI数据传输位数 SPI传输数据过程中总是先发送或接收高字节数据&#xff0c;每个时钟周期接收器或发送器左移一位数据。对于小于16位的数据&#xff0c;在发送前必须左对齐&#xff0c;如果接收的数据小于16位&#xff0c;则采用软…...

【异常关闭clas*h,导致无法访问任何网页_解决办法】

各位经常使用Clash Scientific浏览的朋友们&#xff0c;我要建议大家不要在开启Clash代理的情况下直接关机或者重启电脑&#xff0c;这样的操作会导致网络配置出现严重问题&#xff0c;带来不必要的麻烦。 这是我亲身体验的一次痛苦教训。不管是我在关闭or开启Clas*h代理后&am…...

STL-map和set

目录 一、关联式容器 二、键值对 三、树形结构的关联式容器 3.1 set 3.1.1 set介绍 3.1.2 set的使用 1. set的模板参数列表 2. set的构造 3. set的迭代器(类型是双向迭代器) 4. set的容量 5.set修改操作 6、operator 7. set的使用举例 3.2 map 3.2.1map介绍 3.2.2map的…...

[蓝桥杯 2020 省 B1] 整除序列

[蓝桥杯 2020 省 B1] 整除序列 题目描述 有一个序列&#xff0c;序列的第一个数是 n n n&#xff0c;后面的每个数是前一个数整除 2 2 2&#xff0c;请输出这个序列中值为正数的项。 输入格式 输入一行包含一个整数 n n n。 输出格式 输出一行&#xff0c;包含多个整数…...

【Android】View 的滑动

View 的滑动是 Android 实现自定义控件的基础&#xff0c;同时在开发中我们也难免会遇到 View 的滑动处理。其实不管是哪种滑动方式&#xff0c;其基本思想都是类似的&#xff1a;当点击事件传到 View 时&#xff0c;系统记下触摸点的坐标&#xff0c;手指移动时系统记下移动后…...

基于ZYNQ的PCIE高速数据采集卡的设计(一)

作为信息处理的第一步&#xff0c;数据采集的作用越来越重要。目前&#xff0c;数据采集已经在航 空、民用、军事、医疗等领域得到广泛应用。随着相关技术的不断发展&#xff0c;信号频率越 来高&#xff0c;带宽越来越大&#xff0c;使得数据采集技术逐渐向高速大数据的方向…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

计算机系统结构复习-名词解释2

1.定向&#xff1a;在某条指令产生计算结果之前&#xff0c;其他指令并不真正立即需要该计算结果&#xff0c;如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方&#xff0c;那么就可以避免停顿。 2.多级存储层次&#xff1a;由若干个采用不同实现技术的存储…...