小白月赛 Round 127 题解

A Flower_Rainbow_and_You

记录最大值的下标，查表输出即可。

string s[7] = {"Red", "Orange", "Yellow", "Green", "Blue", "Indigo", "Violet"};

void solve() {
    vector<int> a(7);
    for (int i = 0; i < 7; ++i) cin >> a[i];
    int mx = 0, loc = -1;
    for (int i = 0; i < 7; ++i) {
        if (a[i] > mx) {
            mx = a[i];
            loc = i;
        }
    }
    cout << s[loc] << endl;
}

B Flower_Rainbow_and_Rhythm

用 $\text{unordered_map}$ 记录对应余数的数字个数，每一个余数的数字个数都必须是偶数。

void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int> mp;
    for (int i = 0, x; i < n; ++i) cin >> x, mp[x % k]++;
    for (auto [u, v] : mp) {
        if (v & 1) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

C Flower_Rainbow_and_Wave

$\text{1,2,4}$ 显然是无解的。

对于任意奇数 $x$ ，我们可以构造 $\{1,2,3,...,(x+1)/2,(x+1)/2-1,...,3,2,1\}$ 。

对于形如 $2(2k+1),k\in Z$ 的偶数，我们可以构造两个长度为 $2k+1$ 的波形数组。

对于形如 $2(2k),k\in Z$ 的偶数，我们可以构造长度为 $2k-1,2k+1$ 的两个波形数组。

void solve() {
    int n;
    cin >> n;
    if (n == 1 || n == 2 || n == 4)
        cout << "-1";
    else if (n & 1) {
        for (int j = 1; j <= (n + 1) / 2; ++j) {
            cout << j << " ";
        }
        for (int j = n / 2; j >= 1; --j) {
            cout << j << " ";
        }
    } else if ((n / 2) & 1) {
        int a = n / 2;
        for (int j = 1; j <= (a + 1) / 2; ++j) {
            cout << j << " ";
        }
        for (int j = a / 2; j >= 1; --j) {
            cout << j << " ";
        }
        for (int j = 1; j <= (a + 1) / 2; ++j) {
            cout << j << " ";
        }
        for (int j = a / 2; j >= 1; --j) {
            cout << j << " ";
        }
    } else {
        int a = n / 2 - 1, b = n / 2 + 1;
        for (int j = 1; j <= (a + 1) / 2; ++j) {
            cout << j << " ";
        }
        for (int j = a / 2; j >= 1; --j) {
            cout << j << " ";
        }
        for (int j = 1; j <= (b + 1) / 2; ++j) {
            cout << j << " ";
        }
        for (int j = b / 2; j >= 1; --j) {
            cout << j << " ";
        }
    }
    cout << endl;
}

D Flower_Rainbow_and_Balloon

我们用滑动窗口去统计红黄白三种颜色的气球个数 $r,y,w$ 。

愉悦度即为 $max\{2r+y,r+2y\}+2*min\{m,w\}$ ，判断是否大于 $k$ 即可。

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

    int r = 0, y = 0, w = 0;
    int len = n + 1, l = 0;

    for (int i = 0; i < n; ++i) {
        r += s[i] == 'r';
        y += s[i] == 'y';
        w += s[i] == 'w';

        while (l <= i) {
            int ext = min(w, m) * 2;
            if (max(r * 2 + y, r + 2 * y) + min(w, m) * 2 >= k) {
                len = min(len, i - l + 1);
                r -= s[l] == 'r';
                y -= s[l] == 'y';
                w -= s[l] == 'w';
                l++;
            } else {
                break;
            }
        }
    }

    if (len > n)
        cout << -1 << "\n";
    else
        cout << len << "\n";
}

E Flower_Rainbow_and_Game

代价函数为

rf(u,v) = \begin{cases} 1, & u,v \text{为直系祖先关系} \\ x, & others \end{cases}

我们可以把总代价拆成

S = \sum_{\text{所有点对}} dist(u,v) - \sum_{\text{祖先点对}} dist(u,v) + \sum_{\text{祖先点对}} 1

所以我们记录祖先点对的数量，所有点对距离之和，祖先点对的距离之和即可。

祖先点对数量：对于每个点 $u$ ，它的子树中（除了它自己）的所有点都是它的后代。数量为 $siz[u]−1$ 。
所有点对距离之和：对于节点 $u$ （ $u\ne root$ ），它与父节点的连边将树分成大小为 $siz[u]$ 和 $n−siz[u]$ 的两部分，该边对总距离的贡献为 $siz[u]\times (n−siz[u])$ 。
对于每个点 $u$ ，它有 $dep[u]−1$ 个真祖先（根节点深度为1）。这些祖先到 $u$ 的距离分别为 $1,2,…,dep[u]−1$ 。根据等差数列求和，距离之和为 $\frac{dep[u]×(dep[u]−1)}{2}$ 。

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    vector<int> siz(n + 1), dep(n + 1);
    function<void(int, int)> dfs = [&](int u, int fa) {
        siz[u] = 1;
        dep[u] = dep[fa] + 1;
        for (auto v : g[u]) {
            if (v == fa) continue;
            dfs(v, u);
            siz[u] += siz[v];
        }
    };
    dfs(1, 0);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll s = siz[i];
        ll d = dep[i];

        ans = (ans + s - 1) % MOD;

        if (i > 1) {
            ans = (ans + s * (n - s)) % MOD;
        }

        ll sub = d * (d - 1) / 2 % MOD;
        ans = (ans - sub + MOD) % MOD;
    }

    cout << ans << endl;
}

