【暑期多校补题记录】2025牛客多校(3)(4) 杭电多校(2)(3)

正在检查是否收录...

【暑期多校补题记录】2025牛客多校(3)(4) 杭电多校(2)(3)

本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/19007314

开题情况

7.22牛客多校3 ： 5题 - ADEFJ
7.24牛客多校4 ： 1题 - F
7.21杭电多校2 ： 4题 - 2、6、8、9
7.25杭电多校3 ： 4题 - 2、7、8、12

暑期多校第二周，这周打得有点不尽如人意，主要是好几场的mid题就开始卡了，尤其是牛客多校4，被自己一个很低级的错误葬送了B题，还需多练！

本人个人补题情况

7.22牛客多校3 ： 3题 - BEH
7.24牛客多校4 ： 2题 - BG
7.21杭电多校2 ： 3题 - 7、9、12
7.25杭电多校3 ： 2题 - 4、9

有些题场上虽然过了，但一看并非最优解，就也纳入补题阵列了。

牛客多校3补题

B - Bitwise Puzzle

赛时试图枚举所有初始状态来求解，但还是一WA再WA。
首先 \(b\) 可以进行按位右移操作，所以 \(b\) 是可以变成 \(0\) 的，那么，我们就有一个大致的方向了：用 \(b\) 来改 \(a\)，把 \(a\) 改成 \(c\)，然后把 \(b\) 异或上 \(a\)。
当 \(a\) 和 \(b\) 不都为 \(0\) 的时候，如果 \(a\) 和 \(b\) 的最高位不同，我们一定可以通过一次 \(a \oplus b\)，来把 \(a\) 和 \(b\) 的最高位变成一样的（因为最高位不等的话，在该位，一定有一个 \(1\) 一个 \(0\)，异或一下就可以把 \(0\) 改成 \(1\)），记这个最高位为 \(k\)。
由于我们要把 \(b\) 变成 \(0\)，所以 \(b\) 的最高位 \(1\) 会逐步右移，就足以修改掉 \(a\) 的 \(\leq k\) 的位了，因此对于 \(a\) 的 \(\leq k\) 的位，只需要通过把 \(b\) 逐步右移，对于 \(b\) 当前的最高位，比对 \(a\) 和 \(c\) 在该位是否相等，如果不相等，就用一次异或操作进行修改。由于 \(b\) 的最高位往左全都是 \(0\)，所以修改不会对 \(a\) 已修改的位造成影响。
那如果 \(c\) 的最高位 \(> k\) 呢？\(b\) 右移逐步修改是修改不到更高的位的，那么我们可以换个角度，既然 \(b\) 不能左移，那就让 \(a\) 左移，我们用第 \(k\) 位去修改 \(a\) 的第 \(k\) 位，然后通过左移操作把修改的位往左运输过去，不就行了吗。
因此，我们的操作顺序应该是：

如果 \(a\) 和 \(b\) 最高位不等，那么用一次 \(a \ oplus b\) 把最高位对齐。
通过 \(a \oplus b\) 和 \(a << 1\) 把 \(> k\) 的位修改得和 \(c\) 一样。
通过 \(a \oplus b\) 和 \(b >> 1\) 把 \(\leq k\) 的位修改得和 \(c\) 一样。
用 \(a \oplus b\) 把 \(b\) 改成 \(c\)。

计算一下操作次数：第一步最多执行 \(1\) 次操作，第二步和第三步每次修改最多有 \(2\) 个操作参与，总的位数最多为 \(31\) 位，所以最多 \(31 * 2 = 62\) 次，最后一步执行 \(1\) 次操作，加起来刚好 \(64\) 次，非常稳定！
再看一下上面这个做法成立的条件，我们需要把 \(a\) 和 \(b\) 的最高位对齐，因此，至少要有一个非 \(0\)，如果两个都是 \(0\)，则没有任何的修改机会，当且仅当 \(c = 0\) 的时候有解，否则无解。

点击查看代码

