Codeforces 831C--Jury Marks （思维）-白红宇

Codeforces 831C--Jury Marks （思维）

阅读量：6285 次

发布时间：2019-06-22

本文共 1087 字，大约阅读时间需要 3 分钟。

题目链接：

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

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

然而这么做是WA了的。

分析第一个样例：

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

AC代码：

#include
     
      #include
      
       #include
       
        #include
        #include
         
          using namespace std;typedef long long LL;const int MAXN=2005;int sum[MAXN],a,b;bool vis[MAXN];int main() {    int k,n;    sum[0]=0;    cin>>k>>n;    memset(vis, 0, sizeof(vis));    map
          
            mp; map
           
            ::iterator it; for(int i=1;i<=k;i++){ scanf("%d", &a); sum[i]=sum[i-1]+a; } sort(sum+1, sum+k+1); for(int i=2;i<=k;i++){ if(sum[i]==sum[i-1]) vis[i]=1; } for(int i=1;i<=n;i++){ scanf("%d", &b); for(int j=1;j<=k;j++){ if(vis[j]) continue; mp[b-sum[j]]++; //cout<
            
             <
             
              second==n) res++; } printf("%d\n", res); return 0;}

转载于:https://www.cnblogs.com/MasterSpark/p/7435300.html

你可能感兴趣的文章

【ASP.NET 类库】当你懒得用 Json+Ajax 时，可以试试 AjaxPro