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

A1&A2 Gardener and the Capybaras

Title meaning

Simple version: A1
Hard version: A2
A string contains only two letters a and b. Please divide this string into three non-empty strings so that the lexicographical order of the second string is the largest or the smallest. The data range of the hard version requires that the problem be solved in linear time complexity.

train of thought

It is to use the idea of ​​​​classification and discussion to construct. See the code for the specific construction method. There are many ways to construct this kind of construction question, and it can be done by pushing the boat along the way.

the code

#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

Title meaning

topic link
It is to give you an array, the numbers in this array are all large numbers, represented by binary bits. Ask whether it is possible to select two different sub-arrays so that all the numbers in the two sub-arrays have the same bitwise OR value.

train of thought

Since it is a large number and the data range is not clear enough, this question needs to open a dynamic array and key-value pair storage. To put it bluntly, for each digit of a certain large number, it is satisfied: if this digit is 1, and at least one of the other large numbers is also 1 in this digit, then it meets the meaning of the question.

the code

#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

Title meaning

topic link
Find the smallest m ≥ n m≥n m≥n such that n & ( n + 1 ) & ... ... & m = x n\&(n+1)\&......\&m=x n&(n+1)&......&m=x.

train of thought

Discuss in four situations, each for a certain person i i The specific situation of i:
① n i = 0 , x i = 0 n_{i}=0,x_{i}=0 ni​=0,xi​=0, which has no effect on the answer.
② n i = 1 , x i = 0 n_{i}=1,x_{i}=0 ni​=1,xi​=0, indicating that in [ n , m ] [n,m] In the range [n,m], there exists at least one number i i i bit is 0 0 0.
③ n i = 0 , x i = 1 n_{i}=0,x_{i}=1 ni​=0,xi​=1, no solution, output − 1 -1 −1.
④ n i = 1 , x i = 1 n_{i}=1,x_{i}=1 ni​=1,xi​=1, indicating that in [ n , m ] [n,m] In the range [n,m], the first of all numbers i i i bits are all 1 1 1.

For ④, once there is ② with a higher bit, it is illegal. because one by one & \& In the process of &, we will inevitably encounter 0 0 0 case. That is, if there is a carry in the high position, then the low position must also become 0 0 0.

The highest bit of all ② is the most influential, we need to find this bit. Then judge whether there is ④ in a bit smaller than this bit. If present, output − 1 -1 −1.

Assume that the most significant ② is p o s pos pos, then the final answer is:
turn out to be n n position ratio on n p o s pos big pos p o s + 1 pos+1 pos+1 this position 1 1 1. This one is preceded by 0 0 0, the back is the original n n The binary digit value of n. if it turns out n n on n p o s + 1 pos+1 pos+1 this one is 1 1 1, then p o s pos The pos bit is 0 0 0, p o s + 1 pos+1 The pos+1 bit will inevitably produce a carry, then the original bit of this bit 1 1 1 necessarily becomes 0 0 0, ④ is not satisfied, so the output − 1 -1 −1.

the code

#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;
}

experience

The style of the questions in this competition is very similar. It is basically the operation of binary digits or two characters. Each question has a lot of details. During the competition, it is necessary to clarify each situation one by one on the draft paper and analyze a few more samples.

Tags: C++ Programming Algorithm ICPC CodeForces acm

Posted by cbullock on Thu, 12 Jan 2023 20:11:38 +0300