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

ABC 370 E - Avoid K Partition

原题链接:E - Avoid K Partition

题意:给长度为n的数组,将数组划分成任意份,但是每一份的总和都不能是k,问有多少种分割方法。

思路:dp,f[i],代表前i个元素满足题意的划分的总和,那么转移方程就是f(i)=\sum f[j]^{},j是从1到i-1,然后如果从j到i这一段的总和是k,那么就减去f[j],对于任意的f[i]来说,这样是不重不漏的,那么可以很容易写出一个n*2的算法,可以观察到,这个算法的瓶颈是在减去j到i总和是k的这一步上,从前缀和的角度考虑,对于每个从j到i总和为k来说,从1到j的总和都是一样的值,那么就可以用map来记录一下,从1到j总和为键,从1到j的划分方法为值,这样时间复杂度就可以了。

//冷静,冷静,冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
ll pre[N],p[N],f[N];
void Jiuyuan()
{ll n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>p[i];pre[i]=pre[i-1]+p[i];}map<ll,ll> op;op[0]=1;f[0]=1;ll sum=1;for(int i=1;i<=n;i++){f[i]=(sum-op[pre[i]-k]%mod+mod)%mod;op[pre[i]]=(op[pre[i]]+f[i])%mod;sum=(sum+f[i])%mod; }cout<<f[n];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
//	cin>>T;while(T--){Jiuyuan();}return 0;
}

相关文章:

ABC 370 E - Avoid K Partition

原题链接&#xff1a;E - Avoid K Partition 题意&#xff1a;给长度为n的数组&#xff0c;将数组划分成任意份&#xff0c;但是每一份的总和都不能是k&#xff0c;问有多少种分割方法。 思路&#xff1a;dp&#xff0c;f[i]&#xff0c;代表前i个元素满足题意的划分的总和&a…...

C++: set与map容器的介绍与使用

本文索引 前言1. 二叉搜索树1.1 概念1.2 二叉搜索树操作1.2.1 查找与插入1.2.2 删除1.2.3 二叉搜索树实现代码 2. 树形结构的关联式容器2.1 set的介绍与使用2.1.1 set的构造函数2.1.2 set的迭代器2.1.3 set的容量2.1.4 set的修改操作 2.2 map的介绍与使用2.2.1 map的构造函数2.…...

单片机-STM32 看门狗(八)

目录 一、看门狗概念 1、定义&#xff1a; 二、单片机中的看门狗 1、功能描述&#xff1a; 2、看门狗设置部分 预分频寄存器(IWDG_PR) 3、窗口看门狗 特性&#xff1a; 4、看门狗配置&#xff1a; 一、看门狗概念 看门狗--定时器&#xff08;不属于基本定时器、通用定…...

iOS 18.1将上线新功能,可惜这波国内的小伙伴无缘了

在科技巨头苹果持续推动其生态系统全球化的进程中&#xff0c;最新的iOS 18.1、iPadOS 18.1及macOS 15.1开发者测试版发布&#xff0c;不仅为开发者们带来了新功能的预览&#xff0c;还悄然间对Apple智能功能的地区限制进行了微妙而重要的调整。 这一变化&#xff0c;虽看似细…...

MySQL中DML操作(二)

默认值处理&#xff08;DEFAULT&#xff09; 在MySQL中可以使用DEFAULT为列设定一个默认值。如果在插入数据时并未指定该列的值&#xff0c;那么MySQL将默认值添加到该列中。 创建表时指定列的默认值 CREATE TABLE 表名(列名 类型 default 默认值......); 示例&#xff1a;…...

LLMs技术 | 整合Ollama实现本地LLMs调用

前言 近两年AIGC发展的非常迅速&#xff0c;从刚开始的只有ChatGPT到现在的很百家争鸣。从开始的大参数模型&#xff0c;再到后来的小参数模型&#xff0c;从一开始单一的文本模型到现在的多模态模型等等。随着一起进步的不仅仅是模型的多样化&#xff0c;还有模型的使用方式。…...

【C-实践】文件服务器(3.0)

文件服务器1.0文件服务器2.0文件服务器4.0 概述 使用了 tcp epoll 线程池 生产者消费者模型&#xff0c;实现文件服务器 有两个进程&#xff0c;主进程负责接收退出信号用来退出整个程序&#xff1b;子进程负责管理线程池、客户端连接以及线程池的退出 子进程中的主线程生…...

LeetCode 2181.合并零之间的节点

题目描述 给你一个链表的头节点 head &#xff0c;该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val 0 。 对于每两个相邻的 0 &#xff0c;请你将它们之间的所有节点合并成一个节点&#xff0c;其值是所有已合并节点的值之和。然后将所有 0 …...

千益畅行,共享旅游卡,引领旅游新潮流

