比赛链接：https://codeforc.es/contest/1196
A. Three Piles of Candies
题意：两个人分三堆糖果，两个人先各拿一堆，然后剩下一堆随意分配，使两个人中最后糖果较少的那个人的糖果最多。
分析：水题。
AC代码：
#include <bits/stdc++.h>
#define SIZE 300007
#define rep(i, a, b) for(int i = a; i <= b; ++i)
typedef long long ll;
using namespace std;
void io() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
ll n, m, t, a[3];
int main() {
io(); cin >> t;
while (t--) {
rep(i, 0, 2) cin >> a[i];
sort(a, a + 3);
cout << a[1] + (a[2] - a[1] + a[0]) / 2 << endl;
}
}
B. Odd Sum Segments
题意：给出一个n个数的数组，分成k个部分，使每个部分之和为奇数。
分析：简单构造。首先考虑不能划分的情况，我们统计奇数个数为\(num\)，那么当\(k>num\)时必定不行，此外(num-k)%2==1时也不行。于是剩下的情况就是可行的，我们记录每一个奇数的位置，贪心地输出这些位置，则每一段都是奇数了。本题代码C++17不明原因输出了奇怪的结果，只好用VS2017交了。。。
AC代码：
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <list>
#include <stack>
#include <bitset>
#define SIZE 300007
#define rep(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
typedef long long ll;
void io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ll n, m, t, k;
ll a[SIZE];
vector<ll> v;
int main() {
io();
cin >> t;
while (t--) {
v.clear();
cin >> n >> k;
int num = 0;
rep(i, 1, n) {
cin >> a[i];
if (a[i] & 1) { ++num; v.emplace_back(i); }
}
if (k > num) puts("NO");
else {
if ((num - k) & 1) puts("NO");
else {
puts("YES");
rep(i, 0, k - 2) cout << v[i] << ' ';
cout << n << endl;
}
}
}
}
C. Robot Breakout：
题意：给出n个只能向上下左右四个方向行动的机器人，但是这些机器人有些故障，可能不能朝某个方向移动，构造一个所有机器人都能到达的坐标。
分析：简单思维。我们只需要拿4条线逐步逼近结果就行了，就是将所有机器人不能到达的区域删去，若仍然存在答案则输出。
AC代码：
#include <bits/stdc++.h>
#define SIZE 300007
#define rep(i, a, b) for(int i = a; i <= b; ++i)
typedef long long ll;
using namespace std;
void io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
struct node {
ll x, y;
int a, b, c, d;
}p[SIZE];
ll n, m, t, num;
int main() {
io();
cin >> t;
while (t--) {
ll minx = 1e5, miny = 1e5, maxx = -1e5, maxy = -1e5;
cin >> n;
rep(i, 1, n) {
cin >> p[i].x >> p[i].y >> p[i].a >> p[i].b >> p[i].c >> p[i].d;
if (!p[i].a) maxx = max(maxx, p[i].x);
if (!p[i].b) miny = min(miny, p[i].y);
if (!p[i].c) minx = min(minx, p[i].x);
if (!p[i].d) maxy = max(maxy, p[i].y);
}
if ((minx >= maxx) && (miny >= maxy)) cout << 1 << ' ' << minx << ' ' << miny << endl;
else cout << 0 << endl;
}
}
D2. RGB Substring (hard version)
题意：给出一个只含R,G,B字符的字符串s和一个长度k，询问最少修改几个字符才能在字符串中找到一个长度为k的"RGBRGBRGB..."的子串。因此注意"GBR", "BRG"也是可以的。
分析：我们分别拿字符串"RGBRGBRGB..."，"GBRGBRGBR..."，”BRGBRGBRG..."去和原字符串匹配并对于贡献计算前缀和。例如：
样例原串：BGGGG；
匹配字串：RGBRG；
贡献：10110。
然后在前缀和中找最小值就可以了。
AC代码：
#include <bits/stdc++.h>
#define SIZE 200007
#define rep(i, a, b) for(int i = a; i <= b; ++i)
typedef long long ll;
using namespace std;
void io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ll n, m, t, k; string s;
char c[3][3] = { 'R','G','B','G','B','R','B','R','G' }, p[SIZE][3];
int pre[SIZE][3];
vector<ll> v;
int main() {
io();
rep(i, 0, SIZE - 1) p[i][0] = c[0][i % 3];
rep(i, 0, SIZE - 1) p[i][1] = c[1][i % 3];
rep(i, 0, SIZE - 1) p[i][2] = c[2][i % 3];
cin >> t;
while (t--) {
cin >> n >> k >> s;
pre[1][0] = pre[1][1] = pre[1][2] = 0;
if (s[0] != p[0][0]) pre[1][0] = 1;
if (s[0] != p[0][1]) pre[1][1] = 1;
if (s[0] != p[0][2]) pre[1][2] = 1;
rep(i, 1, n - 1) {
if (s[i] != p[i][0]) pre[i + 1][0] = pre[i][0] + 1;
else pre[i + 1][0] = pre[i][0];
if (s[i] != p[i][1]) pre[i + 1][1] = pre[i][1] + 1;
else pre[i + 1][1] = pre[i][1];
if (s[i] != p[i][2]) pre[i + 1][2] = pre[i][2] + 1;
else pre[i + 1][2] = pre[i][2];
}
int minx = k;
rep(i, k, n) {
minx = min(minx, pre[i][0] - pre[i - k][0]);
minx = min(minx, pre[i][1] - pre[i - k][1]);
minx = min(minx, pre[i][2] - pre[i - k][2]);
}
cout << minx << endl;
}
}
E. Connected Component on a Chessboard
题意：q次询问，每次给出两个整数b和w。对于一个\(1e9\times1e9\)的黑白棋盘，相同颜色在上下左右四个方向不相邻，构造一个联通块使得联通块中黑块数量为b，白块为w。
分析：不难的构造。由于必须构造一个联通块，所以我们发现黑白块的最大比例仅可能为\((3b+1):1\)（假设\(b>w\)）。然后我们可以直接选择一行开始如下图那样分三步构造。
第一步先构造一个1白4黑的形状；然后第二步以1白3黑的布局向右边延申；最后以1白1黑的布局向下延申直到完成。注意前两步的跳出条件均为\(b==w\)。若是黑块多于白块，考虑整体上移一格即可。
AC代码：
#include <bits/stdc++.h>
#define SIZE 200007
#define rep(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
typedef long long ll;
void io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ll n, m, t, b, w;
int main() {
io(); cin >> t;
while (t--) {
int flag = 1, i = 2;
cin >> b >> w;
if (b > w) { flag = 0; swap(b, w); }
if ((3 * b + 1) < w) { cout << "NO" << endl; continue; } //判断能不能构造
cout << "YES" << endl;
cout << 2 + flag << ' ' << 2 << endl; --b; //第一步构造
cout << 2 + flag << ' ' << 3 << endl; --w;
if (b != w) { --w; cout << 3 + flag << ' ' << 2 << endl; }
if (b != w) { --w; cout << 1 + flag << ' ' << 2 << endl; }
if (b != w) { --w; cout << 2 + flag << ' ' << 1 << endl; }
while(b != w) { //第二步构造
cout << 2 * i + flag << ' ' << 2 << endl; --b;
if (b != w) { --w; cout << 2 * i + flag << ' ' << 3 << endl; }
if (b != w) { --w; cout << 2 * i + flag << ' ' << 1 << endl; }
if (b != w) { --w; cout << 2 * i + 1 + flag << ' ' << 2 << endl; }
++i;
}
rep(i, 1, b) { //第三步构造
cout << 2 + flag << ' ' << 2 * i + 2 << endl;
cout << 2 + flag << ' ' << 2 * i + 3 << endl;
}
}
}
F. K-th Path
题意：给定一个n个节点，m条边的无向带权连通图，求子节点两两之间路径中第k长的路径长度。
分析：怎么看都像一道模板题（大雾）。观察到本题的k很小，最大为400，因此考虑暴力的方法。我们先找到边权前k小的边，然后建图，两两之间跑dijkstra，复杂度为\(o(k^{2}logk)\)。
AC代码：
#include <bits/stdc++.h>
#define SIZE 200007
#define INF 1e15
#define rep(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
typedef long long ll;
void io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ll n, m, k, t = 0;
vector<ll> len;
struct tmpedge {
int u, v;
ll val;
}tp[SIZE];
bool cmp1(tmpedge a, tmpedge b) { return a.val < b.val; }
struct edge {
int w;//边权
int to;//编号为i的边的终点
int next;//next[i]表示与第i条边同起点的上一条边的储存位置
}e[SIZE << 1];
ll head[SIZE];//以i为起点的最后一条边的存储位置
ll cnt = 0, dis[SIZE];
int in[SIZE], pos[SIZE];
bool vis[SIZE];
void add_edge(int u, int v, int w) {
e[cnt].w = w;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
}
struct cmpx {
bool operator()(ll &a, ll &b)const {
return dis[a] > dis[b];
}
};
void dijkstra(int x) {
rep(i, 1, t) dis[pos[i]] = INF, vis[pos[i]] = false;
dis[x] = 0;
priority_queue<ll, vector<ll>, cmpx> q;
q.push(x);
while (!q.empty()) {
ll u = q.top();
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (ll i = head[u]; ~i; i = e[i].next) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
if (!vis[v]) q.push(v);
}
}
}
}
int main() {
io();
cin >> n >> m >> k;
memset(head, -1, sizeof(head));
rep(i, 1, m) cin >> tp[i].u >> tp[i].v >> tp[i].val;
sort(tp + 1, tp + 1 + m, cmp1);
rep(i, 1, min(m, k)) {
add_edge(tp[i].u, tp[i].v, tp[i].val);
add_edge(tp[i].v, tp[i].u, tp[i].val);
if (!in[tp[i].u])pos[++t] = tp[i].u, in[tp[i].u] = 1;
if (!in[tp[i].v])pos[++t] = tp[i].v, in[tp[i].v] = 1;
}
rep(i, 1, t) {
dijkstra(pos[i]);
rep(j, i + 1, t)
len.emplace_back(dis[pos[j]]);
}
sort(len.begin(), len.end());
cout << len[k - 1];
}