Cycle
【题目描述】
给出一个序列P
定义F(p,k)操作为把p分成若干组，每组k个元素（最后一组可能不够k个元素），然后每组元素整体左移一位。比如p=(1,2,3,4)，F(p,2)=(2,1,4,3)，F(p,3)=(2,3,1,4)...
现在你需要求出F(F(F(...F([1,2,3,4...,n],2)...),n-1),n)的结果
【输入格式】
一个数字n
【输出格式】
一行n个数字，为F(F(F(...F([1,2,3,4...,n],2)...),n-1),n)的结果
【输入样例】
4
【输出样例】
4 2 3 1
【样例解释】
F([1,2,3,4],2)=[2,1,4,3]
F([2,1,4,3],3)=[1,4,2,3]
F([1,4,2,3],4)=[4,2,3,1]
【数据约定】
40%数据n<=1000
100%数据:1<=n<=10^6
【解法】
暴力的时复杂度为O(n^2),所以想想比较玄学的优化。我们发现每次变化的只有n / i 个,所以我们可以只操作那n / i 个.
刚开始我想的是数组模拟链表,后来我发现经过变化后,序列还是连续的(自己画一下就知道了)前一个数刚好放在后一个数的位置
时间复杂度o(n/2+n/3+....+1)
【代码】从后往前
#include<cstdio> #include<cstdlib> #include<iomanip> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int a[2000001]; int i,j,k,m,n,o,p,js,jl,ma,mb; int main() { FILE *fin,*fout; memset(a,0,sizeof(a)); fin=fopen("cycle.in","rb"); fout=fopen("cycle.out","wb"); fscanf(fin,"%d",&n); for(int i=1;i<=n;i++) { a[i]=i; } ma=0; for (i=2;i<=n;i++) { ma++; mb=ma+n-(n%i); a[n+ma]=a[mb]; for (j=mb;j>=ma+i;j-=i)a[j]=a[j-i]; } for(int i=n;i<=n+n-1;i++)fprintf(fout,"%d ",a[i]); fclose(fin); fclose(fout); }
【代码2】从前往后
#include<cstdio> #include<cstdlib> #include<iomanip> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int a[2000001]; int i,j,k,m,n,o,p,js,jl,ma,mb,ii; int main() { FILE *fin,*fout; memset(a,0,sizeof(a)); fin=fopen("cycle.in","rb"); fout=fopen("cycle.out","wb"); fscanf(fin,"%d",&n); for(int iii=1;iii<=n;iii++) { a[iii]=iii; } ma=0; i=2;j=1; for(i=2;i<=n;i++) { mb=ma; js=a[mb+1]; int kk=n/i; for(j=1;j<=kk;j++) { jl=a[mb+i+1]; a[mb+i+1]=js; js=jl; mb=mb+i; } ma=ma++; if(n%i!=0) { a[ma+n]=jl; } } for(ii=n;ii<=n+n-1;ii++)fprintf(fout,"%d ",a[ii]); fclose(fin); fclose(fout); }
