uva-11129-分治-白红宇

uva-11129-分治

阅读量：5862 次

发布时间：2019-06-19

本文共 1527 字，大约阅读时间需要 5 分钟。

　　题意：对于一个0-(N-1)的等差数列，求其中一个排列Q，使得任意0<=i,j,k<n 时,ai,aj,ak不是等差数列.

解法:考虑0-(N-1)这个等差数列,假设公差为K,那么数列如下

A0+0K,A0+1K,A0+2K,A0+3K..........+A0+(N-1)K.

如果我们把A0+OK,A0+2K,A0+4K.......组成一个等差数列Q,这个等差数列的公差为2K.

同理，把A0+1K,A0+3K,A0+5K+........组成一个等差数列R,这个等差数列的公差为2K,让R排在Q的后面.这样，从Q中选取俩个,从R中选取一个组成ai,aj,ak,都不会组成等差数列.

#include 
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    namespace cc{ using std::cout; using std::endl; using std::cin; using std::map; using std::vector; using std::string; using std::sort; using std::priority_queue; using std::greater; using std::vector; using std::swap; using std::stack; using std::bitset; constexpr int N = 10010; int a[N]; int aa[N]; void init(int n) { for (int i = 0;i < n;i++) a[i] = i; } void dfs(int s, int e) { if (s >= e - 2) return; for (int i = s;i < e;i++) { aa[i] = a[i]; } int ss = s; for (int j = s;j < e;j += 2) a[ss++] = aa[j]; int next = ss; for (int j = s + 1;j < e;j += 2) a[ss++] = aa[j]; dfs(s, next); dfs(next, e); } void solve() { int n; while (cin >> n && n) { init(n); dfs(0,n); cout << n << ":"; for (int i = 0;i < n;i++) cout << " " << a[i]; cout << endl; } }};int main(){#ifndef ONLINE_JUDGE freopen("d://1.text", "r", stdin);#endif // !ONLINE_JUDGE cc::solve(); return 0;}