3 条题解

  • 8
    @ 2025-3-26 11:05:05

    主播主播,你们的倍增确实很强,不过我有和logklogk 无关的做法哦。

    首先暴力处理一轮操作以后得到的序列。

    我们发现这可以认为是一个置换,说白了就是一堆环。

    然后因为每个环相互独立,我们可以把每个环都存下来,然后每个数最终能变成的数字就是在这个环上跑 kk 步,这是显然的。

    然后我们就可以吧 kk 开到特别大了。

    时间复杂度 O(nm)O(nm) ,瓶颈在处理区间交换上

    代码省略。

  • 3
    @ 2025-3-26 11:42:49

    倍增

    我们考虑预处理出来第 ii 位翻转 2j2^j 后的位置,用 dpi,jdp_{i,j} 存下来,然后把 kk 二进制拆分来把每个位置上的数都变为答案需要的

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    const int N=1e5+10;
    int n,m,k,cnt=-1;
    int a[N],p[30];
    int f[N][32];
    inline int reads(){
    	char c=getchar();
    	int x=0,f=1;
    	while(!isdigit(c)){
    		if(c=='-') f=-1;
    		c=getchar();
    	}
    	while(isdigit(c)){
    		x=(x<<3)+(x<<1)+(c^48);
    		c=getchar();
    	}
    	return x*f;
    }
    signed main(){
    //	freopen("C.in","r",stdin);
    //	freopen("C.out","w",stdout);
    	n=reads(),m=reads(),k=reads();
    	for(int i=1;i<=n;i++) a[i]=i;
    	for(int i=1;i<=m;i++){
    		int l,r;
    		l=reads(),r=reads();
    		reverse(a+l,a+r+1);
    	}
    	for(int i=1;i<=n;i++) f[i][0]=a[i],a[i]=i;
    	for(int j=1;j<=30;j++){
    		for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    	}
    //	for(int i=1;i<=n;i++){
    //		for(int j=0;j<=3;j++){
    //			cout<<f[i][j]<<" ";
    //		}
    //		puts("");
    //	}
    	while(k){
    		int t=k&1;
    		p[++cnt]=t;
    		k>>=1;
    	}
    //	for(int i=0;i<=cnt;i++){
    //		cout<<p[i]<<" ";
    //	}
    //	puts("\n---");
    	for(int i=0;i<=cnt;i++){
    		if(p[i]){
    			for(int j=1;j<=n;j++){
    				a[j]=f[a[j]][i];
    			}
    		}
    //		cout<<i<<" "<<p[i]<<":";
    //		for(int j=1;j<=n;j++) cout<<a[j]<<" ";
    	}
    	for(int i=1;i<=n;i++) printf("%d\n",a[i]);
    	return 0;
    }
    
    
    • 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
      */
      
      • 1

      信息

      ID
      105
      时间
      1000ms
      内存
      256MiB
      难度
      6
      标签
      (无)
      递交数
      80
      已通过
      24
      上传者