A - Sasha and the Beautiful Array
难度: ⭐
题目大意
给定一个长度为n的数组, 其分数为An - An-1 + An-1 - An-2 ... + A2 - A1; 问如何排列可以让该数组的分数最大;
解题思路
就是让An - A1最大;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, cnt;
string s;
int p[N];
signed main(){
IOS;
int t;;
cin >> t;
while (t--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i];
sort(p + 1, p + 1 + n);
cout << p[n] - p[1] << endl;
}
return 0;
}
B - Sasha and the Drawing
难度: ⭐⭐
题目大意
一个n * n的方格有4 * n - 2条对角线; 现在需要对这n * n个方格涂色, 要求让至少k条对角线都经过涂色的格子, 请问最少可以涂多少个格子;
解题思路
对于一个n * n的方格, 只要我们把第一行和最后一行都涂色后就可以包含所有对角线, 并且可以发现, 除了四个顶角的格子, 其他格子都必有两条对角线经过; 而这四个顶角, 先涂的前两个格子也会各自有两条对角线, 而后涂的两个虽然也各自有两条, 但是各自其中一条是重复的, 也就是只能算一条; 所以当k <= 4 * n - 4时就按每个格子包含两条对角线来算即可; 如果大于, 则多出来的按一个格子一条即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, cnt;
string s;
int p[N];
signed main(){
IOS;
int t;;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
if(b <= 4 * a - 4) cout << b / 2 + b % 2 << endl;
else cout << 2 * a - 2 + (b - 4 * a + 4) << endl;
}
return 0;
}
C - Sasha and the Casino
难度: ⭐⭐
题目大意
小莫去赌场赌钱, 现有本钱a元, 在某一轮中投入b元, 如果赌赢了则变为k * b元, 即赚了(k - 1) * b元; 赌输了则失去b元; 而且该赌场有一个福利, 即连续输x轮后下一轮必赢; 请问小莫是否可以在任意时刻稳定赢钱;
解题思路
本题题意有点模糊, 总之就是想着以最小的代价输x轮, 然后赢一轮赚回来; 而是每一轮都要想着赢钱; 比如说当前小莫已经输了x元, 那么一轮小莫必须想着赚回来, 也就是至少投入y元, 使得(k - 1) * y >= x; 知道这个逻辑后就可以进行模拟了, 因为x的范围很小, 所以模拟x轮即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, res;
signed main(){
IOS;
int T;
cin >> T;
while(T--){
int k, x, a;
cin >> k >> x >> a;
int now = 0;
bool f = true;
for(int i = 1; i <= x + 1; i++){
if(a < now / (k - 1) + 1){
f = false;
break;
}
a -= now / (k - 1) + 1;
now += now / (k - 1) + 1;
}
if(f) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}