训练赛1题解

牛客题解太乱，并且不全，在此提供个人题解
题解将按照题目顺序排列

A题

签到题，输出 $n-1949$ 即可

B题

签到题，由于只会出现小写字母，可以用数组存，依次遍历两个字符串，检验是否同时出现

C题

签到题，输出正方形面积加两个以正方形边长为直径的圆的面积即可

D题

给出一个长为 $x$ ，宽为 $y$ 的大矩形，需要切成 $n$ 块等面积的小矩形，由于 $n$ 范围较小，使用 $dfs$ 爆搜即可
由于只能平行切，切长时，只有切 $\frac{x}{n}*k(1<=k<n)$ 的位置才能保证小矩形面积相等
故暴力枚举长和宽切的位置即可，若 $n$ 为 $1$ 直接 $return$ 较大的长宽比即可\

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    double x, y;
    int n;
    cin >> x >> y >> n;
    auto dfs = [&](auto dfs, double x, double y, int n) -> double {
        if (n == 1) {
            return max(x / y, y / x);
        }
        double res = 1e18;
        for (int i = 1; i < n; i++) {
            double a = x * i / n;
            double sum1 = max(dfs(dfs, a, y, i), dfs(dfs, x - a, y, n - i));
            double b = y * i / n;
            double sum2 = max(dfs(dfs, x, b, i), dfs(dfs, x, y - b, n - i));
            res = min({res, sum1, sum2});
        }
        return res;
    };
    cout << fixed << setprecision(6) << dfs(dfs, x, y, n) << "\n";
}

E题

题意：一个无向图，删除第 $i$ 条边后，从 $1$ 到 $n$ 的最短路径是多长，无解输出 $-1$
由于遇到一个简单环时，最多 $2$ 条路径，考虑 $dfs$ 搜索
对于一条路径，删除该路径上任意一条，即将除该路径的所有边取 $min$ 即可.
若遍历边时为未被修改的 $inf$ ,则说明该条路径是 $1$ 到 $n$ 必须经过的边，所以才未被修改，此时输出 $-1$

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<PII>> edge(n + 1);
    vector<int> f(n + 1, INT_MAX);
    for (int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back({v, i});
        edge[v].push_back({u, i});
    }
    vector<bool> vis(n + 1);
    auto dfs = [&](auto dfs, int u, int sum) -> void {
        if (u == n) {
            for (int i = 1; i <= n; i++) {
                if (!vis[i]) {
                    f[i] = min(f[i], sum);
                }
            }
            return;
        }
        for (auto [v, i] : edge[u]) {
            if (!vis[i]) {
                vis[i] = 1;
                dfs(dfs, v, sum + 1);
                vis[i] = 0;
            }
        }
    };
    dfs(dfs, 1, 0);
    for (int i = 1; i <= n; i++) {
        if (f[i] == INT_MAX) {
            cout << -1 << '\n';
        } else {
            cout << f[i] << "\n";
        }
    }
    return 0;
}

F题

题意，需要求出所有点 $(x,y)$ 满足无点 $(a,b)$ 满足(a>=x && y>=b)
由于点比较分散，纯暴力会超时，考虑筛选，相同 $y$ 值的点，只有 $x$ 最大的点才有可能是题目要求的点
进行第一次筛选后，剩下的 $n$ 个点从后往前遍历，若当前第 $i$ 个点 $(x,y)$ 满足 $y_i>=max(y_k),(i<k<=n)$ 就是满足要求的点，全部加入sort即可
其中 $x,y$ 数值较大，需要离散化或者使用 $map$ 存\

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using PII = pair<i64, i64>;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    map<i64, i64> mp;
    i64 x, y;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        if (mp.count(y)) {
            mp[y] = max(mp[y], x);
        } else {
            mp[y] = x;
        }
    }
    vector<PII> a;
    for (auto [y, x] : mp) {
        a.push_back({x, y});
    }
    sort(a.begin(), a.end());
    vector<PII> res;
    i64 height = -LLONG_MAX;
    for (int i = a.size() - 1; i >= 0; i--) {
        if (a[i].second > height) {
            res.push_back(a[i]);
        }
        height = max(height, a[i].second);
    }
    sort(res.begin(), res.end());
    for (auto [x, y] : res) {
        cout << x << " " << y << "\n";
    }
    return 0;
}

G题

该题有数学结论，对于长度分别为 $a,b,c(其中a <= b < c)$ 的直角三角形，当半径分别取 $b,c-b,0$ 时三圆取得最大
本题也可以使用二分，枚举即可

constexpr double PI = acos(-1);
constexpr double eps = 1e-14;
void solve() {
    double a, b, c;
    cin >> a >> b >> c;
    double res = 0;
    auto check = [&](double r, double x, double y, double z) -> double {
        double r1 = r, r2 = x - r, r3 = y - r2;
        if (r1 + r3 > z || r2 < 0 || r3 < 0) {
            return -1;
        }
        double sum = (r1 * r1 + r2 * r2 + r3 * r3);
        res = max(res, sum);
        return sum;
    };
    auto ask = [&](double x, double y, double z) {
        double l = 0, r = x;
        while (r - l >= eps) {
            double mid = (l + r) / 2;
            double p1 = check(mid + eps, x, y, z), p2 = check(mid - eps, x, y, z);
            if (p1 > p2) {
                l = mid;
            } else {
                r = mid;
            }
        }
    };
    cout << fixed << setprecision(12) << res * PI << '\n';
}

H题

题意：求 $\sum_{i=2}^{n} gcd(\frac{i*(i-1)}{2},\frac{i*(i+1)}{2})$
由于数据较大，需要考虑优化，该结论可以通过猜测打表观察得到，下面给出证明
当 $i$ 为偶数时 $(i-1)$ 与 $(i+1)$ 为奇数,由于相邻奇数的最大公约数为1，故此时最大公约数为 $\frac{n}{2}$
当 $n$ 为奇数时， $(i-1)$ 与 $(i+1)$ 为相邻偶数,可以发现 $\frac{i-1}{2}$ 与 $\frac{i+1}{2}$ 由于i为相邻偶数，故一定是一奇一偶，其gcd为 $1$
下面证明当 $n$ 为奇数时， $gcd(n,\frac{n-1}{2})=1$
考虑反证,若 $gcd(n,\frac{n-1}{2})=d(d>1)$
需要 $d|n$ (d整除n),且 $d|\frac{n-1}{2}$ 即 $n=d*t$
即存在整数m，使得 $\frac{n-1}{2} = d * m$ ，则 $n = 2d * m + 1$
代入上式得： $d \cdot t = 2d * m + 1 \quad \Rightarrow \quad d(t - 2m) = 1$ 由于 $t, m$ 为整数， $t - 2m$ 也为整数, $t-2m!=\frac{1}{d}$ ,故 $d = 1$
故对于给定的 $n$ ，只需求的 $n$ 以内的奇数 $-1$ (从2开始，无1）之和加上 $n$ 以内的偶数之和的一半即为答案，使用等差数列求和公式即可得到答案
本题数据范围较小，最大数值仍在 $long\space long$ 范围内，最后取模即可

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 MOD = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n;
    cin >> n;
    i64 a = n / 2 + n % 2 - 1, b = n / 2;
    i64 res = ((2 + a) * a + (1 + b) * b / 2) % MOD;
    cout << res << '\n';
    return 0;
}

题解 | #牛牛的奋斗#

训练赛1题解

A题

B题

C题

D题

E题

F题

G题

H题