UVa 11129 - An antiarithmetic permutation

　　题目大意：给一个正整数n，构造一个0...n-1的排列，使得这个排列的任何一个长度大于2的子序列都不为等差数列。

　　把序列按照奇偶位置分成两个序列，这样在两个序列间就不会形成等差数列了，然后再对这两个序列进行分解，直到序列的长度小于3。

　　刚开始把 arithmetic progression 理解错了，以为是单调序列，后来感觉不对劲，发现原来是等差序列，可是还是不会...只好搜解题思路了，然后根据别人的思路写代码。有时写代码也会碰到困难，不知道该怎么写，就只能再参考别人代码了，这样...唉，不多说了

 #include <cstdio>

 #define MAXN 10000+10

 int a[MAXN], tmp[MAXN];

 void divide(int low, int high)

 {

     if (high - low < )   return;

     int p = ;

     for (int i = low; i < high; i += )

         tmp[p++] = a[i];

     for (int i = low+; i < high; i += )

         tmp[p++] = a[i];

     for (int i = ; i < p; i++)

         a[low+i] = tmp[i];

     int mid = (low + high - ) / ;

     divide(low, mid+);

     divide(mid+, high);

 }

 int main()

 {

 #ifdef LOCAL

     freopen("in", "r", stdin);

 #endif

     int n;

     while (scanf("%d", &n) != EOF && n)

     {

         for (int i = ; i < n; i++)

             a[i] = i;

         divide(, n);

         printf("%d:", n);

         for (int i = ; i < n; i++)

             printf(" %d", a[i]);

         printf("\n");

     }

     return ;

 }

巴特西

UVa 11129 - An antiarithmetic permutation

最新文章

热门文章