【题解】Atcoder AGC 006D Median Pyramid Hard

Problem

给定一个金字塔的第 $n$ 层的 $2n-1$ 个数,每一层每个位置上的数是下一层下方的三个数的中位数

求第一层的的数

Thought

我们发现,对于一个排列求中位数非常的麻烦,这就要求你计算出每一层的每一个数
但是如果将其转化为 $01$ 序列,由于中位数的性质,可以大大简化中间过程

那么考虑二分答案,转化为一个判定性问题:将小于答案的设为 $0$ ,大于等于答案的设为 $1$,最后仅需要判断顶部位置的数为 $0$ 还是为 $1$

答案就是使得顶部为 $1$ 的最大数字

考虑一个 $01$ 序列如何向上转移,假设当前序列为 $011001101$

最后的形态大概是:

$$ 0\\ 001\\ 10011\\ 1100111\\ 011001101 $$

发现连续的 $1$ 的上方仍然是连续的 $1$,连续的 $0$ 的上方仍然是连续的 $0$
而在形似于 $10101$ 或者 $01010$ 将会取反(左侧第一个点必须和左端点异色,右侧同理)

那么分隔开 $10101$ 或者 $01010$ 这样的序列的必然是一些 $000$ 或者 $111$ ,其取反相当于给两侧的连续段长度分别增加 $1$

只需要考虑在序列 $n$ 位置是形似于 $10101$ 或者 $01010$ 的段还是形似于 $000$ , $111$ 的段
后者直接输出答案,前者的答案就是其左右离得最近的连续数字段,如果没有答案就是该点取反 $n-1$ 次的结果

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
#define mid ((l + r) >> 1)
int n, a[N << 1];
bool vis[N << 1];
bool p[N << 1];
bool check(int x) {
    memset(p, 0, sizeof(p));
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i < 2 * n; ++ i) {
        if(a[i] < x) vis[i] = 0;
        else vis[i] = 1;
        if(i - 1 && vis[i] == vis[i - 1])
            p[i - 1] = p[i] = 1;
    }
    int dis = n, col = 0;
    if(p[n]) return vis[n];
    else {
        for(int i = n - 1; i; -- i)
            if(p[i]) {
                dis = n - i;
                col = vis[i];
                break;
            }
        for(int i = n + 1; i < 2 * n; ++ i) {
            if(p[i]) {
                if(i - n < dis) {
                    dis = i - n;
                    col = vis[i];
                }
                break;
            }
        }
        if(dis == n) return vis[n] ^ ((n - 1) % 2);
        else return col;
    }
}
int main() {
    n = read();
    for(int i = 1; i < 2 * n; ++ i)
        a[i] = read();
    int l = 1, r = n * 2 - 1, ans;
    while(l <= r) {
        if(check(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}
Comments

添加新评论