AtCoder Beginner Contest 181 个人题解（本场GJ x 3）

补题链接：Here

A - Heavy Rotation

对 进行奇偶判断，奇数穿 Black 、偶数穿 White

B - Trapezoid Sum

前 项和公式：%7D%7B2%7D#card=math&code=S_n%20%3D%20%5Cfrac%7Bn%28a_1%20%2B%20a_n%29%7D%7B2%7D&id=FCaaP)

简单套公式计算即可。

注意点：使用 long long

C - Collinearity

题意：给 N 组坐标，判断这些坐标中，是否存在三个不同点处于同一条直线。如果存在，输出 Yes，否则输出 No。

本题是一个数学题，假设我们有三个点，坐标分别为：点 A 为 (x1, y1)、点 B 为 (x2, y2) 和点 C 为 (x3, y3）。

判断三点共线

假设这三个点共线，则

这样我们可以变换为

%5Ctimes(x_3-x_1)%20%3D%20(y_3-y_1)%5Ctimes(x_2-x_1)%0A#card=math&code=%28y_2%20-%20y_1%29%5Ctimes%28x_3-x_1%29%20%3D%20%28y_3-y_1%29%5Ctimes%28x_2-x_1%29%0A&id=pe4Vy)

由于本题数据范围较小可以暴力遍历

• #card=math&code=%5Cmathcal%7BO%7D%28N%5E3%29&id=G2EKY)

#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

核心在于 整数是否能被 整除都取决于后三位

题意：给定一个字符串（由 1 ~ 9 构成），请问是否能通过重排序来使这个字符串整数为 的倍数。

思路：

在数学问题上，有以下是成立的

• 判断最后一个数字是否为 的倍数：只要判断最后一位是否为 的倍数；
• 判断最后一个数字是否为 的倍数：只需判断最后两个数字是否为 的倍数；
• 判断最后三个数字是否为 的倍数：只需判断最后三位数字是否为 的倍数。

通常，为 的倍数等效于使最后 个数字为 的倍数。 让我简要地展示8的倍数的情况。

注意： 可被 整除，因此，对于任何整数 ，可令 为 除以 的商， 为余数

即：

故此， 恰好为 的最后三位数。

此时：#card=math&code=n%20%5Cequiv%201000q%20%2B%20r%20%5Cequiv%20%28%5C%20mod%5C%208%29&id=RnUSf)

现在回到原来的问题上；

关于 S 是否为 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

题意：

给出 Ｎ个整数，且Ｎ为奇数，回答Ｍ个回答

• 对于每次查询都给定一个整数 M
• 将 个整数 配对成
• 统计 【数值查】总和的最小值

数据范围：

思路：

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

有一个 的网格，其中横坐标区间为 [−100,100]，纵坐标区间为 。平面上有若干个点。
你有一个圆，最开始在 #card=math&code=%280%2C%E2%88%9210%5E9%29&id=znz6c)，询问圆半径最大是多少使得它可以在不接触点的情况下圆心到达 #card=math&code=%280%2C10%5E9%29&id=euMlE)。

思路：

二分圆的直径，如果两个点之间的距离小于直径，那么显然圆没法从这两个点之间经过。注意要把直线 和 也看做一个点。

那么如果连完线之后把直线 和 联通，那么相当于存在若干连线将左右两边隔开，这样圆就无法过去。否则可以到达。
用并查集维护即可。

• #card=math&code=%5Cmathcal%7BO%7D%28n%5E2logk%29&id=UgXJG)

#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;
}