ACM/ICPC 2010 杭州现场赛 To Be a Dream Architect 题解
这道题的题意是给出一个 N × N 的正方体，这个正方体是由 1 × 1 的小正方体垒成的。然后，输入数据会给出若干个命令，这些命令都表示一条平行于某坐标轴的直线，命令的效果是让这个直线上的所有方块消失掉。最后，问消失了多少小方块。
似乎这道题原题标题犯了个小小的语法错误……
关于这道题的解法，Greenmoon55 说，可以用 vector + sort + unique 系列的方法解决这个问题，还提到 set 可能会超时超内存[GRN'11]。我想原因是插入删除过程其实是 O(logn) 的，并且使用动态内存分配频繁，各种冗余数据比较多吧。这种方法的时间复杂度是 O(n2logn).
我的解法是另一种，我使用一个数组 planes[3][N][N], 记录输入的每一条直线。在每执行一条直线的命令的时候，判断某一个方块是否已经被其它直线去掉了。所以这就降了一维，复杂度是 O(n2). 但是现场赛时，我可能会采取 Greenmoon55 的做法。
源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <cstdio> #include <cstring> using namespace std; const int N = 1001; bool planes[3][N][N]; int n, m; inline bool is_coord_valid(int x, int y) { if (x >= 1 && x <= n && y >= 0 && y <= n) return true; return false; } inline int count_cubes(int i0, int x, int y) { int i1 = (i0 + 1) % 3, i2 = (i0 + 2) % 3; if (planes[i0][x][y]) return 0; // Already counted. planes[i0][x][y] = true; int result = 0; for (int z = 1; z <= n; ++z) if (!planes[i1][y][z] && !planes[i2][z][x]) ++result; return result; } int main() { int T, x, y, r; char a, b, buf[32]; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); r = 0; memset(planes, false, sizeof planes); for (int i = 0; i < m; ++i) { gets(buf); // Skip EOLN. scanf("%c=%d,%c=%d", &a, &x, &b, &y); if (a == 'X' && b == 'Y') r += count_cubes(0, x, y); else if (a == 'Y' && b == 'X') r += count_cubes(0, y, x); else if (a == 'Y' && b == 'Z') r += count_cubes(1, x, y); else if (a == 'Z' && b == 'Y') r += count_cubes(1, y, x); else if (a == 'Z' && b == 'X') r += count_cubes(2, x, y); else if (a == 'X' && b == 'Z') r += count_cubes(2, y, x); } printf("%d\n", r); } return 0; } |
跃跃，辛苦了。。。。。真心强大
……辛苦是辛苦，强大不敢说……