当前位置:网站首页>CF1534F2-Falling Sand (Hard Version)
CF1534F2-Falling Sand (Hard Version)
2022-08-10 23:38:00 【QuantAsk】
正题
题目链接:https://www.luogu.com.cn/problem/CF1534F2
题目大意
有一个 n ∗ m n*m n∗m个网格,有的网格上有沙子,一个沙子被刷新后会下落到底并且刷新沿途中四周四连通的沙子,你可以选择一些沙子手动刷新。
现在要求第 i i i列至少有 a i a_i ai个沙子下落,求至少手动刷新多少个沙子。
1 ≤ n × m ≤ 4 × 1 0 5 1\leq n\times m\leq 4\times 10^5 1≤n×m≤4×105
解题思路
显然列要求的 a i a_i ai就是要求最下面的那 a i a_i ai个沙子被刷新。
手动刷新的肯定都是每一列位置最高的沙子,然后刷新关系可以表示成一张有向图,而且是平面图,那么就说明一个沙子被刷新的条件是手动刷新了某个区间中位置最高的沙子。
我们考虑求出这些区间,先建边,这样最多 4 n m 4nm 4nm条边,然后对于每个沙子要求区间的左端点我们从左往右从最高的沙子开始跑,然后每次走到的点标记删除,右区间就变成从右往左跑。
得到这些区间后我们转换成若干个形如区间 [ l , r ] [l,r] [l,r]中必须要有一个 1 1 1的限制,然后考虑 d p dp dp,用单调队列优化一下即可。
时间复杂度: O ( n m ) O(nm) O(nm)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define p(x,y) ((((x)-1)*n)+(y))
using namespace std;
const int N=8e5+10;
struct node{
int to,next;
}a[N*4];
int n,m,tot,ls[N],l[N],r[N],lim[N],f[N];
deque<int> q;vector<int> v[N];char s[N];
void addl(int x,int y){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;return;
}
void dfsl(int x){
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(l[y])continue;
l[y]=l[x];dfsl(y);
}
return;
}
void dfsr(int x){
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(r[y])continue;
r[y]=r[x];dfsr(y);
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++)
if(s[j]=='#')
v[j].push_back(n-i+1);
}
for(int i=1;i<=m;i++){
if(v[i].empty())continue;
for(int j=0;j<v[i].size()-1;j++){
addl(p(i,v[i][j]),p(i,v[i][j+1]));
if(v[i][j+1]+1==v[i][j])addl(p(i,v[i][j+1]),p(i,v[i][j]));
}
for(int g=-1;g<2;g++){
if(!g||!v[i+g].size())continue;
int z=0,_=0;
while(z<v[i+g].size()&&v[i+g][z]>v[i][0])z++;
for(int h=v[i][0];h>=1;h--){
if(_<v[i].size()-1&&h==v[i][_+1])_++;
if(z<v[i+g].size()&&h==v[i+g][z])
addl(p(i,v[i][_]),p(i+g,v[i+g][z])),z++;
}
}
}
for(int i=1;i<=m;i++){
if(v[i].empty())continue;
int x=p(i,v[i][0]);
if(!l[x])l[x]=i,dfsl(x);
}
for(int i=m;i>=1;i--){
if(v[i].empty())continue;
int x=p(i,v[i][0]);
if(!r[x])r[x]=i,dfsr(x);
}
for(int i=1,x;i<=m;i++){
scanf("%d",&x);
for(int j=v[i].size()-1;j>=(int)v[i].size()-x;j--)
{
int y=p(i,v[i][j]);lim[r[y]]=max(lim[r[y]],l[y]);}
}
q.push_back(0);
for(int i=1;i<=m;i++){
f[i]=max(f[i],f[q.front()]+1);
while(!q.empty()&&f[q.back()]>=f[i])q.pop_back();
q.push_back(i);
while(!q.empty()&&q.front()<lim[i])q.pop_front();
}
printf("%d\n",f[q.front()]);
return 0;
}
边栏推荐
猜你喜欢
14. Thymeleaf
开启新征程——枫叶先生第一篇博客
15. 拦截器-HandlerInterceptor
String
Easy-to-use translation plug-in - one-click automatic translation plug-in software
[C language] Implementation of guessing number game
3. 容器功能
卷积神经网络CNN详细介绍
[C Language Chapter] Detailed explanation of bitwise operators (“<<”, “>>”, “&”, “|”, “^”, “~”)
阿里P7晒出1月工资单:狠补了这个,真香...
随机推荐
好用的翻译插件-一键自动翻译插件软件
C language% (%d,%c...)
Deep Learning Transformer Architecture Analysis
【C语言】二分查找(折半查找)
[C Language Chapter] Detailed explanation of bitwise operators (“<<”, “>>”, “&”, “|”, “^”, “~”)
Kioptrix Level 1 靶机wp
sqlmap结合dnslog快速注入
jsp中使用JDBC连接mysql的方法与实例
Promise in detail
2.0966 铝青铜板CuAl10Ni5Fe4铜棒
[C language] Implementation of guessing number game
excel英文自动翻译成中文教程
9. Rest style request processing
How to quickly grasp industry opportunities and introduce new ones more efficiently is an important proposition
How to recover deleted files from the recycle bin, two methods of recovering files from the recycle bin
【C语言篇】表达式求值(隐式类型转换,算术转换)
C语言%(%d,%c...)
图片懒加载(纯手写)
【C语言篇】操作符之 位运算符详解(“ << ”,“ >> ”,“ & ”,“ | ”,“ ^ ”,“ ~ ”)
Is there a way out in the testing industry if it is purely business testing?