B3877 [信息与未来 2015] 分数计数 题解

· · 题解

一道比较入门的模拟题
终于轮到我水一下题解了awa

这道题其实已经将具体的思路在题面上告诉你了。我们只需要按照题目给出的公式：

x_i = ((x_{i-1}\times 3703+1047) \bmod n)+1

求出每一场比赛获胜的队伍，然后遍历整个数组就可以得出每支球队的分数。
那么，在遍历整个数组的时候，我们如何知道该队伍应该加多少分呢。由于第一次胜利是加 1 分，连胜两场是加 2 分，连胜三场及以上每场加 3 分。于是，我们可以使用 cnt 来统计应该加的分。核心实现如下：

int cnt=0;
for(int i=1;i<=n;i++){
    if(x[i]==x[i-1]){ //若该队伍连胜，那么我们就更新 cnt 来确定应该加的分数
        cnt=cnt<3?cnt+1:cnt; //判断连胜有没有超过三场
        s[x[i]]+=cnt; //x[i]为胜利队伍名称，所以s[x[i]]也就是该队伍所对应的得分情况了
    }else{ //这里是连胜中第一次胜利的情况
        cnt=1;
        s[x[i]]+=cnt;
    }
    ans=max(ans, s[x[i]]); //这里可以在每次循环后直接把当前的最大得分求出来
}

在上面代码中，我们使用 x 数组来储存每一场胜利的队伍，用 s 数组来储存每一支队伍的总分。通过遍历 x 数组来计算出每一支队伍的总分。 完整代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,ans,x[N],s[N];

signed main(){
   cin>>n>>x[1];
   for(int i=2;i<=n;i++)
       x[i]=((x[i-1]*3703+1047)%n)+1; //按题目给出的公式来求出每一场胜利的队伍

       int cnt=0;
       for(int i=1;i<=n;i++){
           if(x[i]==x[i-1]){ //若该队伍连胜，那么我们就更新 cnt 来确定应该加的分数
               cnt=cnt<3?cnt+1:cnt; //判断连胜有没有超过三场
               s[x[i]]+=cnt; //x[i]为胜利队伍名称，所以s[x[i]]也就是该队伍所对应的得分情况了
           }else{ //这里是连胜中第一次胜利的情况
               cnt=1;
               s[x[i]]+=cnt;
           }
           ans=max(ans, s[x[i]]); //这里可以在每次循环后直接把当前的最大得分求出来
        }
    cout<<ans;
    return 0;
}