A 花绽晴窗含韵

直接比较就行

void solve() {
    int a, b;
    cin >> a >> b;
    if (a > b)
        cout << "Alice" << endl;
    else if (a < b)
        cout << "Bob" << endl;
    else
        cout << "Draw" << endl;
}

B 寻梅踏雪问春

没看到半径相等卡了一万年，我真的是人类吗。

题目等价于判断三个点是否构成了一个正三角形。

struct Point {
    ll x, y;
};

ll dis(Point A, Point B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

void solve() {
    Point A, B, C;
    cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y;
    ll l1 = dis(A, B), l2 = dis(B, C), l3 = dis(A, C);
    if (l1 == l2 && l2 == l3)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

C 夜揽星河入梦

首先如果 $n+1<m$ ，肯定不能构成 $m$​ 子连珠。

然后用双指针去维护区间，保证区间内最多缺一个数即可。

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    if (n + 1 < m) {
        cout << "NO" << endl;
        return;
    }
    sort(all(a));

    bool f = false;
    int l = 0;

    for (int r = 0; r < n; r++) {
        while (l < r) {
            if (a[r] - a[l] - r + l <= 1)
                break;
            l++;
        }
        if (r - l + 1 >= m - 1 && a[r] - a[l] - r - l <= 1) {
            f = true;
            break;
        }
    }

    cout << (f ? "YES" : "NO") << endl;
}

D 云栖山涧听松

删掉一条边后图仍连通等价于加边后不存在桥。

对于一棵树，所有的边都是桥，记 $L$ 为叶子数，一条边可以配对两个叶子，如果叶子个数为奇数需要再加一条，所以最少需要添加的边数即为 $\lceil\frac{L}{2}\rceil$ 。

void solve() {
    int n;
    cin >> n;

    vector<int> deg(n + 1, 0);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++, deg[v]++;
    }

    int l = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) {
            l++;
        }
    }

    cout << (l + 1) / 2 << endl;
}

E 云卷疏帘观月

不难发现，最优的构造是 $\text{0}$ 放中间，向两边依次递增，此时左数第 $i$ 个和右数第 $i$ 个互相交换也是等价的，总共有 $\lfloor\frac{n}{2}\rfloor$ 组。

void solve() {
    ll n;
    cin >> n;
    cout << ksm(Z(2), n / 2) << endl;
}

F 竹摇清风拂面

将圆上顺时针的点复制一份拼成长度为 $2n$ 的数组，圆上任意从 $st$ 开始的长度为 $n$ 的线性区间就对应复制数组中的某个连续区间 $[st, st+n-1]$ 。

在用 $dp[l][r]$ 表示区间 $[l,r]$ 的最小代价，将 $l$ 与 $k$ 配对 $(k=l+1,l+3,…,r)$ ，且 $s[l]=s[k]$ ，则 $$dp[l][r] = min(dp[l][r], dp[l+1][k-1] + dp[k+1][r] + a[l]*a[k])$$

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    if (n & 1) {
        cout << -1 << endl;
        return;
    }

    vector<int> freq(26, 0);
    for (char c : s)
        freq[c - 'a']++;
    bool f = true;
    for (auto v : freq)
        if (v & 1) {
            f = false;
            break;
        }
    if (!f) {
        cout << -1 << endl;
        return;
    }

    string ss = s + s;
    vector<ll> aa(2 * n);
    for (int i = 0; i < n; ++i)
        aa[i] = a[i], aa[i + n] = a[i];

    vector<vector<ll>> dp(2 * n, vector<ll>(2 * n, INF));

    for (int len = 2; len <= n; len += 2) {
        for (int l = 0; l + len - 1 < 2 * n; ++l) {
            int r = l + len - 1;
            for (int k = l + 1; k <= r; k += 2) {
                if (ss[l] != ss[k])
                    continue;
                ll L = 0;
                if (l + 1 <= k - 1) {
                    L = dp[l + 1][k - 1];
                    if (L == INF)
                        continue;
                }
                ll R = 0;
                if (k + 1 <= r) {
                    R = dp[k + 1][r];
                    if (R == INF)
                        continue;
                }
                ll c = L + R + aa[l] * aa[k];
                if (c < dp[l][r])
                    dp[l][r] = c;
            }
        }
    }

    ll ans = INF;
    for (int st = 0; st < n; ++st)
        ans = min(ans, dp[st][st + n - 1]);
    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

头文件

#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;

void init() {

}

void solve() {

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}

自动取模

template<class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1) res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template<int P>
struct MInt {
    int x;
    constexpr MInt(): x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;