CF1534F2 Falling Sand (Hard Version) 题解

题目链接

点击打开链接

题目解法

• 做法1
  一个沙子消失，会带走所有它所在列下面的沙子
  我们记每列从下往上第 \(a_i\) 个沙子为关键点，第 \(i\) 列至少消失 \(a_i\) 个沙子等价于所有关键点都消失
  一个显然的事情是：记一列最上面的沙子为起始点，则我们只会干扰起始点
  第一感觉是找到一个沙子可以干扰的所有起始点，但它并不是一个列上的区间
  但把这个东西反过来，一个沙子能被干扰到的起始点是一个区间
  证明：假设存在 \(i<k<R_i\)（左边部分类似），第 \(i\) 列的关键点不能被第 \(k\) 列的起始点干扰。如果第 \(R_i\) 列的起始点干扰第 \(i\) 列关键点的路径从第 \(k\) 列起始点的上方经过，那么第 \(k\) 列的起始点的起始点上方就有沙子，矛盾；如果路径从下方经过，那么第 \(k\) 列的起始点能干扰第 \(i\) 列的关键点，矛盾。
  不难用 \(dfs\) 求出所有关键点能被干扰到的起始点的区间，现在问题变成有很多区间，我们要选最少的点，使得每个区间中都存在选择的点
  这显然可以按右端点排序之后贪心求出
  时间复杂度 \(O(nm\log m)\)
• 做法2
  沿用 F1 的思路，我们只把关键点缩点，且只需要关注度数为 \(0\) 的点
  根据做法 1 的结论，非关键点能干扰的度数为 \(0\) 的点是一个区间，然后类似做法 1 一样做就好了
  其实两个做法本质是相同的

做法 1 的代码：

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=400010;
int n,m,a[N],L[N],R[N];
bool mp[N];
char str[N];
int ind(int x,int y){ return (x-1)*m+y;}
void dfs1(int x,int y,int col){
    if(L[ind(x,y)]) return;
    L[ind(x,y)]=col;
    if(x<n) dfs1(x+1,y,col);
    if(x>1&&mp[ind(x-1,y)]) dfs1(x-1,y,col);
    if(y>1&&mp[ind(x,y-1)]) dfs1(x,y-1,col);
    if(y<m&&mp[ind(x,y+1)]) dfs1(x,y+1,col);
}
void dfs2(int x,int y,int col){
    if(R[ind(x,y)]) return;
    R[ind(x,y)]=col;
    if(x<n) dfs2(x+1,y,col);
    if(x>1&&mp[ind(x-1,y)]) dfs2(x-1,y,col);
    if(y>1&&mp[ind(x,y-1)]) dfs2(x,y-1,col);
    if(y<m&&mp[ind(x,y+1)]) dfs2(x,y+1,col);
}
pii rng[N];
int main(){
    read(n),read(m);
    F(i,1,n){
        scanf("%s",str+1);
        F(j,1,m) if(str[j]=='#') mp[ind(i,j)]=1;
    }
    F(i,1,m) read(a[i]);
    F(j,1,m) F(i,1,n) if(mp[ind(i,j)]) dfs1(i,j,j);
    DF(j,m,1) F(i,1,n) if(mp[ind(i,j)]) dfs2(i,j,j);
    int cnt=0;
    F(j,1,m) if(a[j])
        DF(i,n,1) if(mp[ind(i,j)])
            if(!(--a[j])){
                rng[++cnt]={R[ind(i,j)],L[ind(i,j)]};
                break;
            }
    sort(rng+1,rng+cnt+1);
    int cur=0,ans=0;
    F(i,1,cnt) if(rng[i].second>cur) ans++,cur=rng[i].first;
    printf("%d\n",ans);
    return 0;
}