终于涨分了，这算是这段时间来第一次涨分，之前一直都再降，看来终于算是找回了一点点当年的感觉了
A - Approximation
思路：求离 最近的正整数，由于是正整数，就简单了直接求两边的数对比一下即可
/*
Author Owen_Q
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int a, b;
cin >> a >> b;
int aa = a / b;
double real = (double) a / (double) b;
int bb = aa + 1;
if (double(bb) - real > real - double(aa)) {
cout << aa << endl;
} else {
cout << bb << endl;
}
return 0;
}
B - P(X or Y)
思路：给定特定规则，求两次投骰子达成规则的概率。看这么小的数据量，直接枚举判断即可，最后要注意一下，由于概率判定精确到了小数点后九位，所以一定要拉长最终输出的位数
/*
Author Owen_Q
*/
#include <bits/stdc++.h>
using namespace std;
bool check(int a, int b, int x, int y) {
if (a + b >= x) {
return true;
}
if (a >= b && a - b >= y) {
return true;
}
if (a <= b && b - a >= y) {
return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int x, y;
cin >> x >> y;
double count = 0;
for (int i = 1; i <= 6; i++) {
for (int j = 1; j <= 6; j++) {
if (check(i, j, x, y)) {
count++;
}
}
}
double result = count / 36;
cout << fixed << setprecision(12) << result << endl;
return 0;
}
C - Security 2
思路：这就是个策略题，给定一个密码算法，求最小生成步数。不难发现算法分两步，一个是加长密码，一个是给密码增量。所以策略就是从后往前判断相邻位的数差，这个一定是通过增量操作实现的，最后加一下密码长度即为最终步数
/*
Author Owen_Q
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
string s;
cin >> s;
int len = s.length();
int count = 0;
int pre = 0;
for (int i = len - 1; i >= 0; i--) {
count++;
int a = s[i] - '0';
if (a < pre) {
a += 10;
}
count += a - pre;
// cout << i << " " << s[i] << " " << pre << " " << a << " " << count << endl;
pre = s[i] - '0';
}
cout << count << endl;
return 0;
}
D - Domino Covering XOR
思路：给定一个网格区域，用 的板去铺平，求一种铺法，使得剩余的部分异或和最大。一开始考虑异或的各种性质，不过后来看了一眼数据量，完全可以用递归搜索。刚好最近刷了回溯专题，手正热呢，那么直接上
/*
Author Owen_Q
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
typedef long long ll;
ll grid[MAXN][MAXN];
bool cover[MAXN][MAXN];
ll maxRe;
ll re;
void search(int pos, int h, int w) {
int x = pos / w;
int y = pos % w;
if (pos == h * w) {
return;
}
search(pos + 1, h, w);
if (cover[x][y]) {
return;
}
if (x + 1 < h && !cover[x + 1][y]) {
cover[x][y] = true;
cover[x + 1][y] = true;
re ^= grid[x][y];
re ^= grid[x + 1][y];
if (re > maxRe) {
maxRe = re;
}
search(pos + 1, h, w);
cover[x][y] = false;
cover[x + 1][y] = false;
re ^= grid[x][y];
re ^= grid[x + 1][y];
}
if (y + 1 < w && !cover[x][y + 1]) {
cover[x][y] = true;
cover[x][y + 1] = true;
re ^= grid[x][y];
re ^= grid[x][y + 1];
if (re > maxRe) {
maxRe = re;
}
search(pos + 1, h, w);
cover[x][y] = false;
cover[x][y + 1] = false;
re ^= grid[x][y];
re ^= grid[x][y + 1];
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int h, w;
cin >> h >> w;
re = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> grid[i][j];
re ^= grid[i][j];
cover[i][j] = false;
}
}
maxRe = re;
search(0, h, w);
cout << maxRe << endl;
return 0;
}
E - Most Valuable Parentheses
思路：给定一个数组，要求用括号串覆盖数组，最终将所有左括号覆盖除累加求最大值。其实说白了，引入括号串就是为了利用栈的性质，即要保证每一位顺序做选择时，累加的数一定要比丢弃的数多。这题一看就是一个贪心，但是怎么贪的贪法还是很巧妙的。先对比一下括号覆盖的两个极端case。一个是左括号全在前面，即 ，就是前面的数尽可能累加，后面的数全都丢失。另一个就是左括号尽可能往后放，即
，即每两位就累加一个数并丢弃一个数。那么总结来说，左括号可以尽可能多的加直到加够数量，但每两位至少要求一个。因此参考这个特性，我们的贪心策略就来了。我们可以用一个优先队列维护当前队列中最大的元素，然后每两位累加一个最大值。这样就能在保证括号串合法的情况下，获取到最大值
/*
Author Owen_Q
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 5;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int n2 = n * 2;
ll sum = 0;
int a;
priority_queue<ll> queue;
for (int i = 0; i < n2; i++) {
cin >> a;
queue.push(a);
if (i % 2 == 0) {
sum += queue.top();
queue.pop();
}
}
cout << sum << endl;
}
return 0;
}