【湖北工业大学2025年ACM校赛（同步赛）】题解

比赛链接

A. 蚂蚁上树

题目大意

给定一棵 $n$ 个结点的树，根结点为 $1$。每个 叶结点 都有一只蚂蚁，每过 $1$ 秒钟，你可以选一些蚂蚁往其 父结点 走一步，但是要求任意两只蚂蚁都不能在同一个 非根结点 上。

问至少要多少时间，使得所有蚂蚁都走到 根节点。

数据范围

• $2\le n\le 5\cdot 10^5.$

Solution

显然，根结点 $1$ 的每个儿子都是独立的，所以下面考虑其中一个儿子 $x$。

直觉上考虑，对于越深的结点，应该越迟到 $x$，所以我们可以将 $x$ 下所有的叶子按照深度从小到大排序，初始化 $d=0$，接着顺序遍历这些结点，然后不断令 $d=\max (d+1,de{p}_i)$，其中 $de{p}_i$ 表示结点 $i$ 的深度。

这表示，如果深度相同，需要等我往上走一步，再轮到你；否则你至少比我落后一步。

答案就是每个儿子 $d$ 的最大值。

时间复杂度 $O(n\log n)$

C++ Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<int> dep(n);
    std::vector<int> par(n, -1);
    std::vector<std::vector<int>> leaf(n);
    auto dfs = [&](auto &&self, int x, int bel) -> void {
        if (x != bel and adj[x].empty()) {
            leaf[bel].push_back(x);
        }
        for (int y: adj[x]) {
            adj[y].erase(std::ranges::find(adj[y], par[y] = x));
            dep[y] = dep[x] + 1;
            self(self, y, bel != 0 ? bel: y);
        }
    };
    dfs(dfs, 0, 0);

    if (std::ranges::max(dep) == 1) {
        std::cout << 1 << "\n";
        return 0;
    }

    int ans = 1;
    for (auto &l: leaf) {
        std::ranges::sort(l, [&](int x, int y) {
            return dep[x] < dep[y];
        });
        int res = 0;
        for (int x: l) {
            res = std::max(res + 1, dep[x]);
        }
        ans = std::max(ans, res);
    }
    std::cout << ans << "\n";
    
    return 0;
}

B. 奶龙大战贝利亚

题目大意

奶龙和贝利亚在玩一个游戏，给出一个 $n\times m$ 的棋盘，棋盘上摆满了黑白棋。

每一轮玩家可以按顺序执行如下操作：

• 选择其中一行，该行 至少 存在一个黑面朝上的棋子；
• 从该行选择至少一个棋子，且选择的棋子中最左边的那个棋子必须为黑面朝上；
• 将选择的棋子依次翻转（黑变白，白变黑）。

两人轮流依次进行操作，奶龙先手。

如果轮到某人时无法操作，则此人输掉了游戏。

给定起始盘面，$W$ 表示该格棋子是白面朝上，$B$ 表示该格棋子是黑面朝上。

奶龙想知道在两人都足够聪明的情况下，它是否有必胜方案。

数据范围

• $1\le n\times m\le 10^6.$

Solution

赛时是猜了三发猜出来的，证明的话可以直接看 官解。

把 $B$ 看作 $1$，$W$ 看作 $0$，然后我们就有了 $n$ 个长度均为 $m$ 的二进制数。

那么结论就是：这 $n$ 行的二进制数异或和不为 $0$，先手必胜。

时间复杂度 $O(\mathrm{nm})$

C++ Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    auto s = std::string(m, '0');
    for (int i = 0; i < n; i++) {
        std::string g;
        std::cin >> g;

        for (int j = 0; j < m; j++) {
            if (g[j] == 'B') {
                s[j] ^= 1;
            }
        }
    }

    std::cout << (std::ranges::count(s, '1') > 0 ? "Yes\n": "No\n");
    
    return 0;
}

C. 我是奶龙

题目大意

给定 $T$ 组数据，每组给定三个非负整数 $n,m,k$。

