Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)

题目链接：http://codeforces.com/contest/831/problem/C

题意：给定k个评委，n个中间结果。假设参赛者初始分数为x，按顺序累加这k个评委的给分后得到k个结果，在这个过程中，某人只记得其中n次结果(n次结果不一样按照时间顺序来排列)，问你参赛者的初始合法分数有多少种。

思路：维护一个评委给分的前缀和，然后枚举每一种可能的初始分数，然后判断当前枚举的这个分数经过k次累加分数后得到的k个结果有n个结果等于给定的中间结果即可。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

#include<time.h>

#include<stack>

#include<set>

#include<cmath>

#include<functional>

#include<cstdlib>

using namespace std;

typedef long long int LL;

typedef unsigned long long int ULL;

const LL INF = 9223372036854775807L;

const int inf = 0x3f3f3f3f;

const int MAXN =  + ;

const int MAXB = 8e6 + ;

set<LL>se;

LL val[MAXN], source[MAXN],pre[MAXN];

LL statu[MAXN];

bool visb[MAXB],vis[MAXB];

int main(){

#ifdef kirito

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int start = clock();

    int n, k;

    while (~scanf("%d%d",&k,&n)){

        se.clear();

        memset(visb, , sizeof(visb));

        memset(pre, , sizeof(pre));

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

            scanf("%I64d", &val[i]);

            pre[i] += pre[i - ] + val[i];

        }

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

            scanf("%I64d", &source[i]);

            visb[source[i] + ] = ;

        }

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

            int cnt = ;

            statu[] = source[]-pre[i];

            memset(vis, , sizeof(vis));

            if (se.count(statu[])){

                continue;

            }

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

                statu[j] = statu[j-] + val[j];

                if (statu[j] + <MAXB&&visb[statu[j] + ] && vis[statu[j] + ] == false){

                    cnt++;

                    vis[statu[j] + ] = true;

                }

            }

            if (cnt == n){

                se.insert(statu[]);

            }

        }

        printf("%d\n", se.size());

    }

#ifdef LOCAL_TIME

    cout << "[Finished in " << clock() - start << " ms]" << endl;

#endif

    return ;

}

巴特西

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) - C

最新文章

热门文章