A. Villages: Landlines

纯纯翻译题 给定你n条线段 求合并后间隔的距离，直接区间合并即可

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define forr(i,a) for(auto i:a)
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)
#define pb emplace_back
#define int long long
using namespace std;
using T = pair<int, int>;
constexpr int INF = 1e18;
auto merge(vector<T> &A)
{ 
    int L = -INF, R = -INF;
    vector<T> v;
    for (auto &[x, y] : A)
    {
        if (R < x)
        {
            if (R != -INF) v.push_back({ L,R });
            L = x, R = y;
        }
        else R = max(R, y);
    }
    if (L != -INF && R != -INF) v.push_back({ L,R });
    return v;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, ret = 0; cin >> n;
    vector<T> a(n); for (auto &[x, y] : a) cin >> x >> y, tie(x, y) = T{ x - y, x + y };
    sort(a.begin(), a.end());
    auto v = merge(a);
    for (int i = 1;i < v.size();++i) ret += v[i].first - v[i - 1].second;
    return cout << ret, 0;
}

D. Mocha and Railgun

找最长弧 发现当发射方向垂直于发射点与圆心的连线时,破坏圆弧最长

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define forr(i,a) for(auto i:a)
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)
#define pb emplace_back
#define int long long
using namespace std;
void solve()
{
    int r, x, y, d; cin >> r >> x >> y >> d;
    auto l = sqrt(x * x + y * y), a = acos((l - d) / r), b = acos((l + d) / r);
    cout << fixed << setprecision(12) << r * (a - b) << '\n';
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int _;for (cin >> _; _--;) solve();
    return 0;
}

G. Lexicographical Maximum

签到题

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define forr(i,a) for(auto i:a)
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)
#define pb emplace_back
#define int long long
using namespace std;
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    string s; cin >> s;
    if (s.size() == 1) cout << s;
    else cout << max(s, string(s.size() - 1, '9'));
    return 0;
}

I. Chiitoitsu

概率dp, f[i][j] 表示当前牌山剩 i 张牌 还要组成 j 个对子 荣和

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 210;
constexpr int mod = 1e9 + 7;
template<class T> inline T Norm(const T &v) { return (v % mod + mod) % mod; }
template<class T> constexpr T ksm(T a, int b, const int &p = mod, T c = 1)
{
    for (a %= p;b;(a *= a) %= p, b /= 2) if (b & 1) (c *= a) %= p;
    return c;
}
struct Z
{
    using F = long long; F v;
    Z(long long _x = 0) : v(Norm(_x)) {}
    Z operator-() const { return Z(Norm(mod - v)); }
    Z inv() const { return ksm(*this, mod - 2, mod); }
    Z &operator*=(const Z &R) { return v = v * R.v % mod, *this; }
    Z &operator+=(const Z &R) { return v = Norm(v + R.v), *this; }
    Z &operator-=(const Z &R) { return v = Norm(v - R.v), *this; }
    Z &operator/=(const Z &R) { return *this *= R.inv(); }
    Z &operator%=(const F &R) { return v %= R, *this; }
    friend Z operator*(Z L, const Z &R) { return L *= R; }
    friend Z operator+(Z L, const Z &R) { return L += R; }
    friend Z operator-(Z L, const Z &R) { return L -= R; }
    friend Z operator/(Z L, const Z &R) { return L /= R; }
    friend Z operator%(Z L, const F &R) { return L %= R; }
#if __cplusplus > 201703
    auto operator<=>(const Z &) const = default;
#endif
    friend auto &operator>>(istream &i, Z &z) { return i >> z.v; }
    friend auto &operator<<(ostream &o, const Z &z) { return o << z.v; }
};
Z f[N][N];
void solve()
{
    string s; cin >> s;
    int cnt = 0;
    map<string, int> m;
    for (int i = 0;i < s.size();i += 2) m[s.substr(i, 2)]++, cnt += m[s.substr(i, 2)] == 2;
    cout << f[123][7 - cnt] << '\n'; 
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    for (int i = 3;i <= 123;++i)
        for (int j = 1;j <= 7 && 3 * (2 * j - 1) <= i;++j)
            f[i][j] = (f[i - 1][j - 1] + 1) * Z(3 * (2 * j - 1)) / i + // 组成对子 
                      (f[i - 1][j] + 1) * Z(i - 3 * (2 * j - 1)) / i;  // 发牌员没吗
    int _; for (int i = 1 && cin >> _; i <= _;++i) cout << "Case #" << i << ": ", solve();
    return 0;
}