对于每组 $n,m,k$，它表示：

• 有一群奶龙变成了三种颜色，其中 $n$ 条红奶龙，$m$ 条蓝奶龙，$k$ 条黄奶龙。当 两条不同颜色 的奶龙相遇时，它们会为了证明自己是真奶龙都会 变为第三种颜色，每个时刻只有一对奶龙相遇，问一段时间后，所有奶龙颜色是否可能相同？

数据范围

• $1\le T\le 10^5,$
• $0\le n,m,k\le 10^{18}.$

Solution

算是个小数学题，我们一步步来推导。令 $s=n+m+k$。

假设红奶龙（$R$）和蓝奶龙（$B$）相遇，他们都会变成黄奶龙（$Y$），那么就有

$$\begin{array}{rl}n& :=n-1,\\ m& :=m-1,\\ k& :=k+2.\end{array}$$

观察发现，任意两者之间的差值关于 $3$ 的余数都没有变化。

从结果出发，即 $(s,0,0),(0,s,0),(0,0,s)$ 其中之一，我们发现最终的 $n^{\prime },m^{\prime },k^{\prime }$ 一定满足：

• 其中两个数对 $3$ 的余数是相同的。

时间复杂度 $O(T)$

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 n, m, k;
    std::cin >> n >> m >> k;

    std::set<int> s {n % 3, m % 3, k % 3};

    if (s.size() < 3) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int T = 1;
    std::cin >> T;
    
    while (T--) {
        solve();
    }
    
    return 0;
}

D. 多米诺骨牌

题目大意

还是在牛客看题面吧（)

Solution

由于我是 0-indexed，所以下面的叙述全都是在原题的基础上下标 $-1$。

原题中 $a_i+0.5$ 的位置，设其高度为 $h$（这是整数），能覆盖的区间是 $[a_i+0.5-h,a_i+0.5]$，整点覆盖区间就是 $(a_i+0.5-h,a_i+0.5)$，由于浮点有误差，所以我们可以将其变为整点，也就是 $a_i:=a_i+0.5$，这样覆盖区间就变成 $[a_i-h,a_i)$（此时 $a_i$ 是整点）。

根据题意，覆盖到的区间可以传递，因此我们只要保证 $[0,n)$ 都能被覆盖到。因此对于 $[a_i-h,a_i)$ 这样的覆盖区间，我们可以用差分统计，最后做一下前缀和得到 $s$ 数组。

设现在未覆盖的点（即 $s_i=0$ 的位置）有 $\mathrm{sum}$ 个，对于当前的操作，我们把 $a_x$ 改为 $y$，那么 $a_x$ 的覆盖区间 $[a_x-h,a_x)$ 会变为 $[a_x-h+1,a_x)$，因为高度少了 $1$，而对于 $y$，$[y-h,y)$ 会扩展为 $[y-h-1,y)$。

这样就可以在 $a_x-h$ 上和 $y-h-1$ 上进行单点修改。

时间复杂度 $O(n+q)$

C++ Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    std::vector<int> h(n + 2);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        h[a[i]]++;
    }
    std::vector<int> s(n + 1);
    for (int i = 1; i <= n; i++) {
        s[std::max(i - h[i], 0)]++;
        s[i]--;
    }
    int sum = s[0] == 0;
    for (int i = 1; i < n; i++) {
        s[i] += s[i - 1];
        sum += s[i] == 0;
    }

    while (m--) {
        int x, y;
        std::cin >> x >> y;
        x--;

        int &p = a[x];
        if (p >= h[p] and --s[p - h[p]] == 0) {
            sum++;
        }
        h[p]--;
        h[y]++;
        if (y >= h[y] and s[y - h[y]]++ == 0) {
            sum--;
        }
        p = y;
        std::cout << sum << "\n";
    }
    
    return 0;
}

E. 找出猫猫虫

题目大意

给定 $N$ 对数 $(L_i,R_i)$，要求你构造一个数组 $X$，满足：

