灵宝网站制作工作室/百度网站首页

比赛链接

A. 出勤规划

题目大意

给定 $n$ 个点 $m$ 条边的 带权无向连通图 $G$，再给定 $k$ 个点，记为 $S_k$，令 $f(u,v)$ 表示 $u$ 到 $v$ 的最短距离。

这 $k$ 个点构成了一张新图 $G^{\prime }$，每两个点 $u,v$ 之间都有边，边权用原图 $G$ 中的 $f(u,v)$ 定义，求新图 $G^{\prime }$ 最小生成树的边权和。

数据范围

• $1\le \sum n,\sum m\le 5\cdot 10^5,$
• $n-1\le m\le 5\cdot 10^5,$
• $1\le k\le n,$
• 边权不超过 $10^8$。

Solution

考虑 $u$ 到 $v$ 的最短距离，要么是走 $(u,v,w)$ 这条边（$w$ 为边权），要么是通过某些结点中转。

因此可以考虑多源最短路，即以这 $k$ 个给定点为源点，计算每个点到这些源点的最短路，同时记录 $u$ 从哪个源点过来距离最短。

• 这里的意思是这 $k$ 个点一定存在一个 $k_i$ 到 $u$ 的距离最短，而不是每个源点到 $u$ 的最短距离都记录下来。

设这样得到了 $\mathrm{dis}$ 和 $\mathrm{from}$ 数组，分别表示到这 $k$ 个点的最短距离以及相应的源点。

那么我们可以断言，对于 $\forall k_i,k_j\in S_k$，$(k_i,k_j)$ 这条边在新图中的边权一定可以表示为 $dis[u]+w+dis[v]$，其中 $w$ 是原图中 $u,v$ 这条边的边权。

这其实就相当于找一个中转边 $(u,v)$ 计算两个源点 $k_i,k_j$之间的最短距离。

所以我们对这些新边排序做 $\mathrm{kruskal}$ 即可。

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

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;x--;}return is;
}struct DSU {std::vector<int> f, sz;DSU() {}DSU(int n) {init(n);}void init(int n) {f.resize(n);std::iota(f.begin(), f.end(), 0);sz.assign(n, 1);}int find(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}int size(int x) {return sz[find(x)];}bool merge(int x, int y) {x = find(x);y = find(y);if (x == y) {return false;}sz[x] += sz[y];f[y] = x;return true;}bool same(int x, int y) {return find(x) == find(y);}
};constexpr i64 inf = std::numeric_limits<i64>::max() / 4;void solve() {int n, m, k;std::cin >> n >> m >> k;std::vector<std::array<int, 3>> eg(m);std::vector<std::vector<std::array<int, 2>>> adj(n);for (auto &[w, a, b]: eg) {std::cin >> a >> b >> w;a--, b--;if (a == b) {continue;}adj[a].push_back({w, b});adj[b].push_back({w, a});}std::vector<int> chosen(k);std::cin >> chosen;std::vector<i64> dis(n, inf);std::vector<int> from(n, -1);std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;for (int x: chosen) {q.emplace(dis[x] = 0, from[x] = x);}while (not q.empty()) {auto [d, x] = q.top(); q.pop();if (d != dis[x]) {continue;}for (const auto &[w, y]: adj[x]) {if (dis[y] > d + w) {from[y] = from[x];q.emplace(dis[y] = d + w, y);}}}std::vector<std::tuple<i64, int, int>> neg;for (const auto &[w, a, b]: eg) {int fa = from[a];int fb = from[b];if (fa != fb) {neg.emplace_back(dis[a] + w + dis[b], fa, fb);}}std::ranges::sort(neg);DSU dsu(n);int cnt = 0;i64 ans = 0;for (const auto &[w, a, b]: neg) {if (dsu.merge(a, b)) {ans += w;if (++cnt == k - 1) {break;}}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int T = 1;std::cin >> T;while (T--) {solve();}return 0;
}

B. 二分炼狱

题面大意

大概就是说要找一个交替序列的和。

Solution

首先，这个题 $\mathrm{pos}$ 只有改变，可以看作对于同一个值 $\mathrm{val}$ 的大小交替序列（保持下标递增）。

那我们不妨将 $a$ 从小到大排序，然后用一棵线段树维护对于每个 $a_i$ 的交替序列的长度以及序列和。

线段树维护的信息有：

• $l_{0/1}$ 表示交替序列的长度（$0$ 为大 $1$ 为小)；
• $s_{0/1}$ 表示交替序列的交替和（$0$ 为大 $1$ 为小）。