F Flower_Rainbow_and_Forever

不难想到我们可以把节点按点权分为三类：

$\text{X}$ ：点权为奇数
$\text{Y}$ ：点权为 $\text{4}$ 的倍数
$Z$ ：点权为除了 $\text{4}$ 的倍数以外的偶数。

$\text{X}$ 只能和 $\text{Y}$ 相连， $\text{Y}$ 可以和 $\text{X,Y,Z}$ 相连， $Z$ 只能和 $Y,Z$ 相连。

我们分别取任意一个 $\text{X,Y,Z}$ 中的元素作为根，贪心构造这棵树即可。

void solve() {
    int n;
    ll K;
    cin >> n >> K;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> xv, yv, zv;
    vector<int> typ(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        if (a[i] % 2 == 1) {
            typ[i] = 0;
            xv.pb(i);
        } else if (a[i] % 4 == 0) {
            typ[i] = 1;
            yv.pb(i);
        } else {
            typ[i] = 2;
            zv.pb(i);
        }
    }
    if (n == 1) {
        cout << 1 << endl;
        return;
    }
    if (yv.empty() && !xv.empty() && !zv.empty()) {
        cout << -1 << endl;
        return;
    }

    auto tryb = [&](int rt) -> pair<bool, vector<PII>> {
        vector<int> rm(n + 1, K);
        vector<char> in(n + 1, 0);
        deque<int> sx, sy, sz;
        for (int u : xv)
            if (u != rt) sx.pb(u);
        for (int u : yv)
            if (u != rt) sy.pb(u);
        for (int u : zv)
            if (u != rt) sz.pb(u);
        deque<int> ax, ay, az;
        vector<PII> ed;
        ed.clear();
        in[rt] = 1;
        if (rm[rt] > 0) {
            if (typ[rt] == 0)
                ax.pb(rt);
            else if (typ[rt] == 1)
                ay.pb(rt);
            else
                az.pb(rt);
        }
        auto clean = [&](deque<int>& q) {
            while (!q.empty() && rm[q.front()] == 0) q.pof();
        };
        while (ed.size() < n - 1) {
            bool ok = false;
            clean(ax);
            clean(ay);
            clean(az);
            if (!ax.empty() && !sy.empty()) {
                int p = ax.front(), u = sy.front();
                sy.pof();
                ed.eb(p, u);
                in[u] = 1;
                rm[p]--;
                if (rm[p] == 0) ax.pof();
                if (rm[u] > 0) ay.pb(u);
                ok = true;
                continue;
            }
            if (!ay.empty() && !sx.empty()) {
                int p = ay.front(), u = sx.front();
                sx.pof();
                ed.eb(p, u);
                in[u] = 1;
                rm[p]--;
                if (rm[p] == 0) ay.pof();
                if (rm[u] > 0) ax.pb(u);
                ok = true;
                continue;
            }
            if (!az.empty() && !sz.empty()) {
                int p = az.front(), u = sz.front();
                sz.pof();
                ed.eb(p, u);
                in[u] = 1;
                rm[p]--;
                if (rm[p] == 0) az.pof();
                if (rm[u] > 0) az.pb(u);
                ok = true;
                continue;
            }
            if (!ay.empty() && !sz.empty()) {
                int p = ay.front(), u = sz.front();
                sz.pof();
                ed.eb(p, u);
                in[u] = 1;
                rm[p]--;
                if (rm[p] == 0) ay.pof();
                if (rm[u] > 0) az.pb(u);
                ok = true;
                continue;
            }
            if (!ay.empty() && !sy.empty()) {
                int p = ay.front(), u = sy.front();
                sy.pof();
                ed.eb(p, u);
                in[u] = 1;
                rm[p]--;
                if (rm[p] == 0) ay.pof();
                if (rm[u] > 0) ay.pb(u);
                ok = true;
                continue;
            }
            if (!az.empty() && !sy.empty()) {
                int p = az.front(), u = sy.front();
                sy.pof();
                ed.eb(p, u);
                in[u] = 1;
                rm[p]--;
                if (rm[p] == 0) az.pof();
                if (rm[u] > 0) ay.pb(u);
                ok = true;
                continue;
            }
            if (!ok) break;
        }
        if (ed.size() != n - 1) return {false, {}};
        for (int i = 1; i <= n; i++)
            if (!in[i]) return {false, {}};
        return {true, ed};
    };

    vector<int> roots;
    if (!yv.empty()) roots.pb(yv[0]);
    if (!xv.empty()) roots.pb(xv[0]);
    if (!zv.empty()) roots.pb(zv[0]);

    bool ok = false;
    vector<PII> ans;
    int rt = -1;
    for (int r : roots) {
        auto pr = tryb(r);
        if (pr.fi) {
            ok = true;
            ans = pr.se;
            rt = r;
            break;
        }
    }
    if (!ok)
        cout << -1 << endl;
    else {
        cout << rt << endl;
        for (auto [u, v] : ans) cout << u << " " << v << endl;
    }
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#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;
}