[AGC006D] Median Pyramid Hard 题解

题目链接：[AGC006D] Median Pyramid Hard

题意：

给出一个 \(N~(1 \le N \le 10^5)\) 层的方格金字塔，自顶向下依次标号为第 \(1\) 到第 \(N\) 层。

其中第 \(i~(1 \le i \le N)\) 层有 \(2i - 1\) 个方格（具体形态见下面的图）

第 \(N\) 层有一个 \(1\) 到 \(2N-1\) 的排列，其他层的数字按以下规则生成：

• 方格 \(b\) 中填写的整数，是方格 \(b\) 正下方、左下方和右下方方格中所写整数的中位数。

现在给出第 \(N\) 层的数字，请你求第一层的数字。

考虑二分最上层这个数 \(\ge x\)，然后令 \(\ge x\) 的数为 \(1\) ，\(<x\) 的的数为 \(0\) 。

那么原题可以转化为，每次操作对于相邻的三个数，

如果 \(1\) 的个数 \(\ge 3\) 则为 \(1\) ，否则为 \(0\) ，最终最上面的那个数是 \(0\) 还是 \(1\) 。

这样问题就变成了 \(0,1\) 序列如何快速判断了，接下来就是找规律了，请参考 link 或者下图

时间复杂度 \(\mathcal{O}(n \log n)\) ，当然这题还有 \(\mathcal{O}(n)\) 的解法，也是基于这一规律的。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))

int n, a[N], b[N];
bool check(int x)
{
    rep(i, 1, n * 2 - 1) b[i] = (a[i] >= x);
    rep(i, 0, n - 2)
    {
        if(b[n + i] == b[n + i + 1]) return b[n + i];
        if(b[n - i] == b[n - i - 1]) return b[n - i];
    } return b[1];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    rep(i, 1, n * 2 - 1) cin >> a[i];
    int l = 1, r = (n << 1) - 1;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        check(mid) ? l = mid : r = mid - 1;
    }
    cout << l << '\n';
    return 0;
}

---

参考文献

就是上面那个link。

---

题外话：

没图片，但是推歌。