上周的 CCPC 哈尔滨，被队友带飞了，混了块牌牌，还行。又有一段时间没写题解了，随便写几道最近做的题练练手感吧。
另：大家有稳定的图床推荐吗，付费也可，突然发现常用的图床挂了，在这里写的题解示意图也挂了。
B - Taking the middle
题目链接： B - Taking the middle
题意：
给定 $2n$ 个数排成一列，两人进行 $n$ 轮取数，第一个人可以随便取，第二个人只能取剩余数的中间位置的数，问第一个人可以取到数的总和的最大值。
解题思路：
所有数的总和不变，第一个人取到最大值，也就是第二个人取到最小值。
可以发现第一轮中，第一个人取数后，第二个人可能取的数为 $a_{n-1}$ 或 $a_{n}$ ，第二轮中，第一个人取数后，第二个人还可能取到 $a_{n-2}$ 或 $a_{n+1}$ ，以此类推，会发现第二个人能够取数的范围数逐步向两边延伸的，而且一定能够取到范围内的数，因此每轮把候选的数加入可选集合中，从中取最小的数即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(2 * n);
long long res = 0;
for (int i = 0; i < 2 * n; i++) {
cin >> a[i];
res += a[i];
}
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; i++) {
heap.push(a[n - i - 1]);
heap.push(a[n + i]);
res -= heap.top();
heap.pop();
}
cout << res << '\n';
return 0;
}
C - Removing Coins
题目链接： C - Removing Coins
题意：
一棵树中，每个节点有一个硬币，两人轮流操作，每次操作选择一个有硬币的节点，取走节点上所有硬币，其它节点上的硬币同时往选中的节点方向移动一步，第一个不能操作的人失败，问谁必胜。
解题思路：
分析一下一条链的情况，会发现节点数为 $1,3,4,6,7$ 必胜， $2,5,8$ 必败，很有规律，数量模 $3$ 为 $2$ 即必败。
进一步分析发现，在链上之所以会产生这样的必败态，是因为每次操作只能将有硬币的连续节点长度缩短 $1$ 或 $2$ ，因此当前如果处于必败态，操作以后，对手必然可以使局势再次成为必败态。
将情况扩展到常规情况，不难想到最后可以操作一定在树的直径上，因为它是最长的路径，因此如果当前直径是必胜态，只需要不断维持树的直径的必胜态即可，如果当前直径是必败态，无论如何操作，对手也可以使其再次变成必败态。
综上，只需要看树的直径上的 节点数 ，模 $3$ 得 $2$ 则必败，否则必胜。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
--a;
--b;
g[a].emplace_back(b);
g[b].emplace_back(a);
}
vector<int> dist(n);
function<void(int, int, int)> dfs = [&](int u, int fa, int d) -> void {
dist[u] = d;
for (auto &v : g[u]) {
if (v != fa) {
dfs(v, u, d + 1);
}
}
};
dfs(0, -1, 0);
int mx = -1, id = -1;
for (int i = 0; i < n; i++) {
if (mx < dist[i]) {
mx = dist[i];
id = i;
}
}
assert(id != -1);
dist.assign(n, 0);
dfs(id, -1, 0);
mx = *max_element(dist.begin(), dist.end()) + 1;
cout << (mx % 3 == 2 ? "Second\n" : "First\n");
return 0;
}
G. Banquet Preparations 1
题目链接： G. Banquet Preparations 1
题意：
有 $n$ 个盒子，第 $i$ 个盒子有 $a_i$ 个红球和 $b_i$ 个黑球，要从每个盒子中取出恰好 $m$ 个小球，求所有盒子剩余的红球和黑球数量差的绝对值的和最小值，同时求这个情况下每个盒子取出几个红球和几个黑球。
解题思路：
设第 $i$ 个盒子取出 $x_i$ 个红球，那么就要取出 $m-x_i$ 个黑球，那么对最终答案的贡献为 $|a_i-x_i-(b_i-(m-x_i))|=|a_i-b_i+m-2x_i|$ ，其中只有 $x_i$ 是变量，要使所有盒子的这个和最小，就可以从 $x_i$ 入手了。
求出每个盒子 $x_i$ 可取的最大值 $maxx_i=min(m, a_i)$ ，可取的最小值 $minx_i=max(0, b_i-m)$ ，然后分成以下三种情况：
- 如果所有盒子的 $a_i-b_i+m$ 之和大于等于所有盒子 $maxx_i$ 之和乘以 $2$ ，那么就让所有盒子的都取 $maxx_i$ 个红球，$m-maxx_i$ 个黑球；
- 如果所有盒子的 $a_i-b_i+m$ 之和小于等于所有盒子 $minx_i$ 之和乘以 $2$ ，那么就让所有盒子的都取 $minx_i$ 个红球，$m-minx_i$ 个黑球；
- 否则，每个盒子先取 $minx_i$ 个红球，然后尽量使答案更优即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
long long m;
cin >> n >> m;
vector<long long> a(n);
vector<long long> b(n);
vector<long long> maxx(n);
vector<long long> minx(n);
long long smax = 0;
long long smin = 0;
long long s = (long long) n * m;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
maxx[i] = min(m, a[i]);
minx[i] = max(0LL, m - b[i]);
smax += maxx[i];
smin += minx[i];
s += a[i] - b[i];
}
if (s >= 2 * smax) {
cout << s - 2 * smax << '\n';
for (int i = 0; i < n; i++) {
cout << maxx[i] << ' ' << m - maxx[i] << '\n';
}
continue;
}
if (s < 2 * smin) {
cout << 2 * smin - s << '\n';
for (int i = 0; i < n; i++) {
cout << minx[i] << ' ' << m - minx[i] << '\n';
}
continue;
}
cout << (s % 2) << '\n';
long long cur = smin;
for (int i = 0; i < n; i++) {
long long extra = min(maxx[i] - minx[i], (s - 2 * cur) / 2);
cur += extra;
long long take = minx[i] + extra;
cout << take << ' ' << m - take << '\n';
}
}
return 0;
}
H. Banquet Preparations 2
题目链接： H. Banquet Preparations 2
题意：
有 $n$ 个盒子，第 $i$ 个盒子有 $a_i$ 个红球和 $b_i$ 个黑球，要从第 $i$ 个盒子中取出恰好 $m_i$ 个小球，对于两个盒子，如果剩余的红球和黑球数量都相同，那么这两个盒子可以归为一组，问最少可以将所有盒子分成多少组，并给出取球的方案。
解题思路：
对于可能归为同一组的两个盒子 $i,j$ ，必然有 $a_i+b_i-m_i=a_j+b_j-m_j$ ，因此可以按照这个值把盒子归类分别处理，对于每个盒子，求出剩余红球可取到的最小值和最大值，在同一类中，就转化为了区间选点问题：给定若干区间，选择尽量少的点，使得每个区间上至少有一个点。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
vector<int> m(n);
vector<int> l(n);
vector<int> r(n);
map<int, vector<int>> mp;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> m[i];
mp[a[i] + b[i] - m[i]].emplace_back(i);
l[i] = max(0, a[i] - m[i]);
r[i] = a[i] - max(0, m[i] - b[i]);
}
int res = 0;
vector<int> x(n);
vector<int> y(n);
for (auto &[s, ids] : mp) {
int sz = (int) ids.size();
vector<int> order(sz);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (r[ids[i]] != r[ids[j]]) {
return r[ids[i]] < r[ids[j]];
}
return l[ids[i]] > l[ids[j]];
});
int cnt = 0;
int cur = -(int) 2e9;
for (auto &i : order) {
if (l[ids[i]] > cur) {
++cnt;
cur = r[ids[i]];
}
x[ids[i]] = a[ids[i]] - cur;
y[ids[i]] = m[ids[i]] - x[ids[i]];
}
res += cnt;
}
cout << res << '\n';
for (int i = 0; i < n; i++) {
cout << x[i] << ' ' << y[i] << '\n';
}
}
return 0;
}
E - Yutori
题目链接： E - Yutori
题意：
给定 $n$ 个日期，其中有一些日期可以工作，现在一共要工作 $k$ 天，且如果今天工作了，那么从明天开始的 $c$ 天都要休息，题目保证可以工作至少 $k$ 天，问哪些日子是必须工作的。
解题思路：
分别从前往后和从后往前贪心算一遍，$l_i$ 表示第 $i$ 个工作日不早于 $l_i$ ，$r_i$ 表示第 $i$ 个工作日不迟于 $r_i$ ，如果 $l_i=r_i$ ，说明 $r_i$ 是必须要作为第 $i$ 个工作日的。
注意事项：
要特别判断一下无解的情况，也就是可以选取大于 $k$ 个工作日的情况。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, k, c;
string s;
cin >> n >> k >> c >> s;
vector<int> f(n);
for (int i = 0; i < n; i++) {
if (s[i] == 'x') {
f[i] = (i > 0 ? f[i - 1] : 0);
}
if (s[i] == 'o') {
f[i] = (i - c > 0 ? f[i - c - 1] + 1 : 1);
}
}
if (f[n - 1] > k) {
return 0;
}
vector<int> l(k);
for (int i = 0, j = 0, last = (int) -2e9; i < n; i++) {
if (s[i] == 'o' && i - c > last) {
l[j++] = i;
last = i;
}
}
vector<int> r(k);
for (int i = n - 1, j = k - 1, last = (int) 2e9; i >= 0; i--) {
if (s[i] == 'o' && i + c < last) {
r[j--] = i;
last = i;
last = i;
}
}
for (int i = 0; i < k; i++) {
if (l[i] == r[i]) {
cout << l[i] + 1 << '\n';
}
}
return 0;
}
F. Red-Black Number
题目链接： F. Red-Black Number
题意：
给定一列数字，要将每个数字涂成红色或黑色，两种颜色至少要涂上一个数字，问是否能够将红色的数字组成的数值和黑色的数字组成的数值恰好能够分别被 $a,b$ 整除，如果有多种方案，则取红色和黑色数字数量差值绝对值最小的，给出涂色方案。
解题思路：
一个比较直接的 DP 求方案，状态表示为 $f[i][cr][rr][rb]$ ，只看前 $i$ 个数字，有 $cr$ 个数字涂成红色， 当前红色数模 $a$ 得 $rr$ ，黑色数模 $b$ 得 $rb$ ，属性为可行性，转移也很简单，对于每个数字只有两种可能，要么涂成红色，要么涂成黑色。
这个状态表示其实隐含了黑色数字的数量，也就是 $i-cr$ ，因此不必加上黑色数量这一维。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, a, b;
string s;
cin >> n >> a >> b >> s;
vector<vector<vector<vector<int>>>> f(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(a, vector<int>(b))));
f[0][0][0][0] = 1;
for (int i = 0; i < n; i++) {
int x = (int) (s[i] - '0');
for (int cr = 0; cr <= n; cr++) {
for (int rr = 0; rr < a; rr++) {
for (int rb = 0; rb < b; rb++) {
if (f[i][cr][rr][rb]) {
// red
if (cr + 1 <= n) {
f[i + 1][cr + 1][(rr * 10 + x) % a][rb] = 1;
}
// black
f[i + 1][cr][rr][(rb * 10 + x) % b] = 1;
}
}
}
}
}
int cntRed = 0, diff = n + 1;
for (int cr = 0; cr <= n; cr++) {
if (f[n][cr][0][0] && abs(cr - (n - cr)) < diff) {
cntRed = cr;
diff = abs(cr - (n - cr));
}
}
if (cntRed == 0 || cntRed == n) {
cout << "-1\n";
continue;
}
string res;
for (int i = n - 1, rr = 0, rb = 0; i >= 0; i--) {
int x = (int) (s[i] - '0');
bool flag = false;
for (int prr = 0; prr < a && !flag; prr++) {
for (int prb = 0; prb < b && !flag; prb++) {
// red
if (cntRed > 0 && f[i][cntRed - 1][prr][prb] && (prr * 10 + x) % a == rr && prb == rb) {
rr = prr;
rb = prb;
--cntRed;
res += 'R';
flag = true;
break;
}
// black
if (f[i][cntRed][prr][prb] && prr == rr && (prb * 10 + x) % b == rb) {
rr = prr;
rb = prb;
res += 'B';
flag = true;
break;
}
}
}
}
reverse(res.begin(), res.end());
cout << res << '\n';
}
return 0;
}
E. Staircases
题目链接： E. Staircases
题意：
给定一个网格，定义两种路径形态为楼梯，具体可以看看原题连接，不难理解，处理 $q$ 次询问，每次询问会将某个格子的可用性取反，问每次询问后整个网格的楼梯路径有多少条。
解题思路：
对于一个完整的网格，计算路径数量比较简单， DP 一下即可，然后观察一个每次询问，改变某个格子状态，它所影响的路径数量的数量级是 $n$ ，因此对于每次询问，改变的位置是 $(x,y)$ ，都可以用 $O(n)$ 的复杂度计算出经过 $(x,y)$ 的楼梯路径数，计算它对答案的贡献即可。
注意事项：
看代码注释，有些细节要注意。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<vector<long long>>> f(n, vector<vector<long long>>(m, vector<long long>(2)));
long long res = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
f[i][j][0] = f[i][j][1] = 1;
if (i + 1 < n) {
f[i][j][0] += f[i + 1][j][1];
}
if (j + 1 < m) {
f[i][j][1] += f[i][j + 1][0];
}
res += f[i][j][0] + f[i][j][1] - 1;
}
}
vector<vector<int>> st(n, vector<int>(m, 1));
auto go = [&](int x, int y, int dx, int dy) -> long long {
int cnt = 0;
while (true) {
// 这里要先扩展，再判断，否则可能会原地不动
x += dx;
y += dy;
if (x < 0 || y < 0 || x >= n || y >= m || st[x][y] == -1) {
break;
}
++cnt;
swap(dx, dy);
}
return cnt;
};
while (q--) {
int x, y;
cin >> x >> y;
--x, --y;
long long t = 0;
// 计算时把 (x,y) 单独一格的情况先不考虑
{ // 第一种形态经过 (x,y) 的路径数量
long long c1 = go(x, y, -1, 0);
long long c2 = go(x, y, 0, 1);
t += (c1 + 1) * (c2 + 1) - 1;
}
{ // 第二种形态经过 (x,y) 的路径数量
long long c1 = go(x, y, 0, -1);
long long c2 = go(x, y, 1, 0);
t += (c1 + 1) * (c2 + 1) - 1;
}
res -= st[x][y] * t;
res -= st[x][y];
st[x][y] *= -1;
cout << res << '\n';
}
return 0;
}
H. Hidden Fortress
题目链接： H. Hidden Fortress
题意：
在一个 $10^9 \times 10^9$ 的地图上（网格），有一个矩形区域，现在有一个雷达，可以放在地图上的任意一个点，会给出矩形与这个位置距离最近的点与这个位置的曼哈顿距离，保证这个矩形不会在网格的边缘，雷达最多工作 $40$ 次，且不能放在矩形区域中，求两个可以唯一确定矩形区域的坐标。
解题思路：
按照题目条件，其实不难想到用二分，而且选取的位置应该要在边缘上，通过一顿几何运算得到答案。按照官方给出的题解，最优情况是可以只询问四次就可以了，但是似乎官方题解上给出的公式有些问题，直接照搬好像过不了，可以参考以下代码试试。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
auto ask = [&](int x, int y) -> int {
cout << "? " << x << ' ' << y << endl;
cin >> x;
return x;
};
const int N = (int) 1e9;
int d1 = ask(N, 1);
int d2 = ask(N, N);
int ym = 1 + (N - 1 - d2 + d1) / 2;
int d3 = ask(N, ym);
int d4 = ask(1, ym);
int x = 1 + d4;
int y = 1 + d1 - d3;
int p = N - d3;
int q = N - (d2 - d3);
cout << "! " << x << ' ' << y << ' ' << p << ' ' << q << endl;
return 0;
}
gitee当图床
膜大佬