博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU-5776 Sum
阅读量:5324 次
发布时间:2019-06-14

本文共 723 字,大约阅读时间需要 2 分钟。

题目大意:

给定一个数列,求是否存在连续子列和为m的倍数,存在输出YES,否则输出NO

解题思路:

官方题解:预处理前缀和,一旦有两个数模m的值相同,说明中间一部分连续子列可以组成m的倍数。 另外,利用抽屉原理,我们可以得到,一旦n大于等于m,答案一定是YES 复杂度 O(n)

代码:

#include 
#include
using namespace std;const int maxn = 5000 + 5;int vis[maxn];int main(){ int n, m, x, t, sum, flag; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); sum = 0; flag = 0; memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; ++i){ scanf("%d", &x); sum = (sum + x) % m; vis[sum] += 1; if(vis[sum] >= 2) flag = 1; } if(flag || vis[0]) puts("YES"); else puts("NO"); } return 0;}

转载于:https://www.cnblogs.com/wiklvrain/p/8179433.html

你可能感兴趣的文章
Oracle 序列的应用
查看>>
1201 网页基础--JavaScript(DOM)
查看>>
组合数学 UVa 11538 Chess Queen
查看>>
oracle job
查看>>
Redis常用命令
查看>>
XML学习笔记(二)-- DTD格式规范
查看>>
IOS开发学习笔记026-UITableView的使用
查看>>
[转载]电脑小绝技
查看>>
windos系统定时执行批处理文件(bat文件)
查看>>
thinkphp如何实现伪静态
查看>>
BZOJ 2243: [SDOI2011]染色( 树链剖分 )
查看>>
BZOJ 1925: [Sdoi2010]地精部落( dp )
查看>>
c++中的string常用函数用法总结!
查看>>
界面交互之支付宝生活圈pk微信朋友圈
查看>>
字符串比较
查看>>
epoll 技术(转)
查看>>
<转>Shell脚本相关
查看>>
使用FreeMarker加载远程主机上模板文件,比如FTP,Hadoop等(转载)
查看>>
Java的位运算符具体解释实例——与(&amp;)、非(~)、或(|)、异或(^)
查看>>
java 注解 学习
查看>>