在从左往右扫的过程中，设 $k\in [i,j)$ 均有 $a_k=a_i$，我们先把有关 $a_i$ 的信息全都在线段树中删掉，然后求落在 $(i,n)$ 的交替序列和，最后把 $a_i$ 的信息加回来，但是从 $0$ 变成 $1$，即现在开始它会小于之后所有的元素。

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

C++ Code

#include <bits/stdc++.h>using i64 = long long;template<class Info>
struct SegmentTree {#define l(p) (p << 1)#define r(p) (p << 1 | 1)int n;std::vector<Info> info;SegmentTree() {}SegmentTree(int _n, Info _v = Info()) {init(_n, _v);}template<class T>SegmentTree(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());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 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;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;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);}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;}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;}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 Info {std::array<int, 2> l{};std::array<i64, 2> s{};
};
Info operator+(const Info &a, const Info &b) {Info c;for (int i = 0; i < 2; i++) {c.l[i] = a.l[i] + b.l[i ^ (a.l[i] & 1)];c.s[i] = a.s[i] + b.s[i ^ (a.l[i] & 1)];}return c;
}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<int> a(n);std::cin >> a;SegmentTree<Info> sgt(n);for (int i = 0; i < n; i++) {sgt.modify(i, {1, 0, a[i], 0});}std::vector<int> ord(n);std::iota(ord.begin(), ord.end(), 0);std::ranges::sort(ord, [&](int i, int j) {return a[i] < a[j];});std::vector<i64> ans(n);for (int i = 0, j = 0; i < n; i = j) {while (j < n and a[ord[j]] == a[ord[i]]) {sgt.modify(ord[j++], {0, 0, 0, 0});}for (int k = i; k < j; k++) {ans[ord[k]] = sgt.query(ord[k] + 1, n).s[0];}for (int k = i; k < j; k++) {sgt.modify(ord[k], {0, 1, 0, a[ord[k]]});}}std::cout << ans << "\n";return 0;
}

C. BloomsTD6

哥们儿这个真不会，看 官解 也写不出来 😰.

D. 橘猫的背包问题

题目大意

一个 $n\cdot V$ 大概 $10^7$ 的 $01$ 背包，有 $Q\sim 10^4$ 个询问，每次询问只允许取 $[L,R)$ 下标内的物品，求能得到的最大价值。

Solution

考虑线段树维护信息（左闭右开）。

• $l$ 表示线段树左端点；
• $r$ 表示线段树右端点；
• $m$ 表示区间中点；
• $dpl$ 是个二维数组，第一维长度 $m-l+1$，第二维长度 $V$，它表示 $[m-i,m)$ 的逆序背包；
• $dpr$ 是个二维数组，第一维长度 $r-m+1$，第二维长度 $V$，它表示 $[m,m+i)$ 的顺序背包。

在求答案时，

• 如果 $r-l=1$，直接判断当前体积是否不超过询问的体积 $P$；
• 否则找到一个区间 $[l,r)$ 使得 $L\in [l,m)$ 且 $R\in [m,r)$，然后合并 $dpl[m-L]$ 和 $dpr[R-m]$，说人话就是取 $s\in [0,P]$，分配给 $dpl$ 的体积是 $s$，分配给 $dpr$ 的体积是 $P-s$，最后遍历取最大价值。

时间复杂度 $O(nV\log n+Q\max (n,V))$

• $O(nV\log n)$ 是建树的时间，树高有 $\log n$；
• $O(QV)$ 是指每次询问回答需要 $O(\max (n,V))$；
• 这题的空间够大，数组大大方方开，一般 $256MB$ 能开 $6E7$ 的 $\mathrm{int}$ 数组。

