题解 | 小白月赛 Round 129
|
30
|
0
|
小白月赛,牛客,题解

1522 字
|
26 分钟

很好的一套题，个人难度顺序大致为 $ABCDFEG$ 。

A 小橘编译器

扫到 $//$ 时直接截断即可，输出的时候判断一下已经处理的串是否为空。

void solve() {
    string s;
    cin >> s;
    string ans = "";
    char p = '@';
    for (auto v : s) {
        if (v == p && v == '/') {
            ans.pob();
            break;
        }
        ans += v;
        p = v;
    }
    if (ans.size() == 0)
        cout << "null" << endl;
    else
        cout << ans << endl;
}

B 小橙的好序列

看错题 $+1$ 。

记上一位为 $x$ ，那么下一步可以取的范围为 $[x-k,x+k]$ ，一共 $2k+1$ 种可能，而且每一步都是互相独立的，长度为 $n+1$ 的序列需要我们做 $n$ 次选择，所以个数为 $(2k+1)^n$ 。

void solve() {
    int n, k;
    cin >> n >> k;
    cout << ksm(Z(2 * k + 1), n) << endl;
}

C 小橙的完美序列

不难发现，对于每一个位置，需要的 $x$ 都能够唯一被确定，即 $x = a[i]\oplus i$ ，我们统计每一个位置需要的 $x$ ，然后统计一下哪个 $x$ 被最多位置需要，数量为 $t$ ，答案即为 $n-t$ 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    unordered_map<int, int> mp;
    for (int i = 1; i <= n; ++i) {
        mp[a[i] ^ i]++;
    }
    int ans = inf;
    for (auto [_, v] : mp) {
        ans = min(ans, n - v);
    }
    cout << ans << endl;
}

D 小橙的幸运数（easy）

由于我的 $D$ 和 $E$ 采用了不同的方法（实际上是同一个思路，但是 $D$ 写得比较裸，所以 $E$ 就重新写了），所以两道题分开讲。

如果只关注在模 $m$ 意义下的转移，那么每个状态 $i\in {0,1,…,m−1}$ 都会有唯一的确定的下一个状态 $(i+a_i)\mod m$ ，也就是说，转移一定会以循环的形式出现，所以我们直接模拟转移的轨迹，直到超过差值 $d=c-x$ ，或者找到循环。

void solve() {
    int m, c, q;
    cin >> m >> c >> q;
    vector<ll> a(m);
    for (int i = 0; i < m; ++i) cin >> a[i];
    while (q--) {
        ll x;
        cin >> x;
        if (x == c) {
            cout << "Yes" << endl;
            continue;
        }
        if (x > c) {
            cout << "No" << endl;
            continue;
        }
        vector<int> vis(m, -1);
        vector<ll> vals;
        bool ok = false;
        while (true) {
            if (x == c) {
                ok = true;
                break;
            }
            if (x > c) {
                ok = false;
                break;
            }
            int r = x % m;
            if (vis[r] != -1) {
                int p = vis[r];
                ll S = x - vals[p];
                if (S > 0) {
                    for (int i = p; i < vals.size(); ++i) {
                        ll v = vals[i];
                        if (v <= c && (c - v) % S == 0) {
                            ok = true;
                            break;
                        }
                    }
                }
                break;
            }
            vis[r] = vals.size();
            vals.pb(x);
            x += a[r];
        }
        cout << (ok ? "Yes" : "No") << endl;
    }
}

E 小橙的幸运数（hard）

刚刚说到了循环，那我们可以直接把所有的循环先预处理，那么整个图肯定会有以下特点：

  • 环是有向的
  • 环上的每一个点在模 $m$ 意义下均不同
  • 每个点的出度都为 $1$

那么整个转移的过程就会变成一个内向基环森林。

要使某个数字 $x$ 最终变为 $c$，它在状态转移中必须经过目标状态 $tar=c \mod m$ 。当且仅当状态首次到达 $tar$ 时，它才有机会恰好等于 $c$ ；如果不够，则必须依赖 $tar$ 所在的环进行绕圈来累加数值，所以我们统计其他点到 $tar$ 的距离（建反图跑 $bfs$ ），然后计算 $tar$ 所在环的增量 $sc$（不在环上记为 $-1$ ），计算即可。

void solve() {
    int m, c, q;
    cin >> m >> c >> q;
    vector<ll> a(m);
    for (int i = 0; i < m; ++i) cin >> a[i];
    int tar = c % m;

    ll sc = -1, sum = 0;
    int cur = tar;
    vector<bool> vis(m);
    vis[tar] = true;
    while (true) {
        int nxt = (cur + (a[cur] % m)) % m;
        sum += a[cur];

        if (nxt == tar) {
            sc = sum;
            break;
        }
        if (vis[nxt]) {
            sc = -1;
            break;
        }
        vis[nxt] = true;
        cur = nxt;
    }
    vector<vector<int>> g(m);
    for (int i = 0; i < m; ++i) {
        int nxt = (i + (a[i] % m)) % m;
        g[nxt].pb(i);
    }

    vector<ll> dist(m, -1);
    queue<int> qu;

    dist[tar] = 0;
    qu.push(tar);

    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();

        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + a[v];
                qu.push(v);
            }
        }
    }

    while (q--) {
        ll x;
        cin >> x;

        int r = x % m;
        if (dist[r] == -1) {
            cout << "No" << endl;
        } else {
            ll D = dist[r];
            if (x + D > c) {
                cout << "No" << endl;
            } else if (x + D == c) {
                cout << "Yes" << endl;
            } else {
                if (sc > 0) {
                    if ((c - (x + D)) % sc == 0) {
                        cout << "Yes" << endl;
                    } else {
                        cout << "No" << endl;
                    }
                } else {
                    cout << "No" << endl;
                }
            }
        }
    }
}

