2024牛客暑期多校训练营4
比赛链接
英文题面
官方题解
标程/数据
难度梯度 GICH AFJ DBK EL
A LCT
题意
一个有根树，一共有 \(n\)个节点，有 \(n-1\) 次操作。
第 \(i\) 次操作有 \(a_i,b_i,c_i\) 三个整数，
先将 \(b_i\) 节点把 \(a_i\) 节点作为父节点连边，
然后问以 \(c_i\) 为根的最长简单路径的长度。
\(2\le n\le10^6,1\le a_i,b_i,c_i\le n,a_i\neq b_i\)
当 \(1\le i\le j\) 时，保证不存在 \(b_j=c_i\)。
解题思路
当 \(1\le i\le j\) 时，保证不存在 \(b_j=c_i\)。
这个条件其实是说，\(c_i\) 一定是当前树的根。
那么这契合了并查集，并查集路径压缩后，每次都是子节点指向根节点。
那么最长简单路径其实就是说，最大深度。
所以使用带权并查集维护每个节点的深度和以 \(x\) 为根节点的时候的最长简单路径。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int f[1000005];
int d[1000005];
int ans[1000005];
int find(int x){
if (f[x] == x) return x;
find(f[x]);
d[x] += d[f[x]];
return f[x] = f[f[x]];
}
void merge(int a, int b, int v){
int ta = find(a), tb = find(b);
if (ta == tb) return;
int roota =find(a),rootb=find(b);
f[tb] = ta;
d[tb] = d[a] - d[b] + v;
}
void solve() {
int n;
cin >> n;
for (int i = 1 ; i <= n ; i++) {
f[i] = i;
d[i] = ans[i] = 0;
}
for (int i = 1 ; i < n ; i++) {
int a, b, c;
cin >> a >> b >> c;
int ta = find(a);
int tb = find(b);
merge(a, b, 1);
ans[ta] = max(ans[ta], 1 + d[a] + ans[tb]);
cout << ans[c] << " ";
}
cout << "\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
B Pull the Box
题意
在 \(n\) 个点 \(m\) 条边的无向图上进行推箱子游戏，
你从点 \(x\) 开始，箱子在点 \(1\)，
问你把箱子推到点 \(n\) 的最短路径长度。
解题思路
首先我们可以知道，我们一但移动到了箱子相邻的点，那么我们就会一直推着箱子到终点。
所以我们可以将题目分为两个部分：
① 从点 \(x\) 到箱子相邻的点。
② 从箱子相邻的点，推着箱子走到点 \(n\)。
问题①很好解决，直接跑一遍 bfs 最短路即可。
问题②，我们可以把每一条边变为一个状态，跑最短路即可。
对于问题②，在跑的过程中，我们可以发现，如果我们状态为 \((u,v)\)，那么我们不能把箱子推到 \(u\)，
我们应该在状态为 \((x,v)\)，\(x\neq u\)，才能将箱子推到 \(u\)。
这里我们每次对 \(v\) 进行标记，这样我们 bfs 入队出队次数会特别多。
我们需要用 dijkstra 来优化。
最终对点 \(n\) 的所有邻边取 \(\min\) 就是答案。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
array<int, 2> edges[2000005];
vector<int> adj[2000005];
int dist1[2000005], dist2[2000005], flag[2000005];
bool vis[2000005];
struct Node {
int idx, val;
friend bool operator<(const Node &x, const Node &y) {
return x.val > y.val;
}
};
void solve() {
int n, m, x;
cin >> n >> m >> x;
for (int i = 1 ; i <= n ; i++) {
adj[i].resize(0);
dist1[i] = 1e9;
flag[i] = -1;
}
for (int i = 0 ; i <= m * 2 ; i++) {
dist2[i] = 1e9;
vis[i] = false;
}
for (int i = 0 ; i < m ; i++) {
int u, v;
cin >> u >> v;
edges[i << 1] = {u, v};
edges[i << 1 | 1] = {v, u};
adj[u].push_back(i << 1);
adj[v].push_back(i << 1 | 1);
}
{ // 处理人走到任意点的最短路(不经过点1)
queue<int> que;
que.push(x);
dist1[x] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto &idx : adj[u]) {
int to = edges[idx][1];
if (to == 1) continue;
if (dist1[to] > dist1[u] + 1) {
dist1[to] = dist1[u] + 1;
que.push(to);
}
}
}
}
{ // 处理箱子到终点
priority_queue<Node> que;
for (auto &idx : adj[1]) {
// 处理人到箱子边上
int to = edges[idx][1];
dist2[idx] = dist1[to];
que.push({idx, dist2[idx]});
}
while (!que.empty()) {
int idx1 = que.top().idx;
que.pop();
if (vis[idx1]) continue;
vis[idx1] = true;
auto [u1, to1] = edges[idx1];
if (flag[to1] != -1) {
int idx2 = flag[to1];
if (dist2[idx2] > dist2[idx1] + 1) {
dist2[idx2] = dist2[idx1] + 1;
que.push({idx2, dist2[idx2]});
}
} else {
for (auto &idx2 : adj[to1]) {
auto [u2, to2] = edges[idx2];
if (to2 == u1) {
flag[to1] = idx2;
continue;
}
if (dist2[idx2] > dist2[idx1] + 1) {
dist2[idx2] = dist2[idx1] + 1;
que.push({idx2, dist2[idx2]});
}
}
}
}
}
int ans = 1e9;
for (auto &idx : adj[n]) {
ans = min(ans, dist2[idx]);
}
if (ans >= 1e9) {
cout << "Boring Game\n";
} else {
cout << "Vegetable fallleaves\n";
cout << ans << "\n";
}
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
C Sort4
题意
一个 \(n\) 排列，分别为 \(a_i\)，你可以进行任意次操作，
每次操作至多选择 \(4\) 个位置的元素进行排列，
问最少要多少次可以将整个排列变成升序。
解题思路
将排列变成升序，本质上就是 \(a_i=i\)。
那么可以得到若干个环。
我们可以发现，如果环大小为 \(1\)，则不用进行操作。
如果环大小为 \(2\)，则需要一次操作，而且两个这样的环也是一次操作。
如果环大小为 \(3\)，则需要一次操作。
如果环大小为 \(4\)，则需要一次操作。
如果环大小为 \(5\)，进行一次操作最多减少 \(3\)，
当环的大小 \(\ge5\)，则可以进行若干次操作变为大小 \(<5\) 的环。
我们这里可以化简一下，其实对于任意大小的环，每次操作都一定可以使大小减少 \(3\)。
当环的大小被减为 \(0\) 或 \(1\) 时，则无需操作，
当环的大小被减为 \(2\) 时，可以和另外的大小为 \(2\) 的匹配，操作一次。
所以我们的操作次数一定有 \(\sum_{s}\lfloor\frac{|s|}{3}\rfloor\)，
然后假设大小为 \(2\) 的环有 \(cnt\) 个，
则我们的答案为 \(ans=\sum_{s}\lfloor\frac{|s|}{3}\rfloor+\dfrac{cnt+1}{2}\)
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int f[1000005], sz[1000005];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void solve() {
int n;
cin >> n;
for (int i = 1 ; i <= n ; i++) {
f[i] = i;
sz[i] = 1;
}
for (int i = 1 ; i <= n ; i++) {
int x;
cin >> x;
int fa = find(i), fb = find(x);
if (fa == fb) continue;
f[fa] = fb;
sz[fb] += sz[fa];
}
int cnt = 0, ans = 0;
for (int i = 1; i <= n; i++) {
int fx = find(i);
if(fx != i) continue;
if(sz[fx] % 3 == 2) cnt++;
ans += sz[fx] / 3;
}
ans += (cnt + 1) / 2;
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while(T--) {
solve();
}
return 0;
}
|
D Plants vs. Zombies (Sunflower Edition)
题意
有两种向日葵，初始有 \(s\) 阳光。
每个回合开始前可以花费 \(p_i\) 阳光可以种植一颗第 \(i\) 种向日葵。
第 \(i\) 颗向日葵会在每个回合结束后产生 \(q_i\) 阳光。
每个回合每种向日葵至多种植一颗。
问 \(n\) 回合后最大的阳光数量。
\(1\le p,q\le1023\)
\(1\le s,n\le2*10^7\)
解题思路
定义回合阳光产量为 \(v\)
如果 \(v\ge p_1+p_2\)，
- 那么结局已经固定了。
- 我们可以通过枚举第 \(i\) 颗向日葵，设 \(k\) 轮才回本。
- 则 \(k*q\ge p\)，得到 \(k\ge\frac{p}{q}\)。
- 此时我们至少要 \(k=\lceil\dfrac{p}{q}\rceil\) 轮回本。
- 这个时候假设我们从第 \(nday\) 轮结束后开始，则我们在 \([nday+1,n-k+1]\) 的每轮都会种植一颗这种向日葵。
- 令 \(len=(n-k+1)-(nday+1)-1\)，则我们需要支付 \(len*p\) 的阳光。
- 通过等差数列求和，我们获得的阳光为 \(v*(n-(nday+1)+1)+\dfrac{((n-(nday+1)+1)+(n-(n-k+1)+1))*len*q}{2}\)。
否则 \(v<p_1+p_2\)，
定义 \(dp_{i,j}\) 为第 \(i\) 回合结束后，回合阳光产量为 \(j\) 的最大阳光数量。
此时得到一个时间复杂度为 \(O(n*(p_1+p_2))\) 的解法。
这里我们可以思考到，真实回合数并不会有那么大，
假设 \(p_1=p_2=1023,q_1=q_2=1\)
那么回合阳光产量要达到 \(2046\)，大概需要 \(\sum_{i=1}^{1023}\frac{1023}{i}\) 的回合
是一个收敛于 \(n\ln n\) 的一个级数，所以回合数量大概在 \(p*\ln(p)\le8000\)
所以我们只需要枚举这么多回合即可。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const i64 INF = 1e18;
array<i64, 3> p, q;
int main() {
i64 s, n;
cin >> s >> n;
cin >> p[1] >> q[1] >> p[2] >> q[2];
i64 P = p[1] + p[2], Q = q[1] + q[2];
i64 m = P * log(P) + 5;
m = min(m, n);
vector f(m + 2, vector(P, -INF));
i64 ans = s;
f[0][0] = s;
for (int i = 0 ; i <= m ; i++) {
for (int v = 0 ; v < P ; v++) {
if (f[i][v] == -INF) continue;
ans = max(ans, f[i][v] + (n - i) * v);
auto add = [&](int x, int y) {
i64 res = f[i][v];
i64 need = x - res;
i64 nday = 0;
if (need <= 0) {
nday = 1;
} else if (v > 0) {
nday = (need + v - 1) / v + 1;
} else {
return;
}
res = res - x + (nday - 1) * v;
nday += i;
if (nday > n) {
return;
}
res += v + y;
if (v + y >= P) {
// 从第 nday + 1 天早上开始 到 第 n 天晚上结束
i64 sum = res + 1LL * (v + y) * (n - (nday + 1) + 1);
for (auto &x : {1, 2}) {
i64 k = (p[x] + q[x] - 1) / q[x];
// [nday + 1, n - k + 1] 都种
if (nday + 1 <= n - k + 1) {
i64 len = (n - k + 1) - (nday + 1) + 1;
sum += ((n - (nday + 1) + 1) + (n - (n - k + 1) + 1)) * q[x] * len / 2;
sum -= len * p[x];
}
}
ans = max(ans, sum);
return;
}
f[nday][v + y] = max(f[nday][v + y], res);
};
add(p[1], q[1]);
add(p[2], q[2]);
add(P, Q);
}
}
cout << ans << "\n";
return 0;
}
|
E String God's String
题意
给你一个只含 ‘a’ 和 'b' 的字符串 \(t\)，和一个 \(n\)。
有一个空串 \(s\)，你每次可以添加 'a' 或 'b' 在 \(s\) 的末尾。
添加前 \(s\) 的后缀最长能匹配 \(t\) 的前缀长度为 \(x\)，
添加后，可能会多匹配一位，或者失配，
如果失配，那么必须以最优的添加方式来使得匹配长度重新为 \(x\)。
不可以在 \(t\) 的相同位置失配多次。
最终后缀一定存在等于 \(t\)。
问最终长度为 \([0,n]\) 的 \(s\) 有多少种添加的方案。
解题思路
因为一定要有 \(t\)，所以我们 \(s\) 的长度至少为 \(|t|\)，所以当 \(|s|<|t|\) 时，方案数为 \(0\)。
建立 kmp自动机，\(kmp_{i,0/1}\) 表示在 \(t\) 的第 \(i\) 个位置后面放 \(a\) 或 \(b\) 最长会匹配到多长的前缀。
我们会发现，如果添加字符 \(c\) 失配即 \(kmp_{i,c}\le i\)，我们肯定是走一个环重新回到这个点。
此时环的长度为 \(i-kmp_{i,c}+1\)。
因为每个位置至多失配一次，所以每个环最多走一次。
对于所有的 \(kmp_{i,c}\le i\)，有不选择这个环添加 \(0\) 个字符和选择这个环添加 \(i-kmp_{i,c}+1\) 个字符。
所以就转化为了 \(01\) 背包问题。
我们可以使用生成函数来解决 \(01\) 背包求方案数。
假设换的长度为 \(k\)，那么生成函数为 \((1+x^k)\)。
那么最终为 \((1+x^{k_1})*(1+x^{k_2})*…*(1+x^{k_p})\)
我们对上述式子去 \(\ln\) 得，\(\ln((1+x^{k_1})*(1+x^{k_2})*…*(1+x^{k_p}))\)
即 \(\sum_{i=1}^p\ln(1+x^{k_i})\)。
有公式 \(\ln(1+x^k)=\sum_{i=1}^\infty(-1)^{i+1}*\dfrac{x^{k*i}}{i}\)
可以知道我们这里 \(x\) 的指数超过 \(n\) 一定没有意义。
所以这里的计算是调和级数复杂度的。
我们暴力展开，即 \(\sum_{i=1}^p\sum_{i=1}^\infty(-1)^{i+1}*\dfrac{x^{k_p*i}}{i}\)。
然后再进行多项式求 \(\exp\) 即可算出方案数。
时间复杂度 \(n\log n\)
解题代码
代码
| C++ |
|---|
| { 多项式基础 }
int kmp[100005][2];
int main() {
int n;
cin >> n;
string s;
cin >> s;
int m = s.size();
s = " " + s;
if (n <= m) {
for (int i = 0 ; i <= n ; i++) {
cout << 0 << " ";
}
cout << "\n";
return 0;
}
n -= m;
vector<int> nxt(m + 1);
for (int i = 2 ; i <= m ; i++) {
int j = nxt[i - 1];
while (j && s[i] != s[j + 1]) {
j = nxt[j];
}
if (s[i] == s[j + 1]) {
j++;
}
nxt[i] = j;
}
kmp[0][s[1] - 'a'] = 1;
for (int i = 1 ; i <= m - 1 ; i++) {
int k = s[i + 1] - 'a';
kmp[i][k] = i + 1;
kmp[i][k ^ 1] = kmp[nxt[i]][k ^ 1];
}
Poly a(n + 1);
for (int i = 0 ; i < m ; i++) {
for (int j = 0 ; j < 2 ; j++) {
if (kmp[i][j] <= i) {
int v = i - kmp[i][j] + 1;
for (int k = 1 ; k * v <= n ; k++) {
i64 res = inv[k];
if (k % 2 == 0) {
res = P - res;
}
a[v * k] = (a[v * k] + res) % P;
}
}
}
}
a = Exp(a);
for (int i = 0 ; i < m ; i++) {
cout << 0 << " ";
}
cout << a;
return 0;
}
|
F Good Tree
题意
给出一个正整数 \(x\)，
定义 \(f(u)=\sum_vdis(u,v)\)
一个点数为 \(y\) 的树，树上存在两个点 \(u,v\) 满足 \(f(u)-f(v)=x\)，问 \(y\) 的最小值。
确保答案一定存在。
\(1\le x\le10^{18}\)
解题思路
这里我们想到，一条链比较优。
那么有 \(u,v\) 在同一条链上，\(u\) 作为链首，
\(u\) 和 \(v\) 之间有 \(a\) 个点，\(v\) 之后有 \(b\) 个点。
那么有 \(f(u)-f(v)=(a+1)*b\)
定义总共有 \(n\) 个点，那么 \(a+b+2=n\)。
这里我们不好确定 \(a,b\) 的值。
那么我们可以使用二分来枚举 \(n\)，
当我们有了 \(n\) 之后，我们确定了 \(a+b=n-2\)。
此时和为定值，求积的最大值，那么就是让这两个数相等。
当 \(n-2\) 为偶数时，\(f(u)-f(v)=(\dfrac{n-2}{2}+1)*(\dfrac{n-2}{2})\)
当 \(n-2\) 为奇数时，\(f(u)-f(v)=(\dfrac{n-2}{2}+1)*(\dfrac{n-2}{2}+1)\)
我们求当 \(f(u)-f(v)\ge x\) 时的最小 \(n\)。
求出之后的 \(n\) 并不一定是正确答案。
我们还需要检验 \(n\) 个点是否真的能构成 \(f(u)-f(v)=x\)。
我们可以画图，当在 \(u\) 和 \(v\) 中间的链上加点时，贡献为 \(a-1,a-3,a-5,a-7,…\).
这里我们容易想到，这些贡献奇偶性是相同的。
\(a\) 和 \(b\) 只有两种关系，要么 \(a=b\)，要么 \(a=b-1\)。
所以当 \(n\) 是偶数的时候，\(a=b=\dfrac{n-2}{2}\)
这个时候可能是偶数个奇贡献相加，也可能是奇数个偶贡献相加，所以只能得到偶数答案。
同理 \(n\) 是奇数的时候，能得到所有答案。
所以当 \(n\) 是偶数且 \(x\) 是奇数时，必须还要多 \(1\) 个点(把 \(a\) 加成偶数)。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
bool check(i64 x, __int128 mid) {
mid -= 2;
if (mid % 2 == 0) {
mid /= 2;
return (mid + 1) * mid >= x;
} else {
mid /= 2;
return (mid + 1) * (mid + 1) >= x;
}
}
void solve() {
i64 x;
cin >> x;
__int128 L = 3, R = 1000000000000LL;
while (L < R) {
__int128 mid = L + R >> 1;
if (check(x, mid)) {
R = mid;
} else {
L = mid + 1;
}
}
if((L % 2 == 0) && x % 2 == 1 ) {
L++;
}
cout << (i64) L << "\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
G Horse Drinks Water
题意
给你一个二维平面直角坐标系，有一马位于点 \((x_g,y_g)\)，有一帐篷位于 \((x_t,y_t)\)，\(x,y\) 轴正方向表示为河。
问马到河边饮水后再回到帐篷的最短路径长度是多少。
\(0\le x_g,y_g,x_t,y_t\le10^9\)
解题思路
枚举到 \(x\) 轴正方向喝水还是到 \(y\) 轴正方向喝水即可。
作关于坐标轴的对称点计算距离取 \(\min\)
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
i64 x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
double ans = min({
(sqrtl((-x1 - x2) * (-x1 - x2) + (y1 - y2) * (y1 - y2))),
(sqrtl((x1 - x2) * (x1 - x2) + (-y1 - y2) * (-y1 - y2)))
});
cout << fixed << setprecision(10) << ans << "\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
H Yet Another Origami Problem
题意
有 \(n\) 个数，分别为 \(a_i\)。
可以进行任意次操作，
每次操作选取一个下标 \(p\)，
① 对于所有 \(a_i\le a_p\)，\(a_i=a_i+2*(a_p-a_i)\)
② 对于所有 \(a_i\ge a_p\)，\(a_i=a_i-2*(a_i-a_p)\)
问操作后的极差的最小值是多少。
解题思路
可以想到，两种操作，分别是选择一个点为对称点，它的左边的点或者它右边的点以它对称。
我们可以想到，如果我们选定两个点固定为对称点，那么其他所有的点经过一定操作，一定可以被换到这两个点之间。
然后又在这些点之间内选两个点，继续迭代，最终肯定可以让所有点只在两个位置。
然后猜测答案就是差值的 \(\gcd\)。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 a[100005];
void solve() {
int n;
cin >> n;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
n = unique(a + 1, a + n + 1) - (a + 1);
if (a[1] == a[n]) {
cout << 0 << "\n";
return;
}
i64 g = 0;
for (int i = 2 ; i <= n ; i++) {
g = __gcd(g, a[i] - a[i - 1]);
}
cout << g << "\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
I Friends
题意
有 \(n\) 个人编号从 \(1\) 到 \(n\)，一共有 \(m\) 对朋友。
问有多少个区间 \([L,R]\) 满足 \(1\le L\le R\le n\) 且编号在这个区间内的所有人互相为朋友。
解题思路
对于第 \(i\) 个人，如果区间左端点为他，右端点为 \(i+1\) 的时候，\(i\) 必须和 \(i+1\) 是朋友，如果右端点为 \(i+2\) 的时候，\(i\) 也必须和 \(i+2\) 是朋友。
所以我们预处理一个东西，\(mi_i\) 表示比第 \(i\) 个人编号还要大的人的编号的 \(mex\)。
这样如果我们对于区间 \([L,R]\) 我们只需要 \(\min(mi_L,mi_{L+1},…,mi_{R})\le R\)，即可满足要求。
我们可以使用双指针求出以 \(L\) 为左端点最大的 \(R\)，然后直接对区间长度进行求和即可。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
vector<int> adj[1000005];
int mi[1000005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0 ; i < m ; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
}
for (int i = 1 ; i <= n ; i++) {
sort(begin(adj[i]), end(adj[i]));
mi[i] = i;
for (auto &x : adj[i]) {
if (mi[i] + 1 == x) {
mi[i]++;
} else {
break;
}
}
}
multiset<int> st;
st.insert(1e9);
int R = 1;
i64 ans = 0;
for (int i = 1 ; i <= n ; i++) {
while (*begin(st) >= i && R <= n) {
st.insert(mi[R]);
R++;
}
ans += *begin(st) - i + 1;
st.extract(mi[i]);
}
cout << ans;
return 0;
}
|
J Zero
题意
一个长度为 \(n\) 的包含 \(0\), \(1\), \(?\) 的字符串 \(s\)。
如果子串 \(s[L,R]\) 为全 \(1\)，则权值为 \((R-L+1)^k\)。否则权值为 \(0\)。
一个串的权值为，它所有子串的权值和。
现在 \(?\) 等概率的替换成 \(0\) 或 \(1\)，问这个串的期望权值是多少。
解题思路
根据二项式定理 \((a+b)^k=\sum_{i=0}^k(C_k^i*a^i)\)
当 \(b=1\) 的时候，就等价于区间长度多了 \(1\) 之后的权值。
所以我们定义 \(dp_{i,j}\) 为右端点为 \(i\) 时，区间长度的 \(j\) 次方的和。
我们枚举右端点 \(i\)，如果 \(s_i=0\)，那么应该没有贡献，所以我们将 \(dp_i\) 全置 \(0\)。
否则区间长度一定可以加 \(1\)，通过上述二项式定理可以求出权值的 \(j\) 次方的和。
然后我们需要新建一个左端点为 \(i\)，即新增贡献 \(1^j\)，对每个 \(j\) 都有 \(dp_{i,j}=dp_{i,j}+1\)。
如果 \(s_i=?\) 时，这个时候只有为 \(1\) 有贡献，因为等概率，所以我们要把权值的 \(j\) 次方的和都除以 \(2\) 即乘 \(2\) 的逆元。
最后对 \(dp_{i,k}\) 在 \(1\le i\le n\)求和即可。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const i64 P = 998244353;
i64 dp[100005][31], C[31][31];
i64 inv(i64 a, i64 b = P - 2, i64 res = 1) {
while (b) {
if (b & 1) {
res = res * a % P;
}
a = a * a % P;
b >>= 1;
}
return res;
}
int main() {
C[0][0] = 1;
for (int i = 1 ; i <= 30 ; i++) {
C[i][0] = 1;
for (int j = 0 ; j <= i ; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
}
}
int n, k;
cin >> n >> k;
string s;
cin >> s;
s = " " + s;
for (int i = 1 ; i <= n ; i++) {
if (s[i] == '0') {
for (int j = 0 ; j <= k ; j++) {
dp[i][j] = 0;
}
} else {
for (int j = 0 ; j <= k ; j++) {
for (int x = 0 ; x <= j ; x++) {
dp[i][j] = (dp[i][j] + C[j][x] * dp[i - 1][j - x]) % P;
}
dp[i][j] = (dp[i][j] + 1) % P;
if (s[i] == '?') {
dp[i][j] = dp[i][j] * inv(2) % P;
}
}
}
}
i64 ans = 0;
for (int i = 1 ; i <= n ; i++) {
ans = (ans + dp[i][k]) % P;
}
cout << ans << "\n";
return 0;
}
|
K Calculate the Expression
题意
给了你一个只含有数字，加号和乘号的字符串 \(s\).
多次操作。
操作① 查询区间 \([L,R]\) 所构成的表达式的值。
操作② 修改 \(s_{pos}=ch\)。
保证查询和修改合法。
解题思路
可以知道是一个区间查询和单点修改的线段树。
考虑一个表达式，我们怎么计算它的值。
如果这个表达式没有加号，那么这个表达式的值就一定是所有数的乘积。
如果这个表达式有加号，那么这个表达式相当于多个乘法表达式拼接在一起，所以表达式的值是拼接后的部分加上中间剩余部分的值。
我们定义 \(midsum\) 为去掉第一个数和最后一个数的和，\(midk\) 为去掉第一个数秀最后一个数的乘法表达式的值，
\(prev\) 为第一个数的值，\(pred\) 为第一个数的数位(10的次幂)，\(prek\) 为去掉第一个数的乘法表达式的值，
\(sufv\) 为最后一个数的值，\(sufd\) 为最后一个数的数位(10的次幂)，\(sufk\) 为去掉最后一个数的乘法表达式的值，
\(add\) 为加号的数量，\(mul\) 为乘号的数量。
我们先考虑单点。
对于加号和乘号，它们两个的区别在于 \(add\) 和 \(mul\)。
它们的 \(midsum=prev=sufv=0\)，\(midk=prek=sufk=pred=sufd=1\)。
对于数字 \(x\)，\(add=mul=0\)，\(prek=suf=1\)，
\(prev=sufv=x\)，\(pred=sufd=10\)。
我们考虑区间合并，令左区间为 \(x\)，右区间为 \(y\)。
对于 \(add,mul\)，
直接 \(add=x.add+y.add,mul=x.mul+y.mul\) 即可。
对于 \(prev,pred,prek\)，
当左边有加号的时，\(prev,pred,prek\) 肯定是直接等于左区间的。
所以我们考虑左边没有加号的时候，
当左边没有乘号即左边是一个完整的数时，
- 直接把右区间的 \(pre\) 拼上来，
- \(prev=x.prev*y.pred+y.prev,pred=x.pred*y.pred\)。
- 因为左区间是一个完整的数字，所以去掉第一个数字的乘法表达式和右区间的一致，即 \(prek=y.prek\)。
当左边有乘号时，
- 这个时候第一个数字不会变，即 \(prev=x.prev,pred=x.pred\)。
- 然后我们的去掉第一个数的乘法表达式就是中间拼起来后的乘法表达式，即 \(prek=x.midk*(x.sufv*y.pred+y.prev)*y.prek\)。
对于 \(sufv,sufd,sufk\)，
当右边有加号时，\(sufv,sufd,sufk\) 肯定是直接等于右区间的。
所以我们考虑右边没有加号的时候，
当右边没有乘号即右边是一个完整的数时，
- 直接把左区间的 \(suf\) 拼上来，
- \(sufv=x.sufv*y.sufd+y.sufv,sufd=x.sufd*y.sufd\)
- 因为右区间是一个完整的数字，所以去掉最后一个数字的乘法表达式和左区间的一致，即 \(sufk=x.sufk\)。
当右边有乘号时，
- 这个时候右边的最后一个数字是不会变的，即 \(sufv=y.sufv,sufd=y.sufd\)。
- 然后我们去掉最后一个数字的乘法表达式就是把中间拼起来，即 \(prek=x.midk*(x.sufv*y.pred+y.prev)*y.midk\)。
对于 \(midsum,midk\)，
首先 \(midk\) 有值当且仅当两边区间都没有加号。
所以如果两边区间都没有加号时，我们还需要判断 \(x\) 是完整的整数，还是 \(y\) 是完整的整数。
如果都不是则将中间拼起来即可。
然后我们看到 \(midsum\)，
但是当两个表达式都含有加号时，中间的乘法表达式需要拼接。
这个时候 \(midsum=x.midsum+y.midsum+x.sufk*(x.sufv*y.pred+y.prev)*y.prefk\)。
否则 \(midsum=x.midsum+y.midsum\)。
剩下来的就是套线段树模版了。
解题代码
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const i64 P = 998244353;
struct Node {
// add 为加法运算符的数量
// mul 为乘法运算符的数量
int add, mul;
// midsum 为去掉首尾的和
// midk 为去掉首尾的乘积和
i64 midsum, midk;
// pred 为第一个数字的位数(一位则是10^1)
// prev 为第一个数字的数值
// prek 为去掉第一个数字的乘积和的值
i64 prek, pred, prev;
// sufd 为最后一个数字的位数(一位则是10^1)
// sufv 为最后一个数字的数值
// sufk 为去掉最后一个数字的乘积和的值
i64 sufk, sufd, sufv;
Node() {}
Node(char ch) {
add = mul = 0;
midsum = 0;
midk = 1;
prek = sufk = 1;
pred = sufd = 1;
prev = sufv = 0;
if (ch == '+') {
add = 1;
} else if (ch == '*') {
mul = 1;
} else {
pred = sufd = 10;
prev = sufv = ch - '0';
}
}
i64 query() {
if (add == 0) {
// 没有加号
// 则乘积和
// 第一个数乘上去掉第一个数的乘积
return prev * prek % P;
}
// 有加号
// 则加号乘号都有
// 中间的和加上第一个数和去掉第一个数的乘积再加上最后一个数和去掉最后一个数的乘积。
return (midsum + prev * prek % P + sufv * sufk % P) % P;
}
} tr[500005 << 2];
string str;
Node merge(Node x, Node y) {
Node res;
res.add = x.add + y.add;
res.mul = x.mul + y.mul;
if (res.add == 0) {
if (x.mul == 0) {
res.midk = y.midk;
} else if (y.mul == 0) {
res.midk = x.midk;
} else {
i64 sum = (x.sufv * y.pred + y.prev) % P;
res.midk = x.midk * sum % P * y.midk % P;
}
}
if (x.add == 0) {
// 左侧无加号
if (x.mul == 0) {
// 左侧没有乘号
// 则左侧全为数字
res.prev = (x.prev * y.pred + y.prev) % P;
res.pred = x.pred * y.pred % P;
res.prek = y.prek;
} else {
// 左侧有乘号
res.prev = x.prev;
res.pred = x.pred;
i64 sum = (x.sufv * y.pred + y.prev) % P;
res.prek = x.midk * sum % P * y.prek % P;
}
} else {
// 左侧有加法
res.prev = x.prev;
res.pred = x.pred;
res.prek = x.prek;
}
if (y.add == 0) {
// 右侧无加号
if (y.mul == 0) {
// 右侧无乘号
// 则右侧全为数字
res.sufv = (x.sufv * y.sufd + y.sufv) % P;
res.sufd = x.sufd * y.sufd % P;
res.sufk = x.sufk;
} else {
// 右侧有乘号
res.sufv = y.sufv;
res.sufd = y.sufd;
i64 sum = (x.sufv * y.pred + y.prev) % P;
res.sufk = x.sufk * sum % P * y.midk % P;
}
} else {
res.sufv = y.sufv;
res.sufd = y.sufd;
res.sufk = y.sufk;
}
res.midsum = (x.midsum + y.midsum) % P;
if (x.add > 0 && y.add > 0) {
i64 sum = (x.sufv * y.pred + y.prev) % P;
res.midsum = (res.midsum + x.sufk * sum % P * y.prek % P) % P;
}
return res;
}
void pushup(int p) {
tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
}
void build(int p, int L, int R) {
if (L == R) {
tr[p] = Node(str[L]);
return;
}
int mid = L + R >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
pushup(p);
}
void modify(int p, int L, int R, int pos, char k) {
if (L == R) {
str[L] = k;
tr[p] = Node(str[L]);
return;
}
int mid = L + R >> 1;
if (pos <= mid) modify(p << 1, L, mid, pos, k);
if (pos > mid) modify(p << 1 | 1, mid + 1, R, pos, k);
pushup(p);
}
Node query(int p, int L, int R, int QL, int QR) {
if (QL <= L && R <= QR) {
return tr[p];
}
int mid = L + R >> 1;
if (QR <= mid) {
return query(p << 1, L, mid, QL, QR);
}
if (QL > mid) {
return query(p << 1 | 1, mid + 1, R, QL, QR);
}
return merge(query(p << 1, L, mid, QL, QR), query(p << 1 | 1, mid + 1, R, QL, QR));
}
int main() {
int m;
cin >> m;
cin >> str;
int n = str.size();
str = " " + str;
build(1, 1, n);
for (int i = 1 ; i <= m ; i++) {
int op;
cin >> op;
if (op == 1) {
int L, R;
cin >> L >> R;
cout << query(1, 1, n, L, R).query() << "\n";
} else {
int pos;
char ch;
cin >> pos >> ch;
modify(1, 1, n, pos, ch);
}
}
return 0;
}
|