题解 | #“范式杯”2023牛客暑期多校训练营10#

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

double Rand() {
    return (double) rng() / UINT_MAX;
}

using Point = complex<double>;

auto cross(const Point &a, const Point &b) {
    return imag(conj(a) * b);
}
 
auto dot(const Point &a, const Point &b) {
    return real(conj(a) * b);
}

const double Pi = acos(-1.0);
constexpr double inf = 1E18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Point> a(n);
    vector<int> R(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y >> R[i];
        a[i] = Point(x, y);
    }
 
    auto f = [&](const double &rad) {
        double l = inf, r = -inf, d = l, u = r;
        auto v = Point(cos(rad), sin(rad));
        for (int i = 0; i < n; i++) {
            double x = cross(a[i], v), y = dot(a[i], v);
            l = min(l, x - R[i]);
            r = max(r, x + R[i]);
            d = min(d, y - R[i]);
            u = max(u, y + R[i]);
        }
        return max(r - l, u - d);
    };

    double cur = 2 * Pi * rand(), now = f(cur), u = cur, ans = now;
    double t = 1E4;
    for (; t > 0.0001; t *= 0.998) {
        double nex = cur + t * (2 * Rand() - 1);
        double res = f(nex);
        if (res < ans) {
            u = nex, ans = res;
        }
        double delta = res - now;
        if (exp(-delta / t) > Rand()) {
            cur = nex, now = res;
        }
    }
    
    for (int i = 0; i < 1000; i++) {
        double nex = u + t * (2 * Rand() - 1);
        double res = f(nex);
        if (res < ans) {
            u = nex, ans = res;
        }
    }
    
    cout << fixed << setprecision(9) << ans << '\n';
    
    return 0;
}

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int n, m;
    cin >> n >> m;
  
    double ans = 1;
    for (int i = 0; i < m; i++) {
        ans *= 2.0 / n;
    }
    cout << fixed << setprecision(12) << (n == 1 ? 1.0 : ans) << '\n';

    return 0;
}

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int n;
    cin >> n;
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; i++) {
        auto &[r, g, b] = a[i];
        cin >> r >> g >> b;
    }

    auto f = [&](const array<int, 3> &a, const array<int, 3> &b) {
        return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
    };
  
    if (f(a[0], a[1]) || f(a[1], a[0])) {
        cout << "-1\n";
        return 0;
    } 
  
    vector<int> ans(n);
    vector<vector<int>> g(n); 
    vector<int> deg(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                int u = i, v = j;
                if (u == 0) {
                    u = 1;
                }
                if (v == 0) {
                    v = 1;
                }
                if (f(a[j], a[i])) {
                    g[u].push_back(v);
                    deg[v]++;                    
                }
            } 
        }
    }
  
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (!deg[i]) {
            q.push(i);
        }
    }
                          
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (auto &nex : g[cur]) {
            if (!--deg[nex]) {
                ans[nex] = ans[cur] + 1;
                q.push(nex);
            }
        }
    }
                          
    ans[0] = ans[1];
    for (int i = 0; i < n; i++) {
        if (ans[i] > 255) {
            cout << "-1\n";
            return 0;
        }
    }
  
    for (int i = 0; i < n; i++) {
        cout << ans[i] << '\n';
    }
                          
    return 0;
}

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    int a, b, c;
    scanf("%d + %d = %d", &a, &b, &c);
    int ta = c - b, tb = c - a, tc = a + b;

    auto f = [&](int x, int y) {
        string s = to_string(x), t = to_string(y);
        int n = s.size(), m = t.size();

        if (n == m) {
            return s == t;
        }

        if (m != n + 1) {
            return false;
        }
        
        int cnt = 0;
        for (int i = 0, j = 0; i < n && j < m; i++, j++) {
            if (s[i] != t[j]) {
                if (isdigit(t[j])) {
                    i--;
                    cnt++;
                } else {
                    return false;
                }
            }
        }
        return cnt < 2;
    };

    if (f(a, ta)) {
        a = ta;
    } else if (f(b, tb)) {
        b = tb;
    } else if (f(c, tc)) {
        c = tc;
    } else {
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
    printf("%d + %d = %d", a, b, c);
    
    return 0;
}