• $|X|=N$；
• $\forall i\in [1,N]$，均有 $X_i\in [L_i,R_i]$；
• $\sum _{i=1}^N{X}_i=0$。

数据范围

• $1\le N\le 2\cdot 10^5,$
• $-10^9\le L_i,R_i\le 10^9.$

Solution

很明显我们需要贪心。

首先令 $sL=\sum _{i=1}^N{L}_i,sR=\sum _{i=1}^N{R}_i$，若 $sL>0$ 或 $sR<0$，则一定无法满足 $\sum _{i=1}^N{X}_i=0$。

否则我们从 $sL$ 开始，尝试往里填充 $-sL$。令 $add=-sL$，每次需要填充的数为 $\min (add,R_i-L_i)$，最后判断 $add$ 是否减到 $0$ 即可。

时间复杂度 $O(N)$

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &x: v) {
        is >> x;
    }
    return is;
}
template<class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    os << v[0];
    for (size_t i = 1; i < v.size(); i++) {
        os << " " << v[i];
    }
    return os;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<std::pair<int, int>> cat(N);
    std::cin >> cat;

    i64 sL = 0;
    i64 sR = 0;
    for (const auto &[L, R]: cat) {
        sL += L;
        sR += R;
    }
    if (sL > 0 or sR < 0) {
        std::cout << "No\n";
        return 0;
    }

    i64 add = -sL;
    std::vector<int> X;
    X.reserve(N);
    for (const auto &[L, R]: cat) {
        X.push_back(L);
        int x = std::min<i64>(R - L, add);
        X.back() += x;
        add -= x;
    }
    if (add == 0) {
        std::cout << "Yes\n";
        std::cout << X << "\n";
    } else {
        std::cout << "No\n";
    }
    
    return 0;
}

F. 点灯

题目大意

这个讲起来有点麻烦，可以直接去题目链接里看题意，大致就是放灯泡，灯泡之间不能互相照亮，求最多能放的灯泡数。

数据范围

• $2\le n,m\le 200,$
• $0\le a_{i,j}<2.$

Solution

说实话我记得在某届篮球杯看到过类似的题，当时群友说的就是二分图最大匹配，所以我就试了一下，然后也算歪打正着对了。

看官解的描述是这样转化的：

• 称横向每一段黑色格子的右边线为横墙，竖向每一段黑色格子左边线为竖墙。每一个灯泡都对应唯一一段横墙和竖墙。为了使得两个灯泡不互相照亮，每一个横墙或竖墙都得唯一对应一个灯泡。将每一段白色格子所对应横墙和竖墙连一条边，问题就转化成了二分图最大匹配问题。

时间复杂度 $O(n^3)$

• 我这个板子好久了，但是复杂度应该蛮低的，可能不到 $O(n^3)$。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &x: v) {
        is >> x;
    }
    return is;
}

struct augment_path {
    std::vector<std::vector<int>> g;
    std::vector<int> pa;  // 匹配
    std::vector<int> pb;
    std::vector<int> vis;  // 访问
    int n, m;         // 两个点集中的顶点数量
    int dfn;          // 时间戳记
    int res;          // 匹配数

    augment_path(int _n, int _m): n{_n}, m{_m} {
        assert(0 <= n and 0 <= m);
        pa = std::vector<int>(n, -1);
        pb = std::vector<int>(m, -1);
        vis = std::vector<int>(n);
        g.resize(n);
        res = 0;
        dfn = 0;
    }

    void add(int from, int to) {
        assert(0 <= from and from < n and 0 <= to and to < m);
        g[from].push_back(to);
    }

    bool dfs(int v) {
        vis[v] = dfn;
        for (int u: g[v]) {
            if (pb[u] == -1) {
                pb[u] = v;
                pa[v] = u;
                return true;
            }
        }
        for (int u: g[v]) {
            if (vis[pb[u]] != dfn and dfs(pb[u])) {
                pa[v] = u;
                pb[u] = v;
                return true;
            }
        }
        return false;
    }