#include <bits/stdc++.h> #define int long long using i64 = long long; void solve() { int a, b, c;std::cin >> a >> b >> c; if(a == b && b == 0) { if(c == 0) { std::cout << 0 << "\n\n"; } else { std::cout << -1 << '\n'; } return; } std::vector<int> op; if(std::__lg(a) != std::__lg(b)) { if(std::__lg(a) < std::__lg(b)) { a ^= b; op.push_back(3); } else { b ^= a; op.push_back(4); } } int ch = std::__lg(c) - std::__lg(a); int now = std::__lg(a); if(ch > 0) { for(int i = 0;std::__lg(a) < std::__lg(c);i ++) { if((c >> (std::__lg(c) - i) & 1) != (a >> now & 1)) { a ^= b; op.push_back(3); } a <<= 1; op.push_back(1); } } for(int i = now;i >= 0;i --) { if((c >> i & 1) != (a >> i & 1)) { a ^= b; op.push_back(3); } b >>= 1; op.push_back(2); } while(b) { b >>= 1; op.push_back(2); } b ^= a; op.push_back(4); std::cout << op.size() << '\n'; for(auto &x : op) { std::cout << x << ' '; } std::cout << '\n'; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int t = 1; std::cin >> t; while (t--) { solve(); } return 0; }

E - Equal

这个题赛时队友想的。
首先，如果 \(n\) 为奇数，那么一定可行，因为对除了某个数字外的其它的所有数字（一定是偶数个）都做一个相同的操作，等于对这个数字做一个单点的反向操作，那么一定可以把所有数字都变成一样的。（类似于上半年南昌邀请赛的一个题）
如果 \(n\) 为 \(2\)，特殊判断一下，当且仅当两个数字相同的时候才可行，因为此时只能对这两个数字操作，且操作都相同。
如果 \(n\) 为其它偶数，那么，只需要判断，各个质数在这些所有数中的出现次数，是否为偶数次，如果为偶数次，则一定可行，因为每次操作对质数次数变化都是偶数次，如果一开始次数为奇数次，那么最后必然会有孤立的数，并且不能像奇数的情况那样，通过修改其它的来看作反向修改自己，因为此时除了孤立出来的那个数，剩下的数的总数是偶数个。

处理方法，赛时选择对每个数进行唯一分解来计数，通过素数剪枝卡过去了，此做法很极限，瓶颈在于唯一分解。
那么再观察一下这个题要我们干嘛，质数出现次数为偶数，那什么方法很适合用来统计信息出现的奇偶性呢？
那不就是异或哈希嘛！
我们通过给每个质数随机一个哈希值，然后在素筛的过程中通过异或处理出每个数的哈希值，由于次数为偶数的时候，异或值为 \(0\)，因此，判断数组中所有分解出来的质数的出现次数是否都为偶数，也就是判断数组所有数的哈希值异或起来的值是否为 \(0\)。

时间复杂度：\(O(nlog(logn))\)

点击查看代码

#include <bits/stdc++.h> #define int long long const int N = 5e6 + 9; bool notprime[N]; std::vector<int> prime; bool vis[N]; int hash[N]; std::mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count()); int ran(int l, int r) { return rnd() % (r - l + 1) + l; } void init() { notprime[0] = notprime[1] = true; for(int i = 2;i < N;i ++) { if(!notprime[i])prime.push_back(i); for(int j = 0;j < prime.size() && prime[j] * i < N;j ++) { notprime[prime[j] * i] = true; if(i % prime[j] == 0) { break; } } } for(int i = 0;i < prime.size();i ++) { hash[prime[i]] = ran(1e9, 1e18); for(int j = prime[i] * 2;j < N;j += prime[i]) { int tmp = j; while(tmp % prime[i] == 0) { tmp /= prime[i]; hash[j] ^= hash[prime[i]]; } } } } void solve() { int n;std::cin >> n; std::vector<int> a(n); for(auto &x : a) { std::cin >> x; } if(n & 1) { std::cout << "YES\n"; return; } if(n == 2) { if(a[0] == a[1]) { std::cout << "YES\n"; } else { std::cout << "NO\n"; } return; } int ans = 0; for(auto &x : a) { ans ^= hash[x]; } std::cout << ((ans == 0) ? "YES\n" : "NO\n"); } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); init(); int t = 1;std::cin >> t; while(t --) { solve(); } return 0; }

H - Head out to the Target

赛时磕 B 去了，没看这题，现在回想起来应该和队友一起磕这题的。

这个题首先要明确一点，如果我们假设一个结点 \(x\) 是最后答案所在点，那么必定是从根沿着路径走下来，不会走到别的地方去（也就是把别的路切了），不然一定不优。
那么其实我们需要关注的，就是到某个时间点的时候，目标到根的路径上的所有结点，也就是目标的所有祖先结点，是否都有可能在最优情况下走过。
当一个目标出现时，只需要把它的最近的祖先结点往下扩展一格就行了，一个祖先结点是可能走过的，那么这个目标出现时，完全可以认为当前棋子就在这个祖先结点上，因为在其它结点的话，勾引过来到的位置，也一定是之前已经到过的，所以每次最多扩展一格。
只需要判断目标在每个结点时，该结点是否有可能走过即可（因为也可以切断它下面的边避免它被勾引走）。
这个祖先结点可以使用倍增进行查找，单次时间复杂度为 \(O(logn)\)，由于每个点最多被扩展一次，所以最多扩展 \(n\) 次，然后就一定有解了。
时间复杂度：\(O(nlogn)\)。

