数列变换 (Standard IO)
Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits
Time to Submit: 01:59:36
Description
小X 看到堆成山的数列作业十分头疼，希望聪明的你来帮帮他。考虑数列A=[A1,A2,...,An],定义变换f(A,k)=[A2,A3,,,,.Ak,A1,Ak+2,Ak+3,,,,A2k,Ak+1,...]，也就是把a 分段，每段k 个（最后如果不足k 个，全部分到新的一段里，见样例），然后将每段的第一个移动到该段的最后一个。
现在，小 X想知道 f (f (f (f ([1,2,3,⋯,n],2),3),⋯),n)的结果。
Input
输入一行包含一个整数n 。
Output
输出一行包含n 个整数，表示最终的数列。
Sample Input
4
Sample Output
4 2 3 1
【样例说明】
f ([1,2,3,4],2) = [2,1,4,3]
f ([2,1,4,3],3) = [1,4,2,3]（3单独被分在一组，移动到组的最后一位，仍然是3）
f ([1,4,2,3],4) = [4,2,3,1]
Data Constraint
对于60%的数据，1≤ n ≤10^3。
对于100%的数据，1≤ n ≤10^6。
分析题意
在考场上分析这道题题意耗了半天时间。简单来说，是对数列{1,2,3...,n-1,n}进行n次操作，每次进行分段，第i次操作每段有i个数（末尾的自成一段），将每段的第一个数放到末尾。
这道题实际就是模拟，难点在于如何进行操作。
一、六十分暴力
根据题意直接暴力即可。
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 7; int n; int num[MAXN]; void test() { for(register int i = 1; i <= n; ++i) { cerr<<num[i]<<' '; } cerr<<endl; } inline void change(int x) { register int tmp = num[1]; for(register int i = 1; i <= n - n % x; ++i) { if( i % x == 0) { num[i] = tmp; tmp = num[i+1]; } else { num[i] = num[i+1]; } } if(n % x != 0) { tmp = num[n - n % x + 1]; for(register int i = n - n % x + 1; i <= n - 1; ++i) { num[i] = num[i + 1]; } num[n] = tmp; } } int main() { #ifdef lky233 freopen("testdata.in","r",stdin); freopen("testdata_5.out","w",stdout); #endif int tim = clock(); n = 100000; for(register int i = 1; i <= n; ++i) num[i] = i; for(register int i = 1; i <= n; ++i) { change(i); #ifdef lky233 if(i % 1000 == 0) cerr<<i<<endl; if(i % 10000 == 0) cerr<<"C"<<i,cerr<<"using time "<<clock() - tim<<"ms."<<endl; #endif } printf("0,"); for(register int i = 1; i <= n; ++i) printf("%d,",num[i]); #ifdef lky233 cerr<<"using time "<<clock() - tim<<"ms."<<endl; #endif }
本来考场上用这个打表来着，但是空间不够。
后来打算把1e5,1e6这个肯定会有的数据打过去，然而1e6跑了半个小时才跑了一半（纪中的垃圾机子），后来去了一趟wc机子跪了。。。
提交的时候发现1e5的数据太多提示CE。
果然投机取巧会被制裁。
二、八十分做法
这里使用memcpy极大缩短数组复制所需时间，可以卡常拿到80分。
三、正确做法
我们会发现之前的暴力有很多无用的操作，就是将这一段并未进行操作的数copy到前面。那么我们可以考虑将进行操作的数后移，时间复杂度为O(nlogn)。
比如{1,2,3,4,5,6} --> {0,2,1,4,3,6,5},这个1放到原先3的位置，3放到原先5的位置，以此类推。
在实际运算时，用一个head数记录当前数列开头在数组的哪个位置，其余正常操作。
#include<bits/stdc++.h> using namespace std; const int MAXN = 2e6 + 7; int num[MAXN]; int n; int head; void test() { #ifdef lky233 for(register int i = 1; i <= head + n; ++i) cerr<<num[i]; cerr<<endl; #endif } void move(int x) { int tmp_1 = num[head],tmp_2; for(register int i = head + x ; i <= n + head - 1;i+=x) { tmp_2 = num[i]; num[i] = tmp_1; tmp_1 = tmp_2; test(); } num[n + head] = tmp_1; } int main() { cin>>n; for(register int i = 1; i <= n; ++i) num[i] = i; for(register int i = 2; i <= n; ++i) { ++head; move(i); test(); } ++head; for(register int i = head; i <= head + n - 1; ++i) cout<<num[i]<<' '; }
OK这道模拟就用一点技巧过了。