洛谷 LGR-171 赛后总结中，有哪些策略可以借鉴？
摘要：洛谷 LGR-171 赛后总结 比赛链接：https:www.luogu.com.cncontest146495 建议先看原题再看文章。 A - Water（P10056） 有 (n) 个杯子，每个杯子的容积是 (a)，且初
洛谷 LGR-171 赛后总结
比赛链接：https://www.luogu.com.cn/contest/146495
建议先看原题再看文章。
A - Water（P10056）
有 \(n\) 个杯子，每个杯子的容积是 \(a\)，且初始装有 \(b\) 体积水。
你可以进行任意次操作，每次操作选择任意两个杯子，将其中一个杯子内的水全部倒入另一个杯子中，但是过程中杯子里的水不能溢出（即不能超过其容积），如果不满足则无法进行该操作。请通过合法的操作，最大化装有最多水的杯子里水的体积。
Module 1 总结
赛时是一眼秒的。
显然把水全倒在一个杯子里，得到的答案最大，也就是 \(b \times n\)。但是可能会溢出，容量为 \(x\) 的情况下，最多能装 \(\Big\lfloor \dfrac{x}{b} \Big\rfloor\) 个初始装有 \(b\) 体积的水杯的容量。所以答案是 \(\min\Big(n \times b,\ b \times \Big\lfloor \dfrac{x}{b} \Big\rfloor\Big)\)。
记得开 long long！
Module 2 代码
Code
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
const int kMaxN = 5050, kMaxM = 5e4 + 50, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll a, b, n;
cin >> a >> b >> n;
cout << min(n * b, b * (a / b)) << '\n';
return 0;
}
B - Line（P10057）
在一个二维平面内，给定两条分别与 \(x\) 轴和 \(y\) 轴平行的线段 \(AB\) 和 \(CD\)。你可以选择一条线段，将其沿着平行于坐标轴（上下左右）的任意一个方向平移任意单位长度，称为一次操作。问至少进行几次操作可以使两条线段相交？
Module 1 总结
赛时思考了一会，还错了 \(3\) 次。
首先，题目中说 \(x_A<x_B\)，\(x_C=x_D\)，\(y_A=y_B\)，\(y_C<y_D\)。所以我们发现，第一条线段是竖的，第二条是横的。所以我们先判断第一段和第二段的 \(x\) 轴是否重合（\(x_A \le x_C \le x_B\) 或 \(x_A \le x_D \le x_B\)），如果不是，答案 \(+1\)。再判断 \(y\) 轴是否重合（\(y_C \le y_A \le y_D\) 或 \(y_C \le y_B \le y_D\)），如果不是，答案 \(+1\)。
Module 2 代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
const int kMaxN = 5050, kMaxM = 5e4 + 50, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t, x[5], y[5];
for (cin >> t; t; -- t) {
for (int i = 1; i <= 4; ++ i) { // 输入，用数组方便
cin >> x[i] >> y[i];
}
int ans = 0;
if (!(x[3] >= x[1] && x[3] <= x[2])) { // x 轴是否重合
++ ans;
}
if (!(y[1] >= y[3] && y[1] <= y[4])) { // y 轴是否重合
++ ans;
}
cout << ans << '\n';
}
return 0;
}
C - Reverse and Rotate（P10058）
给定一个字符串 \(S\) 和 \(n\) 次操作，每次操作为以下 \(3\) 种形式之一：1. < x 表示将 \(S\) 向左循环移动 \(x\) 位。例如：\(\mathtt{abcde}\) 执行 < 2 后变成 \(\mathtt{cdeab}\)。2. > x 表示将 \(S\) 向右循环移动 \(x\) 位。例如：\(\mathtt{abcde}\) 执行 > 2 后变成 \(\mathtt{deabc}\)。3. rev 表示将 \(S\) 翻转。例如：\(\mathtt{abcde}\) 执行 rev 后变成 \(\mathtt{edcba}\)。求 \(S\) 在依次执行这 \(n\) 次操作后得到的字符串 \(S'\)。
Module 1 总结
赛事想到了正解的 \(70\%\)，但还是与 AC 擦肩而过。
赛时得分：\(30\)，TLE #4~#10。
Module 2 赛后题解
前置知识：\(|S|\) 表示字符串 \(S\) 的长度。
首先我们发现，< 和 > 操作为相反操作，且 \(x\) 可以对 s.size() 取模后再操作。
所以当没有 rev 操作时，可以定义一个变量 \(p\)。当 < 操作时加上 \(x \bmod |s|\)，> 时反之。最后判断正负，如果是正数就执行 < p，负数则执行 > p。
但现在有 rev 操作。rev 操作反转了字符串，所有操作相反。我们定义一个 \(f\) 用来记录 \(S\) 的反转次数，为反转次数 \(\bmod \ 2\)。这里要注意一点，如果 \(p < 0\) 或 \(p \ge |S|\) 时需要把 \(p\) 加上或减去 \(|S|\) 把 \(p\) 的位置调到 \(0 \sim |S| - 1\)。 最后根据 \(f\) 分类输出即可。
Moudule 3 代码
赛时代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
const int kMaxN = 5050, kMaxM = 5e4 + 50, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
string s, t;
int n, rmv = 0, x;
bool rev = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> s >> n;
int m = s.size();
for (; n; -- n) {
cin >> t;
if (t == "<") {
cin >> x;
x %= m;
s = s.substr(x) + s.substr(0, x);
} else if (t == ">") {
cin >> x;
x %= m;
s = s.substr(m - x) + s.substr(0, m - x);
} else {
reverse(s.begin(), s.end());
}
}
cout << s << '\n';
return 0;
}
题解代码（伪代码）：
Input and Define variables
string op
int x
input(op)
if (op = ">" && f = true) || (op = "<" && f = false)
input(x)
x %= s.size()
p -= x
if p < 0
p += s.size()
else if (op = ">" && f = false) || (op = "<" && f = true)
input(x)
x %= s.size()
p += x
if p >= s.size()
p -= s.size()
else
f = !f
if f = true
output(s[p]...s[size() - 1])
output(s[0]...s[p - 1])
else
output(s[p - 1]...s[0])
output(s[s.size() - 1]...s[p])
D - Choose（P10059）
没做，没时间。