题解：P14171 【MX-X23-T1】丢手绢

ACcepted917 · 2025-10-06 18:17:09 · 题解

题解：P14171 丢手绢

分析

为了方便模运算，把小朋友的编号设为 0 \sim n，最后再还原。

由于是转圈丢手绢，当前位置操作后要进行取余，若当前位置为 i，则丢手绢后，手绢会在编号为 (i+a-1)%n 的小朋友背后。

统计手绢在每个小朋友背后的次数，输出最多次数的那几个小朋友的编号。

代码1

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5;
int n,a,cnt[N],maxx;
//cnt 为统计数组
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(register int i=1;i<=n;i++){
        cin>>a;
        maxx=max(maxx,++cnt[(i+a-1)%n]);
    }
    for(register int i=1;i<=n;i++){
        if(cnt[i-1]==maxx){
            cout<<i<<' ';
        }
    }
    return 0;
}

避坑操作

提交，发现 \color{red} \texttt{WA} \color{black} \texttt{+} \color{purple} \texttt{RE} 了，link。

为什么？？？

看这里 (i+a-1)%n，当 a 为负数时，(i+a-1)%n 可能小于 0，导致数组越界。

怎么办？？？

改成 (i+n+a-1)%n 即可，这样就不会越界了。

代码2

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5;
int n,a,cnt[N],maxx;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(register int i=1;i<=n;i++){
        cin>>a;
        maxx=max(maxx,++cnt[(i+n+a-1)%n]);
    }
    for(register int i=1;i<=n;i++){
        if(cnt[i-1]==maxx){
            cout<<i<<' ';
        }
    }
    return 0;
}

提交，终于 \color{lightgreen} \texttt{AC} 了。

感谢管理审核，感谢各位 dalao 阅读。