牛客周赛 Round 124 题解

由于牛客的渲染问题，你可以点此链接进入我的博客查看

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 夜揽星河入梦

首先如果 ，肯定不能构成 ​ 子连珠。

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

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 云栖山涧听松

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

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

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 云卷疏帘观月

不难发现，最优的构造是 放中间，向两边依次递增，此时左数第 个和右数第 个互相交换也是等价的，总共有 组。

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

F 竹摇清风拂面

将圆上顺时针的点复制一份拼成长度为 的数组，圆上任意从 开始的长度为 的线性区间就对应复制数组中的某个连续区间 。

在用 表示区间 的最小代价，将 与 配对 ，且 ，则 。

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