Constructive Algorithms

Mere Array 要求可以交换位置的两个数的最大公约数是数组中的最小数，可以想到先把数组中的最小数找出来，设为 $x$，这样可以让 $x$ 去和所有能够被 $x$ 整除的数字交换，因为不限操作次数，所以这些数字可以一直交换到有序。接下来考虑不能被 $x$ 整除的数字，可以发现它们的位置是永远不变的，因此只需要把数组排好序之后，检查它们的位置是否保持不变即可。 // Date: Mon Dec 11 23:33:35 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 100010; int t, n, a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1401c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i]; b[i] = a[i]; } bool flag = true; int mi = a[1]; For1(i, 2, n) { if (a[i] < a[i - 1]) { flag = false; } mi = min(mi, a[i]); } if (flag) { cout << "YES\n"; continue; } sort(b + 1, b + 1 + n); flag = true; For1(i, 1, n) { if (b[i] % mi == 0) continue; if (b[i] != a[i]) { flag = false; break; } } cout << (flag ? "YES" : "NO") << '\n'; } return 0; }

Huge Boxes of Animal Toys ICPC Indonesia COMPFEST 12 Multi-Provincial Contest Online Mirror Editorial 每次操作都是乘法，所以最终的结果的符号可以确定，并且和操作顺序没有关系。确定了符号之后就只有两种选择：如果乘积为正，结果可能是 $C$ 或者 $D$。接下来只需要考虑所有数字的绝对值的乘积的范围，如果绝对值中包含 $(0, 1)$ 中的数，那么结果可能是 $C$；如果绝对值中包含 $[1, \infin)$ 中的数，那么结果可能是 $D$。乘积为负同理。 // Date: Mon Dec 11 22:53:18 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif int t, a, b, c, d; bool res[10]; int main(void) { #ifdef _DEBUG freopen("1425h.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> a >> b >> c >> d; int sum = a + b, sum1 = b + c, sum2 = a + d; memset(res, false, sizeof res); if (sum & 1) { if (sum1) { res[2] = true; } if (sum2) res[1] = true; } else { if (sum1) res[3] = true; if (sum2) res[4] = true; } For1(i, 1, 4) { cout << (res[i] ? "Ya" : "Tidak") << ' '; } cout << '\n'; } return 0; }

Number into Sequence 因为要保证 $a_{i} \vert a_{i+1}$，又要保证得到的数组最长，可以想到先把 $n$ 因数分解，得到个数最多的因子 $p$，能够保持整除关系并且最长的序列的长度就是 $p$ 的个数，其余的因子全部放在最后一个数字。 // Date: Mon Dec 11 20:15:03 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif int t; ll n; map<ll, int> m; void defact(ll n) { for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) { m[i]++; n /= i; } } } if (n > 1) m[n]++; } int main(void) { #ifdef _DEBUG freopen("1454d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; m.clear(); defact(n); ll ma = 0, val = 0; for (auto &[x, y] : m) { if (y > ma) { ma = y; val = x; } } vector<ll> res(ma + 1, val); cout << ma << '\n'; for (auto &[x, y] : m) { int cnt = y; if (x != val) { while (cnt--) { res[ma] *= x; } } } For1(i, 1, ma) { cout << res[i] << ' '; } cout << '\n'; } return 0; }

Diane tutorial 非常有意思的一道构造题。 首先观察 $k$ 个 $a$ 组成的字符串中，各个子字符串出现的次数：$a$ 出现 $k$ 次，$aa$ 出现 $k - 1$ 次 $\ldots$ 可以发现子字符串出现的次数是奇偶相间的。所以可以利用这一点来构造只出现奇数次的子字符串。 左边放连续 $k$ 个 $a$ 组成前半段，后半段放 $k - 1$ 个 $a$，中间放其他字母。因为 $k$ 和 $k - 1$ 的奇偶性相反，它们当中长度相同的子字符串出现的次数恰好奇偶性也相反，这样就满足左右两侧的子字符串出现的次数一定是奇数。中间根据 $n$ 的奇偶性放一个或者两个其他字符，这样就可以保证横跨中间的子字符串只出现一次，也是奇数。因此所有子字符串都出现奇数次。 构造题比较灵活，比较难想，大部分时候是观察到某个性质，然后利用这个性质贪心地构造满足题意的结构。 // Date: Sun Dec 10 22:06:20 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif int t, n; int main(void) { #ifdef _DEBUG freopen("1554d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; int k = n / 2; if (n == 1) { cout << "a\n"; continue; } string res(k, 'a'); if (n & 1) { res += "bc"; } else { res += "b"; } res += string(k - 1, 'a'); cout << res << '\n'; } return 0; }

