比赛链接：
https://codeforces.com/contest/1623
A. Robot Cleaner
题目大意：
在 \(n * m\) 的地图中，清洁机器人在（\(r_b\)，\(c_b\)）的位置，每一秒，机器人移动 \(dr\) 行、\(dc\) 列并清洁所在行和列所有的单元格，刚开始的时候，\(dr\) = 1，\(dc\) = 1，当机器人碰到上下边界时，\(dr = -dr\)，碰到左右边界的时候，\(dc = -dc\)。脏的单元格在（\(r_d\)，\(c_d\)），求第几秒的时候脏的单元格被清洁。
思路：
直接通过模拟，暴力求解。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL T = 1;
void solve(){
int n, m, a, b, c, d, ans = 0, dx = 1, dy = 1;
cin >> n >> m >> a >> b >> c >> d;
while (a != c && b != d){
if (a == n && dx == 1) dx = -1;
else if (a == 1 && dx == -1) dx = 1;
if (b == m && dy == 1) dy = -1;
else if (b == 1 && dy == -1) dy = 1;
a += dx;
b += dy;
ans++;
}
cout << ans << "\n";
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
显然，当机器人所在的行或列在要被清洗的行或列的左上方，那么清洗单元格需要花费的时间是二者之差，否则的话，机器人需要改变方向后才能清洗，所以所花的时间就是机器人到边界后再去清洗的时间。
所以我们可以有 O(1) 的解法。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL T = 1;
void solve(){
int n, m, a, b, c, d;
cin >> n >> m >> a >> b >> c >> d;
cout << min(c >= a ? c - a : 2 * n - a - c, d >= b ? d - b : 2 * m - d - b) << "\n";
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
B. Game on Ranges
题目大意：
\(Alice\) 有一个包含不相交的整数范围的集合，初始的范围是从 1 到 \(n\)，每一个回合 \(Alice\) 都会选择集合中的一个范围，然后 \(Bob\) 选择这个范围的一个数字，删除这个数，同时分隔这个范围集合。现已知 \(Alice\) 每一回合选取的整数范围，让你求对应的回合中 \(Bob\) 选择的是哪个数。
思路：
记数据的范围为 \([l, r]\)。
当 \(l == r\) 的时候，只有一个数可以选。
而左右边界不相等的时候，选择一个数之后，下一回合的范围一定有一个边界与当前的一个边界是一样的，所以，我们可以遍历所有的区间，去寻找有匹配的，然后输出选择的那个数即可。
代码：
全部查找了一遍
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e3 + 10;
LL T = 1, n, l[N], r[N];
void solve(){
cin >> n;
for (int i = 0; i < n; i++)
cin >> l[i] >> r[i];
for (int i = 0; i < n; i++){
LL ans = l[i];
for (int j = 0; j < n; j++)
if (l[i] == l[j] && r[i] > r[j]) ans = max(ans, r[j] + 1); //若没有与左边界匹配的范围的话，肯定是删除了左边界这个点。
printf("%lld %lld %lld\n", l[i], r[i], ans);
}
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
先排序（减少了查找的次数），然后再查找
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e3 + 10;
LL T = 1, n;
struct node {
int l, r;
}nd[N];
bool cmp(node a, node b){
if (a.r - a.l == b.r - b.l) return a.l < b.l;
return a.r - a.l > b.r - b.l;
}
void solve(){
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%d %d", &nd[i].l, &nd[i].r);
sort(nd + 1, nd + n + 1, cmp);
for (int i = 1; i <= n; i++){
if (nd[i].l == nd[i].r){
printf("%d %d %d\n", nd[i].l, nd[i].r, nd[i].l);
continue;
}
for (int j = i + 1; j <= n; j++){
if (nd[i].l == nd[j].l){
printf("%d %d %d\n", nd[i].l, nd[i].r, nd[j].r + 1);
break;
}
else if (nd[i].r == nd[j].r){
printf("%d %d %d\n", nd[i].l, nd[i].r, nd[j].l - 1);
break;
}
}
}
cout << "\n";
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
C. Balanced Stone Heaps
题目大意：
有 \(n\) 堆石头，你可以按照从第 3 个到第 \(n\) 个石堆这个顺序，选择第 \(i\) 个石堆，然后拿走 3 * \(d\) 个石子，给第 \(i\) - 1 个石堆 \(d\) 个石子，给第 \(i\) - 2 个石堆 \(d\) * 2 个石子，求最小的石堆最大的石子数会是多少？
思路：
将石堆的顺序反过来，就是从第 1 个石堆拿出 3 * \(d\) 个石子，然后分给第 \(i\) + 1 个石堆 \(d\) 个石子，第 \(i\) + 2 个石堆 \(d\) * 2 个石子，然后求最小的石堆最大的石子数。
用二分做，假设结果是 \(x\)，然后通过一遍拿石子的操作，最后判断石堆有没有小于 \(x\) 的，没有的话就扩大 \(x\)。
反过来做需要注意一个问题，拿出的石子不是 (\(g[i] - x\)) / 3【设 \(g\) 数组表示改变后的石堆石子数。】，而是 \(min(h[i]，g[i] - x)\) / 3，因为取出的石子数不会超过原有的石子数。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
LL T = 1, n, h[N], g[N], l, r;
bool judge(LL x){
for (int i = 1; i <= n; i++)
g[i] = h[i];
for (int i = n; i >= 3; i--){
if (g[i] < x) return false;
LL t = min(h[i], g[i] - x) / 3;
g[i - 1] += t;
g[i - 2] += 2 * t;
}
return g[1] >= x && g[2] >= x;
}
void solve(){
scanf("%lld", &n);
l = r = 1;
for (int i = 1; i <= n; i++){
scanf("%lld", &h[i]);
r = max(r, h[i]);
}
while (l < r){
LL mid = (l + r + 1) >> 1; //有左边界，所以让 mid 偏向右边
if (judge(mid)) l = mid;
else r = mid - 1;
}
cout << l << "\n";
}
int main(){
cin >> T;
while (T--)
solve();
return 0;
}