点击查看代码

#include <bits/stdc++.h> #define int long long const int N = 1e7 + 9; void returm() { int n, k;std::cin >> n >> k; std::vector<std::array<int, 30>> fa(n + 1, std::array<int, 30>{}); for(int i = 2;i <= n;i ++) { std::cin >> fa[i][0]; } for(int k = 1;k < 30;k ++) { for(int i = 1;i <= n;i ++) { fa[i][k] = fa[fa[i][k - 1]][k - 1]; } } std::vector<int> vis(n + 1); vis[1] = true; vis[0] = true; auto get = [&](int st) -> int { for(int k = 29;k >= 0;k --) { if(vis[fa[st][k]])continue; st = fa[st][k]; } return st; }; int ans = -1; while(k --) { int u, l, r;std::cin >> u >> l >> r; if(ans != -1)continue; if(vis[u]) { ans = l; continue; } for(int i = l;i <= r;i ++) { int now = get(u); vis[now] = true; if(now == u) { ans = i; break; } } } std::cout << ans << '\n'; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int t = 1;//std::cin >> t; while(t --) { returm(); } }

牛客多校4补题

B - BlindAlley

赛时战犯的一题，由于最大值自底向上转移的时候循环写反了，导致赛时没能开出，记录于此，警钟长鸣！

还是写写思路吧，这个题，其实关注点总结下来就一句话：一个点，是否有可能在某一时刻，以为能向右走过去走到终点，于是向右走到了这个点，但这个点实际上是无法抵达终点的，同时也没有回头路了。
翻译一下题意如下：

在某个点以为能向右走过去，翻译一下其实就是：当前列为 \(j\)，向右走了过后，该右点能向右到达的最远点的列数 \(\geq j + k\)。
这个点实际上是无法抵达终点，翻译一下，其实就是：从重点出发按题目规则反向走走不到这个点。

因此，思路就很简单了。
首先从起点跑一遍BFS再配合一次从右往左的简单DP转移最值，预处理一下每个点可以到达的最远列。
然后从重点跑一遍BFS，找出所有可以抵达的点。
然后再从起点跑一遍BFS，不过这次和第一次不一样，这次在走点的时候，要判断一下是否满足上述第1条题意翻译，然后对于可以抵达的点，判断一下它是不是可以抵达终点的点，如果不是，那就直接输出 Yes 即可。

点击查看代码

#include <bits/stdc++.h> #define int long long const int N = 1e7 + 9; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, 1, -1}; void returm() { int n, m, k;std::cin >> n >> m >> k; std::vector a(n, std::vector<char>(m)); for(auto &x : a) { for(auto &c : x) { std::cin >> c; } } std::vector mx(n, std::vector<int>(m)); std::queue<std::pair<int, int>> q; q.push({0, 0}); std::vector vis(n, std::vector<int>(m)); auto inmp = [&](int x, int y) -> bool { return x >= 0 && x < n && y >= 0 && y < m; }; mx[0][0] = 0; while(q.size()) { auto [x, y] = q.front(); q.pop(); for(int i = 0;i < 3;i ++) { int nx = x + dx[i]; int ny = y + dy[i]; if(!inmp(nx, ny))continue; if(a[nx][ny] == '1')continue; if(vis[nx][ny])continue; mx[nx][ny] = std::max(y, ny); vis[nx][ny] = true; q.push({nx, ny}); } } for(int j = m - 1;j >= 0;j --) { if(j + 1 < m) { for(int i = 0;i < n;i ++) { if(a[i][j + 1] == '0')mx[i][j] = std::max(mx[i][j], mx[i][j + 1]); } } for(int i = 0;i < n;i ++) { if(a[i][j] == '1')continue; if(i - 1 >= 0 && a[i - 1][j] == '0')mx[i][j] = std::max(mx[i][j], mx[i - 1][j]); } for(int i = n - 1;i >= 0;i --) { if(a[i][j] == '1')continue; if(i + 1 < n && a[i + 1][j] == '0')mx[i][j] = std::max(mx[i][j], mx[i + 1][j]); } } std::vector v(n, std::vector<int>(m)); v[0][m - 1] = true; q.push({0, m - 1}); while(q.size()) { auto [x, y] = q.front(); q.pop(); for(int i = 0;i < 4;i ++) { if(i == 2)continue; int nx = x + dx[i]; int ny = y + dy[i]; if(!inmp(nx, ny))continue; if(a[nx][ny] == '1')continue; if(v[nx][ny])continue; v[nx][ny] = true; q.push({nx, ny}); } } std::vector u(n, std::vector<int>(m)); q.push({0, 0}); u[0][0] = true; while(q.size()) { auto [x, y] = q.front(); q.pop(); if(!v[x][y]) { std::cout << "Yes\n"; return; } for(int i = 0;i < 3;i ++) { int nx = x + dx[i]; int ny = y + dy[i]; if(!inmp(nx, ny))continue; if(a[nx][ny] == '1')continue; if(u[nx][ny])continue; if(mx[nx][ny] < y + k)continue; u[nx][ny] = true; q.push({nx, ny}); } } std::cout << "No\n"; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int t = 1;std::cin >> t; while(t --) { returm(); } }

