3 条题解
-
3
倍增
我们考虑预处理出来第 位翻转 后的位置,用 存下来,然后把 二进制拆分来把每个位置上的数都变为答案需要的
#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
置换环典题,直接上 数组标记是否经过,对于每个环看一下长度,求的时候直接跳 长度次即可(因为是环,可以 求出来这个环内每一个位置跳之后的位置)。
时间复杂度 。
#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
- 上传者