C++ Code

#include <bits/stdc++.h>constexpr int V = 10000;using Array = std::array<int, V + 1>;
using Vector = std::vector<Array>;const Vector E(1);struct Info {int l = 0;int m = 0;int r = 0;Vector dpl = E;Vector dpr = E;
};
std::vector<Info> info;std::vector<int> v;
std::vector<int> w;void build(int p, int l, int r) {if (r - l == 1) {return;}int m = l + r >> 1;info[p].l = l;info[p].r = r;info[p].m = m;build(p * 2, l, m);build(p * 2 + 1, m, r);auto &dpl = info[p].dpl;dpl.assign(m - l + 1, Array{});for (int i = m - 1, j = 0; i >= l; i--, j++) {dpl[j + 1] = dpl[j];for (int s = V; s >= v[i]; s--) {dpl[j + 1][s] = std::max(dpl[j + 1][s], dpl[j][s - v[i]] + w[i]);}}auto &dpr = info[p].dpr;dpr.assign(r - m + 1, Array{});for (int i = m, j = 0; i < r; i++, j++) {dpr[j + 1] = dpr[j];for (int s = V; s >= v[i]; s--) {dpr[j + 1][s] = std::max(dpr[j + 1][s], dpr[j][s - v[i]] + w[i]);}}
}
int merge(const Array &a, const Array &b, int P) {int ans = 0;for (int s = 0; s <= P; s++) {ans = std::max(ans, a[s] + b[P - s]);}return ans;
}
int query(int p, int l, int r, int P) {if (r - l == 1) {return v[l] <= P ? w[l]: 0;}int m = info[p].m;if (info[p].l <= l and l < m and m < r and r <= info[p].r) {return merge(info[p].dpl[m - l], info[p].dpr[r - m], P);}if (r <= m) {return query(p * 2, l, r, P);}return query(p * 2 + 1, l, r, 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;v.resize(n);w.resize(n);std::cin >> v >> w;info.assign(4 << std::__lg(n), Info()); build(1, 0, n);int Q;std::cin >> Q;for (int _ = 0, lst = 0; _ < Q; _++) {int iL, iR, iP;std::cin >> iL >> iR >> iP;int L = (iL + lst) % n + 1;int R = (iR + lst) % n + 1;if (L > R) {std::swap(L, R);}int P = (iP + lst) % V + 1;L--;std::cout << (lst = query(1, L, R, P)) << "\n";}    return 0;
}

E. GDUT = 1

题目大意

给定一个由 $\mathrm{G},\mathrm{D},\mathrm{U},\mathrm{T},+$ 组成的表达式（保证合法），问是否存在对这四个字母 $0$ 到 $9$ 的赋值（可以有前导零），使得这个表达式的值 $=x$。

Solution

容易想到，我们对这个字母统计它们在每个幂次上的贡献，比如 $G$ 在 $10^k$ 位上出现了 $c$ 次，那么它对 $10^k$ 次幂贡献为 $c$。

由于 $0\le x\le 10^{18}$，所以凡是出现 $k>18$ 的，那个字母的赋值只能为 $0$。

然后我们计算每个字母每个幂次的贡献上限（即总的贡献不能超过 $x$），如果有不符合的也只能置为 $0$。

这样我们就能愉快枚举 $G,D,U,T$ 了。

但 $T$ 最大是 $10^5$，如果直接 $10^4$ 枚举大概率超时，所以我们可以用折半搜索的思想，先枚举前一半（$G,D$），然后用哈希表存下来每个值对应的 $G,D$ 对，接着再枚举另一半 $U,T$，这样能把单次复杂度降到 $10^2$。

时间复杂度 $O(\sum n+T\cdot 10^2)$

• 上限 $10^7$，但是常数稍大，所以时限还是有点紧的。

C++ Code

#include <bits/stdc++.h>using i64 = long long;constexpr i64 inf = 1E18;std::unordered_map<char, int> ump {{'G', 0},{'D', 1},{'U', 2},{'T', 3}
};
std::vector<i64> p10;
void init(int n) {p10.assign(n + 1, 1);for (int i = 1; i <= n; i++) {p10[i] = p10[i - 1] * 10;}
}
template<class T, size_t L>
std::ostream &operator<<(std::ostream &os, const std::array<T, L> &a) {os << a[0];for (size_t i = 1; i < L; i++) {os << " " << a[i];}return os;
}void solve() {std::string s;std::cin >> s;i64 x;std::cin >> x;int n = s.size();std::array<i64, 4> pows{};std::array<std::array<int, 18 + 1>, 4> cnts{};for (int i = 0, j = 0; i < n; i = j + 1) {j = i + 1;while (j < n and s[j] != '+') {j++;}for (int k = j - 1, p = 0; k >= i; k--, p++) {int id = ump[s[k]];if (p > 18) {pows[id] = -1;} else {cnts[id][p]++;}}}for (int i = 0; i < 4; i++) {if (pows[i] != -1) {for (int j = 0; j <= 18; j++) {if (cnts[i][j] == 0) {continue;}if (inf / cnts[i][j] < p10[j]) {pows[i] = -1;break;}if (pows[i] > inf - cnts[i][j] * p10[j]) {pows[i] = -1;break;}pows[i] += cnts[i][j] * p10[j];}}}auto print = [&](const std::array<int, 4> &a) {std::cout << "YES\n";std::cout << a << "\n";};std::unordered_map<i64, std::pair<int, int>> pair{};for (int g = 0; g < (pows[0] > 0 ? 10: 1); g++) {for (int d = 0; d < (pows[1] > 0 ? 10: 1); d++) {i64 res = g * pows[0] + d * pows[1];if (res == x) {print({g, d, 0, 0});return;}if (res < x) {pair[res] = std::pair {g, d};}}}for (int u = 0; u < (pows[2] > 0 ? 10: 1); u++) {for (int t = 0; t < (pows[3] > 0 ? 10: 1); t++) {i64 res = u * pows[2] + t * pows[3];if (res == x) {print({0, 0, u, t});return;}if (res < x and pair.contains(x - res)) {auto [g, d] = pair[x - res];print({g, d, u, t});return;}}}std::cout << "NO\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);init(18);int T = 1;std::cin >> T;while (T--) {solve();}return 0;
}

