Codeforces 831C--Jury Marks （思维）

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

题意：有一位参赛选手，我们不知道他初始或最后的成绩，但是知道k次评审所加（减）的分数，以及n个在这过程中的他的分数。问这名选手初始分有几种情况。

思路：一开始考虑先求出评审分的前缀和，对过程分减去前缀和就能得到的初始分数，求出所有的初始分数情况，用map记录每个初始分重复的次数，重复次数==n 的即为正确的初始分。

然而这么做是WA了的。

分析第一个样例：

4 1
-5 5 0 20
10

如果按照上面的思路，输出答案是2。由于前缀和为0存在重复，使得10这个初始分重复了2次。
那么我们就需要去除重复的前缀和。
再来思考一下这种做法的正确性：由于前缀和都是不相等的，也就能说明对一个过程分，会产生不同的初始分数，那么对于一个初始分数，其中一个过程分是唯一的（一一对应），当这个初始分存在k个不同的初始分数时它必定是正确的

AC代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

typedef long long LL;

const int MAXN=;

int sum[MAXN],a,b;

bool vis[MAXN];

int main()

{

    int k,n;

    sum[]=;

    cin>>k>>n;

    memset(vis, , sizeof(vis));

    map<int,int> mp;

    map<int,int>::iterator it;

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

        scanf("%d", &a);

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

    }

    sort(sum+, sum+k+);

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

        if(sum[i]==sum[i-])

            vis[i]=;

    }

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

        scanf("%d", &b);

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

            if(vis[j])

                continue;

            mp[b-sum[j]]++;

            //cout<<b-sum[j]<<endl;

        }

    }

    int res=;

    for(it=mp.begin();it!=mp.end();it++){

        if(it->second==n)

            res++;

    }

    printf("%d\n",  res);

    return ;

}

巴特西

Codeforces 831C--Jury Marks （思维）

最新文章

热门文章