AGC025F
有两个长度为(n)和(m)的二进制数(x)和(y)。要做如下操作(k)次：
(x+=x & y,y+=x&y)
问(k)次之后(x)和(y)分别是多少。
(n,m,kle 10^6)
补很久前的题解。
模拟一下暴力：操作(k)次，每次操作就是，从高位往低位，如果两个串对应位上的数为((1,1))，那么将这两位清空并且向前进一位。
不妨改变一下枚举的顺序：从高位往低位，如果两个串对应为上数为((1,1))，做(k)次“向前移动”的操作（即当前位清空，如果前面为((0,0))，那么前面变成((1,1))，指针前移一位；如果前面为((0,1))，前面(x)对应位变成(1)，(y)对应位进位，若是存在形如((100,011))变成((101,100))的情况，那么指针移到前面那个((1,1))；前面不可能为((1,1))）。
用链表来维护状态相同的连续段。模拟即可。
势能分析，时间复杂度是对的：当前面有连续的((0,0))时，(O(1))移动过去，不影响；然后遇到连续的((0,1))。当前面有连续的((0,1))时，可能越过这连续的((0,1))并且在前面创造了新的((1,1))（创造新的((1,1))：连续的((0,1))前有个((1,0))），但是同时意味着这一段连续的((0,1))变成((0,0))（最后一个除外，变成((1,0)))。如果我们把((0,1))连着((1,0))的位置个数定义为势能，那么时间复杂度就显然了。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000010
int n,m,k;
char str[N];
int s[N],t[N];
struct Node{
Node *pre,*suc;
int s,n;
} *fir,*lst;
Node *ins(Node *p,int s,int n=1){
Node *nw=new Node;
*nw={p,p->suc,s,n};
if (p->suc)
p->suc->pre=nw;
else
lst=nw;
p->suc=nw;
return nw;
}
Node *check(Node *p){
if (p->n==0 || p->pre && p->s==p->pre->s){
p->pre->n+=p->n;
p->pre->suc=p->suc;
if (p->suc)
p->suc->pre=p->pre;
else
lst=p->pre;
return p->pre;
}
return p;
}
int ans[N*2],cnt;
void print(int w){
bool bz=0;
for (int i=cnt-1;i>=0;--i){
bz|=ans[i]>>w&1;
if (bz)
putchar('0'+(ans[i]>>w&1));
}
if (bz==0)
putchar('0');
putchar('
');
}
int main(){
scanf("%d%d%d",&n,&m,&k);
scanf("%s",str);
for (int i=0;i<n;++i)
s[i]=str[n-1-i]-'0';
scanf("%s",str);
for (int i=0;i<m;++i)
t[i]=str[m-1-i]-'0';
n=max(n,m);
fir=lst=new Node;
*lst=(Node){NULL,NULL,0,1000000000};
for (int i=n-1;i>=0;--i)
if (s[i]==1 && t[i]==1){
int z=k;
Node *p=lst;
while (z){
while (1){
Node *q=check(p);
if (q==p) break;
p=q;
}
if (p->s==0){
if (p->n<=z){
z-=p->n;
p=p->pre;
if (z==0)
ins(p,3,1);
}
else{
p->n-=z;
Node *q=ins(p,0,z);
ins(p,3,1);
break;
}
}
else{
while (1){
Node *q=check(p->pre);
if (q==p->pre) break;
p->pre=q;
}
int m=p->s;
if (p->pre->s==0){
p->s=0,p->n--;
Node *q=ins(p,m^3,1),*r=ins(q,0,1);
p->pre->n--;
check(p->pre);
ins(p->pre,m,1);
check(p);
break;
}
else{
p->s=0,p->n--;
Node *q=ins(p,m^3,1),*r=ins(q,0,1);
p->pre->n--;
p=p->pre;
z--;
check(p->suc);
if (z==0)
ins(p,3,1);
p=check(p);
}
}
}
}
else
lst=ins(lst,s[i]|t[i]<<1,1);
for (Node *p=lst;p!=fir;p=p->pre)
for (int i=0;i<p->n;++i)
ans[cnt++]=p->s;
print(0),print(1);
return 0;
}