专栏文章

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

AACcepted917
P14171题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minoghlk
此快照首次捕获于
2025/12/02 05:44
3 个月前
此快照最后确认于
2025/12/02 05:44
3 个月前
查看原文

题解：P14171 丢手绢

分析

为了方便模运算，把小朋友的编号设为 0∼n0 \sim n，最后再还原。
由于是转圈丢手绢，当前位置操作后要进行取余，若当前位置为 ii，则丢手绢后，手绢会在编号为 (i+a-1)%n 的小朋友背后。
统计手绢在每个小朋友背后的次数，输出最多次数的那几个小朋友的编号。

代码1

CPP
#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;
}

避坑操作

提交，发现 WA+RE\color{red} \texttt{WA} \color{black} \texttt{+} \color{purple} \texttt{RE} 了，link。
为什么？？？
看这里 (i+a-1)%n，当 aa 为负数时，(i+a-1)%n 可能小于 00，导致数组越界。
怎么办？？？
改成 (i+n+a-1)%n 即可，这样就不会越界了。

代码2

CPP
#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;
}
提交，终于 AC\color{lightgreen} \texttt{AC} 了。
感谢管理审核，感谢各位 dalao 阅读。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...