【二次爆炸记·第一弹】Turnir

旧城等待， 2021-11-23 09:40 342阅读 0赞

### 文章目录 ###

*  前言
 *  题目
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例
     *   *  样例输入1
         *  样例输出1
         *  样例输入2
         *  样例输出2
         *  样例输入3
         *  样例输出3
 *  解析
 *   *  模拟
     *   *  Code
     *  结合样例
     *   *  Code

--------------------

# 前言 #

仍然爆炸了，伤心往事不必再提QwQ

还是赶紧切入正题吧。。。

# 题目 #

## 题目描述 ##

年轻的 J o z e f Jozef Jozef得到了一个由 2 N 2^N 2N个正整数组成的集合作为礼物。考虑到 J o z e f Jozef Jozef经常参加足球锦标赛，他决定为这 2 N 2^N 2N个正整数组织一个锦标赛。 数字锦标赛如下图所示。比赛成对进行，两个数字中较高的一个前进到更高级别。比赛的级别用 1 1 1到 N N N之间的数字表示，其中最高的级别用数字0表示。如图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]

由于 J o z e f Jozef Jozef没有时间组织所有的比赛，他想知道，对于集合中的每个数字，在所有的对阵安排中，能达到的最高级别（数字最小的级别）。

## 输入格式 ##

第一行输入包含一个整数 N N N（ 1 ≤ N ≤ 20 1≤N≤20 1≤N≤20）。表示题目中提到的 N N N。 第二行输入包含了 2 N 2^N 2N个正整数 A i Ai Ai（ A i ≤ 1 e 9 Ai≤1e9 Ai≤1e9）。表示集合中 2 N 2^N 2N个正整数。

## 输出格式 ##

输出一行包含 2 N 2^N 2N个整数。其中第 i i i个数表示按照输入的顺序集合中的第 i i i个正整数能达到的最高级别。

## 样例 ##

### 样例输入1 ###

2
    1 4 3 2

### 样例输出1 ###

2 0 1 1

### 样例输入2 ###

4
    5 3 2 6 4 8 7 1 2 4 3 3 6 4 8 1

### 样例输出2 ###

1 2 2 1 1 0 1 3 2 1 2 2 1 1 0 3

### 样例输入3 ###

1
    1 1

### 样例输出3 ###

0 0

# 解析 #

这道题有两种做法，一种就是纯模拟，但是需要构造一下结构，而另一种就是分析样例可得了话说我也分析了样例，怎么就不一样呢QAQ

## 模拟 ##

首先对这一列数字记个下标，然后排序，接下来构建一个深度为 n n n的二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]  
我们可以结合这个图来看，最上层的肯定是 T 0 T0 T0，接下来就是 T 1 、 T 2 … … T1、T2…… T1、T2……从 T 2 T2 T2变成 T 1 T1 T1时，是从两个变成一个，也就是最大的那个，即为第 2 n − n = 2 0 2^\{n-n\}=2^0 2n−n=20大的数，那么剩下的那个是不是就是第 2 n − ( n − 1 ) = 2 1 2^\{n-(n-1)\}=2^1 2n−(n−1)=21大的数。

这么说来， T 1 T1 T1这一层的数，必须是第 2 1 2^1 21大的数，或者这么说：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]  
看左边那个区间，总共有 2 n − 1 2^\{n-1\} 2n−1个数字作比较，右边同样有 2 n − 1 2^\{n-1\} 2n−1个数字作比较，因此贪心的来说，若要让这个数字能够达到更高层，就得把比他大的放在另一边，它自己放在这一边，即如果这个数字是第 2 n − i 2^\{n - i\} 2n−i大的数或者更大，那么他就可以到第 i i i层，否则的话，就考虑下一层。直到它满足条件为止。

