Codeforces Round #843 (Div. 2) A ~ C 题解

A1&A2 Gardener and the Capybaras

题意

简单版本： A1
困难版本： A2
一个字符串，只包含a和b两种字母，请将这个字符串划分为三个非空字符串，使得第二个字符串的字典序最大或最小。困难版本的数据范围要求此题在线性时间复杂度下解决。

思路

就是用分类讨论的思想去构造，具体的构造方法见代码。这种构造题的构造方法很多，顺水推舟就能做出来。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5e5 + 5;
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--){string s;cin>>s;ll n=s.length()-1;if(s[0]=='a'&&s[n]=='a'){cout<<"a"<<" ";for(ll i=1;i<n;i++)cout<<s[i];cout<<" ";cout<<"a"<<endl;}else if(s[0]=='b'&&s[n]=='b'){cout<<"b"<<" ";for(ll i=1;i<n;i++)cout<<s[i];cout<<" ";cout<<"b"<<endl;}else if(s[0]=='a'&&s[n]=='b'){cout<<"a"<<" ";if(s[1]=='a'){cout<<"a"<<" ";for(ll i=2;i<=n;i++)cout<<s[i];cout<<endl;}else{for(ll i=1;i<n;i++)cout<<s[i];cout<<" ";cout<<"b"<<endl;}}else{cout<<"b"<<" ";if(s[1]=='a'){cout<<"a"<<" ";for(ll i=2;i<=n;i++)cout<<s[i];cout<<endl;}else{for(ll i=1;i<n;i++)cout<<s[i];cout<<" ";cout<<"a"<<endl;}}}return 0;
}

B. Gardener and the Array

题意

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

思路

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

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
vector<ll> v[maxn];
map<ll,ll> 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;j<k;j++){ll 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 \geq n$ ，使得 $n\&(n+1)\&……\&m=x$ 。

思路

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

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

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

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

代码

#include<bits/stdc++.h>
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;i<max(cntn,cntx);i++){if(bitn[i]==0&&bitx[i]==1){flag=false;break;}}ll pos=-1;for(ll i=0;i<max(cntn,cntx);i++){if(bitn[i]==1&&bitx[i]==0)pos=i;}for(ll i=0;i<max(cntn,cntx);i++){if(bitn[i]==1&&bitx[i]==1){if(pos>i){flag=false;break;}}}if(flag==false)cout<<-1<<endl;else{if(pos==-1)cout<<n<<endl;else if(bitn[pos+1]==1&&bitx[pos+1]==1)cout<<-1<<endl;else{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<cntn;i++)m[i]=bitn[i];ll ans = 0;for(ll i=0;i<cntn;i++)ans+=(1LL<<i)*m[i];cout<<ans<<endl;}}}return 0;
}