    int match() {
        while (true) {
            dfn += 1;
            int cnt = 0;
            for (int i = 0; i < n; i += 1) {
                if (pa[i] == -1 and dfs(i)) {
                    cnt += 1;
                }
            }
            if (cnt == 0) {
                break;
            }
            res += cnt;
        }
        return res;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector g(n, std::vector(m, 0));
    for (auto &v: g) {
        std::cin >> v;
    }

    int N = 0;
    std::vector row(n, std::vector(m, -1));
    for (int i = 0; i < n; i++) {
        int k = -1;
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 1) {
                k = -1;
                continue;
            }
            if (k < 0) {
                k = N++;
            }
            row[i][j] = k;
        }
    }
    int M = 0;
    std::vector col(n, std::vector(m, -1));
    for (int j = 0; j < m; j++) {
        int k = -1;
        for (int i = 0; i < n; i++) {
            if (g[i][j] == 1) {
                k = -1;
                continue;
            }
            if (k < 0) {
                k = M++;
            }
            col[i][j] = k;
        }
    }

    augment_path ag(N, M);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 0) {
                ag.add(row[i][j], col[i][j]);
            }
        }
    }

    std::cout << ag.match() << "\n";
    
    return 0;
}

G. 俄罗斯方块

题目大意

给定七个俄罗斯方块的数量，分别为 $I,O,T,J,L,S,Z$，保证 $T=S=Z=0$。下图为示例。

现在要拼成一个 $2\times 2K$ 的矩阵，要求矩阵的每个格子都要被其中一个方块占据，且方块不能超出 $2\times 2K$ 这个矩阵的边缘。同时，方块不能翻转，只能旋转。

求 $K$ 的最大值。

数据范围

• $0\le I,O,T,J,L,S,Z\le 10^9,$
• $T=S=Z=0.$

Solution

显然 $O$ 这个四四方方的直接往上放就好。

对于 $I,J,L$，第一想法都是两个 $I$ 变成 $2\times 4$，两个 $J$（$L$） 变成 $2\times 4$。

但是有一种特殊情况，就是 $I$ 作为底，左上角一个 $L$，右上角一个 $J$，这样能凑出 $2\times 6$。而这个$2\times 6$ 最多只出现一次，因为假设出现 $2$ 次，就相当于 $2\times 12$，根据上面所说，可以变成 $3$ 个 $2\times 4$，分别是 $2I$ 组合，$2J$ 组合，$2L$ 组合，这是等价的。

时间复杂度 $O(1)$

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 I, O, T, J, L, S, Z;
    std::cin >> I >> O >> T >> J >> L >> S >> Z;

    i64 min = std::min({I, J, L});
    int i = I % 2;
    int j = J % 2;
    int l = L % 2;
    int s = i + j + l;

    i64 ans = O;
    if (min == 0) {
        ans += (I - i) + (J - j) + (L - l);
    } else {
        ans += (I + J + L) - std::min(s, 3 - s);
    }
    std::cout << ans << "\n";
    
    return 0;
}

H. Super big cup

题目大意

给定一个长度为 $n$ 的数组 $a$，对其做 $m$ 次操作，每次操作如下：

• 给定区间 $[l,r]\subset [1,n]$ 和 $x$，然后在此区间内随机等概率地选择一个 $p$，令 $a_p=x$。

求 $m$ 次操作后每个 $a_i$ 的期望。答案对 $998244353$ 取模。

数据范围

• $1\le n,m\le 2\cdot 10^5,$
• $1\le a_i\le 10^9,$
• $1\le l\le r\le n,$
• $0\le x\le 10^9.$

Solution

