bitmasks

B. AND Reconstruction

对于bi 而言，如果bi的第j位是1的话，那么ai 和 ai+1的第j位也必须是1，如果是0的话，实际上只需要该位满足不全为1就行了，那么我们可以先将其设置为0，后续如果需要该位为1则用|操作完成，这样构造一定是合法的，随后遍历看看是否都符合就行

#include <iostream>
#include <cstring>
#define N 100010
using namespace std;

int T, n, a[N], b[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--)
	{
		memset(a, 0, sizeof(a)); //多测记得清空
		cin >> n;
		for (int i = 1; i < n; i++) cin >> b[i];
		for (int i = 1; i < n; i++)
			for (int j = 0; j <= 30; j++)
				if (b[i] >> j & 1) a[i] |= 1 << j, a[i + 1] |= 1 << j;
		bool flag = 1;
		for (int i = 1; i < n; i++) if ((a[i] & a[i + 1]) != b[i]) {flag = 0; break;}
		if (flag) {
			for (int i = 1; i <= n; i++) cout << a[i] << ' ';
			cout << '\n';
		}
		else cout << -1 << '\n';
	}
	return 0;
}

B. Turtle and an Infinite Sequence

明显，对于|操作而言，只要某位是1，之后无论如何操作该位都为1，该题中，明显最长只有l=max(0,n-m)至r=n+m这一段闭区间上的1可以扩散到n上面，那么答案即为这一段闭区间的数的相互|异或值，但若遍历一整个区间，为o(n)=1e9,显然不行，考虑位运算，设置一个从0 一直到最接近r的1000....的中间变量sum,每次用其和l进行异或运算，当sum|L>=R的时候，说明已经结束

证明很简单

如

a=100101011100

b=101000000000

对于[a,b]的|值，把a一直加到

c=100111111111

a=100101011100

b=101000000000

就是若ab二进制长度不同则先用0把a补齐，随后从左往右找到第一个不相同的数，这个数开始到结尾的这一段二进制数都用1填充，

再将这个11..111与b进行或操作即可

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N];
void solve()
{
    int n,m;scanf("%d%d",&n,&m);
    int l=max(0,n-m),r=n+m;
    int sum=0;
    while((l|sum)<r)
    {
    	sum<<=1;sum=sum|1;
	}
	cout<<(sum|l)<<endl;
	
}
int main()
{
	int t;scanf("%d",&t);
	while(t--)
	{
		solve();
	}
}

A. Find Minimum Operations

直觉，把n转化为k进制数，再把每位上的数字相加

对了，例如一个k进制数154=1k^2+5*k1+4k^0

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
void solve()
{
	int n,k;cin>>n>>k;int ans=0;
	if(k==1)
	{
		cout<<n<<endl;return ;
	}
	while(n)
	{
		ans+=n%k;
		n=n/k;
	}
	cout<<ans<<endl;
}
int main()
{
	int t;cin>>t;
	while(t--)
	{
		solve();
	}
}