Codeforces Round #806 (Div. 4)

Submission

A. YES or YES?

label

violence

The question

Given length is 3 String , Judge whether the string is YES ( Case insensitive ).

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
    
		string s;cin>>s;
		if(s=="YES" or s=="YEs" or s=="Yes" or s=="yes" or s=="yES" or s=="yeS" or s=="YeS" or s=="yEs") cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

B. ICPC Balloons

label

simulation

The question

Given a string of uppercase letters , Every letter is 1 Times appear to get 2 A balloon , Every time after that 1 Times obtained 1 A balloon , Ask how many balloons you get in total .

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
    
		int n;cin>>n;
		string s;cin>>s;
		int a[30]={
    0};
		for(auto i:s) a[i-'A'+1]++;
		int ans=0;
		FOR(i,1,26) if(a[i]>0) ans+=a[i]+1;
		cout<<ans<<endl;
	}
	return 0;
}

C. Cypher

label

simulation

The question

Given that there is n A code lock of gears , Know the last password lock state and the operation of the rotating gear , Find the initial state of the password lock .

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define mem(a) memset((a),0,sizeof(a))
using namespace std;

#define int long long

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
    
		int n;cin>>n;
		int ed[1000]={
    0};
		FOR(i,1,n) cin>>ed[i];
		string op[1000];
		FOR(i,1,n){
    
			int len;cin>>len;
			cin>>op[i];
			for(auto j:op[i]){
    
				if(j=='U') ed[i]--;
				if(j=='D') ed[i]++;
				if(ed[i]>9) ed[i]-=10;
				if(ed[i]<0) ed[i]+=10;
			}
		}
		FOR(i,1,n) cout<<ed[i]<<" ";
		cout<<endl;
	}
	return 0;
}

D. Double Strings

label

STL, violence

The question

Given n A string $s[i],i\in [1,n],$ Judge s[i] = s[j] + s[k] Is it true , j And k Could be the same .

Each string is no longer than 8.

Ideas

Traverse s[i], Put each s[i] Split into left and right sections , use hash The table judges whether these two paragraphs exist , If there is , s[i] = s[j] + s[k] establish .

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

vector<string> v;
unordered_map<string,int> mp;

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
    
		int n;cin>>n;
		v.clear();
		mp.clear();
		FOR(i,0,n-1){
    
			string s;cin>>s;
			v.push_back(s);
			mp[s]=1;
		}
		string ans;
		for(string i:v){
    
			int has=0;
			FOR(j,0,i.size()-1){
    
				string l,r;
				l=i.substr(0,j+1);
				r=i.substr(j+1);
				if(mp[l] and mp[r]) {
    has=1;break;}
			}
			if(has) ans+='1';
			else ans+='0';
		}
		cout<<ans<<endl;
	}
	return 0;
}

E. Mirror Grid

label

structure

The question

Given n * n Of 01 matrix , You can flip it every time 1 Lattice (0→1 or 1→0), Find the matrix rotation 90 degree , 180 degree , 270 The minimum number of operations required to be the same as the original matrix after degree .

Ideas

Find out (i, j) After spinning 3 One point is that (j, n-i+1), (n-j+1, i), (n-i+1, n-j+1).

Just count this 4 A little bit , 0 Just take it 0 change 1, 1 Just take it 1 change 0.

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define mem(a) memset((a),0,sizeof(a))
using namespace std;

int matx[107][107];

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
    
		int n;cin>>n;
		mem(matx);
		FOR(i,1,n){
    
			FOR(j,1,n){
    
				char c;cin>>c;
				if(c=='1') matx[i][j]=1;
			}
		}
		int ans=0;
		FOR(i,1,n){
    
			FOR(j,1,n){
    
				int sum=matx[i][j]+matx[j][n-i+1]+matx[n-j+1][i]+matx[n-i+1][n-j+1];
				ans+=min(4-sum,sum);
				if(sum>=2){
    
					matx[i][j]=matx[j][n-i+1]=matx[n-j+1][i]=matx[n-i+1][n-j+1]=1;
				}
				else{
    
					matx[i][j]=matx[j][n-i+1]=matx[n-j+1][i]=matx[n-i+1][n-j+1]=0;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

F. Yet Another Problem About Pairs Satisfying an Inequality

label

structure

The question

Given length is n Array of A, Count how many are right $(i,j),1\le i,j\le n$ Satisfy $A_i<i<A_j<j$.

Ideas

Using arrays a Save the given A, If A[i] dissatisfaction A[i] < i Then it is not stored in the array .

a Copy 1 Copy to the array b, a Sort by numerical value , b according to A Array subscript sorting when saving .

Traversal array a, Find the closest a[i]. The number Of b[j]. Subscript bring Subscript < The value holds . such , All in b[j] All the previous elements meet the conditions of the topic , Add up the answers .

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define mem(a) memset((a),0,sizeof(a))
using namespace std;

#define int long long
const int N=2e5+7;

struct node{
    
	int v,idx;
};

vector<node> a,b;

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--){
    
		a.clear();
		int n;cin>>n;
		FOR(i,1,n){
    
			int v; cin>>v;
			if(v>=i) continue;
			a.push_back({
    v,i});
		}
		b=a;
		sort(a.begin(),a.end(),[](node &x, node &y){
    return x.v<y.v;});
		sort(b.begin(),b.end(),[](node &x, node &y){
    return x.idx<y.idx;});
		int ans=0;
		for(auto i:a){
    
			int l=0,r=b.size()-1;
			while(l<r){
    
		        int mid=(l+r)/2;
		        if(b[mid].idx<i.v) l=mid+1;
		        else r=mid;
		    }
		    ans+=r;
		}
		cout<<ans<<endl;
	}
	return 0;
}

G. Good Key, Bad Key

label

greedy , Dynamic programming

The question

Given n A box , In every box there is a[i] A coin , The order of opening the box must be 1 -> n.

There are good keys and bad keys , Each good key costs k Coins to buy , Allow unlimited debt .

After using the bad key , All the next boxes ( Including the box being opened ) Halve the coins in ( Rounding down ).

There were no keys at first , Find the maximum number of coins you can get .

Ideas

Give priority to using the key , Then it's always best to use only bad keys .

Follow this idea to simulate , Be careful $ \log_2 1e9 = 29.9$, When verifying a bad key, you only need to verify at most 30 Just one .

Code

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;

#define int long long
const int N = 1e5+7;
int a[N],pre[N];

void solve(){
    
	int n,k;
	cin>>n>>k;
	FOR(i,1,n){
    
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
	}
	int ans=-1e9,sum=0;
	FOR(i,0,n){
    
		sum = -i*k;
		sum += pre[i];
		FOR(j,i+1,n){
    
			if(j-i-1>32)break;
			sum += a[j]>>(j-i);
		}
		ans=max(ans,sum);
	}
	cout<<ans<<endl;
}

signed main(){
    
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
    while(T--){
    
        solve();
    }
	return 0;
}