B. Gardener and the Array

题意

题目链接
就是给你一个数组，这个数组中的数都是大数，用二进制位表示。问能不能选出两个不同的子数组，使得这两个子数组各自所有的数按位或的值相同。

思路

由于是大数，而且数据范围不够明确，这个题需要开动态数组和键值对存储。说白了，对于某一个大数的每一位，都满足：如果这一位是1，而且其他大数中至少有一个在这一位上也是1，那就符合题意。

代码

#include
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
vector v[maxn];
map cnt;
int main(){//ios::sync_with_stdio(0);//cin.tie(0),cout.tie(0);ll t;scanf("%lld",&t);while(t--){ll n;scanf("%lld",&n);for(ll i=1;i<=n;i++)v[i].clear();cnt.clear();ll bit = -1e9;for(ll i=1;i<=n;i++){ll k;scanf("%lld",&k);for(ll j=0;jll x;scanf("%lld",&x);bit=max(bit,x);v[i].push_back(x);}}for(ll i=1;i<=n;i++){for(auto j: v[i]){cnt[j]++;}}bool flag=false;for(ll i=1;i<=n;i++){bool f=true;for(auto j: v[i]){if(cnt[j]==1){f=false;break;}}if(f==true){flag=true;break;}}if(flag==true)printf("Yes\n");else printf("No\n");}return 0;
}

C. Interesting Sequence

题意

题目链接
求出最小的m≥nm≥nm≥n，使得n&(n+1)&……&m=xn\&(n+1)\&……\&m=xn&(n+1)&……&m=x。

思路

分四种情况讨论，分别看对于某一位iii的具体情况：
① ni=0,xi=0n_{i}=0,x_{i}=0ni​=0,xi​=0，对答案不构成影响。
② ni=1,xi=0n_{i}=1,x_{i}=0ni​=1,xi​=0，说明在[n,m][n,m][n,m]范围内，至少存在一个数的第iii位是000。
③ ni=0,xi=1n_{i}=0,x_{i}=1ni​=0,xi​=1，无解，输出−1-1−1。
④ ni=1,xi=1n_{i}=1,x_{i}=1ni​=1,xi​=1，说明在[n,m][n,m][n,m]范围内，所有数的第iii位都是111。

对于④，一旦存在有更高位的②，那么就不合法。因为在逐个&\&&的过程中必然会遇上000的情况。即高位有进位，那么低位也必然都变成000。

所有②的最高位是影响最大的，我们需要找到这个位。然后判断是否在比这个位小的位上存在④。如果存在，输出−1-1−1。

假设最高位的②是pospospos，那么最终答案就是：
原来nnn上位置比pospospos大的pos+1pos+1pos+1这一位置111，这一位前面都是000，后面就是原来nnn的二进制位数值。如果原来nnn上的pos+1pos+1pos+1这一位就是111，那么pospospos位是000，pos+1pos+1pos+1位必然产生进位，那么这一位原来的111必然成为000，就不满足④，因此输出−1-1−1。

代码

#include
using namespace std;
typedef long long ll;
const ll maxn = 64 + 5;
ll bitn[maxn],bitx[maxn],m[maxn];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--){ll n,x;cin>>n>>x;memset(bitn,0,sizeof(bitn));memset(bitx,0,sizeof(bitx));ll cntn=0,cntx=0;ll nn=n,xx=x;while(nn){bitn[cntn++]=(nn&1);nn=nn>>1;}while(xx){bitx[cntx++]=(xx&1);xx=xx>>1;}bool flag=true;for(ll i=0;iif(bitn[i]==0&&bitx[i]==1){flag=false;break;}}ll pos=-1;for(ll i=0;iif(bitn[i]==1&&bitx[i]==0)pos=i;}for(ll i=0;iif(bitn[i]==1&&bitx[i]==1){if(pos>i){flag=false;break;}}}if(flag==false)cout<<-1<if(pos==-1)cout<for(ll i=0;i<=pos;i++)m[i]=0;m[pos+1]=1;if(pos+1==cntn)cntn++;for(ll i=pos+2;i