比赛链接

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