2025.2.19—

2025.2.19——1500

`------------------------------------------------`

思维/图论+位运算/思维+数学/思维+构造/思维

A

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

B

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

C

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

D

尝试0101进行构造。
再考虑奇偶和 $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个集合 边+1return;}p[pb] = p[pa];        // 改变b的根节点vs[pa] += vs[pb];     // 将b合并进aes[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++;elseF.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;}elser = 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';
// }