admin管理员组文章数量:1582733
神奇的题目。。。
首先很明显,如果l,r最高位不全是1,那么答案肯定每个数位都是1,如样例一
对于其他的情况,我们尝试着把r中0的位置给变成1。
我把二进制列出来以后,发现只有最低位置才有可能从0变成1(只要r-l>=2就可以)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
char s1[N],s2[N];
void add(){
s1[1]++;
for(int i=1;i<=n;i++){
if(s1[i]=='2'){
s1[i+1]++;
s1[i]='0';
}
else break;
}
}
bool bijiao(){
if(s1[n+1]!='0')return 0;
for(int i=n;i>=1;i--){
if(s1[i]>s2[i])return 0;
if(s1[i]<s2[i])return 1;
}
return 1;
}
int main(){
cin>>n;int tt=n;
scanf("%s%s",s1+1,s2+1);
reverse(s1+1,s1+n+1);
reverse(s2+1,s2+n+1);
s1[n+1]=s2[n+1]='0';
while(n){
if(s1[n]=='0'&&s2[n]=='0')n--;
else break;
}
if(!n){
for(int i=1;i<=tt;i++)
putchar('0');
return 0;
}
if(s1[n]!=s2[n]){
for(int i=1;i<=tt;i++)
putchar('1');
return 0;
}
if(s2[1]=='1'){
for(int i=tt;i>=1;i--)
putchar(s2[i]);
return 0;
}
for(int i=1;i<=2;i++)add();
if(bijiao()){
for(int i=tt;i>1;i--)
putchar(s2[i]);
putchar('1');
}
else{
for(int i=tt;i>=1;i--)
putchar(s2[i]);
}
return 0;
}
版权声明:本文标题:CF1493E Enormous XOR 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1727901425a1136959.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论