### Code ###

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <cstring>
    #include <iostream>
    using namespace std;
    #define reg register
    #define LL long long
    #define INF 0x3f3f3f3f
    
    template<typename T>
    void re (T &x){ 
        x = 0;
        int f = 1;
        char c = getchar ();
        while (c < '0' || c > '9'){ 
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){ 
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
    
    template<typename T>
    void pr (T x){ 
        if (x < 0){ 
            putchar ('-');
            x = ~x + 1;
        }
        if (x / 10) pr (x / 10);
        putchar (x % 10 + 48);
    }
    
    #define N 1 << 20
    
    struct node{ 
        int val, id;
        bool operator < (const node &rhs) const{ 
            return val > rhs.val;
        }
    }a[N + 5];
    int n, sum, ans[N + 5];
    
    int main (){ 
        //freopen ("turnir.in", "r", stdin);
        //freopen ("turnir.out", "w", stdout);
        re (n);
        int m = 1 << n;
        for (int i = 1; i <= m; i++){ 
            re (a[i].val);
            a[i].id = i;
        }
        sort (a + 1, a + 1 + m);
        for (int i = 1; i <= m; i++){ 
    		if (a[i].val == a[i - 1].val)
    			ans[a[i].id] = ans[a[i - 1].id];
    		else if (i == 1)
    			ans[a[i].id] = 0;
    		else{ 
    			int tot = 0;
    			for (int j = 1; j <= n; j++){ 
    				tot += 1 << (n - j);
    				if (tot >= i - 1){ 	//一共有i-1个数字比它大，所以当tot>=i-1时，就说明它能够被包含在第j层这个区间内。可是在它把其他的数字踢掉后，已经没有比它更小的了，所以他只能留在这一层中
    					ans[a[i].id] = j;
    					break;
    				}
    			}
    		}
        }
    	for (int i = 1; i <= m; i++){ 
    		pr (ans[i]);
    		putchar (' ');
    	}
        putchar (10);
        return 0;
    }

## 结合样例 ##

说完了“模拟法”，再来讲讲通过样例 蒙 得出结论法。

有这么一个数据：

3
    10 10 2 8 4 10 1 10

将它排序后变成：

1 2 4 8 10 10 10 10

记录他们现在的下标，这个下标的值开上 l o g 2 log2 log2，就等于它能“爬”几层。

但是如果说有多个相同的值的话，下标要算最后那一个。

因为是结合样例手推得到的结论，所以大家可以算算，证明什么的。。。人家也不会了啦QwQ

### Code ###

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <cstring>
    using namespace std;
    #define reg register
    #define LL long long
    #define INF 0x3f3f3f3f
    
    template<typename T>
    void re (T &x){ 
        x = 0;
        int f = 1;
        char c = getchar ();
        while (c < '0' || c > '9'){ 
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){ 
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
    
    template<typename T>
    void pr (T x){ 
        if (x < 0){ 
            putchar ('-');
            x = ~x + 1;
        }
        if (x / 10) pr (x / 10);
        putchar (x % 10 + 48);
    }
    
    #define N 1 << 20
    
    struct node{ 
        int val, id;
        bool operator < (const node &rhs) const{ 
            return val < rhs.val;
        }
    }a[N + 5];
    int n, sum, ans[N + 5];
    
    
    
    int main (){ 
        //freopen ("turnir.in", "r", stdin);
        //freopen ("turnir.out", "w", stdout);
        re (n);
        int m = 1 << n;
        for (int i = 1; i <= m; i++){ 
            re (a[i].val);
            a[i].id = i;
        }
        sort (a + 1, a + 1 + m);
        /*for (int i = 1; i <= m; i++){ if (a[i].val == a[i - 1].val) ans[a[i].id] = ans[a[i - 1].id]; else if (i == 1) ans[a[i].id] = 0; else{ int tot = 0; for (int j = 1; j <= n; j++){ tot += 1 << (n - j); if (tot >= i - 1){ ans[a[i].id] = j; break; } } } }*/
    	for (int i = 1; i <= m; i++){ 
    		if (a[i].val == a[i - 1].val){ 
    			ans[a[i].id] = ans[a[i - 1].id];
    			continue;
    		}
    		int j = i + 1;
    		while (a[j].val == a[j - 1].val && j <= m)
    			j ++;
    		ans[a[i].id] = n - int (log2(j - 1.0));
    	}
    	for (int i = 1; i <= m; i++){ 
    		pr (ans[i]);
    		putchar (' ');
    	}
        putchar (10);
        return 0;
    }

话说我用log/log会崩掉诶，蒟蒻不知道为什么，只能改成这个了。。。

ans[a[i].id] = n - int (log(j - 1.0) / log(2.0));

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20211122/9710addabc634bcc954dddab1e4f54c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]: /images/20211122/cf520a953264449faa69864f1f8aabee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]: /images/20211122/b0a05418a3014728a7dcda2ddbd8a7fb.png