NC23801. DongDong破密码
描述
DongDong是一个喜欢密码学的女孩子，她养的萨摩耶叼着一张带着加密信息的纸条交给了她，如果她不能破解这张密码，萨摩耶是不会高兴的。
给定n,m，给出长度为n的01串，每次向后移动一位，移动m-1次，最后求出这n+m-1位每一位的异或值（0^0=0,1^1=0,0^1=1）成为密码。（如下图这样，此时n=6,m=3）
输入描述
第一行两个整数,n和m
第二行一个01串（共n+m-1位）
2<=n+m<=1000000
输出描述
第一行输出答案：长度为n的01串（保证存在答案）
示例1
输入:
6 3 11010110
输出:
101010
说明:
见题目描述C++14(g++5.4) 解法, 执行用时: 157ms, 内存消耗: 8416K, 提交时间: 2019-06-07 21:04:29
#include<stdio.h>
int n,m,a[1000006],i,b[1000006],j;
int main()
{
scanf("%d%d",&n,&m);
for(i=0;i<m+n-1;i++)
scanf("%1d",&a[i]);
b[0]=a[0];
for(i=1;i<n;i++)
{
b[i]=a[i];
b[i]^=a[i-1];
if(i-m>=0)
b[i]^=b[i-m];
}
for(i=0;i<n;i++)
printf("%d",b[i]);
}
Python3(3.5.2) 解法, 执行用时: 1003ms, 内存消耗: 74312K, 提交时间: 2019-06-07 23:13:43
n,m=map(int,input().split())
strin=list(map(int,input()))
ret=[0 for i in range(n)]
ret[0]=strin[0]
for i in range(1,n) :
if i<m:
ret[i]=strin[i-1]^strin[i]
else :
ret[i]=strin[i-1]^strin[i]^ret[i-m]
print(''.join(map(str,ret)))
C++11(clang++ 3.9) 解法, 执行用时: 67ms, 内存消耗: 5704K, 提交时间: 2019-06-07 21:32:35
#include<bits/stdc++.h>
int n,m,a[2000005],i,j;
std::string s;
int main()
{
std::cin>>n>>m>>s;
for(i=0;i<n;i++)a[i]=s[i]==49^s[i-1]==49,i>=m&&(a[i]^=a[i-m]),putchar(a[i]+48);
}