题解 | 小白月赛 Round 129

参考代码放在最后面。

思路

A.小橘编译器

直接模拟即可。

B.小橙的好序列

对于每个好序列，下一个元素取值为 $[x-k,x+k]$ ，其中 $x$ 为上一个元素。

即数量为 $n^{2k+1}$ 。

C.小橙的完美序列

对于每个 $x$ 其对应的 $a_i$ 是唯一的，所以考虑找出现有序列每个元素的 $x$ ，并且贪心取尽可能数量多的 $x$ 值。

即对原序列变成 $a_i\oplus i$ 即可。

然后用 std::map 统计数量。

D/E.小橙的幸运数

这题做法不唯一。

我们可以考虑把序列抽象成图，且每个点的出度都是 $1$ ，由于题目特殊性，这个图每一个连通块一定是恰好仅有一个环组成的连通块，且环上所有点都可以从连通块任意一点到达。

所以我们可以考虑建反图，求出环上循环节总和 $s$ ，以及对于每个点阈值 $b_u$ ，使得 $b_u-ks(k\ge 0)$ 都能到达 $c$ 。（容易证明 $s$ 能被 $n$ 整除）

时间复杂度为 $O(n)$ 。

F.小橙的异或和

对于每个数字，至多除以 $\log a_i$ 次大于 $1$ 的数就会最终边成 $0$ ，所以暴力更新每个值，然后更新所有数的异或和即可。

用 std::set 维护每个非 $0$ 的下标即可，时间复杂度为 $O(n\log n\cdot \log 10^9)$ 。

G.小橙交换水果

对于无法交换的情况，当且仅当整棵树不存在度 $\ge 3$ 的点，否则，可以将点暂时停留在其中两个邻接点，使得两者不相遇。

此时存在两种情况：

当 $(u,v)$ 路径中（不含端点）存在度大于等于 $3$ 的点，此时可以使 $x$ 停留在该路径外的点，使得 $y$ 到达原来 $u$ 的位置，然后再令 $y$ 到达 $v$ 点，此时步数为 $2\texttt{dist}(u,v)+2$ 。
当 $(u,v)$ 路径中（不含端点）不存在度大于 $3$ 的点，则需寻找距离点 $u$ 和点 $v$ 各自最近度大于等于 $3$ 的点 $w$ ，然后 $x$ 和 $y$ 都前往点 $w$ 另外两个邻点（即不属于路径 $(u,w)$ 和 $(v,w)$ 上任意两个邻点），满足交换，此时步数为 $2\texttt{dist}(u,v)+4k+4$ ，其中 $k$ 为两点中任意一点距离点 $w$ 的距离（ $w$ 点可以与 $u$ 或 $v$ 重合）。

其中，两者都需要先求出 $\texttt{LCA}$ 和路径上度 $\ge 3$ 的点的数量，对于第二种情况，我们可以用 BFS 预处理得出。

在线做法时间复杂度为 $O(n\log n+q)$ 或者 $O(n+q \log n)$ ，离线做法时间复杂度为 $O(n + q)$ ，其中瓶颈在求 $\texttt{LCA}$ 。

代码

A.小橘编译器

void solve(){
    string s,t;
    cin >> s;
    t = s.substr(0,s.find("//"));
    if (t.empty()) cout << "null";
    else cout << t;
}

B.小橙的好序列

void solve(){
    int n,k;
    cin >> n >> k;
    cout << Z::Pow(k*2+1,n) << '\n';
}

C.小橙的完美序列

void solve(){
    int n;
    cin >> n;
    map<int,int> mp;
    for (int i = 1;i <= n;i++){
        int x;
        cin >> x;
        x ^= i;
        mp[x]++;
    }
    int ans = n;
    for (auto [x,y] : mp){
        ans = min(ans,n-y);
    }
    cout << ans << "\n";
}

D/E.小橙的幸运数

