洛谷 P3131 子共七
2024-09-07 16:44:46
看到这一题第一印象就是暴力好打,$O(n^2)$,预计得分$70$分
这明显满足不了啊,我们要用到前缀和。
$sum[i]$记录到i的前缀和,区间$[a,b]$的和就是$sum[b]-sum[a-1]$.
处理完以后怎么统计呢,$n^2$当然不行,我们要用到一个显然的定理。
如果 $a\equiv c(mod$ $k)$并且$b\equiv c(mod$ $k)$,那么$|a-b|\equiv 0(mod$ $k)$
显然两个数的余数在相减的时候同时减去,从而只剩下$k$的倍数。
所以题目里我们只需要考虑每个前缀和$mod$ $7$的余数,若余数相等那么$sum[i]$ $mod$ $7=0$,所以我们只需要记录一下每个余数第一次出现的位置和最后一次出现的位置,相减的出答案(至少出现两次哦)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
int n,a[],sum[],ans,k,f[];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
sum[i]%=; }
for(int i=;i<=n;i++)
{
if(!f[sum[i]])f[sum[i]]=i;
else ans=max(ans,i-f[sum[i]]);
}
printf("%d",ans);
}
最新文章
- Linux C--信号 sigaction函数
- 【Android自学日记】五大布局常用属性
- initial、inherit、unset、revert和all
- jQuery Portamento 滑动定位
- about semget
- 1032 - Intersecting Dates
- C#中方法的参数修饰符
- 应用程序的关闭退出(在FMX中,Activity替代了Form的概念)
- [LeetCode]题解(python):084-Largest Rectangle in Histogram
- C++出现计算机术语5
- ACdream 之ACfun 题解
- 在asp.net中使用ajax记录
- shc &; unshc 安装
- 001 爬虫的基本概念以及urllib的request和parse
- zyupload四种不同的PHP上传demo
- 数据建模工具系列 之 让Oracle Data Modeler支持Vertica
- android 开发 框架系列 使用 FileDownloader 实现检查更新的功能class
- Java下载https文件上传到阿里云oss服务器
- 使用T4Scaffolding 创建自己的代码生成
- nginx使用“sudo service nginx start”启动报错解决方案
热门文章
- bzoj 3594: [Scoi2014]方伯伯的玉米田【二维树状数组+dp】
- hdu3926 Hand in Hand 同构图
- Hexo瞎折腾系列(3) - 添加GitHub彩带和GitHub Corner
- 【模板】c++动态数组vector
- 区间dp实战练习
- 148 Sort List 链表上的归并排序和快速排序
- Retrofit Upload multiple files and parameters
- Android studio 时间选择器
- TCAM 与CAM
- 8 Explicit Animations 指明的动画 笔记