MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 509 - RAID!
AOAPC II

UVaOJ 509 - RAID!

Chai
2021-11-24 0:00:00在线评测阅读 347

问题描述

p509

原题链接:UVaOJ 1590 - IP Networks

相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-7

解法一:模拟

整个流程为:读盘 -> 校验 -> 1. 对于 “校验正确” 或 “存在 1 个无效值(能够恢复)” 的情况,判断为 valid 并输出盘中内容;2. 对于 “校验不正确(每一位上的数据异或结果不为 0)” 或 “无效值超过 1 个” 的情况,判断为 invalid·.

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
#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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz