在CSP初赛后,chen03的RP快用完了。
RP是个神奇的东西。具体来说,chen03的RP值可以用二进制正整数a和十进制正整数n表示。他的RP值可以表示为
RP=axor(a<<1)xor(a<<2)xor...xor(a<<(n-1))。
其中a<<i表示将a左移i位,xor表示按位异或运算。
chen03想知道他的RP值是多少。
注:
1.将a左移i位,即在a后添加i个0,也可以看成a×2i,在C++中的运算符为<<;
2.按位异或:在二进制下,对两个数的每一位进行异或运算,并把结果放到答案的当前位上,在C++中的运算符为^。异或,即两个值同为1或同为0时结果为0,否则为1。
输入
共两行,第一行一个二进制正整数 a(保证不含前导 0),第二行一个十进制正整数 n,意义如题目描述。
输出
一行一个二进制正整数,表示 chen03 的 RP 值。答案不用取模。
样例输入 Copy
100001001
4
样例输出 Copy
111101110111
提示
00001001中最右边一个是1,如果进行这个操作
,则从右边数第1个到第i-n+1个都加上1,最后判断1的个数就是这个操作的时候可以用查分优化出现奇数个1xor起来就是1
偶数就是0
#pragma GCC optimize(2)
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
typedef long long ll;
ll read(){
ll x=0; ll f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
using namespace std;
const int maxn=3e6+100;
const ll INF=1e18;
char a[maxn];
char c[maxn];
int b[maxn];
int sum[maxn];
int m;
int main(){
scanf("%s",a+1);
cin>>m;
int len=strlen(a+1);
for(int i=1;i<=len;i++){
c[i]=a[len+1-i];
}
for(int i=1;i<=len;i++){
if(c[i]=='1'){
b[i]++;
b[i+m]--;
}
}
for(int i=1;i<=len+m;i++){
sum[i]=sum[i-1]+b[i];
}
for(int i=len+m-1;i>=1;i--){
if(sum[i]%2==1){
printf("1");
}
else{
printf("0");
}
}
}
原文链接: https://www.cnblogs.com/lipu123/p/13411825.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/200972
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!