F. 排队

题目大意

将一个序列分成左右两份（可以空），每一份都交给一个理发师（具体排队流程可以去题目里看），会得到两个处理时间，求两个时间总和的最小值。

Solution

首先简要的思路就是前后缀分解 + 枚举，但是这里的前后缀不好处理。

我们以前缀为例，后缀直接翻转处理即可。

考虑把时间划分为若干连续段，每个段内一定存在至少一个人，且有些段存在一些排队的人，每个段所占的区间为 $[t_0,t_0+c\cdot k]$。

• $t_0$ 表示之前某个人的达到时间；
• $c$ 表示段内总人数，段与段之间没有交集。

这样划分之后，假设我们从前往后枚举，现在加入了一个到达时间为 $t$ 的顾客：

• 如果他来得最早/最晚，就先给他在最前面/最后面单开一个段；
• 否则我们可以找到它在段 $[t_0,t_0+c\cdot k]$ 内，它一定在其中一个小区间内，不妨设为 $$[t_0+(c_0-1)\cdot k,t_0+c_0\cdot k],0<c_0\le c.$$ 设在这个小区间中，仍在等待且比他早到或同时到的有 $cn{t}_l$ 个，那么这些人不受影响，剩下的 $(c-c_0)-cn{t}_l$ 个人的等待时间全部增加 $k$，而他自己的等待时间为 $$(t_0+c_0\cdot k)-t+cn{t}_l\cdot k,$$ 这样整体的等待时间就增加了 $$(t_0+c_0\cdot k)-t+cn{t}_l\cdot k+((c-c_0)-cn{t}_l)\cdot k,$$ 化简一下就是 $$(t_0+c\cdot k)-t.$$ 我们发现，这其实相当于非抢占式调度，也就是这个顾客是 $t$ 时间来的，我一直拖到前 $c$ 个顾客都理完发才服务他，这样得到的等待时间增量也是 $(t_0+c\cdot k)-t$，不过是全堆在这位 $t$ 到达的顾客身上了。

