3 条题解
-
2
置换环典题,直接上 数组标记是否经过,对于每个环看一下长度,求的时候直接跳 长度次即可(因为是环,可以 求出来这个环内每一个位置跳之后的位置)。
时间复杂度 。
#include<bits/stdc++.h> using namespace std; #define ll long long int n,m,k,id[100005],nxt[100005],vis[100005],ans[100005]; int xh[100005]; signed main(){ cin.tie(0); ios::sync_with_stdio(false); //freopen("ex.in","r",stdin); //freopen("my.out","w",stdout); cin>>n>>m>>k; for(int i=1; i<=n; i++){ id[i]=i; } for(int i=1; i<=m; i++){ int l,r; cin>>l>>r; for(int j=l,kkc=r; j<=kkc; j++,kkc--){ swap(id[j],id[kkc]); } } for(int i=1; i<=n; i++) nxt[id[i]]=i; for(int i=1; i<=n; i++){ if(vis[i]) continue; int now=i,j=1; vis[i]=1; for(j=1;j<=n;j++){ now=nxt[now]; if(vis[now]){ break; } vis[now]=1; } now=i; int now2=i,cishu=0; cishu=k%j; while(cishu--) now=nxt[now]; xh[i]=now; for(int kkc=1; kkc<j; kkc++){ now2=nxt[now2]; now=nxt[now]; xh[now2]=now; } } for(int i=1; i<=n; i++) ans[xh[i]]=i; for(int i=1; i<=n; i++) cout<<ans[i]<<"\n"; return 0; } /* 1->2->3->4->1 5->5 */
信息
- ID
- 105
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 80
- 已通过
- 24
- 上传者