BestCoder Round #85 sum

大晚上的更一道下午的水题吧。(虽然WA了好多次= =,但真实情况是我比较水)

描述

Given a sequence, you‘re asked whether there exists a consecutive subsequence whose sum is divisible by m. output YES, otherwise output NO.

输入

The first line of the input has an integer T (1≤T≤10), which represents the number of test cases. For each test case, there are two lines: 1.The first line contains two positive integers n, m (1≤n≤100000, 1≤m≤5000). 2.The second line contains n positive integers x (1≤x≤100) according to the sequence.

输出

Output T lines, each line print a YES or NO.

样例输入

2
3 3
1 2 3
5 7
6 6 6 6 6

样例输出

YES
NO

代码如下:

 1 #include <cstdio>
 2 #define N 100100
 3
 4 int main()
 5 {
 6     int t,n,m,a[N];
 7     int flag=0;
 8     scanf("%d",&t);
 9     while(t--){
10         scanf("%d %d",&n,&m);
11         int sum=0;
12         int k=1;
13         for(int j=1;j<=n;j++){
14            scanf("%d",&a[j]);
15         }
16         for(int i=1;i<=n;i++){
17                while(k<=n&&sum<m){
18                   sum+=a[k++];
19                }
20                if(sum==m){
21                      flag=1;
22                      break;
23                }
24                sum-=a[i];
25
26         }
27         if(flag==1){
28             printf("YES\n");
29         }else
30             printf("NO\n");
31         flag=0;
32     }
33     return 0;
34 } 

题意:

题意:能不能找一个连续子区间的和是m的倍数。

思路总结:

简单尺取法。既然说找的是m的倍数,那就从头开始加起来。加到数小于m且加起来得到的和是最大的小于m的数。开始判断。如果失败就从头开始减一个,在接着从后加一个。一点点枚举。像尺子一样~~所以叫尺取法~~HOHO~

时间: 07-29

BestCoder Round #85 sum的相关文章

BestCoder Round #91

传送门:http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2391&source=1&searchmode=source A题:给你n种字母,每种字母有个权值vali,共cnti个,现在让你在里面挑出任意数量的字符,组合成一个字符串,该字符串的权值的计算方式为val1*1+val2*2+--+valn*n,让你输出字符串最大的权值是多少.这题很容易会有一个错误的贪心,就是把val为负的舍去,然后v

hdu 5163 Taking Bus (BestCoder Round #27)

Taking Bus                                                               Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 501    Accepted Submission(s): 203 Problem Description Bestland has a v

BestCoder Round #9

BestCoder Round #9 题目链接 A:暴力枚举一个数字,就能求出另一个数字,for一遍即可 B:博弈,判断前n - 1个开头连续1的奇偶性即可 C:先预处理出每个点对应哪几个点,每次查询计算一次即可 代码: A: #include <cstdio> #include <cstring> #include <vector> #include <set> #include <algorithm> #include <cmath&g

hdu 4956 Poor Hanamichi BestCoder Round #5(数学题)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4956 Poor Hanamichi Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7    Accepted Submission(s): 4 Problem Description Hanamichi is taking part in

BestCoder Round #4 前两题 hdu 4931 4932

第一题太水了.. 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int a[6]; 7 int main(){ 8 int cas; 9 scanf( "%d", &cas ); 10 while( cas-- ){ 11 for( int i = 0; i <

hdu4908 &amp; BestCoder Round #3 BestCoder Sequence(组合数学)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4908 BestCoder Sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 618    Accepted Submission(s): 214 Problem Description Mr Potato is a code

BestCoder Round #88

传送门:BestCoder Round #88 分析: A题统计字符串中连续字串全为q的个数,预处理以下或加个cnt就好了: 代码: 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <ctime> 5 #include <cmath> 6 #include <iostream> 7 #include <algorithm> 8

HDU 5651 xiaoxin juju needs help(BestCoder Round #77 (div.1)1001)

传送门 xiaoxin juju needs help Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 861    Accepted Submission(s): 243 Problem Description As we all known, xiaoxin is a brilliant coder. He knew **palin

BestCoder Round #29——A--GTY&#39;s math problem(快速幂(对数法))、B--GTY&#39;s birthday gift(矩阵快速幂)

GTY's math problem Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 0    Accepted Submission(s): 0 Problem Description GTY is a GodBull who will get an Au in NOI . To have more time to learn alg