题解：P12148 【MX-X11-T2】「蓬莱人形 Round 1」所以我放弃了音乐

· · 题解

赛时为了更高的分，所以我放弃了 T1，因为 70 分仅此而已，就已经足够了。

题意：

大概就是一个点可以向 (x+1,y+1)，(x+1,y)，(x+1,y-1) 这几个方向拓展，使得拓展到的点不用在进行一次操作，若没有，则不再拓展。

思路：

首先我们看数据范围，对于所有的测试数据，满足 1\le n\le 10^6，1\le x_i,y_i\le 10^6。
建图就不用想了，但 n 是 10^6，所以思路肯定是往 \mathcal{O}(n\log_2n) 的方向想的，如果有更优的就是我太唐了。
我的方法就是记录可以到 i 点的个数，若为 0 那就无法从别的点拓展到此处，必须增加一次操作，如果有那么至多三个，一定是优先取横坐标小的，因为每个点只能拓展一次，而取横坐标小的，就可以保证可拓展到下一个点的点尽可能多。

实现：

把所有节点坐标记录，按照横坐标为主关键字，纵坐标为副关键字，从小到大排序，把所有坐标用 map 记录，坐标对应这是哪个点，因为保证没有两个位置相同的棋子。
按照思路中的贪心策略，记录答案，输出即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0 ,f = 1;
    char ch = getchar();
    while('0' > ch || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch & 15);
        ch = getchar();
    }
    return x * f;
}
const int N = 1e6 + 5;
int n ,ans = 0;
int yclx[5] = {1 ,1 ,1} ,ycly[5] = {1 ,0 ,-1} ,zt[N];
pair<int ,int> a[N];
bool vis[N];
map<pair<int ,int> ,int> st;
queue<int>que; 
signed main() {
    n = read();
    for(int i = 1;i <= n;++ i)
        a[i].first = read() ,a[i].second = read();
    sort(a + 1 ,a + n + 1);
    for(int i = 1;i <= n;++ i)st.insert(make_pair(a[i] ,i));
    for(int i = 1;i <= n;++ i)
        zt[i] = ((st[make_pair(a[i].first - 1 ,a[i].second - 1)] != 0) + (st[make_pair(a[i].first - 1 ,a[i].second)] != 0) + (st[make_pair(a[i].first - 1 ,a[i].second + 1)] != 0));
    for(int i = 1;i <= n;++ i) {

        if(zt[i] == 0)vis[i] = true ,++ ans;
    }
    for(int i = 1;i <= n;++ i) {
        if(!vis[i]) {
            if(vis[st[make_pair(a[i].first - 1 ,a[i].second - 1)]]) vis[st[make_pair(a[i].first - 1 ,a[i].second - 1)]] = 0;
            else if(vis[st[make_pair(a[i].first - 1 ,a[i].second)]]) vis[st[make_pair(a[i].first - 1 ,a[i].second)]] = 0;
            else if(vis[st[make_pair(a[i].first - 1 ,a[i].second + 1)]]) vis[st[make_pair(a[i].first - 1 ,a[i].second + 1)]] = 0;
            else ++ ans;
            vis[i] = true;
        }
    }
    cout << ans;
    return 0;
}
好不容易拿了 47 名，并写了题解，求过