上面处理了新到顾客的初始插入情况，还要处理接下来可能的局面：

• 即这段 $[t_0,t_0+c\cdot k]$ 变成 $[t_0,t_0+(c+1)\cdot k]$ 后，有可能和后面一段甚至好几段 $[t_1,t_1+c^{\prime }\cdot k]$ 撞上了，这些段是需要合并的。

合并的原则和上述插入一模一样，不过是 $t$ 发生了变化，从原来的给定 $t$，变成了 $t^{\prime }=t_0+(c+1)\cdot k$，而相对应的，上文的 $t_0+c\cdot k$ 就变为 $t_1$；我们只要一直合并到右侧没有段或者和下一段没有交集为止。

不过等待时间增量的计算稍有不同：

• 由于插入之前一定有 $t_0+c\cdot k<t_1$，所以现在也一定有 $t_1\le t_0+(c+1)\cdot k<t+k$；
• 这里要注意的是，$t$ 时间插入的顾客 不能 再作为非抢占式的对象；换句话说，正是因为 $t$ 时刻插入了这个顾客，才导致两个段合并，所以现在后一个段的 $c^{\prime }$ 个顾客应该让步，也就是每个人的等待时间都延后 $$(t_0+(c+1)\cdot k)-t_1,$$ 总的等待时间增加 $$c^{\prime }((t_0+(c+1)\cdot k)-t_1).$$

时间复杂度 $O(n\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;
}void solve() {int n, k;std::cin >> n >> k;std::vector<int> time(n);std::cin >> time;    auto work = [&]() {std::vector<i64> res{0};res.reserve(n + 1);std::map<int, int> mp;i64 cost = 0;for (int t: time) {auto it = mp.upper_bound(t);if (it == mp.begin()) {mp[t] = 1;it = prev(it);} else {it = prev(it);i64 nt = it->first + static_cast<i64>(it->second) * k;if (t <= nt) {cost += nt - t;it->second++;} else {mp[t] = 1;it = next(it);}}while (next(it) != mp.end()) {auto jt = next(it);i64 nt = it->first + static_cast<i64>(it->second) * k;auto [t, c] = *jt;if (t > nt) {break;}cost += (nt - t) * c;it->second += c;mp.erase(jt);}res.push_back(cost);}return res;};auto pre = work();std::ranges::reverse(time);auto suf = work();std::ranges::reverse(suf);i64 ans = std::numeric_limits<i64>::max() / 4;for (int i = 0; i <= n; i++) {ans = std::min(ans, pre[i] + suf[i]);}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int T = 1;std::cin >> T;while (T--) {solve();}return 0;
}

G. Jump Sort

题目大意

给定一个长度为 $n$ 的排列 $a$。现在选定一个 $x\in [1,n]$ 后，可以交换任意满足 $|i-j|=x$ 的 $a_i,a_j$，问 $x$ 有多少种选法使得 $a$ 变为升序。

Solution

交换的下标组是 $i,i+x,i+2x,\cdots$，组间无法交换，组内随便换，因此 $[i]$ 这一组就要求最终换完后的 $a$ 值是 $i,i+x,i+2x,\cdots$，也就是说 $$a_{i+kx}=i+mx.$$ 移项后可以得到 $$a_{i+kx}-(i+kx)=(m-k)x.$$ 如果 $m=k$，说明一开始就有 $a_i=i$，那就不需要换，否则我们发现，$a_i-i$ 是 $x$ 的倍数。

所以我们只要找 $g=\underset{i=1}{\overset{n}{\gcd }}(a_i-i)$ 的所有因数即可。特别的，若 $g=0$，答案为 $n$，也就是怎么选都有序。

