自动搬运

查看原文

来自洛谷，原作者为

	Dragon_JL QwQ 最后在线时间：2025年8月24日21时14分

搬运于2025-08-24 21:15:40，当前版本为作者最后更新于2025-02-14 22:27:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道比较入门的模拟题
终于轮到我水一下题解了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;
}