3 条题解

  • 2
    @ 2026-10-9 8:45:18

    置换环典题,直接上 visvis 数组标记是否经过,对于每个环看一下长度,求的时候直接跳 kmod   k\mod \space 长度次即可(因为是环,可以 O(长度)O(长度) 求出来这个环内每一个位置跳之后的位置)。

    时间复杂度 O(nm)O(nm)。

    #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
    上传者