时间复杂度 $O(n+\sqrt{n})=O(n)$

C++ Code

#include <bits/stdc++.h>template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (auto &x: v) {is >> x;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;int g = 0;for (int i = 0; i < n; i++) {g = std::gcd(g, std::abs(a[i] - i));}if (g == 0) {std::cout << n << "\n";return 0;}auto calc = [&](int x) {int res = 0;for (int i = 1; i * i <= x; i++) {if (x % i == 0) {res++;if (i * i != x) {res++;}}}return res;};std::cout << calc(g) << "\n";return 0;
}

H. 可爱串串

Solution

直接前后缀分解，然后遍历求最大值。

时间复杂度 $O(n)$

C++ Code

#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::string s;std::cin >> s;std::vector<int> pre(n + 1);for (int i = 0; i < n; i++) {pre[i + 1] = pre[i] + (s[i] - '0');}i64 ans = -1E18;for (int i = 1; i < n; i++) {ans = std::max(ans, static_cast<i64>(pre[i] - (i - pre[i])) * ((pre[n] - pre[i]) - ((n - i) - (pre[n] - pre[i]))));}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int T = 1;std::cin >> T;while (T--) {solve();}return 0;
}

I. 好想成为人类啊

题目大意

$S$ 中包含若干个 $T$，也就是存在若干区间 $[l,r]$ 使得 $S[l...r]=T$，求最少要选择多少个点使得每个区间都存在一个被选点。

Solution

很经典的贪心，把区间按照右端点 $r$ 排序，如果当前选点仍能在区间内，就略过，否则选择新区间的右端点。

而判断哪些区间是 $T$ 可以用 $\mathrm{kmp}$。当然这题数据有点水，所以暴力匹配也可以。

时间复杂度 $O(\sum (|S|+|T|))$

• 可能是由于单测 $n,m\le 1000$，暴力 $nm$ 的复杂度远低于 $(2^{14}{)}^2$。

C++ Code

#include <bits/stdc++.h>void solve() {int n, m;std::cin >> n >> m;std::string S, T;std::cin >> S >> T;std::vector<int> nxt(m, -1);for (int i = 1, j = -1; i < m; i++) {while (j != -1 and T[i] != T[j + 1]) {j = nxt[j];}if (T[i] == T[j + 1]) {j++;}nxt[i] = j;}std::vector<std::pair<int, int>> seg;for (int i = 0, j = -1; i < n; i++) {while (j != -1 and S[i] != T[j + 1]) {j = nxt[j];}if (S[i] == T[j + 1]) {j++;}if (j == m - 1) {seg.emplace_back(i, i - m);}}if (seg.empty()) {std::cout << 0 << "\n";return;}std::ranges::sort(seg);int lst = -1;int cnt = 0;for (const auto &[r, l]: seg) {if (lst <= l) {lst = r;cnt++;}}std::cout << cnt << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int T = 1;std::cin >> T;while (T--) {solve();}return 0;
}

J. 11 背包

哈哈不会 😋

K. 橘猫的后缀问题

题目大意

给定一个长度为 $n$ 的字符串 $S$，现在给定 $Q$ 个操作，每个操作要么改变某个 $S_x$，要么询问 $S[x...n]$ 这个后缀在所有后缀中的排名。

Solution

由于数据的随机性，这题可以乱搞 🤣

也就是我们只检查所有后缀的前三位（不满的话补后缀零），用一个 $27$ 进制数表示，记为 $val$。如果已经有 $val$ 小于 $S[x...n]$ 的 $val$，那么排名 $+1$，否则找相同的 $val$，除了自己都从第四位开始往后比较一遍字典序。

由于要快速算小于某个值的数的个数，因此要用到树状数组或线段树。

是的就是这样，因为数据是随机的，所以很快。

时间复杂度 $O(可以过)$

C++ Code

