积累模拟经验
题目描述
维护一个二进制数，支持如下操作
- "+" 该数加 11
- "-" 该数减 11
- "*" 该数乘 22
- "" 该数除 22 并下取整
保证操作过程中不会出现负数
输入格式
第一行 n,m 表示原数和指令的长度
第二行 一个 01 串，从高位到低位表示一个二进制数
第三行 指令
输出格式
输出操作后的数，二进制，无前导 0
题目分析
延迟处理进退位
1 #include<bits/stdc++.h> 2 const int maxn = 5000035; 3 4 int n,m,a[maxn<<1],lens; 5 char s[maxn],t[maxn]; 6 7 int main() 8 { 9 scanf("%d%d%s%s",&n,&m,s+1,t+1); 10 lens = n; 11 for (int i=1; i<=n; i++) a[i] = s[i]-'0'; 12 for (int i=1; i<=m; i++) 13 { 14 if (t[i]=='+') a[lens]++; 15 if (t[i]=='-') a[lens]--; 16 if (t[i]=='*') a[++lens] = 0; 17 if (t[i]=='/'){ 18 if (a[lens] < 0) 19 a[lens-1] -= (-a[lens]+1)>>1; 20 else a[lens-1] += a[lens]>>1; 21 a[lens--] = 0; 22 } 23 } 24 for (int i=lens; i; i--) 25 if (a[i] < 0) 26 a[i-1] -= (-a[i]+1)>>1, a[i] = (-a[i])&1; 27 else a[i-1] += a[i]>>1, a[i] = a[i]&1; 28 for (int i=1; i<=lens; i++) putchar(a[i]+'0'); 29 return 0; 30 }
END