上海计算机学会2023年5月月赛c++乙组t2集体舞-爱代码爱编程
题目描述
n 名演员围成一个圆圈跳集体舞，每名演员都有一个位置。演员与位置的编号都是从 1 开始到 n 结束。最初，每个演员都站在自己对应的位置编号上。
在舞蹈进行的过程中，陆续会出现若干变换，这些变变换形分成两种类型：
-
第一种变换称为旋转，用字母
r表示。在这种变换下：- 原先 1 号位上的演员将移动去 2 号位
- 原先 2 号位上的演员将移动去 3 号位
- … 以此类推
- 原先 n 号位上的演员将移动去 1 号位
-
第二种变换称为翻转，用字母
f表示。在这种变换下：- 1 号位上的演员与 n 号位上的演员对换
- 2 号位上的演员与 n−1 号位上的演员对换
- … 以此类推
- 特别注意，若 n 是奇数，则在翻转变换下，(n+1)/2 号位置上的演员位置不变。
给定一个字符序列，表示集体舞依次经历的变换，输出每个位置在舞蹈结束后的演员编号。
输入格式
- 第一行：单个整数 n
- 第二行：一个字符串 s 表示变换序列，保证只由
r与f组成。
输出格式
- 共 n 行：在第 i 行有一个整数，表示舞蹈结束时，第 i 个位置上的演员编号。
数据范围
设 ∣s∣ 表示输入字符串的长度
- 30% 的数据，1≤n≤3000，1≤∣s∣≤3000
- 60% 的数据，1≤n≤100,000，01≤∣s∣≤100,000
- 100% 的数据，1≤n≤500,000，1≤∣s∣≤500,000
样例数据
输入:
4
rfr
输出:
4
3
2
1
说明:
(1,2,3,4)--r-->(4,1,2,3)
(4,1,2,3)--f-->(3,2,1,4)
(3,2,1,4)--r-->(4,3,2,1)
解析：经分析，翻转会影响顺序或者倒序，倒序时旋转会变成反方向，旋转只影响开始位置，所以可以将翻转和旋转都统计起来，最后一并处理。详见代码。
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int jl=0;//距离，默认为0，即每个演员向右移动的距离
bool fx=1;//方向，默认1为顺序
int a[500005];
int main(){
cin>>n>>s;
int len;
len=s.size();
for (int i=0;i<len;i++){
if (s[i]=='f'){//如果是f，方向变为反方向
fx=!fx;
}
if (s[i]=='r'){//如果是r，则变化距离
if (fx){//正方向，距离增加
jl++;
}else{//反方向，距离减少
jl--;
}
}
}
jl%=n;//距离超过一圈的部分去掉
if (jl>0){//正方向移动
for (int i=1;i<=n;i++){
a[i]=i-jl;
if (a[i]<=0) a[i]+=n;//小于等于0的加上n
}
}else{//反方向移动
for (int i=1;i<=n;i++){
a[i]=i-jl;
if (a[i]>n) a[i]-=n;//大于n的减掉n
}
}
if (fx){//方向为正，正序输出
for (int i=1;i<=n;i++){
printf("%d\n",a[i]);
}
}else{//方向为反，逆序输出
for (int i=n;i>=1;i--){
printf("%d\n",a[i]);
}
}
return 0;
}