千益畅行旅游卡是一款专为旅游爱好者打造的超值卡片。它就像一把神奇的钥匙&#xff0c;为您打开国内丰富多彩的旅游世界。 我们的旅游卡拥有众多令人惊喜的特点。首先&#xff0c;它涵盖了国内 40 多条精心策划的旅游线路&#xff0c;无论您是向往历史文化名城的厚重底蕴&…...

K均值聚类

根据到给点样本的距离&#xff0c;来聚类。 1.曼哈顿距离、 2.欧几里得距离 直线距离 3.切比雪夫距离 4.闵氏距离 5.余弦相似度 对数据大小/长度等不关注&#xff0c;只关注相似度。 6.汉明距离 二进制距离 二、密度聚类 DBSCAN 前提是样本是根据紧密程度分布的。 先用超参…...

【Ubuntu】安装常用软件包

安装java 直接输入java&#xff0c;如果没有安装的话会提醒你输入命令安装&#xff0c;类似 Command java not found, but can be installed with: sudo apt install jdkxxxxxxxxxxxxxx然后选一个版本安装就好&#xff0c;我这里选的jdk17,安装完确认一下 ubuntuVM-4-13-ubu…...

探索全光网技术 | 全光网产品解决方案整理-(宇洪科技)

探索全光网技术 |全光网产品解决方案整理-宇洪科技 目录 一、数据中心场景1、方案概述2、方案需求3、相关产品4、产品推荐5、方案价值 二、教育场景1、方案概述2、方案需求3、相关产品4、方案价值 三、医疗场景1、方案概述2、方案需求3、相关产品4、方案价值 注&#xff1a;本文…...

资料分析(2)

C B 增长量不变就是1002020 上面是利滚利:按照20%当利息 本题:涨跌幅度的意思就是增长率&#xff0c;本题是按照增长率不变的情况下进行计算D B 7551400X>1.2*100000 B B B 总体增量部分增量之和 先进行计算固定通信业务收入的增长量移动通信业务实现收入的增长量 增长量现期…...

百元以下蓝牙耳机性价比之王品牌?四大高能性价比机型推荐

面对市场上琳琅满目的蓝牙耳机品牌和型号&#xff0c;消费者往往难以抉择&#xff0c;特别是当预算限定在百元以下时&#xff0c;找到一款既满足基本功能又具备一定品质的蓝牙耳机变得尤其困难&#xff0c;那么百元以下蓝牙耳机性价比之王品牌&#xff1f;尽管价格是一个重要的…...

考场考生行为检测数据集 7000张 带标注 voc yolo

数据集名称&#xff1a; 考场考生行为检测数据集 数据集规模&#xff1a; 图像数量&#xff1a;7000张标注类型&#xff1a;行为检测&#xff08;例如&#xff1a;作弊、玩手机、睡觉等&#xff09;格式兼容性&#xff1a;支持VOC和YOLO标注格式 数据集内容&#xff1a; 该…...

深度学习算法,该如何深入,举例说明

深度学习算法的深入学习可以从理论和实践两个方面进行。理论上&#xff0c;深入理解深度学习需要掌握数学基础&#xff08;如线性代数、概率论、微积分&#xff09;、机器学习基础和深度学习框架原理。实践上&#xff0c;可以通过实现和优化深度学习模型来提升技能。 理论深入…...

舵机的原理及应用

舵机是一种位置(角度)伺服的驱动器&#xff0c;主要由外壳、电机、减速齿轮组、位置传感器和控制电路等部分组成。一、工作原理 舵机的工作原理是控制电路接收信号源的控制信号&#xff0c;并将其转换为电流信号&#xff0c;驱动电机转动。电机通过减速齿轮组带动输出轴…...

Nacos与Eureka--微服务注册中心

Nacos与Eureka Nacos和Eureka都是微服务架构中常用的服务发现和注册中心解决方案&#xff0c;它们帮助微服务架构中的各个服务实例进行互相发现和通信。 Nacos 是由阿里巴巴开源的一个动态服务发现、配置管理和服务管理平台。它支持服务的注册与发现&#xff0c;并且提供了配…...

Android 调试桥——ADB

文章目录 前言ADB 的主要功能设备连接与管理应用安装与卸载文件传输日志查看设备重启 常用命令连接方式有线无线注意点 前言 ADB&#xff08;Android Debug Bridge&#xff0c;安卓调试桥&#xff09;是 Android SDK 提供的一种命令行工具&#xff0c;用于在开发者的计算机和 …...

闲鱼放弃成为淘宝复刻版了吗?上线学生专属交易交流版块“学生鱼”频道

闲鱼是阿里巴巴旗下闲置用品交易平台&#xff0c;目前拥有超5亿用户规模、4000万日活&#xff0c;在去年被阿里定位为第一批战略创新业务&#xff0c;更是肩负“造血”的重任。闲鱼并未明确表示放弃成为淘宝&#xff0c;但近期确实上线了一个针对学生群体的专属交易交流版块——…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...