1

我遇到了这个问题,其中所有程序都只给出了一条逻辑。以下问题的缺失行可以填写什么?

问题陈述

杰克和丹尼尔是朋友。他们想加密他们的谈话,这样他们就可以避免被侦探机构拦截。所以他们发明了一种新的密码。每条消息都被编码为其长度为N的二进制表示B。然后将其写下K次,移位0,1,...,K-1位。如果B=1001010K=4它看起来像:

1001010
 1001010
  1001010
   1001010

然后计算每一列的异或并写下来。这个数字称为S。例如,对上面示例中的数字进行异或运算会导致

1110100110

然后将编码后的消息SK发送给 Daniel。

Jack 正在使用这种编码算法,并要求 Daniel 实现解码算法。你能帮助丹尼尔实现这个吗?

输入格式

  • 第一行包含两个整数NK
  • 第二行包含长度为N+K-1的字符串S ,由 1 和 0 组成。

输出格式

长度为N的解码消息,由 1 和 0 组成。

约束

  • 1≤N≤10^6,
  • 1≤K≤10^6
  • |S|=N+K−1
  • 保证S是正确的。

样本输入#00

   7 4
   1110100110

样本输出#00

   1001010

样本输入#01

   6 2
   1110001

样本输出#01

   101111

输入#00 的说明

1001010
 1001010
  1001010
   1001010
----------
1110100110

输入#01 的解释

101111
 101111
-------
1110001 

import java.io.*;

public class Solution {

    public static void solve(Input in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        int k = in.nextInt();
        char[] c = in.next().toCharArray();
        int x = 0;
        char[] ans = new char[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = (char) (((c[i] - '0') ^ x) + '0');// I understand we are converting the character into integer (c[i] - '0') then xoring it with x which is holding 0 and then again adding '0' to convert back it into character.
            x ^= ans[i] - '0';// But why are we doing this!!. From this line onward things are not clear.
            if (i >= k - 1) {
                ****FILL THE MISSING LINE HERE****

            }
        }
        out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}
4

1 回答 1

3

注意请阅读说明,简单地通过复制粘贴答案来解决挑战是没有用的。

您可以利用的约束是

加密算法未触及第一位

确实是因为所有“掩码”都至少向右移动了一个。所以你可以假设加密部分的第一位也是解密内容的第一位。

现在您知道第一位,您可以轻松地重构第二位,因为它仅与我们已经知道的第一位进行异或。所以知道我们可以计算第二个。

第三位与第一位和第二位进行异或运算,因此基本上所做的就是维护一个值,该值是所有已获得值的异或,并将其与下一个值异或。最初该值为零。

示例

取第一个样本输入:

1110100110

我们可以推导出第一位是 a 1。所以现在我们知道第二位的掩码是以下形式:

       1110100110
mask    1????????
result 10

现在我们知道第三位的掩码是和的异1或。01

       1110100110
mask    11???????
result 100

迭代地,这最终将导致:

index      0123456789       
data       1110100110
submasks    1001010
             1001010
              1001010
mask       0111??????
result     1001??????

现在在k-1迭代之后,实际上不再有一个额外的子掩码:一个只k为结果写入数据的倍数,并且对子掩码进行k-1倍数。所以现在我们不再对新数据进行异或:我们只对结果的最后一位进行异或k,这可以通过对左边的结果位置的位进行或(或简单地异或)来完成。k

对于下一个掩码,我们因此将我们的状态(掩码的最后一位)与结果的最后一位 ( ) 和结果的第一位( ) 进行或,这意味着状态保持不变 ( ):111

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       01111?????
result     10010?????

0现在我们对最后一个结果位 ( ) 和第二个结果位 ( )进行异或0

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       011111????
result     100101????

接下来,我们与最后一个 ( 1) 和第三个 ( 0) 进行异或运算,从而交换状态。通过继续执行此过程,我们最终以:

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       0111110???
result     1001010???

现在我们不再对剩余的位感兴趣,所以我们终止。

必须修改什么?

if- 部分,我们还需要对-th 位进行或 ( ^) :i-(k-1)

if (i >= k - 1) {
    x ^= ans[i-(k-1)] - '0';
}
于 2015-05-18T05:38:47.693 回答