Codeforces Round #575 (Div. 3) 解题报告
Nickel_Angel
2019-07-29 16:57:18
[题目总览请点击这里(๑╹◡╹)ﾉ](http://codeforces.com/contest/1196)
由于作者比较菜QAQ，部分参考了 codeforces 和洛谷上的题解……
注意**除最后一题外**，其余题目均为**多组数据**。
------
### A [Three Piles of Candies](http://codeforces.com/contest/1196/problem/A)
#### Description
Alice 和 Bob 收到了三堆糖果。现在他们想尽可能公平的分这些糖果，他们挑糖果的规则为：Alice 先从三堆糖果中选一堆，Bob 从剩下两堆糖果中选一堆，对于剩下那堆糖果，他们会按照他们的意愿分成两份。
在这样分完糖果后，如果 Alice 得到的糖果数比 Bob 多，则她会扔掉一些糖果，直到她所拥有的糖果和 Bob 一样多。同理，如果 Bob 得到的糖果数比 Alice 多，Bob 也会做同样的操作。
Alice 和 Bob 都希望自己能得到尽可能多的糖果，且他们会相应的计划分糖果的过程。问 Alice 最终能得到的糖果数最多是多少？（当然，Bob 也会得到相同数量的糖果）
#### Solution
我们可以设 Alice 先取的那堆中有 $a$ 个糖果，Bob 先取的那堆中有 $b$ 个糖果，剩下那堆一共有 $c$ 个糖果，他们扔掉的糖果数为 $d$ 。
故 $ans = (\frac {a + b + c - d} {2})$ ，显然，$0 \leq d \leq 1$ （即如果 $d \geq 2$ ，则两人不如各多拿 $\lfloor \frac {d} {2} \rfloor$ 个糖果）。并且 $d$ 和 $a + b + c$ 是否能被二整除有关，即：
$$d = \begin{cases} 0 & \text{If $2 \mid (a + b + c)$ } \\ 1 & \text{Otherwise} \end{cases}$$
不难发现答案为 $\lfloor \frac {a + b + c} {2} \rfloor$ 。
#### Code
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
namespace Primary
{
int q;
long long h[3];
void main()
{
scanf("%d", &q);
while (q--)
{
scanf("%I64d%I64d%I64d", &h[0], &h[1], &h[2]);
printf("%I64d\n", (h[0] + h[1] + h[2]) / 2);
}
}
}
int main()
{
Primary::main();
return 0;
}
```
------
### B [Odd Sum Segments](http://codeforces.com/contest/1196/problem/B)
#### Description
给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 。你要将这个序列分为 $k$ 段**非空，不相交**的子序列，且每个子序列的数之和为奇数。
如果给定的序列能分出符合以上条件的序列，请先输出 "YES"，并给出任意一种分割方式，否则输出 "NO" 。
你给出的分割方式需符合以下格式：
输出一个长度为 $k$ 的序列，设其为 $r_1,r_2,\cdots,r_k$ 且 $1 \leq r_1 < r_2 < \cdots < r_k,r_k = n$，其中 $r_j\,(j \in [1,k])$ 意为分成的第 $j$ 个线段的右端点的位置。故这个序列意思是将该线段分成 $[1,r_1],[r_1 + 1,r_2],[r_2 + 1, r_3],\cdots,[r_{k - 1} + 1,n]$ 这 $k$ 个线段。
#### Solution
~~由小学知识可知：~~
奇数 + 奇数 = 偶数，奇数 + 偶数 = 奇数，偶数 + 偶数 = 偶数；
故可知要使一段子序列和为奇数，其中必须有奇数个奇数。进而得知，若设整个序列的奇数的个数为 $cnt$，则当 $cnt < k$ 时(一定有一段无奇数），或 $cnt$ 和 $k$ 的奇偶性不相同时（一定有一段有偶数个奇数），均不能找到一种分割方法符合题意。
对于可以分割为符合条件的序列，一个显然的分割策略是：由于 $cnt \geq k$ 且 $cnt$ 与 $k$ 的奇偶性相同，故取序列中前 $k - 1$ 个奇数作为前 $k - 1$ 段的右端点，最后一段的右端点直接为 $n$ 即可。
#### Code
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
namespace Primary
{
const int maxn = 2e5 + 10;
int q, n, k, a[maxn], cnt = 0;
void main()
{
scanf("%d", &q);
while (q--)
{
cnt = 0;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
cnt += a[i] % 2;
}
if (cnt < k || cnt % 2 != k % 2)
{
puts("NO");
continue;
}
puts("YES");
for (int i = 1; i <= n; ++i)
{
if (k == 1) break;
if (a[i] % 2 == 1)
{
printf("%d ", i);
--k;
}
}
printf("%d\n", n);
}
}
}
int main()
{
Primary::main();
return 0;
}
```
------
### C [Robot Breakout](http://codeforces.com/contest/1196/problem/C)
#### Description
有 $n$ 个机器人逃出了实验室，你需要控制它们，将它们找回。
你知道这 $n$ 个机器人的坐标，其中第 $i$ 个机器人的坐标为 $(x_i, y_i)$ 。你需要控制它们移动至一点 $(X,Y)$ 。
现在知道机器人可以执行四种移动操作：
$1.$ 从 $(x, y)$ 移动至 $(x - 1, y)$；
$2.$ 从 $(x, y)$ 移动至 $(x, y + 1)$；
$3.$ 从 $(x,y)$ 移动至 $(x + 1, y)$；
$4.$ 从 $(x, y)$ 移动至 $(x, y - 1)$；
不幸的是，有一些机器人的动力系统出现了故障，以致于它们不能执行这四种操作中特定的某几种操作，你现在知道第 $i$ 个机器人不能执行操作是哪几种，问它们是否能移动至同一点，若能，输出 "1"，并输出那个点的坐标，否则输出 “0”。
输出坐标的绝对值不超过 $1 \times 10^5$，数据保证若能移动至同一点，则一定存在有一个点满足要求，且其坐标值的绝对值不超过 $1 \times 10^5$ 。
#### Solution
~~本来以为是差分约束，结果几个变量就搞定~~
不难发现若第 $i$ 个机器人不能执行操作 1，则该机器人不能向左走，可以将其转化为 $X \geq x_i$；
同理，其余的三个操作：
操作 2：$Y \leq y_i$；操作 3：$X \leq x_i$；操作 4：$Y \geq y_i$；
故只需维护 $x_{min}, x_{max},y_{min},y_{max}$ 四个边界，若 $x_{min} > x_{max}$ 或 $y_{min} > y_{max}$ 则无解。
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
namespace Primary
{
const int maxn = 1e5;
int q, n, x, y, f[4], bound[4];
void main()
{
scanf("%d", &q);
while (q--)
{
bound[0] = -maxn, bound[3] = -maxn;
bound[1] = maxn, bound[2] = maxn;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d%d%d%d%d", &x, &y, &f[0], &f[1], &f[2], &f[3]);
if (!f[0]) bound[0] = max(bound[0], x);
if (!f[1]) bound[1] = min(bound[1], y);
if (!f[2]) bound[2] = min(bound[2], x);
if (!f[3]) bound[3] = max(bound[3], y);
}
if (bound[0] <= bound[2] && bound[1] >= bound[3])
printf("1 %d %d\n", bound[0], bound[1]);
else
puts("0");
}
}
}
int main()
{
Primary::main();
return 0;
}
```
------
### D [RGB Substring](http://codeforces.com/contest/1196/problem/D2)
#### Description
给你一个长度为 $n$ 的字符串 $s$，其中它只包含字符 'R'，'G'，'B' 。
你还会得到一个正整数 $k$。在字符串 $s$ 的长度为 $k$ 的子串中，你需要选出一个使得：通过修改最少字符，使该子串成为无限字符串 "RGBRGBRGB $\cdots$" 的一个字串。求修改的最少字符数量。
#### Solution
本题有一个 [easy version](http://codeforces.com/contest/1196/problem/D1)（$1 \leq n,k \leq 2000$），而 hard version 是（$1 \leq n,k \leq 2\times 10^5$）。
先考虑弱化版，发现朴素算法可以考虑枚举这个长度为 $k$ 的子串的左端点和无限字符串的循环节开始字符，每次将枚举到的子串依次与无限字符串比对，求出该子串需要修改的字符数，同时维护答案最小值即可。
时间复杂度为 $O(nk)$ 。
#### Code (easy version)
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
namespace Primary
{
const int inf = 0x3f3f3f3f;
const char t[] = {"RGB"};
char s[2010];
int q, n, k;
void main()
{
scanf("%d", &q);
while (q--)
{
scanf("%d%d%s", &n, &k, s);
int ans = inf;
for (int i = 0; i < n - k + 1; ++i)
{
for (int j = 0; j < 3; ++j)//枚举无限字符串的循环节开始字符
{
int res = 0;
for (int pos = 0; pos < k; ++pos)
{
if (s[i + pos] != t[(pos + j) % 3])
++res;
}
ans = min(res, ans);
}
}
printf("%d\n", ans);
}
}
}
int main()
{
Primary::main();
return 0;
}
```
hard version 似乎就不能这样子去算了……
我们发现我们朴素算法每次都需重新比较枚举的子串左端点向后 $k$ 个字符，不妨考虑用数组（设其为 $diff$）记录下，对于循环节从一个字母开始时，$s$ 的第 $i$ 位与无限字符串对应的那位是否**不同**。若不同，则说明当前位置需要改动，$diff_i = 1$，若相同，则说明无需改动，$diff_i = 0$，发现这样只需预处理 $diff$ 的前缀和 $sum$，答案即为：$min(sum_i - sum_{i-k})$，其中 $(k - 1 \leq i < n)$，注意这里的数组及字符串下标从 0 开始。
这样时间复杂度为 $O(n)$ 。
这里没有将 $sum$ 开成数组，而动态维护维护了答案。具体细节见代码。
#### Code (hard version)
```cpp
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;
namespace Primary
{
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
const char t[] = {"RGB"};
int q, n, k, diff[maxn];
char s[maxn];
void main()
{
scanf("%d", &q);
while (q--)
{
scanf("%d%d%s", &n, &k, s);
int ans = inf;
for (int i = 0; i < 3; ++i)//仍然是枚举无限字符串的循环节开始字符
{
int res = 0;
for (int j = 0; j < n; ++j)
{
diff[j] = (s[j] != t[(i + j) % 3]) ? 1 : 0;//每一位的 diff
res += diff[j];//更新本次答案
if (j >= k) res -= diff[j - k];
//扫至 j 时将 diff[j - k] 对答案的影响消去,省去了记录前缀和
if (j >= k - 1) ans = min(res, ans);
}
}
printf("%d\n", ans);
}
}
}
int main()
{
Primary::main();
return 0;
}
```
------
### E [Connected Component on a Chessboard](http://codeforces.com/contest/1196/problem/E)
#### Description
有一个 $10^9 \times 10^9$ 的国际象棋棋盘，其中左上角的格子颜色是**白色**的。
给定两个正整数 $b,w$，你需要在这个国际象棋棋盘上找到一个联通块，使得该联通块中恰好有 $b$ 个黑格子，$w$ 个白格子。
我们说一个格点集合被称为联通块，当且仅当对于集合内任意两个元素 $C_1,C_2$，均有一个集合内的格点序列 $c_1,c_2,\cdots,c_k$（其中 $c_1 = C_1,c_k = C_2$），满足 $c_i$ 和 $c_{i + 1}$ 相邻（$i \in [1,k - 1]$）。
若能找到输出 "YES"，并输出你找到的联通块中的所有格点的坐标；否则输出 "NO" 。
#### Solution
一道神奇的构造题，被虐了(Ｔ▽Ｔ)……
我们可以想出以下构造策略：
我们考虑 $b \geq w$ 的情况，我们可以先选中 $(2, 2)$ 至 $(2,2w)$ 之间（包括端点）的所有格点，这样联通块中就正好有 $w$ 个白色格点了。接下来若选中的黑色格点数未达到要求则选择与这个联通块相邻的黑色格点（共有 $2w + 2$ 个），不难发现，这样构造出的联通块，可添加的黑色格子是最多的。故若将黑色格子添加完毕后仍不满足要求，则无解。
对于 $b < w$ 的情况，我们只需交换一下 $b, w$，再通过以上方法构造一遍后，将构造出的联通块中的每个点右移一格即可。
#### Code
```cpp
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> P;
namespace Primary
{
int q, b, w;
vector<P> point;
void main()
{
scanf("%d", &q);
while (q--)
{
int add = 0;
scanf("%d%d", &b, &w);
if (b < w)
{
add = 1;
swap(b, w);
}
int x = 2, y = 2;
while (w > 0)
{
point.push_back(P(x, y));
if ((x + y) % 2 == 1)
--b;
else
--w;
++y;
}
int ex = 1, ey = 2;
while (b > 0 && ey <= y)
{
point.push_back(P(ex, ey));
ey += 2;
--b;
}
ex = 3, ey = 2;
while (b > 0 && ey <= y)
{
point.push_back(P(ex, ey));
ey += 2;
--b;
}
if (b > 0)
{
point.push_back(P(2, 1));
--b;
}
if (b > 0)
{
point.push_back(P(2, y));
--b;
}
if (b > 0)
puts("NO");
else
{
puts("YES");
for (int i = 0; i < (int)point.size(); ++i)
printf("%d %d\n", point[i].first, point[i].second + add);
}
point.clear();//出题组提醒您:数据千万条,清空第一条.多测不清空,爆零两行泪.
}
}
}
int main()
{
Primary::main();
return 0;
}
```
------
### F [K-th Path](http://codeforces.com/contest/1196/problem/F)
#### Description
给你一张有 $n$ 个节点，$m$ 条边的带权无向图，你需要找出图中权值和第 $k$ 小的**简单路径**。
输出这个简单路径的权值和。
#### Solution
注意是权值和第 $k$ 小的**简单路径**，不是 **k 短路**。
我们不难发现答案一定是由 $m$ 条边中权值前 $k$ 小的边组成的（可以通过交换论证得到）。
故我们选出权值前 $k$ 小的边后，相当于我们选出了原图的一个子图。我们对于子图中跑一遍多源最短路，将各点之间的最短路计算出来后，从小到大排序，找到第 $k$ 小的即是答案。
这里多源最短路是由每个点跑 $dijkstra$ 实现的，然而由于数据范围，复杂度的瓶颈仍在给 $m$ 条边排序，总复杂度为 $O(m \log m + k^2 \log k)$ 。
#### Code
```cpp
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<long long, int> P;
namespace Primary
{
const long long inf = 1e14;
const int maxn = 2e5 + 10;
bool vis[maxn], is_key[maxn];
int n, m, k, key[maxn], cnt = 0;
int head[maxn], to[maxn << 1], next[maxn << 1], tot = 1;
long long val[maxn << 1], dis[maxn];
priority_queue<P, vector<P>, greater<P> > q;
priority_queue<long long, vector<long long>, greater<long long> > h;
struct edge
{
int from, to, val;
bool operator < (const edge &rhs) const
{
return val < rhs.val;
}
}e[maxn];
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
void dijkstra(int S)
{
for (int i = 1; i <= cnt; ++i)
{
dis[key[i]] = inf;
vis[key[i]] = false;
}
dis[S] = 0;
q.push(P(0, S));
while (!q.empty())
{
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int c = head[u], v; c; c = next[c])
{
v = to[c];
if (dis[v] > dis[u] + val[c])
{
dis[v] = dis[u] + val[c];
q.push(P(dis[v], v));
}
}
}
}
void main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].val);
sort(e + 1, e + m + 1);
for (int i = 1; i <= min(m, k); ++i)
{
add_edge(e[i].from, e[i].to, e[i].val);
add_edge(e[i].to, e[i].from, e[i].val);
if (!is_key[e[i].from])
{
is_key[e[i].from] = true;
key[++cnt] = e[i].from;
}
if (!is_key[e[i].to])
{
is_key[e[i].to] = true;
key[++cnt] = e[i].to;
}
}
for (int i = 1; i <= cnt; ++i)
{
dijkstra(key[i]);
for (int j = i + 1; j <= cnt; ++j)
h.push(dis[key[j]]);//这里采用了堆排序
}
for (int i = 1; i < k; ++i)
h.pop();
printf("%I64d", h.top());
}
}
int main()
{
Primary::main();
return 0;
}
```