1 条题解
-
0
题目描述
你在一个魔方工厂工作，一直梦想着发明一种新的5×5×5魔方。今天，你带着一个原型机走进实验室，却不小心把它摔成了两半。现在，你左手拿着一半，正在寻找另一半。然而，地板上散落着之前实验的零件，让你很难找到缺失的那一块。幸运的是，你会编程……
给定两个由单位立方体组成的立体块，判断它们是否能拼合成一个完整的5×5×5立方体。
输入
第一行包含一个整数n，表示数据组数。
接下来的每组数据包含两个并排的俯视图，每个视图是一个5×5的数字矩阵，表示该立体块在对应位置的高度（即堆叠的单位立方体数量）。数字范围是0到9，0表示该位置没有立方体。
题目保证每个立体块是连通的（即单一整体），且可以通过平移（不一定是旋转）拼合。输出
对于每组数据，如果两个立体块能拼合成一个5×5×5的立方体，输出“Yes”，否则输出“No”。示例
输入：2 55551 11111 55551 11111 55551 11111 55551 11110 55552 00000 22222 33333 22222 33333 22222 33233 22222 33333 22222 33333输出：
Yes No解题思路
-
问题分析：
- 我们需要判断两个给定的立体块是否可以拼合成一个完整的5×5×5立方体。
- 每个立体块由一个5×5的俯视图表示，每个格子的数字表示该位置堆叠的单位立方体数量。
- 拼合的条件是两个立体块在同一个5×5×5的空间中不重叠，且它们的立方体总数加起来正好是125（5×5×5）。
-
关键点：
- 两个立体块可以通过平移（不能旋转）拼合，因此我们需要检查是否存在一种平移方式，使得两个立体块在5×5×5的空间中不重叠且填满整个空间。
- 具体来说，可以将其中一个立体块固定，然后尝试将另一个立体块在x、y、z三个方向上进行平移，检查是否存在一种平移方式使得两个立体块的立方体不重叠且总数为125。
-
实现步骤：
- 对于每组数据，首先解析出两个立体块的俯视图，分别记为A和B。
- 将俯视图转换为三维表示。例如，立体块A可以表示为一个三维数组A[x][y][z]，其中z的范围是0到A[x][y]-1（即每个位置的高度）。
- 尝试将立体块B在x、y、z三个方向上进行平移（平移范围为-4到4，因为5×5×5的空间限制），然后检查是否存在一种平移方式使得：
- 两个立体块的立方体不重叠。
- 两个立体块的立方体总数加起来为125。
- 如果存在这样的平移方式，则输出“Yes”，否则输出“No”。
-
优化：
- 由于平移的范围有限（x、y、z方向的平移最多为4），可以直接枚举所有可能的平移方式（最多9×9×9=729种情况）。
- 对于每种平移方式，检查两个立体块的立方体是否重叠以及总数是否为125。
-
示例解释：
- 第一个示例中，两个立体块的立方体总数是125，且可以通过平移拼合（具体拼合方式需要验证），因此输出“Yes”。
- 第二个示例中，两个立体块的立方体总数不是125（或者拼合时有重叠），因此输出“No”。
代码实现思路
- 将两个立体块的俯视图转换为三维坐标集合。
- 枚举所有可能的平移向量（dx, dy, dz）。
- 对于每个平移向量，将第二个立体块的坐标平移后，检查是否与第一个立体块的坐标无重叠，且合并后的立方体数量为125。
- 如果找到满足条件的平移向量，则返回“Yes”；否则返回“No”。
代码实现：
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <vector> using namespace std; #define ll long long const int N = 300010; int n, m, t; char a[N]; int s[N]; int sa[N], x[N], y[N], c[N], rk[N], height[N], base[N], f[N][30], belong[N]; void get_sa() { for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ; for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1]; for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i; for (int k = 1; k <= n; k <<= 1) { int num = 0; for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i; for (int i = 1; i <= n; i ++ ) if (sa[i] > k) y[ ++ num] = sa[i] - k; for (int i = 1; i <= m; i ++ ) c[i] = 0; for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ; for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1]; for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0; swap(x, y); x[sa[1]] = 1, num = 1; for (int i = 2; i <= n; i ++ ) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num; if (num == n) break; m = num; } } void get_height() { for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i; for (int i = 1, k = 0; i <= n; i ++ ) { if (rk[i] == 1) continue; if (k) k -- ; int j = sa[rk[i] - 1]; while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ; height[rk[i]] = k; } } void init_rmq() { base[0] = -1; for(int i = 1; i <= n; i ++) { f[i][0] = height[i]; base[i] = base[i>>1] + 1; } for(int j = 1; j <= 18; j ++) { for(int i = 1; i + (1 << (j - 1)) <= n; i++) { f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); } } } int LCP(int x, int y) //第x和第y个后缀(不是排名)的最长公共前缀 { if(x == y) return n - x + 1; x = rk[x], y = rk[y]; if(x > y) swap(x, y); x ++; int t = base[y - x + 1]; return min(f[x][t], f[y - (1 << t) + 1][t]); } vector<int> pos[1010]; void init() { for(int i = 0; i < 1010; i ++) pos[i].clear(); memset(c, 0, sizeof c); memset(x, 0, sizeof x); } bool check(int mid) { bool vis[110]; memset(vis, 0, sizeof vis); int cnt = 0; bool ret = false, in = false; for(int i = 1; i <= n; i ++) { if(height[i] >= mid) { if(!vis[belong[sa[i]]]) vis[belong[sa[i]]] = 1, cnt ++; if(cnt > t / 2) { ret = true; if(!in) { in = true; pos[mid].push_back(sa[i]); // 第一次进入， 去重相同字符串 } } } else { memset(vis, 0, sizeof vis); vis[belong[sa[i]]] = 1, cnt = 1, in = false; } } return ret; } int main() { bool f = 0; while(scanf("%d", &t) && t) { if(f) printf("\n"); else f = 1; init(); n = 0; for(int i = 1; i <= t; i ++) { scanf("%s", a + 1); int len1 = strlen(a + 1); for(int j = 1; j <= len1; j ++) { s[++n] = a[j] - 'a' + 1; belong[n] = i; } s[++n] = 133 + i; } m = 300; // for(int i = 1; i <= n; i ++) cout << s[i]; // cout << endl; get_sa(); get_height(); init_rmq(); // for(int i = 1; i <= n; i ++) // { // for(int j = sa[i]; j <= n; j ++) cout << s[j] ; // cout << endl; // } int l = 0, r = 1000, ans = 0; while(l <= r) { int mid = l + r >> 1; if(check(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } //cout << ans << endl; if(ans == 0) printf("?\n"); else { // 由于后缀数组性质, 就已经是 for(unsigned int i = 0; i < pos[ans].size(); i ++) { for(int j = 0; j < ans; j ++) { printf("%c", s[pos[ans][i] + j] + 'a' - 1); } printf("\n"); } } } return 0; } -
- 1
