免費開源的建站系統(tǒng)成免費crm軟件有哪些優(yōu)點
【題解】[ABC312E] Tangency of Cuboids
少見的 at 評分 \(2000+\) 的 ABC E 題，非常巧妙的一道題。
特別鳴謝：@dbxxx 給我講解了他的完整思路。
題目鏈接
ABC312E - Tangency of Cuboids
題意概述
給定三維空間中的 \(n\) 個長方體，每個長方體以其一條體對角線的兩個端點的坐標形式給出，即對于每一個長方體 \(i\)，給定其體對角線端點的坐標 \((x_{i,1},y_{i,1},z_{i,1})\) 和 \((x_{i,2},y_{i,2},z_{i,2})\)。
要求對于給定的每一個長方體，求出給定的其它長方體中，與其共享一個面的長方體數(shù)量。
具體地說，對于每個 \(i(1 \le i \le n)\)，找到 \(1≤j≤n\) 且 \(j≠i\) 的 \(j\) 的數(shù)量，使得第 \(i\) 個長方體和第 \(j\) 個長方體的表面有一個正面積的交集。
題目保證每個長方體兩兩不交，即對于任意兩個長方體，它們的交集體積為 \(0\)。
數(shù)據(jù)范圍
- \(1\le n \le 10^5\)
- \(0 \le x_{i,1}<x_{i,2}\le 100\)
- \(0 \le y_{i,1}<y_{i,2}\le 100\)
- \(0 \le z_{i,1}<z_{i,2}\le 100\)
思路分析
\(n\) 的范圍很大，但是觀察長方體體對角線端點的坐標范圍只有 \(100\)，容易想到最終的時間復雜度應該是 \(100^3\) 或者 \(100^4\)，啟示我們要處理單位小正方體的信息。
注：單位小正方體指的是坐標范圍內(nèi)棱長為 \(1\) 的正方體。
可以考慮將題目中所有已知的長方體，都分解成多個單位小正方體處理。即，對于長方體 \(i\)，我們把這個長方體中包含所有單位小正方體都染色成 \(i\)。
換句話說，我們定義體對角線端點坐標為 \((i,j,k)\) 和 \((i+1,j+1,k+1)\) 的單位小正方體的坐標為 \((i,j,k)\)，\(col_{i,j,k}\) 表示坐標為 \((i,j,k)\) 的單位小正方體被染成的顏色。那么對于體對角線端點坐標為 \((x_{t,1},y_{t,1},z_{t,1})\) 和 \((x_{t,2},y_{t,2},z_{t,2})\) 的長方體 \(t\)，就將所有坐標為 \((i,j,k)\)，其中 \(x_{t,1}\le i <x_{t,2},y_{t,1} \le j < y_{t,2},z_{t,1} \le k < z_{t,2}\) 的單位小正方體都染成 \(t\)，即讓 \(col_{i,j,k}=t\)。
注意：這里 \(i,j,k\) 條件是 \(x_{t,1}\le i <x_{t,2},y_{t,1}\le j<y_{t,2},z_{t,1} \le k <z_{t,2}\)，而不是 \(x_{t,1}\le i \le x_{t,2},y_{t,1}\le j \le y_{t,2},z_{t,1} \le k \le z_{t,2}\)。因為當 \(i=x_{t,2}\) 或 \(j=y_{t,2}\) 或 \(k=z_{t,2}\) 時，對應的單位小正方體已經(jīng)不屬于這個長方體內(nèi)了。所以必須是小于，不能是小于等于。
接下來，我們枚舉坐標范圍(即 \([0,100)\) 內(nèi))的每一個單位小正方體的坐標 \((i,j,k)\)，那么如果這個小正方體和它相鄰小正方形，即 \((i+1,j,k)\) 或 \((i,j+1,k)\) 或 \((i,j,k+1)\) 顏色不同，則說明它們所在的長方體有公共面。那么這樣的方法就可以找到所有的有公共面長方體。
我們考慮對于每一個長方體開一個 set，如果長方體 \(i\) 與長方體 \(j\) 有公共面。那么就往 \(i\) 對應的 set 里扔一個 \(j\)，同時往 \(j\) 對應的 set 里面扔一個 \(i\)，由于 set 無重復元素，這樣順便也完成了去重。那么最后輸出 \(1\) 到 \(n\) 的每個正方體 \(i\) 的 set 的 size 就好了。
注意：如果題目不保證給定長方體兩兩不交，就不能這么做了。因為如果有交，同一個單位小正方形就可以同時被染成兩種顏色，而這個做法必須保證染色的唯一性。
時間復雜度 \(O(100^3 \log n)\)(set 是 \(\log n\) 的復雜度)。
代碼實現(xiàn)
//E
//The Way to The Terminal Station…
#include<cstdio>
#include<iostream>
#include<set>
using namespace std;
const int maxn=1e5+10;
const int maxx=105;
int X1[maxn],X2[maxn],Y1[maxn],Y2[maxn],Z1[maxn],Z2[maxn];
int col[maxx][maxx][maxx];set<int>s[maxn];inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}void work(int xx,int xy,int yx,int yy,int zx,int zy,int t)
{for(int i=xx;i<xy;i++){for(int j=yx;j<yy;j++){for(int k=zx;k<zy;k++){col[i][j][k]=t;}}}
}int main()
{int n=read();for(int i=1;i<=n;i++){X1[i]=read();Y1[i]=read();Z1[i]=read();X2[i]=read();Y2[i]=read();Z2[i]=read();work(X1[i],X2[i],Y1[i],Y2[i],Z1[i],Z2[i],i);}for(int i=0;i<100;i++){for(int j=0;j<100;j++){for(int k=0;k<100;k++){if(col[i][j][k]!=col[i+1][j][k]){if(col[i][j][k]&&col[i+1][j][k]){s[col[i][j][k]].insert(col[i+1][j][k]);s[col[i+1][j][k]].insert(col[i][j][k]);}}if(col[i][j][k]!=col[i][j+1][k]){if(col[i][j][k]&&col[i][j+1][k]){s[col[i][j][k]].insert(col[i][j+1][k]);s[col[i][j+1][k]].insert(col[i][j][k]);}}if(col[i][j][k]!=col[i][j][k+1]){if(col[i][j][k]&&col[i][j][k+1]){s[col[i][j][k]].insert(col[i][j][k+1]);s[col[i][j][k+1]].insert(col[i][j][k]);}}}}}for(int i=1;i<=n;i++)cout<<s[i].size()<<'\n';return 0;
}