**Nhắc nhở: hãy đọc kĩ và hiểu được ý tưởng và thuật toán trong hướng dẫn này, không quá phụ thuộc vào code hướng dẫn**
**Trước hết, để làm được bài này thì ta cần phải biết được cách biểu diễn một số trong hệ đếm thập phân dưới dạng hệ đếm nhị phân và ngược lại:**
Để chuyển một số trong hệ đếm thập phân sang nhị phân, ta làm như sau:
Trong khi số đó còn lớn hơn 0, chia số đó cho 2, dùng một xâu để cộng thêm các số dư của số đó trong quá trình chia cho 2.
Đảo ngược xâu kết quả, ta có đáp án của bài toán (1).
Còn để chuyển một dãy nhị phân sang số hệ thập phân thì ta áp dụng ngược lại với cách trên:
Ví dụ gọi dãy bit cần chuyển sang kiểu số hệ thập phân là s, biến kết quả của bài toán là n.
Duyệt xâu s theo chiều từ phải qua trái. Áp dụng ngược công thức (1), trong mỗi lần lặp: n=n*2+s[i]-48;
Ta được n là kết quả bài toán (2).
Trong bài này ta có 3 loại truy vấn:
+ Loại 1: bật bit thứ k
+ Loại 2: tắt bit thứ k
+ loại 3: đảo bit thứ k
**Ý tưởng:**
Gọi st là dãy bit lưu kết quả qua từng truy vấn. Với truy vấn loại 1, st[k]=1. Với truy vấn loại 2, st[k]=0. Với truy vấn loại 3, Nếu st[k]==0 thì st[k]=1, Nếu st[k]==1 thì st[k]=0.
Qua từng truy vấn, ta áp dụng công thức (2) rồi ghi ra kết quả dạng số nguyên.
**Code mẫu C++:**
```
#include <bits/stdc++.h>
using namespace std;
string st="00000000000000000000000000000000";
int k,a,m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
while(n--){
cin>>a>>k;
m=max(m,k);
if(a==1){
st[k]='1';
}else if(a==2)st[k]='0';
else{
if(st[k]=='0')st[k]='1';
else st[k]='0';
}long long s=0;
for(int i=m;i>=0;--i){
s=s*2+st[i]-48;
}cout<<s<<'\n';
}
}
```
hvnamyd
Created at
0 likes