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

郦湘云 · 前天 13:01

本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：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 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;
}

复制代码

G - Ghost intheParentheses

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

账号		自动登录	找回密码
密码			立即注册

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

浏览过的版块

签约作者