G - Ghost intheParentheses

看到括号对，作为一个栈匹配的经典模型，常见的思路就是转化为前缀问题，对 ( 赋值为 \(1\)，对 ) 赋值为 \(-1\)。
题目说对于未知的括号对，要让它们的填法是唯一的，来满足合法的括号序列。
那考虑一下，什么样的括号对，如果未知，其填法不是唯一的呢？
对于一个合法的括号对序列，应该满足它的任何一个前缀和都 \(\geq 0\)，如果交换一个左括号和一个右括号，该条件仍然满足，那么就说明不唯一！
因此，唯一的条件是，交换任何一个左括号和任何一个右括号，都会导致存在一个前缀值 \(< 0\)。
回到这个题目，我们对于每一个点 \(i\)，找到右边最近的一个满足前缀值 \(= 1\) 的位置 \(j\)，这时候， \(i\) 左侧的左括号，都可以未知，且只能是左括号未知，\(j\) 右侧的右括号，都可以未知，且只能是右括号未知，因为此时交换左边未知左括号和右边未知的右括号，必然导致 \(j\) 处的前缀值变成 \(-1 < 0\)。
同时，考虑 \(i\) 到 \(j\) 之间的字符都已知，因为 \(i\) 到 \(j\) 之间的字符如果未知，都会对 \(j\) 的位置造成影响，不便于计数。
由于选出的未知字符一定是左边很多左括号，右边很多右括号，不会出现先右括号再左括号的情况（出现这种情况了则可以交换他俩了，前缀值只会增大），这样的话，为了不重不漏，我们可以以每个左括号为分界点来进行计数，一定可以做到不重不漏。
但其实还是会漏掉一种情况，由于在上面的枚举过程中，我们保证了每种情况至少有一个左括号是不选为未知的，所以所有左括号都被选为未知的情况会被漏掉，并且这时候一定唯一，所以最后再加上这种情况即可。

点击查看代码

#include <bits/stdc++.h> #define int long long const int M = 998244353; int power(int n, int m) { int res = 1; while(m) { if(m & 1)res = res * n % M; n = n * n % M; m >>= 1; } return res; } int inv(int x) { return power(x, M - 2) % M; } void returm() { std::string s;std::cin >> s; int n = s.size(); s = ' ' + s; std::vector<int> pre(n + 2), suf(n + 2), sum(n + 2); for(int i = 1;i <= n;i ++) { sum[i] = sum[i - 1] + (s[i] == '(' ? 1 : -1); } for(int i = 1;i <= n;i ++) { pre[i] = pre[i - 1] + (s[i] == '('); } for(int i = n;i >= 1;i --) { suf[i] = suf[i + 1] + (s[i] == ')'); } std::vector<int> p(n + 1); p[0] = 1; for(int i = 1;i <= n;i ++) { p[i] = p[i - 1] * 2 % M; } int ans = 0; for(int i = 1, j = 1;i <= n;i ++) { j = std::max(j, i); while(j <= n && sum[j] > 1)j ++; if(s[i] == '(') { ans = (ans + p[pre[i - 1]] * p[suf[j + 1]] % M) % M; } } ans = (ans + p[n / 2]) % M; ans = ans * inv(p[n]) % M; std::cout << (ans % M + M) % M << '\n'; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int t = 1;//std::cin >> t; while(t --) { returm(); } }