⭐AtCoder Beginner Contest 334
前言:
比赛题目链接
--按照惯例只写了主要部分的代码--
特别说明：Rust有一个竞赛用的输入库，并且写ABC是可以用的，但是平时写洛谷是用不了的，所以我自己写了一个cin(),凑活能用，代码见下：
读输入函数
fn cin() -> String {
let mut input = String::new();
std::io::stdin().read_line(&mut input).unwrap();
input.trim().to_string()
}
明明 2、3 都是简单题却过不了，果然是因为做了一天题导致晚上状态下滑了嘛
模拟只会猜题意，贪心只能过样例；数学上来先打表，DP一般看规律；组合数学靠运气，计算几何瞎暴力；图论强行套模板，数论只会GCD；递推莫名UKE，递归堆栈往外溢；深搜茫然TLE，广搜队列MLE；二分查找总CE，叉堆结果必RE；高精算法找规律，做完全都OLE；数据结构干瞪眼，水题也都WA;长知识也不容易，考试一来全懵Ｂ！
目录：
点击题目跳转
第一题
A
题目分析：
签到题，输出大的就行，题目还说明了不会有相等的情况
代码实现：
C++代码
void solve() {
int b, g;
cin >> b >> g;
cout << (b > g ? "Bat" : "Glove");
}
Rust代码
fn solve() {
let (a, b) = cin()
.split_whitespace()
.fold((0, 0), |x, y| (x.1, y.parse::<i32>().unwrap()));
println!("{}", if a > b { "Bat" } else { "Glove" });
}
第二题
B
题目分析：
数学题，我们分别计算出 r 到 a 有多少点以及 l 到 a 有多少点。我们希望左区间减一后向下取整，右区间向下取整，接着作差得到答案
- Rust代码中，我们使用
div_euclid()实现向下取整。div_euclid()是执行欧几里得除法，即找到\(Self=q*rhs+r\)中的 q ，实现向下取整（默认的除法是省略小数部分，并非向下取整）
代码实现：
C++代码
void solve() {
long double a,m,l,r;
cin >> a >> m >> l >> r;
ll ans = floor((r - a) / m) - floor((l - 1 - a) / m);
cout << ans;
}
Rust代码
fn solve() {
let (a, b, c, d) = cin().split_whitespace().fold((0, 0, 0, 0), |x, y| {
(x.1, x.2, x.3, y.parse::<i128>().unwrap()) //读输入
});
println!("{}", (d - a).div_euclid(b) - (c - 1 - a).div_euclid(b));
}
第三题
C
题目分析：
理解题意，题目中的袜子按递增顺序给出，而我们都知道差值最小的方案就是两个颜色最接近的，而对于任意两个袜子之间的最大值，我们按如下方式考虑：
不难想到，每次取相邻的得到的差是最小的
而得到的差即为n-1，而这等于直接将xn与x1配对
于是我们得到结论，每次取相邻两个之间的差即可
但对于奇数个的情况，我们需要找到哪个是需要不配对的，也就是找出最小值
可以先将第一个排除，我们得到后\(\lfloor \frac{n}{2}\rfloor\)对的和，即：
接着我们开始向后遍历，每次取前两个差的和减去后两个差的和：
这里我们假设蓝色会与绿色相消，那么得到的结果就是：
那么依次执行，每次比较这个值和一开始的值哪个小，遍历完之后得到结果
代码部分：
C++代码
void solve() {
int n, i, ans = 0;
cin >> n >> n;
vector<int> qwq(n);
for(auto &x : qwq)cin >> x;
for(i = n % 2 == 0 ? 1 : 2;i < n;i += 2)ans += qwq[i] - qwq[i - 1];
if(n % 2 == 1) {
int now = ans;
for(i = 1;i < n;i += 2) {
now += 2 * qwq[i] - qwq[i - 1] - qwq[i + 1];
ans = min(ans, now);
}
}
cout << ans;
}
Rust代码
fn solve() {
let (_, n) = cin()
.split_whitespace()
.fold((0, 0), |x, y| (x.1, y.parse::<usize>().unwrap()));
let qwq = cin()
.split_whitespace()
.map(|s| s.parse().unwrap())
.collect::<Vec<i32>>();
let st = if n % 2 == 1 { 2 } else { 1 };
let mut ans = 0;
for i in (st..n).step_by(2) {
ans += qwq[i] - qwq[i - 1];
}
if st == 2 {
let mut now = ans;
(1..n - 1).step_by(2).for_each(|i| {
now += 2 * qwq[i] - qwq[i - 1] - qwq[i + 1];
ans = ans.min(now);
})
}
println!("{}", ans);
}
第四题
D
题目分析：
我们知道最小的两个货物数之和肯定是最小的，我们每次取最小的肯定是最理想的情况
于是我们先对数组排个序，接着求出前缀和数组，得到的数组的索引加一就是能拉的货物数量，只需判断给定的鹿的数量在数组中的哪个位置即可，所以我们利用二分查找得到答案。
记得开long long
十年OI一场空，不开long long见祖宗
代码部分：
C++代码
void solve() {
int n, q, i;
ll j;
cin >> n >> q;
vector<ll>qwq(n);
for(auto &x : qwq)cin >> x;
sort(qwq.begin(), qwq.end());
for(i = 1;i < n;++i)qwq[i] += qwq[i - 1];
for(i = 0;i < q;++i) {
cin >> j;
cout <<' '<< (upper_bound(qwq.begin(), qwq.end(), j)-qwq.begin())<<'\n';
}
}
Rust代码
fn solve() {
let (a, b) = cin()
.split_whitespace()
.fold((0, 0), |x, y| (x.1, y.parse::<usize>().unwrap()));
let mut qwq = cin()
.split_whitespace()
.map(|s| s.parse().unwrap())
.collect::<Vec<i128>>();
qwq.sort_unstable();
(1..a).for_each(|x| qwq[x] += qwq[x - 1]);
for _ in 0..b {
let n: i128 = cin().parse().unwrap();
println!("{}", qwq.partition_point(|&x| x <= n))
}
}