蚂蚁建站,手提电脑做网站服务器,互联网营销培训的课程学费,织梦cms使用教程【题解】[ABC312E] Tangency of Cuboids 少见的 at 评分 \(2000\) 的 ABC E 题#xff0c;非常巧妙的一道题。 特别鸣谢#xff1a;dbxxx 给我讲解了他的完整思路。 题目链接 ABC312E - Tangency of Cuboids 题意概述 给定三维空间中的 \(n\) 个长方体#xff0c;每个长方体… 【题解】[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})\)。 要求对于给定的每一个长方体求出给定的其它长方体中与其共享一个面的长方体数量。 具体地说对于每个 \(i(1 \le i \le n)\)找到 \(1≤j≤n\) 且 \(j≠i\) 的 \(j\) 的数量使得第 \(i\) 个长方体和第 \(j\) 个长方体的表面有一个正面积的交集。 题目保证每个长方体两两不交即对于任意两个长方体它们的交集体积为 \(0\)。 数据范围 \(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\)启示我们要处理单位小正方体的信息。 注单位小正方体指的是坐标范围内棱长为 \(1\) 的正方体。 可以考虑将题目中所有已知的长方体都分解成多个单位小正方体处理。即对于长方体 \(i\)我们把这个长方体中包含所有单位小正方体都染色成 \(i\)。 换句话说我们定义体对角线端点坐标为 \((i,j,k)\) 和 \((i1,j1,k1)\) 的单位小正方体的坐标为 \((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 jy_{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}\)。因为当 \(ix_{t,2}\) 或 \(jy_{t,2}\) 或 \(kz_{t,2}\) 时对应的单位小正方体已经不属于这个长方体内了。所以必须是小于不能是小于等于。 接下来我们枚举坐标范围(即 \([0,100)\) 内)的每一个单位小正方体的坐标 \((i,j,k)\)那么如果这个小正方体和它相邻小正方形即 \((i1,j,k)\) 或 \((i,j1,k)\) 或 \((i,j,k1)\) 颜色不同则说明它们所在的长方体有公共面。那么这样的方法就可以找到所有的有公共面长方体。 我们考虑对于每一个长方体开一个 set如果长方体 \(i\) 与长方体 \(j\) 有公共面。那么就往 \(i\) 对应的 set 里扔一个 \(j\)同时往 \(j\) 对应的 set 里面扔一个 \(i\)由于 set 无重复元素这样顺便也完成了去重。那么最后输出 \(1\) 到 \(n\) 的每个正方体 \(i\) 的 set 的 size 就好了。 注意如果题目不保证给定长方体两两不交就不能这么做了。因为如果有交同一个单位小正方形就可以同时被染成两种颜色而这个做法必须保证染色的唯一性。 时间复杂度 \(O(100^3 \log n)\)(set 是 \(\log n\) 的复杂度)。 代码实现 //E
//The Way to The Terminal Station…
#includecstdio
#includeiostream
#includeset
using namespace std;
const int maxn1e510;
const int maxx105;
int X1[maxn],X2[maxn],Y1[maxn],Y2[maxn],Z1[maxn],Z2[maxn];
int col[maxx][maxx][maxx];setints[maxn];inline int read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-48;chgetchar();}return x*f;
}void work(int xx,int xy,int yx,int yy,int zx,int zy,int t)
{for(int ixx;ixy;i){for(int jyx;jyy;j){for(int kzx;kzy;k){col[i][j][k]t;}}}
}int main()
{int nread();for(int i1;in;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 i0;i100;i){for(int j0;j100;j){for(int k0;k100;k){if(col[i][j][k]!col[i1][j][k]){if(col[i][j][k]col[i1][j][k]){s[col[i][j][k]].insert(col[i1][j][k]);s[col[i1][j][k]].insert(col[i][j][k]);}}if(col[i][j][k]!col[i][j1][k]){if(col[i][j][k]col[i][j1][k]){s[col[i][j][k]].insert(col[i][j1][k]);s[col[i][j1][k]].insert(col[i][j][k]);}}if(col[i][j][k]!col[i][j][k1]){if(col[i][j][k]col[i][j][k1]){s[col[i][j][k]].insert(col[i][j][k1]);s[col[i][j][k1]].insert(col[i][j][k]);}}}}}for(int i1;in;i)couts[i].size()\n;return 0;
}
