Codeforces Global Round 19(A~D)

The ten thousand year supplementary question is strange ~

A. https://codeforces.com/contest/1637/problem/A

The question ：

Given a length of n Array of numbers , from 1 To n-1 Choose any number as len
Then check before len Is the sequence of elements and the subsequent sequence of elements in ascending order , If not, sort them separately
Now ask if you can sort the given array

analysis ： In fact, it is to check whether the array is in ascending order

AC Code：

#include <iostream>
using namespace std;
int t,n;
int main()
{
	cin >>t;
	while(t--)
	{
		cin >>n;
		int temp = -1,x,ans = 1;	
		for(int i = 1; i <= n; i++){
			cin >>x;
			if(temp > x) ans = 0;
			temp = x;
		}	
		if(ans) cout <<"NO" <<endl;
		else cout <<"YES" <<endl;
	}
    return 0;
}

B. https://codeforces.com/contest/1637

The question ：

Given length is n Array of

Definition ： Each subsequence is divided into k paragraph , Then the value of this subsequence is k+MEX( Subsequence elements ).

Find the maximum value of the sum of the values of all subsequences

analysis ：

Last time cf Of MEX The problem made me choke , It took me a long time to understand this question , Can't understand English ...

First ：

To be the most valuable , It is best to divide each element into a segment

So if an element is 0, The value of contribution is 1 +MEX0  = 2;

If it's other elements , The value of contribution is 1 + 0 = 1

Then think about the code ：

My last step requires the sum of the values of all subsequences , That's many times 1 and 2 Add up , To avoid double counting , You can directly input a[i] Change to the value it can contribute .

As for the final optimization ：

Since it is all subsequences , Then the number of occurrences of each element has a fixed relationship with its position , According to the conclusion, it is not impossible to sum directly when inputting , That is to say sum += Contribution value * Number of occurrences , This will eliminate n^3 Subsequence traversal

The code will not write ~

C. https://codeforces.com/contest/1637/problem/C

The question ：

Given a length of n Array of , To operate ： selected i<j<k, a[j]>=2, a[j] reduce 2,a[i] and a[k] Add one

ask ： At least how many times such operations can turn all array elements except the beginning and end into 0, If it cannot be achieved, output -1

analysis ：

First think about the simplest

There is an even number in the middle , Then I can i,k Point to a[1] and a[n], And then pass by a[j]/2 This operation will a[j] Turn into 0

If it's an odd number , Then I'll use it as i perhaps k, Make it even first .

in other words , Remove the leading and trailing elements , The number of times each element contributes is ： Odd number ,(a[i]+1)/2; even numbers a[i]/2;

After derivation, we can get res = (sum + cnt) /2; sum For elements other than the first and last elements and ,cnt It is an odd number

A special case

All the numbers in the middle are 1, Unable to operate , Output -1

Only 3 Elements , The element in the middle is an odd number , No matter how you operate odd numbers or odd numbers , Output -1

AC Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,cnt,sum;
int a[100010];

int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >>t;
	while(t--){
		sum = cnt = 0;
		cin >>n;
		bool ans = true;
		for(int i=1;i<=n;++i) cin >>a[i];
		//3 Number and the middle number is odd  
		if( n==3 && (a[2]&1) ){
			cout <<-1 <<endl; continue;
		}
		
		for(int i=2;i<n;++i){
			sum += a[i];
			if(a[i]&1) cnt++;
			if(a[i]>1) ans = false;
		}
		// The middle numbers are all 1 
		if(ans) { cout <<-1 <<endl; continue; }
		
		cout <<(sum + cnt)/2 <<endl;
	}
	return 0;
}

D.  https://codeforces.com/contest/1637/problem/D

The question ：

Two lengths are given n Array of , You can perform any number of exchanges ai and bi The operation of , Finally, we should minimize the result of the formula given by the topic , Output minimum result

analysis ：

Observe the given formula ：

In other words, the problem becomes ： After exchanging elements , Minimize the sum of the squares of the respective elements of the two arrays

So you need to list all the elements and possible values , Then find the minimum , Equivalent to a knapsack problem , I write recursion and it explodes directly

Stone or not ？

Problems like this can't be written normally at my level , Membrane guy ~

AC Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,res,res1,sum;
//sum Record the overall elements and 
//res Record the final result ,res1 Record (n-2)... Value 
int a[101],b[101];
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >>t;
	while(t--)
	{
		res = 1e9,sum = 0,res1 = 0;
	//cin 
		cin >>n;
		for(int i = 1; i <= n; i++){
			cin >>a[i];
			res1 += a[i]*a[i]*(n-2);
			sum += a[i];
		}
		for(int i = 1; i <= n; i++){
			cin >>b[i];
			res1 += b[i]*b[i]*(n-2);
			sum += b[i];
		}
		bool dp[n+1][sum+1];
		memset(dp,false,sizeof(dp));
		dp[0][0] = true;
		// Enumerate all possible elements and 
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= sum; j++){
				if(j >= a[i] & dp[i-1][ j-a[i] ]) dp[i][j] = true;
				if(j >= b[i] & dp[i-1][ j-b[i] ]) dp[i][j] = true;
			}	
		} 
		
		
		// Find the formula 2 minimum value  
		for(int i = 1; i <= sum; i++){
			if(dp[n][i]) res = min(res, i*i + (sum-i)*(sum-i));
		}	
		
		cout <<res + res1 <<endl;
	}
    return 0;
}