题解：P6844 [CEOI 2019] Building Skyscrapers

· · 题解

打开题解区发现唯一一篇题解出自我校功勋学长，写了 10k 看得我眼花缭乱的，这里给出一个更简洁的代码实现。

注意到要求字典序最大是从 n 到 1 的字典序最大，这与我们常规的对字典序的要求不太一样，是一个提示，暗示我们应该反过来做。

把建造变成拆除，考虑拆除顺序的字典序最大即可。

显然存在方案的充要条件是所有大楼均连通，那么在拆除过程中，一旦发现图不连通，则无解，说明刚才拆错了。

那么一栋大楼能够被删除当且仅当：

考虑这个东西该怎么判。

先判断前者。我们不妨把整张网格图建出来，有尚未被拆除的大楼的点标记为黑点，反之为白点。最外层的白点是可以到达无穷远处的，与可以到达无穷远处的白点四连通的点是可以到达无穷远处的。

可以用并查集来合并，不过其实没必要。因为我们注意到每次将一个黑点变成白点的时候一定只会将至多一个白色连通块合并到能到达无穷远处的连通块上，而不会对其他白色连通块产生影响，每个点的合并次数都是 O(1) 的，所以可以直接暴力合并。

可是这个平面是 10^9 \times 10^9 的，真把图建出来时空都要炸了。不过发现黑点个数只有 n 个，我们可以只添加所有黑点以及黑点周围的 8 个点，这样点数就是 O(n) 级别的了。

然后考虑后者如何判断。无向图动态删点维护连通性，这东西做不了一点。不过好在这道题比较特殊，是在一个网格图上，那么只需要判一下周围八个点的状态即可。

一个点是割点有且只有两种情况：

A*B
A#B
A*B

A*B
*#B
BBB

其中 # 代表这个点，* 代表一个白点，A 和 B 对应两个不同的区域。

如果两个 * 在同一个连通块里，且 A 区域和 B 区域都至少有一个黑点，那么这个 # 是割点。

实际上情况有六种，第一种情况旋转后总共有两种情况，第二种情况旋转后总共有四种情况。我们可以预处理把这六种情况都记录下来，这样在代码实现的其他地方会更加简洁。

注意到每次只有删除的点的周围的八个点的状态可能会变，这确保了我们的操作数是 O(n) 的，可以直接暴力大模拟来解决。

代码实现上的细节可以参考我的代码，写了不到 5k，应该还是比较简洁的。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 114;
const int dx[9] = {0, 1, -1, 0, 0, 1, 1, -1, -1};
const int dy[9] = {0, 0, 0, 1, -1, 1, -1, 1, -1};

struct node
{
    pair <int, int> pos[2];
    vector <pair <int, int> > a;
    vector <pair <int, int> > b;
};
node c[7];

void init()
// 预处理出所有可能成为割点的六种情况
{
    c[1].pos[0] = {1, 0};
    c[1].pos[1] = {0, 1};
    c[1].a.push_back({1, 1});
    c[1].b.push_back({-1, 1});
    c[1].b.push_back({-1, 0});
    c[1].b.push_back({-1, -1});
    c[1].b.push_back({0, -1});
    c[1].b.push_back({1, -1});

    c[2].pos[0] = {1, 0};
    c[2].pos[1] = {0, -1};
    c[2].a.push_back({1, -1});
    c[2].b.push_back({1, 1});
    c[2].b.push_back({0, 1});
    c[2].b.push_back({-1, 1});
    c[2].b.push_back({-1, 0});
    c[2].b.push_back({-1, -1});

    c[3].pos[0] = {-1, 0};
    c[3].pos[1] = {0, 1};
    c[3].a.push_back({-1, 1});
    c[3].b.push_back({1, 1});
    c[3].b.push_back({1, 0});
    c[3].b.push_back({1, -1});
    c[3].b.push_back({0, -1});
    c[3].b.push_back({-1, -1});

    c[4].pos[0] = {-1, 0};
    c[4].pos[1] = {0, -1};
    c[4].a.push_back({-1, -1});
    c[4].b.push_back({-1, 1});
    c[4].b.push_back({0, 1});
    c[4].b.push_back({1, 1});
    c[4].b.push_back({1, 0});
    c[4].b.push_back({1, -1});

    c[5].pos[0] = {1, 0};
    c[5].pos[1] = {-1, 0};
    c[5].a.push_back({1, 1});
    c[5].a.push_back({0, 1});
    c[5].a.push_back({-1, 1});
    c[5].b.push_back({1, -1});
    c[5].b.push_back({0, -1});
    c[5].b.push_back({-1, -1});

    c[6].pos[0] = {0, 1};
    c[6].pos[1] = {0, -1};
    c[6].a.push_back({1, 1});
    c[6].a.push_back({1, 0});
    c[6].a.push_back({1, -1});
    c[6].b.push_back({-1, 1});
    c[6].b.push_back({-1, 0});
    c[6].b.push_back({-1, -1});
}

