AtCoder Beginner Contest 338
ABC 切 ABC，什么实力。
C - Leftover Recipes
Problem Statement
Your refrigerator has \(N\) kinds of ingredients. Let us call them ingredient \(1\), \(\dots\), ingredient \(N\). You have \(Q_i\) grams of ingredient \(i\).
You can make two types of dishes. To make one serving of dish A, you need \(A_i\) grams of each ingredient \(i\) \((1 \leq i \leq N)\). To make one serving of dish B, you need \(B_i\) grams of each ingredient \(i\). You can only make an integer number of servings of each type of dish.
Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?
Solution
枚举 A 菜品的数量 \(i\)。那么很显然 B 菜品的数量应当小于等于每一个 \(\left \lfloor \frac {q_j - i \times a_j}{b_j} \right \rfloor\)，其中 \(1 \le j \le n\)，表示有 \(i \times a_j\) 克的配料给 A，剩下的 \(q_j - i \times a_j\) 给 B。
我们希望在满足上述条件的情况下，总的菜数最多。那么取 \(\min_{j = 1}^n \left \lfloor \frac {q_j - i \times a_j}{b_j} \right \rfloor\) 个 B 菜品是最好的选择。
所以答案为：
\[\max_{i = 0}^B \left \{i + \min_{j = 1}^n \left \lfloor \frac {q_j - i \times a_j}{b_j} \right \rfloor \right \} \]将上面的 \(B\) 设为一个很大的数即可，比如 \(10^6\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, q[N], a[N], b[N], res;
int main() {
cin >> n;
for (int i = 1; i <= n; ++ i ) cin >> q[i];
for (int i = 1; i <= n; ++ i ) cin >> a[i];
for (int i = 1; i <= n; ++ i ) cin >> b[i];
for (int i = 1; i < N; ++ i ) {
// i 个 A
int k = 2e9;
bool flg = false;
for (int j = 1; j <= n; ++ j ) {
if (q[j] < i * a[j]) {
flg = true;
break;
}
if (!b[j]) continue;
k = min(k, (q[j] - i * a[j]) / b[j]);
}
if (flg) break; // 如果这些配料光做 A 菜品都不够了，直接结束
res = max(res, i + k);
}
cout << res;
return 0;
}
D - Island Tour
Problem Statement
The AtCoder Archipelago consists of \(N\) islands connected by \(N\) bridges. The islands are numbered from \(1\) to \(N\), and the \(i\)-th bridge (\(1\leq i\leq N-1\)) connects islands \(i\) and \(i+1\) bidirectionally, while the \(N\)-th bridge connects islands \(N\) and \(1\) bidirectionally. There is no way to travel between islands other than crossing the bridges.
On the islands, a tour that starts from island \(X_1\) and visits islands \(X_2, X_3, \dots, X_M\) in order is regularly conducted. The tour may pass through islands other than those being visited, and the total number of times bridges are crossed during the tour is defined as the length of the tour.
More precisely, a tour is a sequence of \(l+1\) islands \(a_0, a_1, \dots, a_l\) that satisfies all the following conditions, and its length is defined as \(l\):
- For all \(j\ (0\leq j\leq l-1)\), islands \(a_j\) and \(a_{j+1}\) are directly connected by a bridge.
- There are some \(0 = y_1 < y_2 < \dots < y_M = l\) such that for all \(k\ (1\leq k\leq M)\), \(a_{y_k} = X_k\).
Due to financial difficulties, the islands will close one bridge to reduce maintenance costs. Determine the minimum possible length of the tour when the bridge to be closed is chosen optimally.
Solution
Code
E - Chords
Problem Statement
There are \(2N\) points placed at equal intervals on a circle, numbered \(1\) to \(2N\) in a clockwise direction starting from a certain point.
There are also \(N\) chords on the circle, with the \(i\)-th chord connecting points \(A_i\) and \(B_i\). It is guaranteed that all the values \(A_1,\dots,A_N,B_1,\dots,B_N\) are distinct.
Determine whether there is an intersection between the chords.
Solution
首先我们保证 \(a_i < b_i\)。若不满足先把它们交换。
然后圆拆开成一条链。一张官方题解的图示：
可以发现，如果两条线 \(x, y\) 有交叉，那么一定有 \(a_x < a_y < b_x < b_y\)。
枚举 \(x\)，然后找是否存在一个 \(y\) 满足以上条件。
如果我们令 \(c_i\) 表示在 \(a_x = i\) 时 \(b_x\) 的值。由于 \(a_i, b_i\) 这总共 \(2n\) 个数互不相同，所以 \(c_i\) 是唯一确定的。那么上面的问题其实就是：
是否存在一个 \(a_x < j < b_x\)，使得 \(c_j > b_x\)。
这是经典问题。我们只需要求这个区间内的最大值，然后判断是否大于 \(b_x\) 即可。也就是判断：
\[\max_{j = a_x + 1}^{b_x - 1} c_j > b_x \]这就是静态区间求最大值的问题。ST 表即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 400010, M = 25;
int n, a[N], b[N];
int st[N][M];
int query(int l, int r) {
if (l > r) return -2e9;
int k = log2(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i ) {
cin >> a[i] >> b[i];
if (a[i] > b[i]) swap(a[i], b[i]);
st[a[i]][0] = max(st[a[i]][0], b[i]);
}
for (int j = 1; j < M; ++ j )
for (int i = 1; i + (1 << j) - 1 <= 2 * n; ++ i )
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
for (int i = 1; i <= n; ++ i )
if (query(a[i] + 1, b[i] - 1) > b[i])
return puts("Yes"), 0;
puts("No");
return 0;
}