C1-I

题目要求

2^n个正整数从第一个开始与相邻数比较，大的进入下一轮比较，小的被淘汰，重复比n轮，计算每个编号下的数据在比较过程中遇到的最大的数

核心算法与思路

• 每轮比较的胜者放在下一个数组（下一块空间）下继续比较。开一块∑2^i (i from 0 to n)的数组来装每轮的胜者数据（前2^n个数据装原始数据）

• 维护数据：每次比两个，更新遇到的最大数，然后胜者装到这一轮末尾之后的i / 2块空间里，比完这一轮再比下一轮（更新赛区初始位置start，赛区容量delta）

• 细节：由于需要记录那个赛区位置上的数据编号，故需要一个∑2^i (i from 0 to n)的数组来装赛区每个位置对应数据的原始编号

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXBOUND = 1048576;

int ll[MAXBOUND + 1];  //ll[idx]表示这个位置的小猫的原始编号
int maxF[262145]; //maxF[idx]表示这个位置的小猫遇到最强的实力值
int p[MAXBOUND + 1];    //p[i][j]表示第i组数据的编号为j(或者等价于某个原始编号)的小猫实力值

long long fpm(long long a, long long b);
int main(){
    int tt, n;
    cin >> tt;
    while(tt--){
        cin >> n;
        int nn = fpm(2, n);
        for(int i = 1; i <= nn; i++){
            cin >> p[i];
            ll[i] = i;
            maxF[i] = 0;
        }

        int start = 1;
        int delta = nn;
        for(int i = 0; i < n; i++){
            for(int j = start; j < start + delta; j += 2){
                if(p[j] > p[j + 1]){
                    p[(j - start)/2 + delta + start] = p[j];
                    //谁获胜，(start + delta) + (j - start) / 2的位置（下一个赛区对应的位置）就是谁的实力值（除以二是因为下一轮比较只有这么点人，少一点）
                    ll[(j - start)/2 + delta + start] = ll[j];
                }else{
                    p[(j - start)/2 + delta + start] = p[j + 1];
                    ll[(j - start)/2 + delta + start] = ll[j + 1];
                }

                //更新最强实力
                if(maxF[ll[j]] < p[j + 1]){
                    maxF[ll[j]] = p[j + 1];
                }

                if(maxF[ll[j + 1]] < p[j]){
                    maxF[ll[j + 1]] = p[j];
                }
            }
            start += delta;
            delta /= 2;
        }

        for(int i = 1; i <= nn; i++){
            cout << maxF[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

long long fpm(long long a, long long b) {
    long long ans = 1;
    for ( ; b; b >>= 1, a = a * a)
        if (b & 1) ans = ans * a;
    return ans;
}