2025.2.19——1500

2025.2.19——1500

---

A 1500 B 1500 C 1500 D 1500 ------------------------------------------------ 思维/图论+位运算/思维+数学/思维+构造/思维

---

A 存在路径即在一个连通块。加上必须加的边，删去必须要删去的边。并查集维护查询，考虑一下删边和加边的先后顺序。

---

B 位运算入手点当然是单独考虑每一位。发现三个数中在同一位中有1个/2个1才会有贡献。注意区间范围。

---

C 分奇偶模拟下过程发现结论。

---

D 尝试0101进行构造。再考虑奇偶和 x 、 y x、y x、y 关系，找通解。

---

------------------------代码------------------------ A #include <bits/stdc++.h> #define int long long using namespace std; #define bug(BUG) cout << "bug:# " << (BUG) << endl #define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl #define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl #define bugv(VEC) \ { \ for (auto Vec : VEC) \ cout << Vec << ' '; \ cout << '\n'; \ } void _(); signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(10); int T = 1; cin >> T; while (T--) _(); return 0; } // 带权并查集 struct DSU { vector<int> p, vs, es; // 集合数 点数 边数 (对一个连通块而言) DSU(int n1) // p[x]不一定为根节点 find(x)一定是根节点 { int n = n1 + 2; p.assign(n, 0); vs.assign(n, 0); es.assign(n, 0); for (int i = 1; i <= n1; i++) p[i] = i, vs[i] = 1, es[i] = 0; } int find(int x) // 找到根节点 { if (p[x] == x) return x; int px = find(p[x]); return p[x] = px; } bool same(int a, int b) { return find(a) == find(b); } void merge(int a, int b) // 合并集合 { int pa = find(a); int pb = find(b); if (pa == pb) // pa pb 均为根节点 p[pa]==pa { es[pa]++; // 1个集合 边+1 return; } p[pb] = p[pa]; // 改变b的根节点 vs[pa] += vs[pb]; // 将b合并进a es[pa] += es[pb] + 1; // 2个集合 } int size(int a) // 集合内的元素的个数 { return vs[find(a)]; } }; // DSU(n); void _() { int n, m1, m2; cin >> n >> m1 >> m2; DSU F(n), G(n); vector<pair<int, int>> ef(m1), eg(m2); for (auto &[x, y] : ef) cin >> x >> y; for (auto &[x, y] : eg) { cin >> x >> y; G.merge(x, y); } int res = 0; for (auto [x, y] : ef) { if (!G.same(x, y)) res++; else F.merge(x, y); } for (auto [x, y] : eg) { if (!F.same(x, y)) { res++; F.merge(x, y); } } cout << res << '\n'; }

---

B #include <bits/stdc++.h> #define int long long using namespace std; #define bug(BUG) cout << "bug:# " << (BUG) << endl #define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl #define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl #define bugv(VEC) \ { \ for (auto Vec : VEC) \ cout << Vec << ' '; \ cout << '\n'; \ } void _(); signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(10); int T = 1; cin >> T; while (T--) _(); return 0; } void _() { int l, r; cin >> l >> r; int a = 0, b = 0, c = 0; int hi = 32; for (;; hi--) { int r_bit = r >> hi & 1, l_bit = l >> hi & 1; if (r_bit - l_bit) break; else if (l_bit) { a |= 1 << hi, b |= 1 << hi, c |= 1 << hi; } } c |= 1 << hi; b = c - 1; a = b - 1 < l ? c + 1 : b - 1; cout << a << ' ' << b << ' ' << c << '\n'; } // void _() // { // int a, b, c; // cin >> a >> b >> c; // cout << (a ^ b) + (b ^ c) + (a ^ c) << '\n'; // }

---

C #include <bits/stdc++.h> #define int long long using namespace std; #define bug(BUG) cout << "bug:# " << (BUG) << endl #define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl #define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl #define bugv(VEC) \ { \ for (auto Vec : VEC) \ cout << Vec << ' '; \ cout << '\n'; \ } void _(); signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(10); int T = 1; cin >> T; while (T--) _(); return 0; } void _() { int n, k; cin >> n >> k; int st = 1, cnt = 0; int l = 1, r = n; while (r - l + 1 >= k) { int mid = l + r >> 1; if (r - l + 1 & 1) { cnt += st; r = mid - 1; } else r = mid; st <<= 1; } // int res = (1 + n >> 1) * cnt; // if (n % 2 == 0) // res = (1 + n) * cnt >> 1; int res = (1 + n) * cnt >> 1; cout << res << '\n'; }

---

D #include <bits/stdc++.h> #define int long long using namespace std; #define bug(BUG) cout << "bug:# " << (BUG) << endl #define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl #define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl #define bugv(VEC) \ { \ for (auto Vec : VEC) \ cout << Vec << ' '; \ cout << '\n'; \ } void _(); signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(10); int T = 1; cin >> T; while (T--) _(); return 0; } void _() { int n, x, y; cin >> n >> x >> y; vector<int> f(n + 1); if (n & 1) { int ans = 0; for (int i = 1; i <= n; i++) { if (i == x) f[i] = 2; else { f[i] = ans; ans ^= 1; } } } else { int ans = 0; for (int i = 1; i <= n; i++) { f[i] = ans; ans ^= 1; } if (abs(x - y) % 2 == 0) f[x] = 2; } for (int i = 1; i <= n; i++) cout << f[i] << ' '; cout << '\n'; } // void _() // { // int n, x, y; // cin >> n >> x >> y; // vector<set<int>> a(n + 1, set<int>()); // for (int i = 1; i <= n; i++) // { // int l = i - 1, r = i + 1; // if (!l) // l = n; // if (r > n) // r = 1; // a[i].insert(l); // a[i].insert(r); // } // a[x].insert(y); // a[y].insert(x); // auto cal = [](set<int> s) // { // int st = 0; // for (auto v : s) // { // if (v - st) // return st; // st++; // } // return st; // }; // for (int i = 1; i <= n; i++) // cout << cal(a[i]) << ' '; // cout << '\n'; // }

---