#include <bits/stdc++.h>template<class T>
struct Fenwick {int n, down;std::vector<T> a;Fenwick(int _n = 0): down(0) {init(_n);}Fenwick(std::vector<int> _a, int op): down(0) {init(_a, op);}void init(int _n) {n = _n;a.assign(n, T{});}void init(std::vector<int> _a, int op) {assert(op == 0 or op == 1);if (op == 0) {init(_a.size());for (int i = 0; i < _a.size(); i += 1) {add(i, _a[i]);}} else {int max = *std::max_element(_a.begin(), _a.end());int min = *std::min_element(_a.begin(), _a.end());init(max - min + 1);for (int x: _a) {add(x - min, 1);}down = min;}}int lowbit(int x) {return x & -x;}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += lowbit(i)) {a[i - 1] = a[i - 1] + v;}}void clear() {a.assign(n, T{});}T sum(int x) {T ans{};for (int i = x; i > 0; i -= lowbit(i)) {ans = ans + a[i - 1];}return ans;}T sum(int l, int r) {return sum(r) - sum(l);}int kth(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n and cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};constexpr int L = 3;
constexpr int B = 27;
constexpr int N = (B - 1) * (B * (B + 1) + 1);int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;std::string S;std::cin >> S;S += char('a' - 1);S += char('a' - 1);auto calc = [&](int i) {int val = 0;for (int j = i; j < i + L; j++) {val = val * B + (S[j] - 'a' + 1);}return val;};Fenwick<int> fen(N);std::map<int, std::set<int>> mp;std::vector<int> suf(n);for (int i = 0; i < n; i++) {suf[i] = calc(i);mp[suf[i]].insert(i);fen.add(suf[i], 1);}int Q;std::cin >> Q;while (Q--) {int o, x;std::cin >> o >> x;if (o == 1) {char c;std::cin >> c;for (int i = std::max(0, x - L); i < x; i++) {mp[suf[i]].erase(i);fen.add(suf[i], -1);}S[x - 1] = c;for (int i = std::max(0, x - L); i < x; i++) {suf[i] = calc(i);mp[suf[i]].insert(i);fen.add(suf[i], 1);}} else {x--;int ans = fen.sum(suf[x]) + 1;for (int i: mp[suf[x]]) {if (i != x) {for (int l = L; ; l++) {if (S[i + l] != S[x + l]) {ans += S[i + l] < S[x + l];break;}}}}std::cout << ans << "\n";}}return 0;
}

L. 字符串匹配太多了！

题目大意

定义了一个后缀匹配数组，要求构造字符串 $\mathrm{T}$，使得 $\mathrm{match}({\mathrm{S}}_1,\mathrm{T})=\mathrm{match}({\mathrm{S}}_2,\mathrm{T})$。

Solution

如果 $S_1=S_2$，输出 $S_1$ 即可。

否则我们考虑极端情况，即 $|T|=1$。

我们只要能找到一个 $S_1$ 和 $S_2$ 都不包含 的字母 ∈ { a , b , c } \in \{a, b, c\} ∈{a,b,c}，那么 $\mathrm{match}$ 一定都是 $0$，输出即可，否则一定无法构造出 $T$ 满足条件。

这个证明不太会，大家可以感性理解一下（

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

C++ Code

#include <bits/stdc++.h>using namespace std::literals::string_literals;void solve() {int n;std::cin >> n;std::string S1, S2;std::cin >> S1 >> S2;if (S1 == S2) {std::cout << "YES\n";std::cout << n << "\n";std::cout << S1 << "\n";return;}for (auto c: "abc"s) {auto check = [&](char c) {for (int i = 0; i < n; i++) {if ((S1[i] == c) != (S2[i] == c)) {return false;}}return true;};if (check(c)) {std::cout << "YES\n";std::cout << 1 << "\n";std::cout << c << "\n";return;}}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;
}

M. 橘猫的后缀问题

题目大意

$n$ 天要出去 $k$ 天，共 $m$ 家餐厅，要求不能连续两天去同一个餐厅，求总共有多少种出门方式，答案对 $10^9+7$ 取模。

Solution

考虑连续出一段门，长度为 $L$，那么第一天随便选，后面 $L-1$ 天只要保证和前一天不同即可，所以有 $m(m-1{)}^{L-1}$ 种情况。

