牛客周赛 Round 145 题解

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

A 小红的好串

知识点：字符串、集合

长度只有 ，直接统计不同字符个数。若恰好有 种不同字符，就是好串，否则不是。

时间复杂度 。

void solve() {
    string s;
    cin >> s;
    set<char> st(s.begin(), s.end());
    cout << (st.size() == 2 ? "Yes" : "No") << endl;
}

B 小红的好串计数

知识点：字符串、连续段、计数

字符串只包含 和 ，一个非空子串是好串，当且仅当它同时含有 和 。

推导 :

第一种是总子串数减去所有单色子串，若某个相同字符连续段长度为 ，需要减去：

时间复杂度 。

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

    int ans = n * (n + 1) / 2;
    for (int l = 0; l < n; ) {
        int r = l;
        while (r < n && s[l] == s[r]) ++r;

        int len = r - l;
        ans -= len * (len + 1) / 2;
        l = r;
    }

    cout << ans << endl;
}

推导 :

按起点所在连续段统计，设当前段为 ，起点有 种，终点有 种，贡献为：

每个好串会被唯一统计一次。

时间复杂度 。

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

    int l = 0, ans = 0;
    for (int r = 1; r < n; ++r) {
        while (r < n && s[l] == s[r]) ++r;
        ans += (r - l) * (n - r);
        l = r;
    }
    cout << ans << endl;
}

C 小红的染色平均数

知识点：数学、平均数、总和不变量

一次操作会让一个数 ，另一个数 ，所以数组总和不变。若最终红蓝平均数相等，则它们都等于整体平均数。设红色个数为 ，数组总和为 ，红色当前和为 ，则红色目标和为：

若 不能被 整除，则无解；否则每次跨颜色操作都能让红色总和改变 ，答案为：

时间复杂度 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &v : a) cin >> v;

    string s;
    cin >> s;

    int sum = accumulate(a.begin(), a.end(), 0LL), r = 0, sr = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') r++, sr += a[i];
    }

    int b = n - r;
    if (!r || !b || r * sum % n) return cout << -1 << endl, void();

    int tar = r * sum / n;
    cout << llabs(sr - tar) << endl;
}

D 小红的排列构造

知识点：构造、排列、出现次数

对于某个值 ，排列 中都只能各出现一次，因此 中同一个值最多只能出现两次；若出现超过两次，必然无解。若 出现一次，就让对应位置的 都等于 ；若出现两次，就分别放入 和 ；若没有出现，则作为缺失值填入 尚未填的位置。这样 都是排列，且两个排列中与 相等的位置数都不少于 。

时间复杂度 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    vector<vector<int>> p(n + 1);
    for (int i = 0; i < n; ++i) cin >> a[i], p[a[i]].push_back(i);

    vector<int> ms;
    for (int x = 1; x <= n; ++x) {
        if (p[x].size() > 2) return cout << -1 << endl, void();
        if (p[x].empty()) {
            ms.push_back(x);
        } else if (p[x].size() == 1) {
            b[p[x][0]] = c[p[x][0]] = x;
        } else {
            b[p[x][0]] = x;
            c[p[x][1]] = x;
        }
    }

    vector<int> eb, ec;
    for (int i = 0; i < n; ++i) {
        if (!b[i]) eb.push_back(i);
        if (!c[i]) ec.push_back(i);
    }

    for (int i = 0; i < ms.size(); ++i) {
        b[eb[i]] = ms[i];
        c[ec[i]] = ms[i];
    }

    for (auto v : b) cout << v << " ";
    cout << endl;
    for (auto v : c) cout << v << " ";
    cout << endl;
}

E 小红的染色生成树

知识点：图论、生成树、

合法生成树恰好使用两种颜色。枚举颜色对 ，只保留这两种颜色的边。如果该颜色对构成的子图连通，并且两种颜色各至少有一条边，那么可以先强制加入一条颜色 的边和一条颜色 的边，再用 继续扩展成生成树。因为连通图中的任意森林都可以扩展成生成树。

时间复杂度 。

void solve() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> e(m);
    vector<int> id(3, -1);
    for (int i = 0; i < m; i++) {
        cin >> e[i][0] >> e[i][1] >> e[i][2];
        id[e[i][2]] = i;
    }

    if (n < 3) return cout << -1 << endl, void();

    for (int x = 0; x < 3; x++) {
        for (int y = x + 1; y < 3; y++) {
            if (id[x] == -1 || id[y] == -1) continue;

            DSU d(n);
            vector<PII> ans;

            for (auto [u, v, w] : {e[id[x]], e[id[y]]}) {
                if (d.merge(u, v)) ans.push_back({u, v});
            }

            for (auto [u, v, w] : e) {
                if (w != x && w != y) continue;
                if (d.merge(u, v)) ans.push_back({u, v});
            }

            if (ans.size() == n - 1) {
                for (auto [u, v] : ans) cout << u << " " << v << endl;
                return;
            }
        }
    }

    cout << -1 << endl;
}

F 小红的好串构造

知识点：构造、字符串计数

先构造 + 个 + 。此时好串只会出现在 与 段之间、 与 段之间，共有 个。令 ，取 ，之后按 补齐长度。每补一个字符，只会新增一个长度为 的好串，不会新增更长好串，因为任意连续三个字符都含有三种不同字符，最终好串数量为：

时间复杂度 。

void solve() {
    int n, k;
    cin >> n >> k;
    int x = k - (n - 1), len = x + 1;

    string s;
    s += 'a';
    s += string(k - n + 2, 'b');
    s += 'c';

    string t = "abc";
    for (int i = 0; s.size() < n; i++) s += t[i % 3];

    cout << s << endl;
}

约定

using namespace std;
#define int long long
#define endl "\n"
#define PII pair<int, int>
int __INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(15);
    return 0;
}();