Bit operation notes
Nature 1: ( x + y ) = ( ( x & y ) < < 1 ) + ( x ⊕ y ) \large (x+y)=((x\& y)<<1)+(x\oplus y) (x+y)=((x&y)<<1)+(x⊕y)
Nature 2: ( x + y ) (x+y) (x+y) and ( x ⊕ y ) (x\oplus y) (x ⊕ y) same parity
Nature 3: ( x + y ) ≥ ( x ⊕ y ) (x+y)\ge (x\oplus y) (x+y)≥(x⊕y)
Nature 4: ( x + y ) = ( x ⊕ y ) (x+y)=(x\oplus y) (x+y)=(x ⊕ y), etc. and only if ( x & y = 0 ) (x\& y=0) (x&y=0)
XOR operation is equivalent to non carry addition.
So property 3 is proved.
And from property 1 we know △ = [ ( x + y ) − ( x ⊕ y ) ] ( m o d 2 ) = 0 \triangle=[(x+y)-(x\oplus y)]\pmod{2}=0 △=[(x+y)−(x⊕y)](mod2)=0
So property 2 is proved.
D. Plus and xor
Given two numbers A + B A+B Sum of A+B X X 10. X OR sum Y Y Y. Beg ( A , B ) (A,B) (A,B) is there and A A The minimum nonnegative integer solution of A.
Using properties 2 and 3 to judge the solution, and then using properties to construct A = X − Y 2 , B = X − A A=\dfrac{X-Y}{2},B=X-A A=2X−Y,B=X−A
Pay attention at this time A ⊕ B A\oplus B A ⊕ B is not necessarily equal to Y Y Y.
We can understand this:
X − Y 2 + X − Y 2 + Y = X \dfrac{X-Y}{2}+\dfrac{X-Y}{2}+Y=X 2X−Y+2X−Y+Y=X
X − Y 2 ⊕ X − Y 2 ⊕ Y = X \dfrac{X-Y}{2}\oplus \dfrac{X-Y}{2}\oplus Y=X 2X−Y⊕2X−Y⊕Y=X
B = X − Y 2 + Y , B = X − Y 2 ⊕ Y B=\dfrac{X-Y}{2}+Y,B=\dfrac{X-Y}{2}\oplus Y B=2X−Y+Y,B=2X−Y⊕Y
Then it is required: X − Y 2 + Y = X − Y 2 ⊕ Y \dfrac{X-Y}{2}+Y=\dfrac{X-Y}{2}\oplus Y 2X−Y+Y=2X−Y⊕Y
Then according to nature 4 X − Y 2 & Y = 0 \dfrac{X-Y}{2}\& Y=0 2X−Y&Y=0
Only when this condition is satisfied can the solution be constructed.
code
int main(){
ull x,y;scanf("%llu%llu",&x,&y);
ll z=(x-y)>>1;
if( x<y || (x-y)&1 || z&y ) return puts("-1"),0;
else printf("%llu %llu\n",z,x-z);
return 0;
}
Nature 5: ( x & y ) + ( x ∣ y ) = ( x + y ) (x\& y)+(x|y) =(x+y) (x&y)+(x∣y)=(x+y)
F. Anton and School
Construct A A A.
Nature 5: ( x & y ) + ( x ∣ y ) = ( x + y ) (x\& y)+(x|y) =(x+y) (x&y)+(x∣y)=(x+y)
It can be proved by mathematical induction.
Therefore:
order d i = b i + c i = n a i + ∑ i = 1 n a i \large d_i=b_i+c_i= na_i+\sum\limits_{i=1}^n a_i di=bi+ci=nai+i=1∑nai
t o t = ∑ i = 1 n a i = ∑ i = 1 n d i 2 n = n ∑ i = 1 n a i + n ∑ i = 1 n a i 2 n tot=\large \sum\limits_{i=1}^n a_i=\dfrac{\sum\limits_{i=1}^n d_i}{2n}=\dfrac{n\sum\limits_{i=1}^n a_i+n\sum\limits_{i=1}^na_i}{2n} tot=i=1∑nai=2ni=1∑ndi=2nni=1∑nai+ni=1∑nai
So: a i = d i − t o t n \large a_i=\dfrac{d_i-tot}{n} ai=ndi−tot
So you can find all the values a i a_i ai #.
But we also need to judge whether the unique solution exists.
We can use it a i a_i ai reverse launch b i , c i b_i,c_i bi, ci ， and then with a given b i , c i b_i,c_i bi, ci} contrast.
Specifically, it is processed by bit.
Preprocess out array A A The number of 1 bits per bit in A.
Code reference problem solution
code
#include <iostream>
using namespace std;
const int max_n = 300000;
int n;
int b[max_n];
int c[max_n];
int a[max_n];
int d[max_n];
int b1[max_n];
int c1[max_n];
int bits[31][max_n];
int kbit[31];
int main()
{
// input
ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0; i < n; i++) d[i] = b[i] + c[i];
// searching for answer
long long sum = 0;
for (int i = 0; i < n; i++) sum += d[i];
sum /= (2 * n);
for (int i = 0; i < n; i++) a[i] = (d[i] - sum) / n;
// checking the answer
for (int i = 0; i < n; i++)
if (a[i] < 0)
{
cout << -1 << endl;
return 0;
}
for (int i = 0; i < 31; i++)
for (int j = 0; j < n; j++)
if ((a[j] & (1LL << i)) == 0)
bits[i][j] = 0;
else
bits[i][j] = 1;
for (int i = 0; i < 31; i++)
{
kbit[i] = 0;
for (int j = 0; j < n; j++)
kbit[i] += bits[i][j];
}
for (int i = 0; i < n; i++) b1[i] = 0;
for (int i = 0; i < n; i++) c1[i] = 0;
for (int i = 0; i < 31; i++)
for (int j = 0; j < n; j++)
{
int bbase = bits[i][j] ? kbit[i] : 0;
int cbase = bits[i][j] ? n : kbit[i];
b1[j] += bbase << i;
c1[j] += cbase << i;
}
for (int i = 0; i < n; i++)
if (b1[i] != b[i] || c1[i] != c[i])
{
cout << -1 << endl;
return 0;
}
// output
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
return 0;
}
B. Magic Forest
Find the number of triangles whose XOR sum of three sides is 0.
Enumerate two edges, and then judge the third edge.
k k k meet: k = i ⊕ j , k ∈ [ j , n ] , i + j > k k=i\oplus j, k\in [j,n], i+j>k k=i ⊕ j,k ∈ [J, n], I + J > K.
int main(){
int n;scanf("%d",&n);
int s=0;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
int k=i^j;
if(k<=n&&k>=j&&(i+j>k)) s++;
}
printf("%d\n",s);
return 0;
}
C. Boboniu and Bit Operations
because a n s ∈ [ 0 , 2 9 − 1 ] ans\in [0,2^9-1] ans ∈ [0,29 − 1] is very small. You can enumerate the answers, and then for each a i a_i ai, find a i & b j ∣ a n s = a n s a_i\& b_j | ans= ans ai &bj ∣ ans = minimum of ANS a n s ans ans is enough.
Time complexity: O ( 2 9 n m ) O(2^9 nm) O(29nm)
In fact, you can only enumerate whether each bit exists, O ( 9 n m ) O(9nm) O(9nm)
#include<bits/stdc++.h>
#define ci const int&
using namespace std;
int n,m,p[210],d[210],ans;
bool Check(ci x){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)if(((p[i]&d[j])|x)==x)goto Next;
return 0;
Next:;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&p[i]);
for(int i=1;i<=m;++i)scanf("%d",&d[i]);
ans=(1<<9)-1;
for(int i=8;i>=0;--i)Check(ans^(1<<i))?ans^=(1<<i):0;
printf("%d",ans);
return 0;
}
A. XOR Equation
Given the XOR sum and additive sum of two numbers, find the number of ordered solutions.
First, there is a solution, and then the answer is: record: c n t = y cnt=y The number of 1 under the binary of cnt=y, a n s = 2 c n t ans=2^{cnt} ans=2cnt.
Because this problem requires a positive integer solution, we should pay attention to removing it 0 0 0.
a n s = 2 c n t − ( x = = y ) × 2 ans=2^{cnt}-(x==y)\times 2 ans=2cnt−(x==y)×2.
int main(){
ll x,y;scanf("%lld%lld",&x,&y);
ll z=(x-y)>>1;
if(x<y || (x-y)&1 || z&y ) return puts("0"),0;
printf("%lld\n",(1LL<<__builtin_popcountll(y))-2*(x==y));
return 0;
}
B. And
given n n n numbers, and one & x \& x &X operation, ask the least operation to make at least two numbers equal.
Obviously, there are only four answers: - 1, 0, 1, 2.
0 directly determines the original array, 1 directly enumerates the modified number, 2 determines that the modified array is equal, and if none of them is - 1.
#include <bits/stdc++.h>
using namespace std;
const int maxm=1e5+5;
int a[maxm],b[maxm];int n,x,y;int r=-1;
int main() {
for(cin>>n>>x;n--;)
{
cin>>y;
if(a[y])r=0;
if(r)if(a[y&x]||b[y])r=1;
if(r&&r!=1)if(b[y&x])r=2;
a[y]=b[y&x]=1;
}
cout<<r;
}
D. Xenia and Bit Operations
The merging operation is the merging of complete binary trees. Consider using segment tree maintenance.
#include<iostream>
#include<stdio.h>
using namespace std;
const int maxx = 1<<18;
int num[maxx];
int ans[maxx<<2];
void build(int l,int r,int rt,int op)
{
if(l==r)
{
ans[rt]=num[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1,1-op);
build(mid+1,r,rt<<1|1,1-op);
if(op==1) ans[rt]=ans[rt<<1]|ans[rt<<1|1];
else ans[rt]=ans[rt<<1]^ans[rt<<1|1];
}
void update(int l,int r,int rt,int index,int value,int op)
{
if(l==r&&l==index)
{
ans[rt]=value;
return;
}
int mid=(l+r)>>1;
if(mid<index)
{
update(mid+1,r,(rt<<1|1),index,value,1-op);
}
else
{
update(l,mid,rt<<1,index,value,1-op);
}
if(op==1) ans[rt]=ans[rt<<1]|ans[rt<<1|1];
else ans[rt]=ans[rt<<1]^ans[rt<<1|1];
}
int main()
{
//cout<<maxx+1<<endl;
int n,m;
scanf("%d%d",&n,&m);
int sum=1<<n;
for(int i=1;i<=sum;i++)
scanf("%d",&num[i]);
build(1,sum,1,n%2);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
update(1,sum,1,a,b,n%2);
printf("%d\n",ans[1]);
}
return 0;
}
B. AGAGA XOOORRR
hold n n n numbers divided into at least 2 2 2 exclusive or and equal intervals.
Maximum score 3 3 3, if greater than 3 3 3, you can merge 3 3 Three are 1 1 1 because: x ⊕ x ⊕ x = x x\oplus x\oplus x=x x⊕x⊕x=x.
Therefore, it only needs to judge whether it can be divided into 2 or 3 intervals.
Preprocessing prefix XOR and.
if p r e [ n ] = 0 pre[n]=0 pre[n]=0, obviously it can be divided into two.
otherwise p r e [ n ] > 0 pre[n]>0 Pre [n] > 0, if it can be divided into three, obviously this x = p r e [ n ] x=pre[n] x=pre[n], because there are an odd number x x x XOR or x x x.
So just O ( n ) O(n) O(n) scan once to judge whether there are more than 3.
If the question is changed to at least k k k exclusive or and equal intervals.
if p r e [ n ] > 0 pre[n]> 0 Pre [n] > 0. Obviously, it can only be divided into odd numbers, and x = p r e [ n ] x=pre[n] x=pre[n], so just O ( n ) O(n) O(n) scan for at least k k k XORs and intervals are p r e [ n ] pre[n] pre[n].
if p r e [ n ] = 0 pre[n]=0 pre[n]=0. You can only enumerate the answers. It seems to be O ( n l o g n ) O(nlogn) O(nlogn).
void solve() {
int n, ans = 0; cin >> n;
int xr = 0;
vi a(n);
F(i, n) {
cin >> a[i];
xr ^= a[i];
}
if(xr == 0){
cout << "YES" << '\n';
}
else{
int t = 0, c = 0;
for(int i=0;i<n;i++) {
t^=a[i];
if(t==xr){
c++;
t = 0;
}
}
if(c >= 3 ){
cout << "YES" << '\n';
}
else{
cout << "NO" << '\n';
}
}
}
B. The Child and Set
Inverted enumeration l i m i t limit limit if l w o b i t ( i ) ≤ n lwobit(i) \le n lwobit(i) ≤ n, then select i i i. Because l o w b i t lowbit In the case of the same lowbit, it is better to select the large number first, so that there are more opportunities to use the small number to gather some missing 1 bits.
#include<bits/stdc++.h>
using namespace std;
int arr1[100009];int main()
{int n,k,l=0;
cin>>n>>k;
for(int i=k;i>=1;i--)
{int t=i&-i;
if(t<=n)
{n-=t;arr1[l++]=i;
if(n==0)break;}
}
if(n>0)cout<<-1;
else
{printf("%d\n",l);
for(int i=0;i<l;i++)
cout<<arr1[i]<<" ";
}
}