cslg2022-06-12组队训练
C Swapping Game
题意:大致题意就是奇数次操作交换前2n项两两交换,偶数次操作2-2n-1次两两交换,问你k次操作后,第q个数是几
通过画出n=3,n=4的图能看出数字的顺序是没2n一次循环,所以先把k对2n取模
接着可以发现每一个数字的运动都可形象化成一个小人在两块墙之间(1和n)来回跑并且每到墙壁都要休息一次,那我从我要求的q这个位置反向往回跑,我跑回的位置就是我们所要求的值
通过图可以发现,如果往回跑的话,奇数排中,下标为奇数的人初始方向向右,下标为偶数的人初始方向为左,偶数排相反(这里我觉得题目数据可以加强一下。我一开始的代码是奇数排向右偶数排向左,很明显这是不对的。但是题给我弄巧成拙的过了0.0,想题解的时候才发现前面的规律0.0),接着模拟就可以了
过题代码
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
int main()
{
long long int t;
cin>>t;
while(t--){
long long int n,k,q;
cin>>n>>k>>q;
k%=2*n;
long long int x;
if(k%2==1){
if(q%2==1){
x=1;
}else{
x=0;
}
}else{
if(q%2==0){
x=0;
}else{
x=1;
}
}
while(k){
if(x==1){
long long int y=n-q;
if(n-q<k){
k-=(n-q);
q=n;
if(k>=1){
k-=1;
}
x=0;
}else{
q+=k;
k=0;
}
}else if(x==0){
long long int y=q-1;
if(q-1<k){
k-=(q-1);
q=1;
if(k>=1){
k-=1;
}
x=1;
}else{
q-=k;
k=0;
}
}
}
cout<<q<<endl;
}
}