补题链接:Here
A - Heavy Rotation
对 \(N\) 进行奇偶判断,奇数穿 Black
、偶数穿 White
B - Trapezoid Sum
前 \(n\) 项和公式:\(S_n = \frac{n(a_1 + a_n)}{2}\)
简单套公式计算即可。
注意点:使用 long long
C - Collinearity
题意:给 N 组坐标,判断这些坐标中,是否存在三个不同点处于同一条直线。如果存在,输出 Yes,否则输出 No。
本题是一个数学题,假设我们有三个点,坐标分别为:点 A 为 (x1, y1)、点 B 为 (x2, y2) 和点 C 为 (x3, y3)。
判断三点共线
假设这三个点共线,则
\[\left |\frac{y_2-y_1}{x_2-x_1} \right| = \left |\frac{y_3-y_1}{x_3-x_1} \right| \]这样我们可以变换为
\[(y_2 - y_1)\times(x_3-x_1) = (y_3-y_1)\times(x_2-x_1) \]由于本题数据范围较小可以暴力遍历
- \(\mathcal{O}(N^3)\)
#include <bits/stdc++.h>
using namespace std;
typedef struct _POS {
int x;
int y;
} POS;
const int MAXN = 1e2 + 4;
POS arr[MAXN];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i].x >> arr[i].y;
//暴力枚举
for (int i = 1; i <= n - 2; i++)
for (int j = i + 1; j <= n - 1; j++)
for (int k = j + 1; k <= n; k++)
if ((arr[k].x - arr[i].x) * (arr[j].y - arr[i].y) ==
(arr[j].x - arr[i].x) * (arr[k].y - arr[i].y)) {
cout << "Yes\n";
return 0;
}
cout << "No\n";
return 0;
}
D - Hachi
核心在于 整数是否能被 \(8\) 整除都取决于后三位
题意:给定一个字符串(由 1
~ 9
构成),请问是否能通过重排序来使这个字符串整数为 \(8\) 的倍数。
- \(1 \le N\le2\times10^5\)
思路:
在数学问题上,有以下是成立的
- 判断最后一个数字是否为 \(2\) 的倍数:只要判断最后一位是否为 \(2\) 的倍数;
- 判断最后一个数字是否为 \(4\) 的倍数:只需判断最后两个数字是否为 \(4\) 的倍数;
- 判断最后三个数字是否为 \(8\) 的倍数:只需判断最后三位数字是否为 \(8\) 的倍数。
通常,为 \(2^k\) 的倍数等效于使最后 \(k\) 个数字为 \(2^k\) 的倍数。 让我简要地展示8的倍数的情况。
\(1000 = 2^3 \times 5^3\)
注意:\(1000\) 可被 \(8\) 整除,因此,对于任何整数 \(n\) ,可令 \(q\) 为 \(n\) 除以 \(1000\) 的商,\(r\) 为余数
即:\(n = 1000q + r\)
故此,\(r\) 恰好为 \(n\) 的最后三位数。
此时:\(n \equiv 1000q + r \equiv (\ mod\ 8)\)
现在回到原来的问题上;
关于 S 是否为 8 的倍数,我们进行分情况讨论
-
\(|S| \le 3\) 的情况我们可以直接全排列
-
\(|S| > 4\) 的情况我们可以考虑如下。
考虑 \(8\) 的倍数的所有可能的后三位数字。 确定是否可以从 \(S\) 满足它们中的任何一个。
实际上 \(1000\) 以内的 \(8\) 的倍数仅 124个,所以运行速度会很快
#incwlude <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve(string S) {
if (S.size() <= 5) {
sort(S.begin(), S.end());
do {
int val = 0;
for (auto c : S) val = val * 10 + (int)(c - '0');
if (val % 8 == 0) return true;
} while (next_permutation(S.begin(), S.end()));
return false;
}
vector<int> all(10, 0);
for (const auto c : S) all[c - '0']++;
for (int i = 0; i < 1000; i += 8) {
vector<int> num(10, 0);
int i2 = i;
for (int iter = 0; iter < 3; ++iter) {
num[i2 % 10]++;
i2 /= 10;
}
bool ok = true;
for (int v = 0; v < 10; ++v)
if (num[v] > all[v]) ok = false;
if (ok) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
string s;
cin >> s;
cout << (solve(s) ? "Yes" : "No");
return 0;
}
E - Transformable Teacher
题意:
给出 N个整数,且N为奇数,回答M个回答
- 对于每次查询都给定一个整数 M
- 将 \(N + 1\) 个整数 \(H_1,……,H_n,W\) 配对成 \(\frac{N + 1}{2}\)
- 统计 【数值查】总和的最小值
数据范围:
- \(1\le N,M\le 2\times10^5\)
思路:
https://blog.csdn.net/justidle/article/details/109509824
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
void chmax(T &a, T b) {
if (a < b) a = b;
}
template <class T>
void chmin(T &a, T b) {
if (a > b) a = b;
}
const ll inf = 1LL << 60;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int N, M;
cin >> N >> M;
vector<ll> X(N), W(M);
for (ll &x : X) cin >> x;
for (ll &x : W) cin >> x;
sort(X.begin(), X.end());
vector<ll> left(N + 1, 0), right(N + 1, 0);
for (int i = 2; i < N; i += 2) {
left[i] = left[i - 2] + X[i - 1] - X[i - 2];
right[i] = right[i - 2] + X[N - i + 1] - X[N - i];
}
ll ans = inf;
for (auto w : W) {
int i = lower_bound(X.begin(), X.end(), w) - X.begin();
if (i % 2 == 0) chmin(ans, left[i] + right[N - i - 1] + X[i] - w);
else
chmin(ans, left[i - 1] + right[N - i] + w - X[i - 1]);
}
cout << ans << '\n';
return 0;
}
F - Silver Woods
有一个 \(200×2×10^9\) 的网格,其中横坐标区间为 [−100,100]
,纵坐标区间为 \([−10^9,10^9]\)。平面上有若干个点。
你有一个圆,最开始在 \((0,−10^9)\),询问圆半径最大是多少使得它可以在不接触点的情况下圆心到达 \((0,10^9)\)。
思路:
二分圆的直径,如果两个点之间的距离小于直径,那么显然圆没法从这两个点之间经过。注意要把直线 \(x=100\) 和\(x=−100\) 也看做一个点。
那么如果连完线之后把直线 \(x=100\) 和 \(x=−100\) 联通,那么相当于存在若干连线将左右两边隔开,这样圆就无法过去。否则可以到达。
用并查集维护即可。
- \(\mathcal{O}(n^2logk)\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using Edge = pair<double, pii>;
struct UnionFind {
vector<int> par;
UnionFind(int n) : par(n, -1) {}
void init(int n) { par.assign(n, -1); }
int find(int x) {
return par[x] < 0 ? x : par[x] = find(par[x]);
}
bool issame(int x, int y) {
return find(x) == find(y);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
if (par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
}
}
};
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
vector<double> x(N), y(N);
for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
auto calc = [&](int i, int j) -> double {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
};
vector<Edge> edges;
int s = N, t = N + 1;
for (int i = 0; i < N; ++i) {
edges.push_back(Edge(100.0 - y[i], pii(s, i)));
edges.push_back(Edge(100.0 + y[i], pii(t, i)));
for (int j = i + 1; j < N; ++j) {
edges.push_back(Edge(calc(i, j), pii(i, j)));
}
}
sort(edges.begin(), edges.end());
UnionFind uf(N + 2);
double res = 0.0;
for (auto e : edges) {
uf.merge(e.second.first, e.second.second);
if (uf.issame(s, t)) {
res = e.first / 2;
break;
}
}
cout << fixed << setprecision(10) << res << endl;
return 0;
}