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

· · 题解

这道题看上去很难，但是慢慢思考其实还是会发现很简单的。

思路

这道题的思路也是很简单。

哪一个队伍获胜了

我们首先根据题目给出的公式 x_i = ((x_{i-1}\times 3703+1047) \bmod n)+1 来算出这 n 场比赛中每一场比赛都是哪一队取得了胜利。

for(int i=2;i<=n;i++)
        x[i]=((x[i-1]*3703+1047)%n)+1;//根据题目要求来判断这场比赛那一个队伍获胜了

然后。我们先定义两个变量 a_i 和 cnt，a_i 就是我这个队伍现在的得分，而 cnt 则是我现在是几连胜。然后就该判断是几连胜了，这里我们分类讨论。

一连胜

一连胜就是说我现在这场获胜的队伍不是前面一场获胜的队伍，那么他就是一连胜了。这个时候，我们银应该让 a_{x_i} 的得分加一，并且让 cnt 等于一，表示我现在是一连胜了。

if(x[i]!=x[i-1]){
    a[x[i]]++;//加分
    cnt=1;//cnt++
}

二连胜

二连胜就是我现在这场比赛获胜的队伍是前面一场比赛获胜的队伍，并且 cnt 是一。这个时候就是二连胜了。我们要令 a_{x_i} 加二，cnt 要等于二或者加一。然后我们就做完了二连胜。

if(x[i]==x[i-1] && cnt==1){
    a[x[i]]+=2;//加分
    cnt++;//cnt=2
}

三连胜及多连胜

我们这里可以先看题，会发现，如果一支队伍连续赢了三场及以上，那么我就只加三分，所以我们把这两种情况合并成一种。判断条件就是我现在这场比赛获胜的队伍是前面一场比赛获胜的队伍，并且 cnt 是大于等于二的才算三连胜或者多连胜。如果满足就要 a_{x_i} 加三并且 cnt 加一，注意这里是加一。因为他如果是多连胜的话就不能是三了。

if(x[i]==x[i-1] && cnt>=2){
    a[x[i]]+=3;//加分
    cnt++;//几连胜
}

找答案

最后我们找最大的 a_i 就好了。

for(int i=1;i<=n;i++)
        ans=max(ans,a[i]);

把代码拼一下就好了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
long long n, x[N];
long long a[N], cnt;
long long ans;
int main(){
    cin>>n>>x[1];
    for(int i=2;i<=n;i++)
        x[i]=((x[i-1]*3703+1047)%n)+1;//根据题目要求来判断这场比赛那一个队伍获胜了
    for(int i=1;i<=n;i++){
        if(x[i]!=x[i-1]){
            a[x[i]]++;//加分
            cnt=1;//cnt++
        }else if(x[i]==x[i-1] && cnt==1){
            a[x[i]]+=2;//加分
            cnt++;//cnt=2
        }else if(x[i]==x[i-1] && cnt>=2){
            a[x[i]]+=3;//加分
            cnt++;//几连胜
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,a[i]);
    cout<<ans<<endl;
    return 0;
}