Codeforces Round #799 (Div. 4)

link

A. Marathon

The main idea of the topic

There are four people (a , b , c ,d) running , Ask how many people are a front

Code

int a[N] ; 
 
bool cmp(int a , int b){
	return a > b ;
}
void solve(){
	int aa ;
	for(int i = 1 ; i <= 4 ; i ++ ){
		cin>>a[i]; 
		if(i == 1 ) aa = a[i] ; 
	}
	sort(a + 1 , a + 1 + 4 , cmp) ;
	int res =0 ;
	for(int i = 1 ; i <= 4 ; i ++){
		if(a[i] == aa) break ; 
		res ++ ; 
	}
	cout<<res<<"\n" ; 
 
}

B. All Distinct

The question

n An array of lengths , You can delete two different locations , How long is the longest array left , Two are different

Ideas

Statistics delete a few , If you delete an even number , The answer is different numbers , If it's odd , The answer is different numbers - 1

Code

void solve(){
	int n ;
	read(n) ; 
	map<int , int> mp ; 
	for(int i = 1 ; i <= n ; i ++){
		read(a[i]) ; 
		mp[a[i]] ++ ; 
	}
	int s = n - mp.size() ;
	int res = mp.size() ;
	if(s % 2 )res -- ; 
	cout<<res <<"\n" ; 
 
}

C. Where’s the Bishop?

The question

Each king can attack diagonals and diagonals , Ask the king where he is

Ideas

Check each position

Code

char a[10][10] ; 
 
bool check(int x , int y){
	if(a[x][y] != '#') return false ; 
	for(int i = 1 ; i <= 8 ; i ++ ) {
		int xx = x + 1 , yy = y + 1 ; 
		if(xx <= 8 && yy <= 8) {
			if(a[xx][yy] !='#') return false ; 
		}else break ; 
	}
	for(int i = 1 ; i <= 8 ; i ++ ) {
		int xx = x - 1 , yy = y - 1 ; 
		if(xx >=1  && yy >= 1) {
			if(a[xx][yy] !='#') return false ; 
		}else break ; 
	}
	for(int i = 1 ; i <= 8 ; i ++ ) {
		int xx = x + 1 , yy = y - 1 ; 
		if(xx <= 8 && yy >= 1) {
			if(a[xx][yy] !='#') return false ; 
		}else break ; 
	}
	for(int i = 1 ; i <= 8 ; i ++ ) {
		int xx = x - 1 , yy = y + 1 ; 
		if(xx >= 1 && yy <= 8) {
			if(a[xx][yy] !='#') return false ; 
		}else break ; 
	}
	return true;
} 
 
void solve(){
	for(int i = 1 ; i <= 8 ; i ++ ) {
		for(int j = 1 ; j <= 8 ; j ++ ) {
			cin>>a[i][j] ; 
		}
	}
	for(int i = 2 ; i <= 7 ; i ++  ){
		for(int j = 2 ; j <= 7 ; j ++ ) {
			if(check(i , j )) {
				cout<<i <<" " <<j<<"\n" ; 
				return ; 
			}
		}
	}
}

D. The Clock

The question

At a given time , every other x Look at your watch every minute , How many palindromes can I see

Ideas

Initialize all times , Record the time you have seen , If you haven't seen it at the current time , Check whether it is a palindrome string , If you've seen it before , Jump out of

Code

vector<string>ve; 
map<string , int> mp ; 
int idx ;
void init() {
	
	for(int i = 0 ; i <= 23 ; i ++ ) {
		for(int j = 0 ; j <= 59 ; j ++ ) {
			string str = "" ; 
			if(i < 10 ) str +='0' ,str +='0' + i ;
			else str += i /10 + '0' , str += i % 10 + '0' ; 
			str +=':' ;
			if(j < 10 ) str +='0' ,str +='0' + j ;
			else str += j /10 + '0' , str += j % 10 + '0' ; 
			ve.pb(str) ; 
			mp[str] = ++idx ; 
		}
	}
}
 
bool check(string str){
	if(str[0] == str[4] && str[1] == str[3]) return true;
	else return false ;  
}
 
void solve(){
	string str ; 
	int k ; 
	cin>>str >> k ; 
	int id = mp[str] - 1 ; 
	int res = 0 ; 
	map<int , int > ok; 
	while(true) {
		if(ok[id]) break ; 
		else ok[id] = 1 ; 
		if(check(ve[id])) res ++ ; 
		id += k ; 
		id %= 1440 ; 
	}
	
	cout<<res<<"\n" ;  
}
 
signed main() {
	init() ; 
	
	int t = 1 ;
	read(t) ;
	while(t -- ) solve() ;
	return 0;
}

E. Binary Deque

The question

The length is n Array of , from 0 and 1 constitute , You can delete the first or last , Ask the least number of times , Make the total length of the array s

Ideas

Prefixes and records , Start from the first position , Half the maximum length , Finally, judge whether it is -1

Code