Co-growing Sequence 从左到右找到每对 $a_i \bigoplus b_i$ 要包含上一个 $a_{i - 1} \bigoplus b_{i - 1}$ 中所有的二进制表示中的 1 所需要额外的位，计算公式是：$b_i = [a_i \bigoplus (a_{i - 1} \bigoplus b_{i - 1})] \bigwedge (\overline{a_i})$ // Date: Sun Dec 10 21:14:31 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int t, n, a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1547d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i]; } memset(b, 0, sizeof b); int pre = a[1]; For1(i, 2, n) { if ((a[i] & pre) == pre) { pre = a[i]; continue; } b[i] = (a[i] ^ pre) & (~a[i]); pre = b[i] ^ a[i]; } For1(i, 1, n) { cout << b[i] << ' '; } cout << '\n'; } return 0; }

Bit Flipping tutorial 先考虑每一位要变成 1 需要翻转的次数，从左往右考虑，每一位要变成 1 最多需要一次翻转。反过来想，每一位也最多需要一次固定操作，固定总操作数是 $k$，从左往右计算直到用完 $k$ 次，如果用不完，那么把剩下的次数都给最右边的位，因为它对字典序的影响最小。 // Date: Sun Dec 10 20:11:10 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int t, n, k, d[N]; string s; int main(void) { #ifdef _DEBUG freopen("1659b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k >> s; int cur = k; memset(d, 0, sizeof d); For(i, 0, n) { if (!cur) break; if (s[i] == '1') { if (k & 1) { cur--; d[i] = 1; } else { } } else { if (k & 1) { } else { cur--; d[i] = 1; } } if (!cur) break; } if (cur) { d[n - 1] += cur; } For(i, 0, n) { int cnt = k - d[i]; if (cnt & 1) { if (s[i] == '1') s[i] = '0'; else s[i] = '1'; } } cout << s << '\n'; For(i, 0, n) { cout << d[i] << ' '; } cout << '\n'; } return 0; }

Make Nonzero Sum (easy version) tutorial 分组之后的和并不会数组和改变奇偶性，当数组和为奇数的时候无解。考虑 $(a_{2i - 1}, a_{2i})$ 这样的组，如果两元素相等，这两个数字组成一组；如果不等，那么每个数字各自是一个单独的组。 // Date: Sun Dec 10 16:11:53 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int n, t, a[N]; int main(void) { #ifdef _DEBUG freopen("1753a1.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; int sum = 0; For1(i, 1, n) { cin >> a[i]; sum += a[i]; } if (sum & 1) { cout << -1 << '\n'; continue; } vector<PII> res; For1(i, 1, n - 1) { if (a[i] == a[i + 1]) { res.pb({i, i + 1}); } else { res.pb({i, i}); res.pb({i + 1, i + 1}); } ++i; } cout << SZ(res) << '\n'; for (auto &[x, y] : res) { cout << x << ' ' << y << '\n'; } } return 0; }

Elemental Decompress 先把原数组从大到小排序，然后依次往两个答案数组 $p_1$ 和 $p_2$ 中填数，两个数组是等价的，不妨优先在 $p_1$ 中填，如果一个数字在两个数组中都已经用过了，说明这个数字出现了三次，可以判定无解。填完一遍之后，再从大到小往两个 $p$ 数组中从前往后填入各自缺少的数字，如果填入的数字大于原数组，那么也无解。 // Date: Sun Dec 10 15:00:10 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; struct point { int v, p1, p2, idx; }; int t, n; point a[N]; bool vis[2][N]; int main(void) { #ifdef _DEBUG freopen("1768c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i].v; a[i].idx = i; a[i].p1 = a[i].p2 = 0; } sort(a + 1, a + n + 1, [&](const point &x, const point &y) { if (x.v > y.v) return true; else if (x.v == y.v) return x.idx < y.idx; return false; }); memset(vis, false, sizeof vis); bool flag = true; For1(i, 1, n) { int x = a[i].v; if (!vis[0][x]) { vis[0][x] = true; a[i].p1 = x; } else if (!vis[1][x]) { vis[1][x] = true; a[i].p2 = x; } else { flag = false; break; } } VI rem1; Rof1(i, 1, n) { if (!vis[0][i]) { rem1.pb(i); } } if (nonempty(rem1)) { int idx = 0; For1(i, 1, n) { if (!a[i].p1) { if (rem1[idx] <= a[i].v) { a[i].p1 = rem1[idx++]; } else { flag = false; break; } } } } VI rem2; Rof1(i, 1, n) { if (!vis[1][i]) { rem2.pb(i); } } if (nonempty(rem2)) { int idx = 0; For1(i, 1, n) { if (!a[i].p2) { if (rem2[idx] <= a[i].v) { a[i].p2 = rem2[idx++]; } else { flag = false; break; } } } } if (flag) { cout << "YES\n"; sort(a + 1, a + n + 1, [&](const point &x, const point &y) { return x.idx < y.idx; }); For1(i, 1, n) { cout << a[i].p1 << ' '; } cout << '\n'; For1(i, 1, n) { cout << a[i].p2 << ' '; } cout << '\n'; } else { cout << "NO\n"; } } return 0; }

