Codeforces Round 979 (Div. 2)

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;
}