ACM/ICPC 2011 成都现场赛 Isabella’s Message 题解
这种题目，说水也不算水，写起来还是挺麻烦的。每一步都很简单，但是每一步都需要注意细节。写起来比较耗时间，所以习惯要好才行。
这道题给我的教训是，返回对象的时候，那个对象不能太大。寒假刚开始的时候看了一下操作系统，里面涉及了一些 C 和汇编交叉编译的东西，就大概知道 C 的函数调用约定下，返回值是要存在 [.SECTION stack] 的。而且似乎 C 是不能够返回“太大”的东西的，C++ 才行。我猜 C++ 的调用约定应该也是类似的，所以返回大东西会有问题。这一次具体地表现在，对那个需要返回的对象的修改无法进行。
代码如下：
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | #include <cstdio> #include <vector> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct matrix { char w[55][55]; int n; inline matrix &rotcw(matrix &r) const { r.n = n; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) r.w[j][n-1-i] = w[i][j]; return r; } vector<string> &mask(const matrix &data, vector<string> &buffer) const { buffer.clear(); buffer.resize(4); matrix mat[2]; int k = 0; for (mat[0] = *this; k < 4; ++k) { for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (mat[k&1].w[i][j] & data.w[i][j]) buffer[k].push_back(mat[k&1].w[i][j] & data.w[i][j]); if (k < 3) mat[k&1].rotcw(mat[(k&1)^1]); } return buffer; } }; inline void read_data(int n, matrix &data) { data.n = n; for (int i = 0; i < n; ++i) gets(data.w[i]); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (data.w[i][j] == '.') data.w[i][j] = ' '; } inline void read_mask(int n, matrix &mat) { mat.n = n; for (int i = 0; i < n; ++i) gets(mat.w[i]); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (mat.w[i][j] == '*') mat.w[i][j] = -1; else mat.w[i][j] = 0; } inline string strict_trim(string str) { int offset = 0; bool first = true; for (int i = 0; i < str.size(); ++i) { if (str[i] == ' ') { if (first) first = false; else ++offset; } else { first = true; } str[i - offset] = str[i]; } str.resize(str.size() - offset); if (str[0] == ' ') str.erase(0, 1); if (str[str.size() - 1] == ' ') str.resize(str.size() - 1); return str; } inline bool understand(const string &str, const vector<string> &keys) { string::const_iterator it = str.begin(), start; while (it != str.end()) { for (start = it; it != str.end() && *it != ' '; ++it); string word(start, it); if (find(keys.begin(), keys.end(), word) == keys.end()) return false; if (it != str.end() && *it == ' ') ++it; } return true; } inline string decrypt(const vector<string> &oris, const vector<string> &keys) { vector<string> possibles; for (int start = 0; start < 4; ++start) { string sentence; for (int ofst = 0; ofst < 4; ++ofst) { int i = (start + ofst) % 4; sentence += oris[i]; } sentence = strict_trim(sentence); if (understand(sentence, keys)) possibles.push_back(sentence); } if (possibles.empty()) return string("FAIL TO DECRYPT"); sort(possibles.begin(), possibles.end()); return possibles.front(); } int main() { // freopen("input.txt", "r", stdin); int T, n, m; char buffer[100]; vector<string> strarr; scanf("%d", &T); for (int i = 1; i <= T; ++i) { scanf("%d", &n); gets(buffer); matrix data; read_data(n, data); matrix mask; read_mask(n, mask); scanf("%d", &m); vector<string> keys; string key; while (m--) { cin >> key; keys.push_back(key); } printf("Case #%d: %s\n", i, decrypt(mask.mask(data, strarr), keys).c_str()); } return 0; } |
