牛客OI测试赛 C 序列 思维

链接：https://www.nowcoder.com/acm/contest/181/C
来源：牛客网

题目描述

小a有n个数，他想把他们划分为连续的权值相等的k段，但他不知道这是否可行。

每个数都必须被划分

这个问题对他来说太难了，于是他把这个问题丢给了你。

输入描述:

第一行为两个整数n,q，分别表示序列长度和询问个数。
第二行有n个数，表示序列中的每个数。
接下来的q行，每行包含一个数k，含义如题所示。

输出描述:

输出q行，每行对应一个数Yes或者No，分别表示可行/不可行

示例1

输入

复制

5 3
2 1 3 -1 4
3
2
1

输出

复制

Yes
No
Yes

备注:

对于的数据，

对于的数据，

对于的数据，

设a_i表示数列中的第i个数，保证

保证数据完全随机

 

分析：

AC代码：

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
const double pi = acos(-1.0);
ll a[maxn];
int main() {
    std::ios::sync_with_stdio(false);
    ll n, q, sum = 0;
    scanf("%lld%lld",&n,&q);
    for( ll i = 0; i < n; i ++ ) {
        scanf("%lld",&a[i]);
        sum += a[i];
    }
    while( q -- ) {
        ll k;
        scanf("%lld",&k);
        if( sum%k || k > n ) {
            printf("No
");
            continue;
        }
        ll ans = 0, avg = sum/k, cnt = 0;
        bool flag = false;
        for( ll i = 0; i < n; i ++ ) {
            ans += a[i]; //最后可能加上0，而0可以合并到前面区间，所以用ans=0来判断
        //开始用flag判断最后一位是否刚好可以让ans=avg，判断错了
        if( ans == avg ) {
                ans = 0;
                cnt ++;
            }
        }
        if( ans == 0 && cnt == k ) {
            printf("Yes
");
        } else {
            printf("No
");
        }
    }
    return 0;
}