void solve(){
    int n,c,q;
    cin >> n >> c >> q;
    vector<int> a(n),b(n),k(n),vis(n);
    vector<vector<int>> G(n);
    DSU dsu(n);
    for (int i = 0;i < n;i++){
        cin >> a[i];
        int u = i,v = (i+a[i]) % n;
        G[v].push_back(u);
        dsu(u,v);
    }
    auto dfs1 = [&](auto&& dfs,int u,int lmt)->void {
        if (vis[u]) {
            k[u] = abs(b[u] - lmt);
            return;
        }
        vis[u] = 1;
        b[u] = lmt;
        for (int v : G[u]){
            dfs(dfs,v,lmt - a[v]);
        }
    };
    dfs1(dfs1,c%n,c);
    for (int i = 1;i <= q;i++){
        int x;
        cin >> x;
        if (dsu[x%n] != dsu[c%n]) {
            cout << "No\n";
            continue;
        }
        if (b[x%n] < x) {
            cout << "No\n";
            continue;
        }
        if (k[c%n] && (b[x%n] - x) % k[c%n] == 0) {
            cout << "Yes\n";
            continue;
        }
        if (b[x%n] == x) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

F.小橙的异或和

void solve(){
    int n,q;
    cin >> n >> q;
    vector<int> a(n+1);
    int ans = 0;
    set<int> st;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++){
        ans ^= a[i];
        if (a[i]) st.insert(i);
    }
    for (int i = 1;i <= q;i++){
        int op;
        cin >> op;
        if (op == 2) cout << ans << "\n";
        else {
            int l,r;
            cin >> l >> r;
            for (int j = l;j <= r;){
                ans ^= a[j];
                a[j] /= j - l + 1;
                ans ^= a[j];
                if (a[j] == 0) st.erase(j);
                auto it = st.upper_bound(j);
                if (it == st.end()) j = n+1;
                else j = *it;
            }
        }
    }
    
}

G.小橙交换水果

void solve(){
    int n,q;
    cin >> n >> q;
    vector<vector<int>> G(n+1);
    int dfnt = 0;
    vector<int> dep(n+1),dfn(n+1),dist(n+1,1e9),pre(n+1),fa(n+1),seq(1);
    vector<bool> vis(n+1);
    for (int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    queue<int> que;
    for (int i = 1;i <= n;i++){
        if (G[i].size() >= 3) {
            que.push(i);
            dist[i] = 0;
            vis[i] = 1;
        }
    }
    while (que.size()){
        int u = que.front();
        que.pop();
        for (int v : G[u]){
            if (vis[v]) continue;
            que.push(v);
            vis[v] = 1;
            dist[v] = dist[u] + 1;
        }
    }
    auto dfs = [&](auto&& dfs,int u,int pa)->void {
        seq.push_back(u);
        dep[u] = dep[pa] + 1;
        fa[u] = pa;
        dfn[u] = ++dfnt;
        pre[u] = pre[pa] + (G[u].size() >= 3);
        for (int v : G[u]){
            if (v == pa) continue;
            dfs(dfs,v,u);
        }
    };
    dfs(dfs,1,0);
    // O(1) LCA
    SparseTable<int> st(seq,1,[&](int x,int y)->int {
        return dep[x] < dep[y] ? x : y;
    });
    auto lca = [&](int x,int y)->int {
        if (x == y) return x;
        x = dfn[x],y = dfn[y];
        if (x > y) swap(x,y);
        return fa[st(x+1,y)];
    };
    
    for (int _i = 1;_i <= q;_i++){
        int x,y;
        cin >> x >> y;
        int anc = lca(x,y);
        int cnt = pre[fa[x]] + pre[fa[y]] - pre[anc] - pre[fa[anc]];
        int ans = -1;
        if (cnt > 0) {
            ans = (dep[x] + dep[y] - dep[anc] * 2) * 2 + 2;
        } else if (dist[x] <= n || dist[y] <= n) {
            ans = (dep[x] + dep[y] - dep[anc] * 2) * 2;
            int dis = min(dist[x],dist[y]);
            ans += (dis + 1) * 4;
        }
        cout << ans << "\n";
    }
}

模板

ST 表

template<typename T>
struct SparseTable {
    std::vector<std::vector<T>> st;
    std::function<T(T, T)> opt;
    SparseTable(const vector<T>& ele, int beg, std::function<T(T, T)> func) : opt(func) {
        build(ele, beg);
    }
    SparseTable(const vector<T>& ele, int beg = 0) {
        opt = [](T a, T b) { return max(a, b); };
        build(ele, beg);
    }
    void build(const vector<T>& ele, int beg) {
        int n = ele.size() - 1;
        int len = n - beg + 1;
        if (len <= 0) return;
        int p = __lg(len);
        st.assign(n + 1, vector<T>(p + 1));
        for (int i = beg; i <= n; i++) st[i][0] = ele[i];
        for (int j = 1; j <= p; j++) {
            for (int i = beg; i + (1 << j) - 1 <= n; i++) {
                st[i][j] = opt(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    T operator()(int l, int r) const {
        int p = __lg(r - l + 1);
        return opt(st[l][p], st[r - (1 << p) + 1][p]);
    }
};

取模类与组合数

template <long long MOD>
struct ModInt{
    long long val = 0;
    ModInt(long long x = 0):val(norm(x)){}
    long long operator()(){ return val; }
    constexpr ModInt operator-() const {
        return ModInt(MOD - val);
    }
    constexpr ModInt operator~() const {
        assert(val != 0);
        return Pow(val,MOD-2);
    }
    constexpr ModInt& operator+=(ModInt x){
        return val += x(),val = norm(val),*this;
    }
    constexpr ModInt& operator-=(ModInt x){
        return val -= x(),val = norm(val),*this;
    }
    constexpr ModInt& operator*=(ModInt x){
        return val *= x(),val = norm(val),*this;
    }
    constexpr ModInt& operator/=(ModInt x){
        return val *= (~x)(),val = norm(val),*this;
    }
    constexpr ModInt& operator^=(long long y){
        return val = Pow(*this,y)(),*this;
    }
    constexpr ModInt& operator++(){
        return val ++,val = norm(val),*this;
    }
    constexpr ModInt operator++(int){
        ModInt v = *this;
        return val ++,val = norm(val),v;
    }
    constexpr ModInt& operator--(){
        return val --,val = norm(val),*this;
    }
    constexpr ModInt operator--(int){
        ModInt v = *this;
        return val --,val = norm(val),v;
    }
    constexpr friend ModInt operator+(ModInt x, ModInt y){
        return x += y;
    }
    constexpr friend ModInt operator-(ModInt x, ModInt y){
        return x -= y;
    }
    constexpr friend ModInt operator*(ModInt x, ModInt y){
        return x *= y;
    }
    constexpr friend ModInt operator/(ModInt x, ModInt y){
        return x /= y;
    }
    constexpr friend ModInt operator^(ModInt x, long long y){
        return x ^= y;
    }
    constexpr friend std::ostream& operator<<(std::ostream& os,ModInt x){
        return os << x();
    }
    constexpr friend std::istream& operator>>(std::istream& is,ModInt &x){
        is >> x.val, x.val = norm(x.val);
        return is;
    }
    constexpr static long long norm(long long x){
        return x < 0 ? (x % MOD + MOD) % MOD : x % MOD;
    }
    constexpr static ModInt Pow(ModInt x,long long y){
        ModInt ans = 1;
        for (;y; y >>= 1,x *= x)
            if (y & 1) ans *= x;
        return ans;
    }
};
 
using Z = ModInt<998244353>;

主程序

#include<bits/stdc++.h>
#if __has_include("tool/local.hpp")
#include "tool/local.hpp"
#include "grader.hpp"
#else
#define Testcases(T) while(T--) solve();
    #ifndef ONLINE_JUDGE
    #define listen(...) freopen("data.in","r",stdin),freopen("data.out","w",stdout);
    #else
    #define listen(...)
    #endif
#endif
using namespace std;
// Base type
using ll = long long;
using ld = long double;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using p32 = std::array<int,2>;
using p64 = std::array<i64,2>;

// mt19937_64 rnd(time(0));

void solve(){
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr),std::cout.tie(nullptr);
    listen(_TIMER,_FILE,_CHECKER);
    int T = 1;
    std::cin >> T;
    Testcases(T);
    return 0;
}

/*
 | Code By Kendieer
 | Model Updated : 2025/12/09
 | Code With VSCode
*/

题解 | 小白月赛 Round 129

思路

A.小橘编译器

B.小橙的好序列

C.小橙的完美序列

D/E.小橙的幸运数

F.小橙的异或和

G.小橙交换水果

代码

A.小橘编译器

B.小橙的好序列

C.小橙的完美序列

D/E.小橙的幸运数

F.小橙的异或和

G.小橙交换水果

模板

ST 表

取模类与组合数

主程序

The End