uva 11129 - An antiarithmetic permutation

本文主要是介绍uva 11129 - An antiarithmetic permutation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求用1到t-1的数组成的序列在长度大于2的子序列步存在等差数列，把原数列先分成两个数列，分别是S,S+2d,S+4d......和S+d,S+3d,S+5d.....，动手写一下的话会发现如果，我们一直这么分下去，直到个数为2的时候，会发现子数列的差值是它的原数列差值的2倍，而相邻的子数列头和尾差值又是原数列的差值，所以我们细分到长度是2的时候，那么构成的数列的子树列将不会是等差数列，而这种重复的方法就是递归分治

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 10005;int arr[MAXN],temp[MAXN],t;void DO(int l,int r)
{int cur = l;if (l == r)return;for (int i = l; i <= r; i += 2)temp[cur++] = arr[i];for (int i = l + 1; i <= r; i += 2)temp[cur++] = arr[i];for (int i = l; i <= r; i++)arr[i] = temp[i];DO(l,(l+r)/2);DO((l+r)/2+1,r);
}int main()
{while (scanf("%d",&t) != EOF && t){for (int i = 0; i < t; i++)arr[i] = i;DO(0,t-1);printf("%d: %d",t,arr[0]);for (int i = 1; i < t; i++)printf(" %d",arr[i]);printf("\n");}return 0;
}

这篇关于uva 11129 - An antiarithmetic permutation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---