uva 11129 - An antiarithmetic permutation

点击打开链接uva 11129

题目意思：

给定一个初始序列为0 1 2 3 .....n-1;要求找到一个序列能够满足所有的子序列都不能够形成等差序列

解题思路：

1思路：递归+分治
2分析：网上那些神牛是这么说的：把这个序列按照奇偶位置分开成两个序列，然后再对两个序列进行奇偶位置分开......最后得到的数组就是所要的ans，为什么这样可以呢，因为在奇数位置内和偶数位置内等差为2，而两个序列之间为１，所以这样肯定不会构成等差序列。

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXN 10010

int n;
int ans[MAXN] , tmp[MAXN];
/*递归求解*/
void solve(int l , int r) {
    int i , j;
    if(r == l) return;/*只有一个数的时候直接返回*/
    memcpy(tmp , ans , sizeof(ans));/*将ans数组复制给tmp数组*/
    for(i = l , j = l ; i <= r ; i += 2 , j++)/*奇数位置存储*/
        ans[j] = tmp[i];
    for(i = l+1; i <= r ; i += 2 , j++)/*偶数位置存储*/
        ans[j] = tmp[i];
    solve(l , (l+r)/2);/*左半部递归*/
    solve((l+r)/2+1 , r);/*右半部递归*/
}

void output(){
    printf("%d:" , n);
    for(int i = 0 ; i < n ; i++)
        printf(" %d" , ans[i]);
    printf("\n");
}

int main() {
    //freopen("input.txt", "r", stdin);
    while(scanf("%d%*c" , &n) && n){
        for(int i = 0 ; i < n ; i++)/*初始化*/
            ans[i] = i;
        solve(0 , n-1) ; output();
    }
    return 0;
}