个人博客版：http://www.noobzyk.top/?p=692

A. Average Height

分析

堪比div3 A的水题

代码

/**
  * @file    :vsDebug2.cpp
  * @brief   :
  * @date    :2021-04-16
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <deque>
#include <cmath>
#include <algorithm>
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define int long long
const int inf = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
const int maxn = 2005;
int main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		vector<int> odd, even;
        int x;
		for(int i = 0; i < n; ++i){
			cin >> x;
			if(x & 1) odd.push_back(x);
			else even.push_back(x);
		}
		for(int i = 0; i < odd.size(); ++i) cout << odd[i] << ' ';
		for(int i = 0; i < even.size(); ++i) cout << even[i] << ' ';
		cout << endl;
	}
	return 0;
}

B. TMT Document

题意

给一个只含有T，M的字符串，问是否可以分割成若干个不相交的“TMT"子序列。

例如，TMTMTT可以划分成两个TMT（TMTMTT）.

分析

首先，为确保数据合法，保证T的总个数是M的两倍.

然后，从左往右看，保证字符串所有前缀都满足T的数目不小于M的，这样就能保证“TM”序列总是可以划分的。

由于是对称的，再从右往左看，保证“MT”序列总可以划分，即保证了“TMT"总可以划分。

代码

/**
  * @file    :vsDebug2.cpp
  * @brief   :
  * @date    :2021-04-16
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <deque>
#include <cmath>
#include <algorithm>
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define int long long
const int inf = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
 
int main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		int T = 0, M = 0;
		bool flag = 1;
		for(int i = 0; i < s.size(); ++i){
			if(s[i] == 'T') T++;
			else if(s[i] == 'M'){
				M++;
				if(T < M){
					flag = 0;
					break;
				}
			}
		}
		if(T != 2 * M) flag = 0;
		if(!flag){
			cout << "NO" << endl;
			continue;
		}
		T = 0, M = 0;
		for(int i = n - 1; i >= 0; --i){
			if(s[i] == 'T') T++;
			else if(s[i] == 'M'){
				M++;
				if(T < M){
					flag = 0;
					break;
				}
			}
		}
		if(!flag) cout << "NO" << endl;
		else cout << "YES" << endl;
	}
	return 0;
}

C.The Sports Festival

题意

给定一组数，现在将这些数按某种顺序加入。设置一个初始值为0的值 x x x.

每加入一个数， x x x加上当前加入的所有数的最大值-最小值。

问怎么排加入的顺序来保证最后得到的 x x x最小，输出最小 x x x即可。

分析

首先要贪心分析一波：

当序列中的数都是一样的时候， x x x每次都只能加0；如果不一样，保证尽量接近， x x x每次加的值也会较小。

所以，我们先将原输入序列排个序。

接下来是区间DP.

设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示区间 { i , j } \{i,j\} {i,j}得到的最小 x x x，则：
d p [ i ] [ j ] = m i n ( d p [ i + 1 ] [ j ] , d p [ i ] [ j − 1 ] ) + a [ j ] − a [ i ] dp[i][j]=min(dp[i+1][j], dp[i][j-1])+a[j]-a[i] dp[i][j]=min(dp[i+1][j],dp[i][j−1])+a[j]−a[i]
因为已经排好序，所以当前最大值减最小值就是 a [ j ] − a [ i ] a[j]-a[i] a[j]−a[i].

之后按长度动规， d p dp dp复杂度为 O ( n 2 ) O(n^2) O(n2)，总复杂度为 O ( n 2 + n l o g n ) = O ( n 2 ) O(n^2+nlogn)=O(n^2) O(n2+nlogn)=O(n2).

代码

/**
  * @file    :vsDebug2.cpp
  * @brief   :
  * @date    :2021-04-16
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <deque>
#include <cmath>
#include <algorithm>
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
 
signed main()
{
	IOS;
		int sum = 0;
		int n;
		cin >> n;
		int a[n];
		for(int i = 0; i < n; ++i){
			cin >> a[i];
		}
		sort(a, a + n);
		int dp[n][n];
		memset(dp, 0, sizeof(dp));
		for(int l = 2; l <= n; ++l){
			for(int i = 0, j = i + l - 1; j < n; ++i, ++j){
					dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + a[j] - a[i];
			}
		}
		
		cout << dp[0][n - 1] << endl;
		
	return 0;
}

D. Binary Literature

其他

CF官方的解法真的妙~~~~~~~~~~~~~~~~啊

题意

给定一个数字 n n n，然后给出3个长度为 2 n 2n 2n的01字符串，现在要你构造一个长度不超过 3 n 3n 3n的字符串，要求至少有2个给出的01串是这个字符串的子序列（不是子串！）

另外，可以证明，这样的构造总是存在的。

分析

三指针做法，初始依次指向各个01字符串的开头。另外，新建一个字符串 s s s.

由于为01字符串，故3个指针指向的位置至少有2个的字符是一样的，将这个字符加入 s s s，并将这两个指针右移一位，剩下的一个指针不动。

如果有一个指针 p p p移动到了终点，那么现在进一步分析：

• 此时字符串 s s s已经完全包含了 p p p所在的字符串， p p p所在字符串已经可以是 s s s的子序列了。
• 由于每次移动都是移动2个指针，故所有指针移动了4n次，其中 p p p移动了 2 n 2n 2n次，那么剩下两个指针一共移动了 2 n 2n 2n次。也可以得到 s s s当前长度为 2 n 2n 2n.
• 剩下两个指针至少移动了 n n n次，那么至少有一个指针，其剩余未匹配的字符数小于等于 n n n个，把这些字符加入 s s s，就保证了该01串也是 s s s的子序列，且长度一定不超过 3 n 3n 3n!

/**
  * @file    :vsDebug2.cpp
  * @brief   :
  * @date    :2021-04-16
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <deque>
#include <cmath>
#include <algorithm>
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define int long long
const int inf = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
int p[3] = {0};
string s[3];
int main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		memset(p, 0, sizeof(p));
		int n;
		cin >> n;
		string u;
		cin >> s[0] >> s[1] >> s[2];
		while(p[0] < 2 * n && p[1] < 2 * n && p[2] < 2 * n){
			if(s[0][p[0]] == s[1][p[1]]){
				u += s[0][p[0]];
				p[0]++, p[1]++;
			}
			else if(s[0][p[0]] == s[2][p[2]]){
				u += s[0][p[0]];
				p[0]++, p[2]++;
			}
			else if(s[1][p[1]] == s[2][p[2]]){
				u += s[1][p[1]];
				p[1]++, p[2]++;
			}
		}
		string u1, s1;
		if(p[0] == 2 * n){
			while(p[1] < 2 * n){
				u1 += s[1][p[1]++];
			}
			while(p[2] < 2 * n){
				s1 += s[2][p[2]++];
			}
		}
		else if(p[1] == 2 * n){
			while(p[0] < 2 * n){
				u1 += s[0][p[0]++];
			}
			while(p[2] < 2 * n){
				s1 += s[2][p[2]++];
			}
		}
		else if(p[2] == 2 * n){
			while(p[1] < 2 * n){
				u1 += s[1][p[1]++];
			}
			while(p[0] < 2 * n){
				s1 += s[0][p[0]++];
			}
		}
		if(u1.size() + u.size() <= 3 * n) cout << u + u1 << endl;
		else cout << u + s1 << endl;
	}
	return 0;
}