对于一个 $[l,r]$，考虑 $i\in [l,r]$，$a_i$ 有 $p=\frac{1}{r-l+1}$ 的概率被选中被改为 $x$，有 $1-p=\frac{r-l}{r-l+1}$ 的概率不变，因此有 $$a_i^{\prime }=(1-p)a_i+p\cdot x.$$ 于是我们发现了熟悉的形式：对旧值乘一个系数，加一个偏移量，这就是线段树的经典题目了。

简单来说，维护乘积积 $\mathrm{mul}$，以及偏移量 $\mathrm{add}$，每次修改只要

$$\begin{array}{rl}mul& :=(1-p)\cdot mul,\\ add& :=(1-p)\cdot add+p\cdot x.\end{array}$$

时间复杂度 $O((\mathrm{n}+\mathrm{m})\log \mathrm{n}+\mathrm{m}\log \mathrm{V})$

• 其中 $\log n$ 是线段树操作，$\log V$ 是求逆元操作。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &x: v) {
        is >> x;
    }
    return is;
}

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::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();
 
constexpr int P = 998244353;
using Z = MInt<P>;

template<class Info, class Tag>
struct LazySegmentTree {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() {}
    LazySegmentTree(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    LazySegmentTree(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag &v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y or r <= x) {
            return -1;
        }
        if (l >= x and r <= y and !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        push(p, r - l);
        int m = l + r >> 1;
        int res = findFirst(l(p), l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(r(p), m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y or r <= x) {
            return -1;
        }
        if (l >= x and r <= y and !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        push(p, r - l);
        int m = l + r >> 1;
        int res = findLast(r(p), m, r, x, y, pred);
        if (res == -1) {
            res = findLast(l(p), l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
    #undef l(p)
    #undef r(p)
};

struct Tag {
    Z mul = 1;
    Z add = 0;
    void apply(const Tag &t) {
        mul = mul * t.mul;
        add = add * t.mul + t.add;
    }
};
struct Info {
    Z sum = 0;
    void apply(const Tag &t, int len) {
        sum = sum * t.mul + t.add;
    }
};
Info operator+(const Info &a, const Info &b) {
    return {a.sum + b.sum};
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    std::cin >> a;

    LazySegmentTree<Info, Tag> sgt(n);
    for (int i = 0; i < n; i++) {
        sgt.modify(i, {a[i]});
    }

    while (m--) {
        int l, r, x;
        std::cin >> l >> r >> x;
        l--;

        Z p = Z(r - l).inv();
        sgt.Apply(l, r, {1 - p, p * x});
    }

    for (int i = 0; i < n; i++) {
        std::cout << sgt.query(i, i + 1).sum << " \n"[i == n - 1];
    }
    
    return 0;
}

I. DeepSeek

Solution

前缀和 + 二分即可。

看官解是 $\mathrm{deepseek}$ 出的，感觉还挺有意思。

时间复杂度 $O(Q\log N)$

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &x: v) {
        is >> x;
    }
    return is;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, Q;
    std::cin >> N >> Q;

    std::vector<int> R(N);
    std::cin >> R;

    std::ranges::sort(R);

    std::vector<i64> s(N + 1);
    for (int i = 0; i < N; i++) {
        s[i + 1] = s[i] + R[i];
    }

    while (Q--) {
        i64 X;
        std::cin >> X;

        int i = std::ranges::upper_bound(s, X) - s.begin() - 1;
        std::cout << i << "\n";
    }
    
    return 0;
}

J. 湖工三宝

Solution

非常明显的反悔贪心。

具体做法已经套路化：对截止时间 $e$ 排序，然后如果 $T+t\le e$，就选它；否则看大根堆里之前选的那些有没有 $t^{\prime }$ 比当前的 $t$ 大的，直接换掉。

官解似乎还有个 $01$ 背包解法，感兴趣可以去看看。

时间复杂度 $O(n\log n)$

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<std::array<int, 4>> job(n);
    for (auto &[e, a, b, c]: job) {
        std::cin >> a >> b >> c >> e;
    }
    std::ranges::sort(job);

    int T = 0;
    int ans = 0;
    std::priority_queue<int> q;
    for (const auto &[e, a, b, c]: job) {
        int t = a + b + c;
        if (T + t <= e) {
            T += t;
            q.push(t);
            ans++;
            continue;
        }
        if (not q.empty() and q.top() > t) {
            T -= q.top(); q.pop();
            q.push(t);
            T += t;
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

K. 在哪签到?

Solution

直接输出 $\mathrm{HBUT}$。

Python Code

print("HBUT")

L. 帮帮Carson

Solution

模拟题，直接三位三位模拟。

C++ Code

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    int ans = std::numeric_limits<int>::max() / 2;
    for (int i = 0; i + 3 <= s.size(); i++) {
        ans = std::min(ans, std::abs(std::stoi(s.substr(i, 3)) - 753));
    }
    std::cout << ans << "\n";
    
    return 0;
}

M. 奶龙农场的宝藏计算

题目大意

给定 $n$ 只奶绿，每只奶龙都有一个“可爱值”，用一个整数表示，可爱值越大越可爱。

农场主发现了一个神奇的现象：当几只奶龙聚在一起玩耍时，它们会创造出一个“快乐宝藏”，而宝藏的价值取决于这个小团体中“最可爱”的奶龙和“最不可爱”的奶龙的可爱值的乘积。

现在，农场主记录了所有奶龙的可爱值，形成了一个长度为 $n$ 的序列 $a$。

他想知道，如果考虑所有可能的奶龙组合（即所有非空子序列），这些组合创造的“快乐宝藏”的总价值是多少, 最后的结果模 $998244353$。

数据范围

• $1\le n\le 2\cdot 10^5,$
• $0\le a_i<998244353.$

Solution

长度为 $1$ 的区间的快乐价值总和显然是 $$\sum _{i=1}^n{a}_i^2.$$ 下面考虑区间长度 $>1$ 的。

设 $a$ 已经排好序，当前选择的最小值为 $a_i$，最大值为 $a_j$，满足 $j-i+1>1$。

那么固定最大最小值的子序列就有 $2^{j-i-1}$ 种选法（中间爱选不选）。

因此总的价值是 $$\sum _{i=1}^{n-1}\sum _{j=i+1}^n{2}^{j-i-1}{a}_i\cdot a_j.$$

下面开始化简。

$$\begin{array}{rl}\sum _{i=1}^{n-1}\sum _{j=i+1}^n{2}^{j-i-1}{a}_i\cdot a_j& =\sum _{i=2}^n\sum _{j=1}^{i-1}{2}^{i-j-1}{a}_i\cdot a_j\\ & =\sum _{i=2}^n{a}_i\left(\sum _{j=1}^{i-1}{2}^{(i-1)-j}{a}_j\right).\end{array}$$

令 $f(i)=\sum _{j=1}^{i-1}{2}^{(i-1)-j}{a}_j$，那么

$$\begin{array}{rl}f(i+1)& =\sum _{j=1}^i{2}^{i-j}{a}_j\\ & =\left(\sum _{j=1}^{i-1}{2}^{i-j}{a}_j\right)+a_i\\ & =2\left(\sum _{j=1}^{i-1}{2}^{(i-1)-j}{a}_j\right)+a_i\\ & =2f(i)+a_i.\end{array}$$

初值条件：$f(1)=a_1$。于是求总和只要 $O(n)$。

时间复杂度 $O(n\log n)$

• 瓶颈是排序。

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::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();
 
constexpr int P = 998244353;
using Z = MInt<P>;

template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &x: v) {
        is >> x;
    }
    return is;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    std::cin >> a;

    std::ranges::sort(a);

    Z ans = std::accumulate(a.begin(), a.end(), Z(0), [&](Z s, int x) {
        return s + Z(x) * x;
    });

    Z dp = a[0];
    for (int i = 1; i < n; i++) {
        ans += a[i] * dp;
        dp = 2 * dp + a[i];
    }
    std::cout << ans << "\n";
    
    return 0;
}