int a[N] , b[N] ; 
void solve(){
	int n , s ; 
 	read(n) , read(s) ; 
 	for(int i = 1 ; i <= n ; i ++ ) read(a[i]) ; 
 	for(int i = 1 ; i <= n ; i ++ ) a[i] += a[i - 1];
 	int res = N ; 
 	for(int i = 1 ; i <= n ; i ++ ) {
 		int l = i , r = n ; 
 		while(l < r ){
			int mid = l + r + 1 >> 1 ; 
			if(a[mid] - a[i - 1]<= s)l = mid; 
			else r = mid - 1 ;  	
		}
		
		if(a[l] - a[i - 1]== s) res = min(res , i - 1 + (n - l)) ; 
		
	}
	if(res == N) res = -1 ; 
	cout<<res <<"\n" ; 
 
}

F. 3SUM

The question

n An array of lengths , Whether there are three positions i, j , k , bring （ai + aj + ak） % 10 == 3

Ideas

The answer only relates to the single digits , Record the number of each number on your list , Again $10^3$ Solve whether the conditions are met

Code

int a[N] , cnt[25]; 
void solve(){
	int n ; 
	read(n) ; 
	map<int , int> mp ; 
	for(int i = 1 ; i <= n ; i ++ ){
		read(a[i]) ; 
		a[i] = a[i] % 10 ;
		mp[a[i]] ++ ;  
	}
	for(int i = 0 ; i < 10 ; i ++ ) {
		cnt[i] = mp[i] ; 
	}
	for(int i = 0 ; i < 10 ; i ++ ) {
		for(int j = 0 ; j < 10 ; j ++ ) {
			for(int k = 0 ; k < 10 ; k ++ ) {
				mp[i] -- ; 
				mp[j] -- ; 
				mp[k] -- ; 
				if(mp[i] >= 0 && mp[j] >= 0 && mp[k] >= 0 ) {
					if((i + j + k) % 10 == 3) {
						cout<<"YES\n" ;
						return ; 
					}
				}
				mp[i] ++ ; 
				mp[j] ++ ; 
				mp[k] ++ ; 
			}
		}
	}
	cout<<"NO\n" ; 
}

G. 2^Sort

The question

Find subscript in [1 , n - k] There are several conditions $2^0$ * a_i < $2^1$ * a_i+1<$2^2$ * a_i+2< ⋯< $2^k$ *a_i+k.

Ideas

Prefixes and records , Whether the current Cheng Yu is greater than the previous one , Sweep it over , Judge whether the current interval is all satisfied

Code

int a[N] , ok[N]; 
void solve(){
	int n , s ;
	read(n) , read(s) ; 
	for(int i = 1 ; i <= n ; i ++ ) {
		read(a[i]) ;
		ok[i] = 0 ; 
	}
	for(int i = 1 ; i < n ; i ++ ) {
		if(a[i + 1 ] * 2 > a[i]) ok[i + 1 ] = 1 ; 
	} 
	
	for(int i = 2 ; i <= n ; i ++ ) ok[i] += ok[i - 1] ; 
	int res = 0 ; 
	for(int i = 1 ; i <= n - s ; i ++){

		if(ok[i + s] - ok[i] == s ) {
			res ++; 
		}
	}
	cout<<res <<"\n" ; 
}

H. Gambling

The question

Given n An array of lengths , Ask for one a , l , r .a Is a number , l Is the table below the left section , r Is the subscript of the right interval . Conditions , The beginning is x = 1 , Start from the left section , identical x×=2 , Different x/=2 , requirement x Value is the largest

Ideas

Put the same values together , The current value is the previous bit and there are several differences between this bit *2 , Scan the maximum value , to update

Code

int a[N] ;
vector<int> ve[N] ;  

void solve(){
   int n ; 
   read(n) ;
   int id = 0 ; 
   for(int i = 1 ; i <= n ; i ++ ) ve[i].clear() ; 
   map<int , int> mpid ;  
   map<int , int> mpnum ; 
   for(int i = 1 ; i <= n ; i ++ ) {
   	read(a[i]) ;
   	if(mpnum[a[i]] == 0 ) {
   		mpnum[a[i]] = ++ id ; 
   		mpid[id] = a[i] ; 
   	}
   	ve[mpnum[a[i]]].push_back(i) ; 
   }

   int ansmaxx = 0 , l = -1 , r = -1 ,idans; 
   for(int i = 1 ; i <= id ; i ++ ) {
   	vector<int> all ; 
   	all.push_back(0) ; 
   	for(int j = 1 ; j < ve[i].size() ; j ++ ) {
   		all.push_back(all[j - 1] - (ve[i][j] - ve[i][j - 1] - 1) + 1) ; 
   	}

   	int minn = 0 , minnid = ve[i][0] ;
   	for(int j = 0 ; j < ve[i].size() ; j ++ ) {
   		if(all[j] - minn >= ansmaxx ) {
   			ansmaxx = all[j] - minn ; 
   			idans = i ; 
   			
   			l = minnid ; 
   			r = ve[i][j];
   		}
   		if(all[j] <= minn ) {
   			minn = all[j] ; 
   			minnid = ve[i][j];
   		}
   	} 
   	
   	
   }
   cout<<mpid[idans]<<" " << l<<" " <<r <<"\n" ;

   
}