A 小红的好串

知识点：字符串、集合

长度只有 $\texttt{3}$，直接统计不同字符个数。若恰好有 $\texttt{2}$ 种不同字符，就是好串，否则不是。

时间复杂度 $\mathcal{O}(1)$。

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

B 小红的好串计数

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

字符串只包含 $\texttt{0}$ 和 $\texttt{1}$，一个非空子串是好串，当且仅当它同时含有 $\texttt{0}$ 和 $\texttt{1}$。

推导 $\texttt{1}$ :

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

$$\frac{len(len+\texttt{1})}{\texttt{2}}$$

时间复杂度 $\mathcal{O}(n)$。

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

推导 $\texttt{2}$ :

按起点所在连续段统计，设当前段为 $[l,r)$，起点有 $r-l$ 种，终点有 $n-r$ 种，贡献为：

$$(r-l)(n-r)$$

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

时间复杂度 $\mathcal{O}(n)$。

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 小红的染色平均数

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

一次操作会让一个数 $\texttt{+1}$，另一个数 $\texttt{-1}$，所以数组总和不变。若最终红蓝平均数相等，则它们都等于整体平均数。设红色个数为 $r$，数组总和为 $sum$，红色当前和为 $sr$，则红色目标和为：

$$tar=\frac{r\cdot sum}{n}$$

若 $r\cdot sum$ 不能被 $n$ 整除，则无解；否则每次跨颜色操作都能让红色总和改变 $\texttt{1}$，答案为：

$$|sr-tar|$$

时间复杂度 $\mathcal{O}(n)$。

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 小红的排列构造

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

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

时间复杂度 $\mathcal{O}(n)$。

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 小红的染色生成树

知识点：图论、生成树、$\texttt{DSU}$

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

时间复杂度 $\mathcal{O}(m)$。

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 小红的好串构造

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

先构造 $\texttt{a}$ + $L$ 个 $\texttt{b}$ + $\texttt{c}$。此时好串只会出现在 $\texttt{a}$ 与 $\texttt{b}$ 段之间、$\texttt{b}$ 与 $\texttt{c}$ 段之间，共有 $\texttt{2}L$ 个。令 $x=k-(n-\texttt{1})$，取 $L=x+\texttt{1}$，之后按 $\texttt{abcabc…}$ 补齐长度。每补一个字符，只会新增一个长度为 $\texttt{2}$ 的好串，不会新增更长好串，因为任意连续三个字符都含有三种不同字符，最终好串数量为：

$$\texttt{2}L+(n-L-\texttt{2})=n+L-\texttt{2}=k$$

时间复杂度 $\mathcal{O}(n)$。

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;
}();