Gardener and the Array tutorial tutorial on bilibili 思路参考上面 bilibili 的视频链接。 如果 $x | y = x$，那么 $y$ 这个数字是可有可无的，如果能够在数组中找到任何一个这样的 $y$，那么就存在解：子序列 $a$ 是所有的元素，子序列 $b$ 是除了 $y$ 之外的所有元素。$y$ 的特征是它所有的位在其它元素中存在至少一次，也就是 $y$ 的二进制位在所有元素中出现了至少两次。如果 $y_1$ 有一个位是独一无二的，那么一定不满足 $x | y_1 = x$，所以只需要找到一个所有二进制位在所有元素中出现至少两次的元素。 // Date: Sun Dec 10 14:25:09 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 100010; int t, n; int main(void) { #ifdef _DEBUG freopen("1775b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; vector<VI> a(n); map<int, int> m; For(i, 0, n) { int len; cin >> len; For1(j, 1, len) { int x; cin >> x; m[x]++; a[i].pb(x); } } bool flag = false; For(i, 0, n) { bool mark = true; for (auto x : a[i]) { if (m[x] < 2) { mark = false; break; } } if (mark) { flag = true; break; } } cout << (flag ? "YES\n" : "NO\n"); } return 0; }

Parity Shuffle Sorting tutorial 题目要求单调不减，同时也不要求操作次数最少。一次操作可以改变一个数字，最少操作 $n$ 次可以对所有的数字都修改一次。如果所有数字相等也可以满足条件，所以利用这一点，先把 $a_1$ 和 $a_n$ 操作成相等的元素，然后对中间的每个数字 $a_i$，根据 $a_i + a_1$ 的奇偶性来让 $a_i$ 和 $a_1$ 或者 $a_n$ 配对，这样最后所有的元素都相等。 // Date: Sat Nov 25 20:41:10 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 100010; int t, n, a[N]; int main(void) { #ifdef _DEBUG freopen("1733c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i]; } if (n == 1) { cout << "0\n"; continue; } vector<PII> res; res.pb({1, n}); if ((a[1] + a[n]) & 1) a[n] = a[1]; else a[1] = a[n]; For1(i, 2, n - 1) { int tmp = a[1] + a[i]; if (tmp & 1) res.pb({1, i}); else res.pb({i, n}); } int m = SZ(res); cout << m << '\n'; if (m) { For(i, 0, m) { cout << res[i].f1 << ' ' << res[i].f2 << '\n'; } } } return 0; }

Permutation Operations tutorial 很有意思的一道题目。考虑数组 $b_i = a_{i + 1} - a_i$ ，题目要求最终的数组 $a$ 是单调不减的，因此只需要保证变换之后的数组 $b$ 是非负的。由于数组 $a$ 全部都是正数，所以 $b_i > -a_i$，要使得 $b_i \ge 0$，只需要 $b_i + a_i \ge 0$，又由于数列是一个 $[1, n]$ 的排列，所以对于每个 $b_i$ 都可以找到唯一的 $a_i$，只需要从 $i + 1$ 开始都增加 $a_i$ 即可。对于第 $n$ 个数字，指定全部数字递增即可。 // Date: Tue Nov 21 20:22:57 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define LN ListNode #define LNP ListNode * #define TN TreeNode #define TNP TreeNode * #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif #ifdef _DEBUG struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int val) : val(val), next(nullptr) {} ListNode(int val, ListNode *next) : val(val), next(next) {} }; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; #endif const int N = 100010; int t, n, a[N], pos[N]; int main(void) { #ifdef _DEBUG freopen("1746c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i]; pos[a[i]] = i; } For1(i, 1, n) { int p = pos[i]; if (p == n) { cout << 1 << ' '; } else { cout << p + 1 << ' '; } } cout << '\n'; } return 0; }