A. A Gift From Orangutan

题意：

思路： 贪心 + 模拟

 重新排列的数组 -> 最大的元素放第一个位置 ，最小的元素放第二个位置

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ( x & -x )

#define int long long
typedef long long ll;
typedef pair<int, int> pii;

void solve()
{
	int n; cin >> n;
    vector<int> a(n + 1);
    for( int i = 1 ; i <= n ; i++) cin >> a[i];
    sort( a.begin() + 1 , a.end() );
    swap( a[1] , a[n] );
    swap( a[2] , a[n] );
    vector<int> b(n + 1) , c(n + 1); b[0] = 2e18;
    int sum = 0;
    for( int i = 1 ; i <= n ;i++)
    {
        c[i] = max( c[i-1] , a[i] );
        b[i] = min( b[i-1] , a[i] );
        sum += c[i] - b[i];
    }
    cout << sum << endl;
}
signed main()
{
	int tt = 1;
	cin >> tt;
	while (tt--)solve();
	return 0;
}

B. Minimise Oneness

题意：

思路：构造题

一般构造题都是按照某种规律来做的 -> 关键是找规律

我的方法是先看样列，如果不能看出规律，就在手搓样例（都试几组），继续看，如果还不能，就只能猜了

我是通过手搓 n = 4发现规律的

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ( x & -x )

#define int long long
typedef long long ll;
typedef pair<int, int> pii;
void insert(vector<vector<int>>& f, int x1, int y1, int x2, int y2, int c) // 二维差分模版
{
    f[x1][y1] += c;
    f[x2 + 1][y1] -= c;
    f[x1][y2 + 1] -= c;
    f[x2 + 1][y2 + 1] += c;
}
int count_binary( int x , int k ) // 返回的是 0 ~ x 中二进制第 j 位为 1 的个数
{
    int y = 1ll << ( k + 1 );
    x++;
    int ans = x / y * ( y / 2 );
    x %= y; x -= y / 2;
    if( x > 0 ) ans += x;
    return ans;
}
int qmi(int a, int b, int mod) // 快速幂模版
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
bool is_prime(int n) // 判断素数模版
{
	if (n < 2)return false;
	for (int i = 2; i <= n / i; i++)
	{
		if (n % i == 0)return false;
	}
	return true;
}
int gcd( int a , int b )
{
    return b ? gcd( b , a % b ) : a;
}
int lcm( int a , int b )
{
    return a * b / gcd( a , b );
}
void solve()
{
	int n; cin >> n;
    string s; 
    for( int i = 1 ; i <= n ; i++ ) 
    {
        if( i == 1 ) s += '1';
        else s += '0';
    }
    cout << s << endl;
}
signed main()
{
	int tt = 1;
	cin >> tt;
	while (tt--)solve();
	return 0;
}

C. A TRUE Battle

题意：

 思路：结论题

如果首尾 有 '1'  -> true

如果 有两个连续的 '1' -> true

否则 -> false

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ( x & -x )

#define int long long
typedef long long ll;
typedef pair<int, int> pii;
void insert(vector<vector<int>>& f, int x1, int y1, int x2, int y2, int c) // 二维差分模版
{
    f[x1][y1] += c;
    f[x2 + 1][y1] -= c;
    f[x1][y2 + 1] -= c;
    f[x2 + 1][y2 + 1] += c;
}
int count_binary( int x , int k ) // 返回的是 0 ~ x 中二进制第 j 位为 1 的个数
{
    int y = 1ll << ( k + 1 );
    x++;
    int ans = x / y * ( y / 2 );
    x %= y; x -= y / 2;
    if( x > 0 ) ans += x;
    return ans;
}
int qmi(int a, int b, int mod) // 快速幂模版
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
bool is_prime(int n) // 判断素数模版
{
	if (n < 2)return false;
	for (int i = 2; i <= n / i; i++)
	{
		if (n % i == 0)return false;
	}
	return true;
}
int gcd( int a , int b )
{
    return b ? gcd( b , a % b ) : a;
}
int lcm( int a , int b )
{
    return a * b / gcd( a , b );
}
void solve()
{
	int n; cin >> n;
    string s; cin >> s;
    if( s[0] == '1' || s[n-1] == '1' )
    {
        puts("YES");  return;
    }
    for( int i = 1 ; i < n ; i++ )
    {
        if( s[i] == '1' && s[i-1] == '1' )
        {
            puts("YES");  return;
        }
    }
    puts("NO");
}
signed main()
{
	int tt = 1;
	cin >> tt;
	while (tt--)solve();
	return 0;
}

 D. QED's Favorite Permutation

题意：

思路：（类似于并查集）

首先观察字符串 ，如果相邻的两个字符分别是 'L' 和 'R'，则一定不能交换 （就属于两个集合） 

通过改变，可以使他们变为一个集合，于是可以交换

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n , q;
    cin >> n >> q;
    vector<int> a( n + 1 ) , am( n + 1 );
    for( int i = 1 ; i <= n ; i++ ) cin >> a[i];
    for( int i = 1 ; i <= n ; i++ ) am[i] = max( am[i-1] , a[i] );
    // am数组在这里类似于 并查集中的parent 
    string s; cin >> s;
    s = " " + s + " ";
    int cnt = 0;
    for( int i = 2 ; i <= n ; i++ )
    {
        if( s[i-1] == 'L' && s[i] == 'R' )
        {
            if( am[i - 1] != i - 1 )cnt++; // 属于两个集合,cnt++;
        }
    }
    while(q--)
    {
        int x; cin >> x;
        if( s[x] == 'L' )
        {
            if( s[x + 1] == 'R' && am[x] != x ) cnt--; // 合并两个集合
            if( s[x - 1] == 'L' && am[x - 1] != x - 1 ) cnt++; // 拆成两个集合
            s[x] = 'R';
        }
        else
        {
            if( s[x - 1] == 'L' && am[x - 1] != x - 1 )cnt--;
            if( s[x + 1] == 'R' && am[x] != x )cnt++;
            s[x] = 'L';
        }
        if(cnt)puts("NO");
        else puts("YES");
    }
}
signed main()
{
    int tt; cin >> tt;
    while(tt--)solve();
    return 0;
}