題目鏈接：點擊查看

題目大意：給出一個 $n?m$ 的矩陣，有 $k$ 個點被 $ban$ 掉了，現在從點 $(1,1)$ 出發，只能向右或向下移動，問可以到達的點有多少個

題目分析：

先做一些定義，定義無法到達的點為“壞點”，可以到達的點為“好點”

雖然 $n?m$ 很大，不能直接 $bfs$，但是單獨的 $n$ 或 $m$ 卻不大，這里我從列入手，考慮相鄰的兩列，假設 $pre$ 為上一列的狀態，現在考慮 $cur$ 的情況。對于第 $cur$ 列的每個“壞點”來說，設其橫坐標為 $x$，我們需要找到第 $pre$ 列中，行區間 $[x+1,n]$ 中的首個“好點”的位置記為 $p$，不難看出，$cur$ 列中的行區間 $[x,p?1]$ 這段都是無法到達的“壞點”。還有一種情況就是 $p$ 不存在，也就是 $pre$ 列的行區間 $[x+1,n]$ 這段都是“壞點”，那么顯然 $cur$ 列中行區間為 $[x,n]$ 的點也是無法到達的

區間修改、區間查找某個數字首次出現的位置，用線段樹很容易就能實現了，時間復雜度 $O(nlo{g}^{2}n)$

需要注意的是，每一列的第 $0$ 行也要視為一個壞點

代碼：

// Problem: Lawn of the Dead // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-6992 // Memory Limit: 262 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; struct Seg {struct Node {int l,r,len,sum,lazy;}tree[N<<2];void pushup(int k) {tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;}void pushdown(int k) {if(tree[k].lazy!=-1) {int lz=tree[k].lazy;tree[k].lazy=-1;tree[k<<1].lazy=tree[k<<1|1].lazy=lz;tree[k<<1].sum=tree[k<<1].len*lz;tree[k<<1|1].sum=tree[k<<1|1].len*lz;}}void build(int k,int l,int r) {tree[k]={l,r,r-l+1,0,-1};if(l==r) {return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l>=l&&tree[k].r<=r) {tree[k].lazy=val;tree[k].sum=tree[k].len*val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k);}int query_sum(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].sum;}pushdown(k);return query_sum(k<<1,l,r)+query_sum(k<<1|1,l,r);}int query(int k,int l,int r) {if(l>r||query_sum(k,l,r)==0) {return -1;}if(tree[k].l==tree[k].r) {return tree[k].l;}pushdown(k);if(query_sum(k<<1,l,r)) {return query(k<<1,l,r);} else {return query(k<<1|1,l,r);}} }t[2]; vector<int>node[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {int n,m,k;read(n),read(m),read(k);for(int i=1;i<=m;i++) {node[i].clear();node[i].push_back(0);}while(k--) {int x,y;scanf("%d%d",&x,&y);node[y].push_back(x);}LL ans=0;t[0].build(1,1,n),t[1].build(1,1,n);sort(node[1].begin(),node[1].end());if(node[1].size()>1) {t[1].update(1,1,node[1][1]-1,1);} else {t[1].update(1,1,n,1);}ans+=t[1].tree[1].sum;for(int i=2;i<=m;i++) {int cur=i&1,pre=cur^1;t[cur].update(1,1,n,1);for(auto it:node[i]) {int p=t[pre].query(1,it+1,n);if(p==-1) {t[cur].update(1,it,n,0);} else {t[cur].update(1,it,p-1,0);}}ans+=t[cur].tree[1].sum;}printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的HDU多校4 - 6992 Lawn of the Dead(线段树+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。