问题描述
p509相关说明：本题为《算法竞赛入门经典（第2版）》习题 4-7
解法一：模拟
整个流程为：读盘 -> 校验 -> 1. 对于 “校验正确” 或 “存在 1 个无效值（能够恢复）” 的情况，判断为 valid 并输出盘中内容；2. 对于 “校验不正确（每一位上的数据异或结果不为 0）” 或 “无效值超过 1 个” 的情况，判断为 invalid·.
|
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 |
#include <bits/stdc++.h> using namespace std; int main() { int d, s, b, num_disk_set = 0; // disks, size per block, blocks char parity, d2h[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'}; string disk; while (cin >> d && d) { num_disk_set += 1; cin >> s >> b >> parity; vector<string> disks; for (int i = 0; i < d; ++i) { cin >> disk; disks.push_back(disk); } bool valid = true; for (int bit = 0; bit < disk.size(); ++bit) { // Check per bit int unaval_cnt = 0, unaval_idx = -1; int expect_value = (parity == 'O' ? 1 : 0); // Should be 0 finally for (int i = 0; i < d; ++i) { if (disks[i][bit] == 'x') unaval_cnt++, unaval_idx = i; else expect_value ^= disks[i][bit] - '0'; } if (unaval_cnt == 1) { disks[unaval_idx][bit] = expect_value + '0'; // recover } else if (unaval_cnt >= 2 || (!unaval_cnt && expect_value)) { cout << "Disk set " << num_disk_set << " is invalid." << endl; valid = false; break; } } if (valid) { string res; for (int block = 0; block < b; ++block) for (int i = 0; i < d; ++i) if (i != block % d) res += disks[i].substr(s * block, s); int extra_bit = (4 - res.length() % 4) % 4; while (extra_bit--) res += "0"; cout << "Disk set " << num_disk_set << " is valid, contents are: "; for (int i = 0; i < res.length(); i += 4) { int decimal = 8 * (res[i] - '0') + 4 * (res[i + 1] - '0') + 2 * (res[i + 2] - '0') + (res[i + 3] - '0'); cout << d2h[decimal]; } cout << endl; } } return 0; } |
|
1 |
#TODO |
