#424 Div2 C

题意

给出 k 个分数，初始分数未知，按顺序把这 k 个分数加到初始分数上，已知 n 个加入分数后的结果（无序），问初始分数有多少种可能。

分析

也就是说这 n 个结果，它们之间的差是确定的（排序之后作差），对 k 个分数求前缀和，分别枚举每一个数作为起点，是否能找到后面的数使得最后的数列数之间的差与 n 个结果的差相同。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3000;

int a[MAXN], b[MAXN];

set<int> S;

int main() {

    int n, k;

    cin >> n >> k;

    for(int i = 0; i < n; i++) {

        cin >> a[i];

        if(i) {

            a[i] += a[i - 1];

        }

        S.insert(a[i]);

    }

    for(int i = 0; i < k; i++) {

        cin >> b[i];

    }

    sort(a, a + n);

    sort(b, b + k);

    int ans = 0;

    for(int i = 0; i + k <= n; i++) {

        if(i && a[i] == a[i - 1]) continue;

        int st = a[i];

        int p = 1;

        for(int j = 1; j < k; j++) {

            int x = b[j] - b[j - 1];

            st += x;

            if(!S.count(st)) {

                p = 0;

                break;

            }

        }

        ans += p;

    }

    cout << ans << endl;

    return 0;

}

巴特西

#424 Div2 C

#424 Div2 C

题意

分析

code

最新文章

热门文章