SP1108 题解
Rookie_t
·
·
题解
再看了几篇题解以后，我发现这道题要用链表。
具体如何模拟，其他几篇题解已经讲的很清楚了。
我说一下手打链表该如何使用。
只要每次赋值之后就将这个数组下标值对应的链表值进行更改就行。
我们可以模拟一下样例中 $ n = 4$ 的情况。
1. 0 0 0 0
2. 0 1 0 0
3. 2 1 0 0
4. 2 1 0 3
5. 2 1 4 3
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 20010;
int T,n,a[maxn],next[maxn],last[maxn],now;
int main(){
ios::sync_with_stdio(false);
cin>>T;
while(T--){
scanf("%d",&n);
memset(a,0,sizeof(a));
for(int i = 0;i<=n;i++){
next[i] = i+1,last[i] = i-1;
}
next[n] = 1,last[1] = n;
now = 0;
for(int i = 1;i <= n;i++){
int k = n-i+1,t = i%k+1;
for(int j = 1;j <= t;j++){
now = next[now];
}
a[now] = i;
next[last[now]] = next[now];
last[next[now]] = last[now];
}
for(int i = 1;i<=n;i++){
printf("%d ",a[i]);
}
cout<<endl;
}
return 0;
}
```