F 小橙的异或和

因为每次值发生变化时，这个值至少减半，也就是说，一个元素最多修改 $log_2(a_i)$ 次，所以我们暴力修改即可，每次跳过已经变成 $0$ 的元素（使用链表）。

void solve() {
    int n, q, osum = 0;
    cin >> n >> q;
    vector<int> a(n + 1), nxt(n + 2);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        osum ^= a[i];
        if (a[i] == 0)
            nxt[i] = i + 1;
        else
            nxt[i] = i;
    }
    nxt[n + 1] = n + 1;

    function<int(int)> find = [&](int x) { return nxt[x] == x ? x : nxt[x] = find(nxt[x]); };

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            int pos = find(l);
            if (pos == l) pos = find(l + 1);
            while (pos <= r) {
                int d = pos - l + 1;
                ll nv = a[pos] / d;
                if (nv != a[pos]) {
                    osum ^= a[pos];
                    osum ^= nv;
                    a[pos] = nv;
                    if (nv == 0) {
                        nxt[pos] = pos + 1;
                    }
                }
                pos = find(pos + 1);
            }
        } else {
            cout << osum << endl;
        }
    }
}

G 小橙交换水果

$u$ 和 $v$ 的交换本质上是：

  • $u$ 和 $v$ 相遇
  • 一个点让步到某个非主干路径的侧边节点上，让另一个点先过
  • 各自到终点

也就是说我们要找到 $u$ 到 $v$ 的一条路径，路径上至少有一个度为 $3$ 的点让 $u$ 和 $v$ 跨越。

首先先判断整棵树上有没有度 $\geq 3$ 的点，如果没有，那么肯定无法完成让步，即交换肯定无法完成。

对于剩余的情况，我们需要讨论最短的路径内有没有度 $\geq 3$ 的点：

  • 最短路径内存在度 $\geq 3$​ 的点： 我们可以直接在这个点完成让步，最少操作次数为：
    $$2\times dist(u,v)+2$$
  • 最短路径内不存在度 $\geq 3$​ 的点： 也就是说，两个水果都不可避免地需要走到某个远离主路且度数 $\geq 3$​ 的最近换道点去完成跨越。设某个节点 $x$ 到最近的度数 $\geq 3$ 的节点的距离为 $D3(x)$（如果节点 $x$ 本身度数 $\geq 3$ ，则 $D3(x)=0$ ）。此时应该选择靠近 $u$ 或靠近 $v$ 较近的一侧出去完成交换。此时最少操作数为：
    $$2\times dist(u,v)+4\times \min(D3(u),D3(v))+4$$

使用 $LCA$ 求一下最短路径即可。

void solve() {
    int n, q;
    cin >> n >> q;
    Tree tr(n);
    vector<int> deg(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        tr.add(u, v);
        deg[u]++, deg[v]++;
    }

    queue<int> qu;
    vector<int> D3(n + 1, inf);

    for (int i = 1; i <= n; ++i) {
        if (deg[i] >= 3) {
            tr.d3[i] = 1;
            D3[i] = 0;
            qu.push(i);
        }
    }

    if (qu.empty()) {
        while (q--) {
            int u, v;
            cin >> u >> v;
            cout << -1 << endl;
        }
        return;
    }

    tr.work();

    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int v : tr.ver[u]) {
            if (D3[v] > D3[u] + 1) {
                D3[v] = D3[u] + 1;
                qu.push(v);
            }
        }
    }

    while (q--) {
        int u, v;
        cin >> u >> v;

        int lca = tr.lca(u, v), d = tr.clac(u, v);

        if (tr.sum[u] + tr.sum[v] - 2 * tr.sum[lca] + tr.d3[lca] - tr.d3[u] - tr.d3[v] > 0) {
            cout << 2ll * d + 2 << endl;
        } else {
            cout << 2ll * d + 4ll * min(D3[u], D3[v]) + 4 << endl;
        }
    }
}

自动取模

constexpr int MOD = 998244353;

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

倍增 LCA

struct Tree {
    int n;
    vector<vector<int>> ver, val;
    vector<int> lg, dep;

    vector<int> sum, d3;

    Tree(int n) {
        this->n = n;
        ver.resize(n + 1);
        val.resize(n + 1, vector<int>(30));
        lg.resize(n + 1);
        dep.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        }

        sum.resize(n + 1);
        d3.resize(n + 1);
    }
    void add(int x, int y) {
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    void dfs(int x, int fa) {
        val[x][0] = fa;
        dep[x] = dep[fa] + 1;

        sum[x] = sum[fa] + d3[x];

        for (int i = 1; i <= lg[dep[x]]; i++) {
            val[x][i] = val[val[x][i - 1]][i - 1];
        }
        for (auto y : ver[x]) {
            if (y == fa) continue;
            dfs(y, x);
        }
    }
    int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);
        while (dep[x] > dep[y]) {
            x = val[x][lg[dep[x] - dep[y]] - 1];
        }
        if (x == y) return x;
        for (int k = lg[dep[x]] - 1; k >= 0; k--) {
            if (val[x][k] == val[y][k]) continue;
            x = val[x][k];
            y = val[y][k];
        }
        return val[x][0];
    }
    int clac(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }
    void work(int root = 1) { dfs(root, 0); }
};
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