下面考虑将 $k$ 天切割为 $s$ 段，每一段之间都至少有一天不出门，那么切割方式有 $$\left(\genfrac{}{}{0ex}{}{k-1}{s-1}\right)$$ 种，因为每一段不能是空的。

根据第一段的结论，此时这 $s$ 段内部选择餐厅有 $m^s(m-1{)}^{k-s}$ 种情况。

现在继续考虑把这 $s$ 段放入 $n$ 天里，其实就相当于把剩下的 $n-k$ 个不出门的天数匀到这 $s$ 段的两边。设 $x_i$ 表示分给第 $i$ 到 $i+1$ 段之间的不出门天数，若 $i\in [1,s)$ 则要求 $x_i>0$，否则 $i=0$ 或 $i=s$，只要 $x_i\ge 0$ 即可。现在要求的就是 $$x_0+x_1+x_2+\cdots +x_{s-1}+x_s=n-k,$$ 这个方程解的个数，我们令 $$\{\begin{array}{ll}{x}_i^{\prime }=x_i,& i\in [1,s),\\ x_i^{\prime }=x_i+1,& i=0\mid \mid i=s.\end{array}$$ 这样就变成求解一个 $\forall x_i^{\prime }>0$ 的不定方程解的个数，$$x_0^{\prime }+x_1^{\prime }+x_2^{\prime }+\cdots +x_{s-1}^{\prime }+x_s^{\prime }=n-k+2.$$ 由隔板法，解的个数为 $$\left(\genfrac{}{}{0ex}{}{(n-k+2)-1}{(s+1)-1}\right)=\left(\genfrac{}{}{0ex}{}{n-k+1}{s}\right).$$ 因此最终答案为 $$\sum _{s=1}^k\left(\genfrac{}{}{0ex}{}{n-k+1}{s}\right)\left(\genfrac{}{}{0ex}{}{k-1}{s-1}\right)m^s(m-1{)}^{k-s}.$$

时间复杂度 $O(\sum k\log k)$

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 = 1000000007;
using Z = MInt<P>;struct Comb {int n;std::vector<Z> _fac;std::vector<Z> _invfac;std::vector<Z> _inv;Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}Comb(int n) : Comb() {init(n);}void init(int m) {m = std::min(m, Z::getMod() - 1);if (m <= n) return;_fac.resize(m + 1);_invfac.resize(m + 1);_inv.resize(m + 1);for (int i = n + 1; i <= m; i += 1) {_fac[i] = _fac[i - 1] * i;}_invfac[m] = _fac[m].inv();for (int i = m; i > n; i -= 1) {_invfac[i - 1] = _invfac[i] * i;_inv[i] = _invfac[i] * _fac[i - 1];}n = m;}Z fac(int m) {if (m > n) init(2 * m);return _fac[m];}Z invfac(int m) {if (m > n) init(2 * m);return _invfac[m];}Z inv(int m) {if (m > n) init(2 * m);return _inv[m];}Z binom(int n, int m) {if (n < m || m < 0) {return 0;}return fac(n) * invfac(m) * invfac(n - m);}Z Lucas(i64 n, i64 m, int p) {if (n < p and m < p) {return binom(n, m);}return Lucas(n / p, m / p, p) * binom(n % p, m % p);}Z Lucas(i64 n, i64 m) {if (n < Z::getMod() and m < Z::getMod()) {return binom(n, m);}return Lucas(n / Z::getMod(), m / Z::getMod()) * binom(n % Z::getMod(), m % Z::getMod());   }Z perm(int n, int m) {if (n < m or m < 0) {return 0;}return fac(n) * invfac(n - m);}
} comb;void solve() {int n, m, k;std::cin >> n >> m >> k;Z ans = 0;for (int s = 1; s <= k; s++) {Z res = comb.binom(n - k + 1, s) * comb.binom(k - 1, s - 1);res *= power(Z(m), s) * power(Z(m - 1), k - s);ans += res;}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int T = 1;std::cin >> T;while (T--) {solve();}return 0;
}