1007. Code words
Memory Limit: 16 MB
- Any (but only one) symbol 0 is replaced by 1.
- Any (but only one) symbol is removed.
- A symbol (0 or 1) is inserted at any position.
Input
Output
Sample
| input | output |
|---|---|
|
4 0000 011 1011 11011 |
0000 0110 1001 1111 |
Problem Source: USU Championship 1997
解答如下：
2
3 namespace Skyiv.Ben.Timus
4 {
5 // http://acm.timus.ru/problem.aspx?space=1&num=1007
6 sealed class T1007
7 {
8 static void Main()
9 {
10 int n = int.Parse(Console.ReadLine().Trim());
11 byte[] word = new byte[n + 2];
12 int[] cnt = new int[n + 2], sum = new int[n + 2];
13 for (string s; (s = Console.ReadLine()) != null; )
14 {
15 if ((s = s.Trim()).Length == 0) continue;
16 for (int i = 0; i < s.Length; i++) word[i + 1] = (byte)(s[i] - '0');
17 Initialize(s.Length, word, sum, cnt);
18 if (n < s.Length) Remove(word, sum, cnt);
19 else if (n > s.Length) Insert(word, sum, cnt);
20 else Replace(word, sum);
21 for (int i = 1; i <= n; i++) Console.Write(word[i]);
22 Console.WriteLine();
23 }
24 }
25
26 static void Initialize(int len, byte[] word, int[] sum, int[] cnt)
27 {
28 for (int i = 1; i <= len; i++)
29 {
30 cnt[i] = cnt[i - 1] + word[i];
31 sum[i] = sum[i - 1] + word[i] * i;
32 }
33 }
34
35 static void Replace(byte[] word, int[] sum)
36 {
37 if (sum[word.Length - 2] % (word.Length - 1) == 0) return;
38 for (int n = word.Length - 2, i = 1; i <= n; i++)
39 {
40 if (word[i] == 0 || (sum[n] - i) % (n + 1) != 0) continue;
41 word[i] = 0;
42 return;
43 }
44 }
45
46 static void Remove(byte[] word, int[] sum, int[] cnt)
47 {
48 for (int n = word.Length - 2, i = 1; i <= n + 1; i++)
49 {
50 if ((cnt[n+1] - cnt[i] + sum[i] - sum[i-1] - sum[n+1]) % (n + 1) != 0) continue;
51 for (int k = i; k <= n; k++) word[k] = word[k + 1];
52 return;
53 }
54 }
55
56 static void Insert(byte[] word, int[] sum, int[] cnt)
57 {
58 for (int n = word.Length - 2, i = 1; i <= n; i++)
59 {
60 int v = sum[n - 1] + cnt[n - 1] - cnt[i - 1];
61 int bit = (v % (n + 1) == 0) ? 0 : (((v + i) % (n + 1) == 0) ? 1 : -1);
62 if (bit < 0) continue;
63 for (int k = n; k > i; k--) word[k] = word[k - 1];
64 word[i] = (byte)bit;
65 return;
66 }
67 }
68 }
69 }
这道题目是说，发送方通过一个有噪声的信道发送二进制编码的单词，所有的单词都具有相同的长度 N (4 ≤ N ≤ 1000)。经过该信道后，每个单词可能产生以下一项变化：
- 某个 0 被替换为 1
- 删除任何一个 0 或 1
- 在任何位置插入 0 或 1
已知原始的单词具有以下性质：字符 1 的位置的和(以下称为校验码)是 N + 1 的倍数。现在要求写一个程序输出原始的单词。
在上述程序中，第 8 到 24 行为程序的入口点 Main 方法，负责依次读入接收到的单词，接着在 17 行调用 Initialize 方法对单词进行预计算，然后在第 18 到 20 行根据接收到的单词的长度分别调用 Remove 、Insert 和 Replace 方法进行处理，最后在第 21 到 22 行输出经过处理后的单词。
第 26 到 33 行的 Initialize 方法计算单词在每个位置上的 1 的个数 cnt 以及校验码 sum。注意 sum[n] 就是整个单词的检验码。
第 35 到 44 行的 Replace 方法处理可能发生的第一种变化(某个 0 被替换为 1)。第 37 行判断如果校验码是 n + 1 的倍数，说明该单词没有发生变化，就直接返回。第 38 行开始的循环遍历整个单词(该单词的长度是 n)，试图寻找出发生变化的位置。关键在于第 40 行：
首先，如果该位置处的字符是 0 就跳过。否则，该位置处的字符肯定是 1，如果该单词的校验码 sum[n] 减去该位置处本身的校验码 i 是 n + 1 的倍数的话，说明这个位置就是所要寻找的。那么，就在第 41 行将该位置处的字符设置为 0 以去除噪声的干扰。
第 46 到 54 行的 Remove 方法处理第三种变化(在任何位置插入 0 或 1)。第 48 行开始的循环遍历整个单词(该单词的长度是 n + 1)，试图寻找出插入的位置。关键在于第 50 行：
在这个条件语句的表达式中，cnt[n+1] - cnt[i] 表示在该位置右边的 1 的个数，也就是说，如果在该位置处删除一个字符的话，由此减少的校验码的数值。sum[i] - sum[i-1] 表示该位置处本身的校验码，它实际上可能是 i (该位置上的字符是 1 的话)或 0 (该位置上的字符是 0 的话)。sum[n+1] 表示该单词的校验码，如果它与前两项之和的差值是 n + 1 的倍数的话，说明这个位置就是所要寻找的。那么，就在第 51 行将该位置右边所有的字符左移一位，以删除被噪声插入的字符。
第 56 到 67 行的 Insert 方法处理第二种变化(删除任何一个 0 或 1)。第 58 行开始的循环遍历整个单词(该单词的长度是 n - 1)，试图寻找出删除的位置。关键在于第 60 和 61 行：
在上面的语句中，sum[n - 1] 表示该单词的校验码，cnt[n - 1] - cnt[i - 1] 表示在该位置右边的 1 的个数，也就是说，如果在该位置处插入一个字符的话，由此增加的校验码的数值。如果以上两项之和是 n + 1 的倍数的话，表示需要在该位置插入字符 0 。如果以上两项之和再加上该位置处本身的校验码 i 是 n + 1 的倍数的话，表示需要在该位置插入字符 1 。第 63 行将该位置右边所有的字符右移一位，然后在该位置处插入被噪声删除的字符 0 或 1 (第 64 行)。
返回目录