自学内容网 自学内容网
自学内容网 > 正文

ABC370：Cross Explosion（数据结构，模拟）

🕗 发布于 2024-09-27 23:55 数据结构  

题目

有一个网格，网格中有 HH 行和 WW 列。让 (i,j)(i,j) 表示从上往下第 ii 行和从左往上第 jj 列的单元格。
最初，每个单元格中都有一面墙。
按照下面给出的顺序处理 QQ 个查询后，求剩余墙的数量。

在 qq -th 查询中，我们给出了两个整数 RqRq​ 和 CqCq​ 。
你在 (Rq,Cq)(Rq​,Cq​) 处放置了一枚炸弹来摧毁墙壁。结果发生了以下过程。

  • 如果 (Rq,Cq)(Rq​,Cq​) 处有墙壁，则摧毁该墙壁并结束进程。
  • 如果{2227765}处没有墙壁，则摧毁从 (Rq,Cq)(Rq​,Cq​) 向上、向下、向左、向右观察时出现的第一面墙壁。更确切地说，以下四个过程是同时进行的：
    • 如果存在一个 i<Rqi<Rq​ ，在所有 i<k<Rqi<k<Rq​ 中， (i,Cq)(i,Cq​) 处有一堵墙，而 (k,Cq)(k,Cq​) 处没有墙，则摧毁 (i,Cq)(i,Cq​) 处的墙。
    • 如果存在一个 i>Rqi>Rq​ ，使得在 (i,Cq)(i,Cq​) 处有一堵墙，而在所有 Rq<k<iRq​<k<i 中，在 (k,Cq)(k,Cq​) 处没有墙，则破坏 (i,Cq)(i,Cq​) 处的墙。
    • 如果存在一个 j<Cqj<Cq​ ，使得在 (Rq,j)(Rq​,j) 处有一堵墙，而在 (Rq,k)(Rq​,k) 处没有墙，且所有的 j<k<Cqj<k<Cq​ 都是如此，则破坏 (Rq,j)(Rq​,j) 处的墙。
    • 如果存在一个 j>Cqj>Cq​ ，使得在 (Rq,j)(Rq​,j) 处有一堵墙，而在所有 Cq<k<jCq​<k<j 的 (Rq,k)(Rq​,k) 处都没有墙，则摧毁 (Rq,j)(Rq​,j) 处的墙。

限制因素

  • 1≤H,W1≤H,W
  • H×W≤4×105H×W≤4×105
  • 1≤Q≤2×1051≤Q≤2×105
  • 1≤Rq≤H1≤Rq​≤H
  • 1≤Cq≤W1≤Cq​≤W
  • 所有输入值均为整数

做法

行和列进行模拟。

这是我用vector写的，又臭又长，还超时了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int n,m,q;
vector<int> h[N],l[N];
unordered_map<int,int> mp;
int ans;
signed main(){
scanf("%lld%lld%lld",&n,&m,&q);
ans=n*m;
vector<vector<int> > a(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
h[i].push_back(j);
l[j].push_back(i);
}
}
while(q--){
int x,y;
scanf("%lld%lld",&x,&y);
x--,y--;
if(!mp[x*m+y]) {//没销毁 
ans--;
mp[x*m+y]=1;
int id1=lower_bound(l[y].begin(),l[y].end(),x)-l[y].begin();//删除行 
int id2=lower_bound(h[x].begin(),h[x].end(),y)-h[x].begin();//删除列 
l[y].erase(l[y].begin()+id1);
h[x].erase(h[x].begin()+id2);
continue;
}

int id1=upper_bound(l[y].begin(),l[y].end(),x)-l[y].begin();//删除行 
if(id1>0&&id1<l[y].size()) {//上 
mp[l[y][id1-1]*m+y]=1;
int id=lower_bound(h[l[y][id1-1]].begin(),h[l[y][id1-1]].end(),y)-h[l[y][id1-1]].begin();
h[l[y][id1-1]].erase(h[l[y][id1-1]].begin()+id); 
l[y].erase(l[y].begin()+id1-1);
ans--;
}
else if(l[y].size()>0&&id1==l[y].size()){
int yy=l[y].size()-1;
mp[l[y][yy]*m+y]=1;
int id=lower_bound(h[l[y][yy]].begin(),h[l[y][yy]].end(),y)-h[l[y][yy]].begin();
h[l[y][yy]].erase(h[l[y][yy]].begin()+id); 
l[y].erase(l[y].begin()+yy);
ans--;
}


id1=upper_bound(l[y].begin(),l[y].end(),x)-l[y].begin();//删除行 
if(id1<n-1&&id1<l[y].size()){//下 
mp[l[y][id1]*m+y]=1;
int id=lower_bound(h[l[y][id1]].begin(),h[l[y][id1]].end(),y)-h[l[y][id1]].begin();
h[l[y][id1]].erase(h[l[y][id1]].begin()+id); 
l[y].erase(l[y].begin()+id1);
ans--;
}

int id2=upper_bound(h[x].begin(),h[x].end(),y)-h[x].begin();//删除列 
if(id2>0&&id2<h[x].size()){//左 
mp[x*m+h[x][id2-1]]=1;
int id=lower_bound(l[h[x][id2-1]].begin(),l[h[x][id2-1]].end(),x)-l[h[x][id2-1]].begin();
l[h[x][id2-1]].erase(l[h[x][id2-1]].begin()+id);
h[x].erase(h[x].begin()+id2-1);
ans--;
}
else if(h[x].size()>0&&id2==h[x].size()){
int yy=h[x].size()-1;
mp[x*m+h[x][yy]]=1;
int id=lower_bound(l[h[x][yy]].begin(),l[h[x][yy]].end(),x)-l[h[x][yy]].begin();
l[h[x][yy]].erase(l[h[x][yy]].begin()+id);
h[x].erase(h[x].begin()+yy);
ans--;
}

id2=upper_bound(h[x].begin(),h[x].end(),y)-h[x].begin();
if(id2<m-1&&id2<h[x].size()){//右 
mp[x*m+h[x][id2]]=1;
int id=lower_bound(l[h[x][id2]].begin(),l[h[x][id2]].end(),x)-l[h[x][id2]].begin();
l[h[x][id2]].erase(l[h[x][id2]].begin()+id);
h[x].erase(h[x].begin()+id2);
ans--;
}

}
cout<<ans; 
}

这是题解的做法，用set模拟，代码短多了，而且set的迭代器操作很方便。例如prev，还有set的删除操作erase可以直接删值，而不用下标。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n,m,q;
set<int> h[N],l[N];
int ans;
signed main(){
scanf("%d%d%d",&n,&m,&q);
ans=n*m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
h[i].insert(j);
l[j].insert(i);
}
}

while(q--){

int x,y;
scanf("%d%d",&x,&y);
x--,y--;

if(h[x].count(y)) {//没销毁 
ans--;
l[y].erase(x);
h[x].erase(y);
continue;
}

auto id=l[y].upper_bound(x);
if(id!=l[y].begin()) {//上 
ans--;
h[*prev(id)].erase(y);
l[y].erase(*prev(id));
}

id=l[y].upper_bound(x);
if(id!=end(l[y])){//下 
ans--;
h[*id].erase(y);
l[y].erase(*id);
}

id=h[x].upper_bound(y);
if(id!=begin(h[x])){//左 
ans--;
l[*prev(id)].erase(x);
h[x].erase(*prev(id));

}

id=h[x].upper_bound(y);
if(id!=end(h[x])){//右 
ans--;
l[*id].erase(x);
h[x].erase(*id);
}

}

cout<<ans; 
}


原文地址：https://blog.csdn.net/2301_80718054/article/details/142487224

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024