Question C is really a little thrilling. It's almost 1:57. There are only three or four minutes left

A. Fair Playoff

meaning of the title

Give the ability values of a,b, C and D, and then a,b, C and D. the winner will enter the finals. Ask whether the two players in the finals have the greatest ability. Is it fair or not
analysis

Well, you can write whatever you want
Give a relatively complex code

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
 
signed main()
{
	IOS;
	int  t;
	cin >> t;
	while(t--)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int p[4] = {a, b, c, d};
		sort(p, p + 4, greater<int>());
		if(a < b) swap(a, b);
		if(c < d) swap(c, d);
		if(a < c) swap(a, c);
		if(a == p[0] && c == p[1]) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

B. Array Reodering

meaning of the title

Given an array, now you need to rearrange the array so that there are the largest number of pairs, meeting the following requirements:
1 ≤ i ＜ j ≤ n , g c d ( a i , 2 a j ) > 1 1≤i＜j≤n, gcd(a_i,2a_j)>1 1≤i＜j≤n,gcd(ai​,2aj​)>1
analysis

Greedy. Since the data is only 2000, there is a concave one O ( n 2 ) O(n^2) Greedy QWQ of O(n2). Don't look at the conditions first 1 ≤ i ＜ j ≤ n 1≤i＜j≤n 1 ≤ i < j ≤ n, calculate the number pair formed by each number and all other numbers at most. Then, if we add conditions 1 ≤ i ＜ j ≤ n 1≤i＜j≤n 1 ≤ i < j ≤ n, then each number will certainly lose some number pairs. Greedy construction is to minimize the number of pairs lost by the whole array. Then it can be guessed that the result is to sort the number in descending order according to the original number of each number.

Rough proof

(I thought about it casually yesterday, but I didn't feel too strict)

Since the largest number of "the number pair formed by the largest number with all other numbers" is ranked first, this largest number will certainly have no loss. Further thinking, put the formed number pair in front as much as possible, the more the number behind, the less the number in front, and the original number pair is satisfied 1 ≤ i ＜ j ≤ n 1≤i＜j≤n 1 ≤ i < j ≤ n has more chances, so the number of pairs lost will be less. Because the chance of forming a number to large number loss is greater, we need to put them in front to reduce the chance of loss.

code

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2005;
int n;
struct node{
	int x, cnt;
	node(){
		x = cnt = 0;
	}
}a[maxn];
bool cmp(node x, node y){
	return x.cnt > y.cnt;
}
signed main()
{
	IOS;
	int  t;
	cin >> t;
	while(t--)
	{
		int ans = 0;
		cin >> n;
		fors(i, 1, n) cin >> a[i].x, a[i].cnt = 0;
		fors(i, 1, n){
			fors(j, 1, n){
				if(i == j) continue;
				if(__gcd(a[i].x, a[j].x * 2) > 1){
					a[i].cnt++;
				}
			}
		}
		sort(a + 1, a + 1 + n, cmp);
		fors(i, 1, n){
			a[i].cnt = 0;
		}
		fors(i, 1, n){
			fors(j, i + 1, n){
				if(__gcd(a[i].x, a[j].x * 2) > 1){
					ans++;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

C. Unstable String

meaning of the title

(the meaning of the question is a little difficult to understand)

Give a string containing '0', '1', '?' Among them, '‘ It can be regarded as' 1 'or' 0 '. If a string can alternate between 0 and 1, it is called a string b e a u t i f u l beautiful beautiful. How many strings are there now b e a u t i f u l beautiful A substring of beautiful?

For example,
Strings 1,10 are beautiful;
String 1??? 1 is also beautiful, because it can be converted to 10101 through the question mark;
But string 1??? 1 is not beautiful, because no matter how the question mark changes, it is impossible to make 01 appear alternately.

analysis

My practice is double pointer. (I thought of it at the beginning, but I didn't discuss it in detail, which led to the final AC after more than an hour)

Set two pointers p 1 p1 p1, p 2 p2 p2, all from 0 0 Start with 0, then p 2 p2 p2 move forward, check during p 1 p1 p1 to p 2 p2 Whether p2 can form a b e a u t i f u l beautiful The substring of beautiful. Move forward if you can.

How to judge? My approach is:

First, preprocess, for each continuous question mark segment, maintain the number in front of the whole question mark segment.

Why maintain like this? It can be found that when the length of a question mark segment is an odd number, if the left and right numbers are the same, the question mark can be replaced with numbers, so that the question mark string plus two numbers is still the same b e a u t i f u l beautiful beautiful. For example, 1??? 1 can be replaced by 10101. On the contrary, if the numbers at both ends are different, it is impossible to ensure that the question mark segment can be added with the numbers at both ends b e a u t i f u l beautiful beautiful. The opposite is true when the length of the question mark segment is even. In particular, if the question mark segment is at the leftmost / rightmost end of the entire string, it must be qualified

Therefore, to judge whether the number behind the question mark can be connected or not, the key is to look at the relationship between this number and the number at the front of the question mark segment and preprocess it. It will be clearer to discuss whether to move forward later.

For example, for 10011???, For the question mark segment "??", his p r e [ i ] = 4 pre[i]=4 pre[i]=4, indicating that the subscript of the first number is 4

If you judge, you find p 2 p2 p2 cannot be guaranteed after moving left [ p 1 , p 2 ] [p1,p2] [p1,p2] still b e a u t i f u l beautiful beautiful, what should I do?

1. If p 2 p2 p2 and p 2 + 1 p2+1 p2+1 is not a question mark, which means that these are two equal numbers. In any case, they can't be connected together. Calculate it directly p 1 p1 p1 to p 2 p2 The answer to p2 is added a n s ans In ans. p 1 p1 p1 to p 2 p2 All substrings of p2 are qualified, so the answer is ∑ i = 1 p 2 − p 1 + 1 i \sum_{i=1}^{p2-p1+1}i Σ i=1p2 − p1+1 − i, the sum of an equal difference sequence. Finally p 2 p2 p2 move right, then make p 1 = p 2 p1=p2 p1=p2 (the original interval has been counted and can be completely discarded)
2. If p 2 p2 p2 is a question mark, p 2 + 1 p2+1 p2+1 is not a question mark, indicating p 2 p2 Those in front of the question mark segment where p2 is located can no longer be connected. However, from p r e [ p 2 ] + 1 pre[p2]+1 pre[p2]+1 to p 2 p2 The question mark segment p2 does not necessarily no longer work, but it is certain that p 1 p1 p1 to p r e [ p 2 ] pre[p2] pre[p2] is definitely not needed, so the statistics show that p 1 p1 p1 to p r e [ p 2 ] pre[p2] The arithmetic sum of pre[p2]. Don't rush to order at this time p 1 = p r e [ p 2 ] + 1 p1=pre[p2]+1 p1=pre[p2]+1, which should be considered from p 1 p1 p1 to p r e [ p 2 ] pre[p2] pre[p2], and p r e [ p 2 ] pre[p2] pre[p2] to p 2 p2 p2 can still be connected to form b e a u t i f u l beautiful beautiful string, remember to count these in. Order later p 1 = p r e [ p 2 + 1 ] p1=pre[p2+1] p1=pre[p2+1].

code

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int n;
string s;
int cnt(int len)
{
	return (len + 1) * len / 2LL;
}
int cnt(int l, int r)
{
	return (r - l + 1) * (r - l + 2) / 2LL;
}
int pre[maxn];
signed main()
{
	IOS;
	// Prefix processing: for each?, Find the first non question mark of its public sequence
	int  t;
	cin >> t;
	
	while(t--)
	{
		// 0 and 1 are definitely not continuous For?, According to the length of the whole question mark sequence
		// Double pointer
		cin >> s;
		int p1 = 0, p2 = 0;
		for(int i = 0; i < s.size(); ++i){
			pre[i] = -1;
		}
		for(int i = 0; i < s.size(); ++i){
			if(i == 0 && s[i] == '?'){
				pre[i] = -1;
			}
			else if(i > 0 && s[i] == '?' && s[i - 1] == '?'){
				pre[i] = pre[i - 1];
			}
			else if(s[i] == '?'){
				pre[i] = i - 1;
			}
		}
		int ans = 0;
		for(;;){
			if(p2 + 1 >= s.size()){
				if(p2 == s.size() - 1){
					ans += cnt(p2 - p1 + 1);
				}
				break;
			}
			int flag = 1;
			if(s[p2] == '?' && s[p2 + 1] == '?');
			else if(s[p2] == '?' && pre[p2] == -1);
			else if(s[p2] == '?' && s[p2 + 1] != '?'){
				int len = p2 - pre[p2];
				if(len % 2 == 0 && s[p2 + 1] != s[pre[p2]]);
				else if(len % 2 != 0 && s[p2 + 1] == s[pre[p2]]);
				else flag = -1;
			}
			else if(s[p2] != '?' && s[p2] == s[p2 + 1]) flag = 0;
			if(flag == 1) p2++;
			else if(flag == 0){
				ans += cnt(p2 - p1 + 1);
				p2++;
				p1 = p2;
			}
			else{
				ans += cnt(pre[p2] - p1 + 1) + (pre[p2] - p1 + 1) * (p2 - pre[p2]);
				p1 = pre[p2] + 1;
				p2++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Love Sakurai Yamauchi forever!!!