The same thinking field.

A. Average Height

Give an array and ask to rearrange its elements to meet a i + a i + 1 2 \frac {a_i+a_{i+1}}{2} 2ai + ai+1 ， is an integer i i i as much as possible.
Practice: it's easy to think of putting odd numbers together and even numbers together to meet the requirements i i i most.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[2020], b[2020];
int t;
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		t = 0;
		for(int i = 1; i <= n; i++) cin >> a[i];
		for(int i = 1; i <= n; i++)
		{
			if(a[i] & 1) b[++t] = a[i];
		}
		for(int i = 1; i <= n; i++) if(a[i] % 2 == 0) b[++t] = a[i];
		for(int i = 1; i <= n; i++)
		{
			cout << b[i];
			if(i == n) cout << endl;
			else cout << ' ';
		}
	}
	return 0;
}

B. TMT Document

Give a string s s s. Ask if you can s s s is divided into several disjoint sequences, and each sequence is TMT. If YES, output YES; otherwise, output NO.
Practice: think about it, that is, there must be an available t in front of each M, and there must be an available t behind it, and the total number of T is the length of the string 2 3 \frac {2}{3} 32, YES, otherwise NO. By prefix and before recording i i In i characters, the number of T and M is enough. Check from front to back and from back to front. And don't forget to check the quantity of T 2 3 n \frac {2}{3}n 32​n.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
char s[N];
int n, f, cnt[N], pre;
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> s + 1;
		f = 1;
		pre = 0;
		for(int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + (s[i] == 'T');
		if(cnt[n] * 3 != n * 2) f = 0;
		for(int i = 1; i <= n; i++)
		{
			if(s[i] == 'M')
			{
				if(cnt[i - 1] < pre + 1)
				{
					f = 0;
					break;
				}
				else pre++;
			}
		}
		pre = 0;
		for(int i = n; i >= 1; i--)
		{
			if(s[i] == 'M')
			{
				if(cnt[n] - cnt[i - 1] < pre + 1)
				{
					f = 0;
					break;
				}
				else pre++;
			}
		}
		cout << (f? "YES" : "NO") << endl;
	}
	return 0;
}

C. The Sports Festival

I guessed it was DP during the game, but I couldn't define the state for half a day. I found it was interval DP by checking the official problem solution. I can only say that I didn't master interval DP very well.
Give an array a a a. Definition d i d_i di is a a a array, before i i The difference between the maximum value and the minimum value in the number of i is now required to be rearranged a a a array so that ∑ i = 1 n b i \sum_{i=1}^{n}b_i Σ i=1n bi min.
Practice (official solution): first, sort the original array. set up d p [ l ] [ r ] dp[l][r] dp[l][r] stands for interval [ l , r ] [l,r] After reordering the elements in [l,r], the smallest d d Sum of d. Transfer equation: d p [ l ] [ r ] = s [ r ] − s [ l ] + m i n ( d p [ l + 1 ] [ r ] , d p [ l ] [ r − 1 ] ) dp[l][r]=s[r]-s[l]+min(dp[l+1][r],dp[l][r-1]) dp[l][r]=s[r]−s[l]+min(dp[l+1][r],dp[l][r−1]). Each represents the decision to add a larger value from the end of the array or a minimum value in front of the interval.
Why are there only two kinds of decisions?
Because through example 2, we can find that making the global maximum and minimum appear at the extreme of the array as much as possible can make the new sum less than or equal to the original, at least not increase. The way to delay the appearance of the global maximum and global minimum is to move the global maximum and minimum to both ends of the array, and how to move it needs to be dp solved.
Several examples are easy to understand:

5
1e9 1e9-1 1e9-2 1e9-3 1

5
1 2 3 4 1e9

6
3 3 3 6 6 1

Since this dp depends on the optimal value of the subsequent state, it is not recommended to use the loop to solve it, and use the memory search to solve it. obviously d p [ i ] [ i ] = 0 dp[i][i]=0 dp[i][i]=0.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2020;
const ll INF = 0X3F3F3F3F3F3F3F3F;
int n, s[N], b[N];
ll dp[N][N];
ll dfs(int l, int r)
{
	if(dp[l][r] != -1) return dp[l][r];
	if(l == r) return 0;
	return dp[l][r] = min(dfs(l + 1, r), dfs(l, r - 1)) + s[r] - s[l]; 
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> s[i];
	sort(s + 1, s + 1 + n);
	memset(dp, -1, sizeof(dp));
	cout << dfs(1, n) << endl;
	return 0;
}

D. Binary Literature

Give a number n n n and 3 lengths 2 n 2n 2n different 01 strings, it is required to construct a string with a length of no more than 3 n 3n 3n so that its length is 2 n 2n The subsequence of 2n contains at least two given strings.
Practice (official solution): if there is no length limit, we can directly splice and output the two given strings. Now that there is a length limit, what should I do? First, we notice that the original question does not require substring, but that the substring contains the given string. Then, 0 / 1 in one position can be shared by multiple subsequences. If a common location is available ≥ n \ge n ≥ n, the length can be further reduced to 3 n 3n Within 3n.
Note that the given string is 01 string, so if the number of one character is insufficient n n n. Then the number of other characters must be greater than n n n. It can be known from the drawer principle that the number of two strings 0 in the three strings must be greater than n n n or the number of two strings 1 is greater than n n n. Therefore, the answer can be constructed.
Since the question does not require to minimize the length of the answer string, we reduce the length of the answer string to 3 n 3n 3n is enough. Suppose that the number of zeros of two strings is greater than n n n. We first construct a string 0000... (n), representing the common 0. Then set the front n n n zeros separate two strings into s 1 , s 2 . . s_1,s_2.. s1​,s2​.. and t 1 , t 2 . . t_1,t_2.. t1​,t2​..， Then we just need to s 1 + t 1 s_1+t_1 s1 + t1 before inserting the first 0 of all zero string, s 2 + t 2 s_2+t_2 s2 + t2 ￠ is inserted between the first and second zeros of the all zero string... And so on. (although the code is not implemented in this way, it means this.).
The number of two strings 1 is greater than n, which is a similar process.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string s;
vector<string> s0, s1;
string mix(string s, string t, char c)
{
	vector<int> v1, v2;
	v1.push_back(-1);
	v2.push_back(-1);
	for(int i = 0; i < 2 * n; i++)
	{
		if(s[i] == c) v1.push_back(i);
		if(t[i] == c) v2.push_back(i);
	}
	string res = "";
	for(int i = 0; i < n; i++)
	{
		for(int j = v1[i] + 1; j < v1[i + 1]; j++) res += s[j];
		for(int j = v2[i] + 1; j < v2[i + 1]; j++) res += t[j];
		res += c;
	}
	for(int j = v1[n] + 1; j < 2 * n; j++) res += s[j];
	for(int j = v2[n] + 1; j < 2 * n; j++) res += t[j];
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		s0.clear();
		s1.clear();
		for(int i = 1; i <= 3; i++)
		{
			cin >> s;
			int cnt = 0;
			for(int j = 0; j < 2 * n; j++) cnt += s[j] == '0';
			if(cnt >= n) s0.push_back(s);
			else s1.push_back(s);
		}
		if(s0.size() > 1) cout << mix(s0[0], s0[1], '0') << endl;
		else cout << mix(s1[0], s1[1], '1') << endl;
	}
	return 0;
}