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