map <pair <int, int>, int> p, id;
int n, t, cnt;
pair <int, int> pt[N];
bool vis[N];

int tot = 0;

// 首先判断是否有解
void dfs(pair <int, int> x)
{
    if(p[x] == 0 || vis[p[x]])
        return;
    vis[p[x]] = 1;
    tot ++;
    for(int i = 1; i <= 8; i = i + 1)
        dfs({x.first + dx[i], x.second + dy[i]});
}

set <int> s;

int rg;

vector <pair <int, int> > vv;

// 判断一个白点属于哪个白色联通块
void search(pair <int, int> x)
{
    if(p.find(x) == p.end())
        return;
    if(p[x] > 0 || p[x] == rg)
        return;
    vv.push_back(x);
    p[x] = rg;
    for(int i = 1; i <= 4; i = i + 1)
        search({x.first + dx[i], x.second + dy[i]});
}

// 判断一个黑点是否是割点
bool ok(pair <int, int> x, int id)
{
    pair <int, int> r1 = {x.first + c[id].pos[0].first, x.second + c[id].pos[0].second};
    pair <int, int> r2 = {x.first + c[id].pos[1].first, x.second + c[id].pos[1].second};
    int pr1 = p[r1], pr2 = p[r2];
    if(pr1 != pr2 || pr1 > 0)
        return 0;
    bool a = 0;
    for(auto i : c[id].a)
    {
        pair <int, int> rr = {x.first + i.first, x.second + i.second};
        a |= (p[rr] > 0);
    }
    if(a == 0)
        return 0;
    bool b = 0;
    for(auto i : c[id].b)
    {
        pair <int, int> rr = {x.first + i.first, x.second + i.second};
        b |= (p[rr] > 0);
    }
    return b;
}

// 判断一个黑点是否可以被拆除
bool check(int x)
{
    pair <int, int> r = pt[x];
    bool f = 0;
    for(int i = 1; i <= 4; i = i + 1)
        if(p[{r.first + dx[i], r.second + dy[i]}] == -1)
        {
            f = 1;
            break;
        }
    if(f == 0)
        return 0;
    for(int i = 1; i <= 6; i = i + 1)
        if(ok(r, i))
            return 0;
    return 1;
}

vector <int> ans;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> t;
    init();
    for(int i = 1, x, y; i <= n; i = i + 1)
    {
        cin >> x >> y;
        p[{x, y}] = i;
        pt[i] = {x, y};
        for(int k = 1; k <= 8; k = k + 1)
            if(p.find({x + dx[k], y + dy[k]}) == p.end())
                p[{x + dx[k], y + dy[k]}] = 0;
    }
    dfs(pt[1]);
    if(tot < n)
    {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for(auto &i : p)
        if(i.second == 0)
        {
            rg --;
            search(i.first);
        }
    for(int i = 1; i <= n; i = i + 1)
    {
        if(check(i))
            s.insert(i);
    }
    rg = -1;
    while(ans.size() < n)
    {
        vv.clear();
        set <int> :: iterator it = s.end();
        it --;
        int res = *it;
        s.erase(it);
        ans.push_back(res);
        pair <int, int> ndd = pt[res];
        p[ndd] = 0;
        search(ndd);
        for(auto nd : vv)
        {
            for(int i = 1; i <= 8; i = i + 1)
            {
                pair <int, int> rr = {nd.first + dx[i], nd.second + dy[i]};
                int ret = p[rr];
                if(ret > 0)
                {
                    bool f = check(ret);
                    if(f)
                        s.insert(ret);
                    else
                    {
                        if(s.find(ret) != s.end())
                            s.erase(s.find(ret));
                    }
                }
            }
        }
    }
    while(ans.size())
    {
        cout << ans.back() << "\n";
        ans.pop_back();
    }
    return 0;
}