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

· · 题解

赛时想抢首杀，第一个开的就是这题。

然后爆炸了，先去写了其他题转回来才发现自己糖成啥了。

最左端显然必须消耗操作，然后就是从下往上遍历会劣于从上往下遍历。

因为当前列最下面的点能消的较低点上面一定消不掉，但如果从它开始，它会锁定到上面可能能消的点，那这样上面的贡献就被挤掉了。

于是你像我一样对每一列写了个可删堆模拟每次操作发现挂了。

考虑这么一张图：

...@
.@@.
.@..
@.@.

@ 表示棋子，. 表示空地。

我们的做法：

...1
.21.
.1..
1.3.

答案为 3。

正解：

...1
.11.
.2..
2.2.

答案为 2。

这启示我们对于每一个棋子进行转移而不是直接模拟。

从左到右从上到下的枚举棋子，然后从能抵达它并且未使用的棋子中取最上面的点进行转移。

无法转移的计入答案。

然后你会发现做完了，时间复杂度综合 O(n \log n)，瓶颈在于排序。

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>ve[1000005];
map<int,bool>mp[1000005];
bool cmp(int a,int b){
    return a>b;
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        mp[u][v]=1;
        ve[u].push_back(v);
    }
    int ans=0;
    for(int i=1;i<=1000000;i++){
        if(ve[i].size()==0)continue;
        sort(ve[i].begin(),ve[i].end(),cmp);
        for(int j=0;j<ve[i].size();j++){
            if(mp[i-1][ve[i][j]+1])mp[i-1][ve[i][j]+1]=0;
            else if(mp[i-1][ve[i][j]])mp[i-1][ve[i][j]]=0;
            else if(mp[i-1][ve[i][j]-1])mp[i-1][ve[i][j]-1]=0;
            else ans++;
        }
    }
    cout<<ans;
    return 0;
}