Description

為了封印輝之環，古代塞姆利亞大陸的人民在異空間中建造了一座設備塔。
簡單的說，這座設備塔是一個漂浮在異空間中的圓柱體，圓柱體兩頭的圓是計算核心，而側面則是
傳輸信息所用的數據通道，劃分成 N?m 個區塊。
然而，隨著工作的繼續進行，他們希望把側面的一部分區塊也改造成其他模塊。然而，任何時候都
必須保證存在一條數據通道，能從圓柱體的一端通向另一端。
由于無法使用輝之環掌控下的計算系統，他們尋求你的幫助來解決這個問題。他們將逐個輸入想要
改造的區域，而你則執行所有可行的改造并忽略可能導致數據中斷的改造。

Input

第一行，包含兩個整數 N;M;K，表示側面的長和寬，以及操作數。
接下來K 行，每行包含三個整數 xi;yi ，表示操作的區塊的坐標。
數據保證不會對已經操作成功的區塊進行操作。

Output

輸出一行，表示有多少個操作可以被執行。

Sample Input

3 4 9
2 2
3 2
2 3
3 4
3 1
1 3
2 1
1 1
1 4

Sample Output

6

Data Constraint

? 對于分值為30 的子任務1，保證 N;M<=100;K<=5000
? 對于分值為30 的子任務2，保證 N;M<=3000;K<=5000
? 對于分值為40 的子任務3，保證 N;M<=3000;K<=300000。

Hint

Solution

• 這道題是一道神奇的模擬題！！！

• 很容易想到的普通暴力枚舉在這個超大范圍下也無能為力~

• 這里有一個利用并查集的巧妙方法

• 首先，注意到路徑可以橫跨左右邊界

• 所以，把這個圖向右復制一份，即 長*2 ，點都雙份處理

• 每一個點（編號排成一列地處理）與八連通的點進行并查集

• 那么如何判斷加點時，所構成的聯通快有沒有橫向封蓋呢？

• 于是設一個標記數組，記號可以設為數據編號這種獨一無二的號碼

• 將要加入的點在左邊地圖里的八連通點，這些點的父親編號在標記數組里賦值

• 然后在右邊地圖里的八連通點的父親編號在標記數組里查詢

• 如果已賦值，說明加入的話會構成橫向封蓋，則不能加入！

• 這樣，我們就能方便的判斷，省去了在并查集數組里加加刪刪的麻煩！

• 這樣巧妙地運用并查集，使時間復雜度降到了 O(K) 再加一些常數！！！

Code

#include<cstdio> using namespace std; const int N=3001,M=2*N*N; const int way[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{-1,1},{-1,-1},{1,-1}}; int n,m,cnt,ans; int f[M],g[M]; bool bz[M]; bool pd; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } inline int get(int x,int y){return (x-1)*2*m+y;} inline int find(int x){return (f[x]==x)?x:f[x]=find(f[x]);} inline void work(int x,int y) {int p=get(x,y);bz[p]=true;for(int i=0;i<8;i++){int xx=x+way[i][0],yy=y+way[i][1];if(!xx || xx>n) continue;if(!yy) yy+=2*m; else if(yy>2*m) yy-=2*m;int q=get(xx,yy);if(bz[q]){int f1=find(p),f2=find(q);if(f1!=f2) f[f1]=f2;} } } int main() {n=read(),m=read(),cnt=get(n,2*m);for(int i=1;i<=cnt;i++) f[i]=i;int k=read()+1;while(--k){int x=read(),y=read();for(int i=0;i<8;i++){int xx=x+way[i][0],yy=y+way[i][1];if(!xx || xx>n) continue;if(!yy) yy+=2*m; else if(yy>2*m) yy-=2*m;int p=get(xx,yy);if(bz[p]) g[find(p)]=k;}for(int i=pd=0;i<8;i++){int xx=x+way[i][0],yy=y+m+way[i][1];if(!xx || xx>n) continue;if(!yy) yy+=2*m; else if(yy>2*m) yy-=2*m;int p=get(xx,yy);if(bz[p] && g[find(p)]==k){pd=true;break;}}if(!pd){ans++;work(x,y);work(x,y+m);}}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3809. 【NOIP2014模拟8.25】设备塔的全部內容，希望文章能夠幫你解決所遇到的問題。

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