题目大意:给一个正整数n,构造一个0...n-1的排列,使得这个排列的任何一个长度大于2的子序列都不为等差数列。
把序列按照奇偶位置分成两个序列,这样在两个序列间就不会形成等差数列了,然后再对这两个序列进行分解,直到序列的长度小于3。
刚开始把 arithmetic progression 理解错了,以为是单调序列,后来感觉不对劲,发现原来是等差序列,可是还是不会...只好搜解题思路了,然后根据别人的思路写代码。有时写代码也会碰到困难,不知道该怎么写,就只能再参考别人代码了,这样...唉,不多说了
1 #include <cstdio> 2 #define MAXN 10000+10 3 4 int a[MAXN], tmp[MAXN]; 5 6 void divide(int low, int high) 7 { 8 if (high - low < 3) return; 9 int p = 0; 10 for (int i = low; i < high; i += 2) 11 tmp[p++] = a[i]; 12 for (int i = low+1; i < high; i += 2) 13 tmp[p++] = a[i]; 14 for (int i = 0; i < p; i++) 15 a[low+i] = tmp[i]; 16 int mid = (low + high - 1) / 2; 17 divide(low, mid+1); 18 divide(mid+1, high); 19 } 20 21 int main() 22 { 23 #ifdef LOCAL 24 freopen("in", "r", stdin); 25 #endif 26 int n; 27 while (scanf("%d", &n) != EOF && n) 28 { 29 for (int i = 0; i < n; i++) 30 a[i] = i; 31 divide(0, n); 32 printf("%d:", n); 33 for (int i = 0; i < n; i++) 34 printf(" %d", a[i]); 35 printf(" "); 36 } 37 return 0; 38 }