Posts

Make It Permutation 两种操作都和顺序无关，要生成一个 $[1, n]$ 的排列，先把原数组排序，对于每个点有三种策略：1. 从这个点开始后面的元素都删除。2. 当前元素比需要的下标 $idx$ 小，此时删除这个元素。3. 当前元素比需要的下标 $idx$ 大，补足中间缺少的数字。注意整型溢出。 // Date: Sun Nov 26 16:48:05 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, c, d, a[N]; int main(void) { #ifdef _DEBUG freopen("1810c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> c >> d; For1(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n); ll res = ll(n) * c + d, cur = 0; int idx = 1; For1(i, 1, n) { if (a[i] == idx) { idx++; } else { ll cur1 = cur + ll(n - i + 1) * c; if (i > 1) { res = min(res, cur1); } else { res = min(res, cur1 + d); } if (a[i] > idx) { cur += ll(a[i] - idx) * d; idx = a[i] + 1; } else { cur += c; } } } res = min(res, cur); cout << res << '\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; }

Number of Pairs 题目和元素顺序无关，先排序，然后对每个元素二分找符合条件的左端点和右端点，注意边界，二分之前如果左右端点是空集，直接返回 $-1$。 // Date: Sat Nov 25 19:10:08 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, l, r, a[N]; int find_left(int left, int right, int x) { if (left > right) return -1; int l = left, r = right, mid; while (l < r) { mid = (l + r) / 2; if (a[mid] >= x) r = mid; else l = mid + 1; } if (a[r] >= x) return r; return -1; } int find_right(int left, int right, int x) { if (left > right) return -1; int l = left, r = right, mid; while (l < r) { mid = (l + r + 1) / 2; if (a[mid] <= x) l = mid; else r = mid - 1; } if (a[l] <= x) return l; return -1; } int main(void) { #ifdef _DEBUG freopen("1538c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> l >> r; For1(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n); ll res = 0; For1(i, 1, n) { int left = find_left(i + 1, n, l - a[i]), right = find_right(i + 1, n, r - a[i]); if (left != -1 && right != -1) { res += right - left + 1; } } cout << res << '\n'; } return 0; }

And It’s Non-Zero tutorial 只需要找到一个二进制位满足所有数字对应的二进制位都为 1 即可，如果没有，那么找到二进制为 1 的数字个数最大的那个位，然后把这位上为 0 的数字删除。接下来只需要求对于一个二进制位有多少个数字满足这个位为 1，题目给定的是左右端点，所以可以前缀和优化。 // Date: Sat Nov 25 10:27: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, M = 32; int t, l, r, b[N][M]; int main(void) { #ifdef _DEBUG freopen("1615b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); For1(i, 1, 31) { For1(j, 1, int(2e5)) { if (j & (1 << (i - 1))) b[j][i] = b[j - 1][i] + 1; else b[j][i] = b[j - 1][i]; } } cin >> t; while (t--) { cin >> l >> r; int res = 0, n = r - l + 1; For1(i, 1, 31) { int tmp = b[r][i] - b[l - 1][i]; res = max(res, tmp); } cout << n - res << '\n'; } return 0; }

Chat Ban 等差数列求和，找到中点 $k$，前半部分求和之后，分三种情况，前半部分和后半部分再利用等差数列求和来二分答案。 // Date: Fri Nov 24 21:14:51 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; int main(void) { #ifdef _DEBUG freopen("1612c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; ll k, x; while (t--) { cin >> k >> x; ll res = 0, top = (1 + k) * k / 2, l, r, mid, sum; if (x == top) { res = k; } else if (x < top) { l = 1, r = k; while (l < r) { mid = (l + r) / 2; sum = mid * (1 + mid) / 2; if (sum >= x) r = mid; else l = mid + 1; } res = r; } else { res = k; x -= top; l = 1, r = k - 1; while (l < r) { mid = (l + r) / 2; sum = k * mid - (mid + 1) * mid / 2; if (sum >= x) r = mid; else l = mid + 1; } sum = k * r - (r + 1) * r / 2; if (sum < x) { res = 2 * k - 1; } else { res += r; } } cout << res << '\n'; } return 0; }

3SUM 把所有元素对 10 取余，只考虑个位即可。因为个位的范围是 10，只需要找三个数字，所以每个数字最多出现三次就够用了。因此需要考虑的数组大小最多只有 30，暴力三层循环即可。 // Date: Fri Nov 24 20:09: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 = 200010; int t, n, a[N]; int main(void) { #ifdef _DEBUG freopen("1692f.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; map<int, int> m; For1(i, 1, n) { cin >> a[i]; m[a[i] % 10]++; } VI b; For(i, 0, 10) { int cnt = m[i]; if (cnt) { cnt = min(cnt, 3); while (cnt--) { b.pb(i); } } } int len = SZ(b); bool mark = false; For(i, 0, len) { For(j, i + 1, len) { For(k, j + 1, len) { int sum = (b[i] + b[j] + b[k]) % 10; if (sum == 3) { mark = true; break; } } if (mark) break; } if (mark) break; } cout << (mark ? "YES\n" : "NO\n"); } return 0; }

Make it Increasing tutorial 若 $b_1 > 0$ 或者 $b_n < 0$ 那么肯定不是最优解，因为此时把 $b_1$ 或者 $b_n$ 设置成 0 不会使得结果更差，同时也能够保持数组递增。如果 $b_i - a_i > b_{i - 1}$，此时也不是最优解，此时把 $b_i$ 变成 $b_i - a_i$ 不会使得结果更差，也能够保持数组递增。猜测最终的数组 $b$ 中必有一个元素是 $0$（如何证明？），然后枚举为 $0$ 的位置即可。 根据上面的分析，最终的数组满足 $b_1 \le 0, b_n \ge 0$，由于数组 $b$ 是严格递增的，所以其中必定有一个元素是 $0$。 // Date: Fri Nov 24 19:17:58 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 = 5010; int t, n, a[N]; int main(void) { #ifdef _DEBUG freopen("1667a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while (cin >> n) { For1(i, 1, n) { cin >> a[i]; } if (n == 1) { cout << "0\n"; continue; } ll res = -1; For1(i, 1, n) { ll sum = 0, pre = 0; Rof1(j, 1, i - 1) { if (pre == 0) { pre = a[j]; sum++; } else { sum += pre / a[j]; if (pre % a[j] == 0) { pre += a[j]; sum++; } else { pre = pre - (pre % a[j]) + a[j]; sum++; } } } pre = 0; For1(j, i + 1, n) { if (pre == 0) { pre = a[j]; sum++; } else { sum += pre / a[j]; if (pre % a[j] == 0) { pre += a[j]; sum++; } else { pre = pre - (pre % a[j]) + a[j]; sum++; } } } if (res == -1) res = sum; else res = min(res, sum); } cout << res << '\n'; } return 0; }

Maximal AND 按位考虑，只有31位，要使得最后的结果某一位是1，需要所有 $a_i$ 的对应的位为1，统计出每个数字的第 $j$ 个二进制位为1的个数，从高位到低位依次考虑即可。 // Date: Thu Nov 23 21:01:56 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 = 200010, M = 40; int t, n, k, a[N], b[M], b1[M]; int main(void) { #ifdef _DEBUG freopen("1669h.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k; memset(b1, 0, sizeof b1); memset(b, 0, sizeof b); For1(i, 1, n) { cin >> a[i]; int x = a[i], idx = 1; while (x) { if (x & 1) b1[idx]++; idx++; x >>= 1; } } For1(i, 1, 31) { b[i] = n - b1[i]; } Rof1(i, 1, 31) { if (k >= b[i]) { k -= b[i]; b[i] = 0; } } ll res = 0; Rof1(i, 1, 31) { res = res * 2 + (b[i] == 0); } cout << res << '\n'; } return 0; }

Twist the Permutation 容易发现解总存在，只需要倒过来构造即可。原题右移数组，所以需要从后往前构造的时候左移数组。数组长度只有 $1000$，暴力即可。 // Date: Wed Nov 22 20:46:50 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 = 2010; int a[N], t, n, b[N]; void my_rot(int l, int r, int pre) { int i = l, j = pre; while (i < j) { swap(a[i], a[j]); ++i, --j; } i = pre + 1, j = r; while (i < j) { swap(a[i], a[j]); ++i, --j; } i = l, j = r; while (i < j) { swap(a[i], a[j]); ++i, --j; } } int main(void) { #ifdef _DEBUG freopen("1650d.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); Rof1(i, 1, n) { if (i == a[i]) continue; int ans = -1; For1(j, 1, i - 1) { if (a[j] == i) { ans = j; break; } } b[i] = ans; my_rot(1, i, ans); } For1(i, 1, n) { cout << b[i] << ' '; } cout << '\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; }

Elas Fitness and the Luxury Number tutorial 观察区间 $[a^2, (a+1)^2)$ 中有多少个数字满足条件，满足条件的数字一定有因数 $a$，满足形式：$a, a(a+1), a(a+2), \ldots$，又注意到 $(a+1)^2 - 1 = a(a+2)$，因此每个区间只有三个数字满足条件。剩下的就是区间处理了，先计算出完整的区间个数，然后考虑两端的不完整区间中满足条件的数字。数字范围是 $10^{18}$，求平方根使用二分，二分求中点可能会溢出，把右边界设置成最大可能的平方根即可。 // Date: Tue Nov 21 19:23:45 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 ull a, b; int t; bool check(ull x) { return x >= a && x <= b; } ull sqrt1(ull x) { if (x == 1) return 1; ull l = 1, r = 1e9 + 10, m; while (l < r) { m = (l + r + 1) / 2; if (m * m <= x) l = m; else r = m - 1; } return l; } int main(void) { #ifdef _DEBUG freopen("1737b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; while (t--) { cin >> a >> b; ull a1 = sqrt1(a), b1 = sqrt1(b), ans = 0; if (a1 == b1) { ans = 0; For(i, 0, 3) { if (check(a1 * (a1 + i))) ans++; } cout << ans << '\n'; continue; } ans = (b1 - a1 - 1) * 3; For(i, 0, 3) { if (check(a1 * (a1 + i))) ans++; if (check(b1 * (b1 + i))) ans++; } cout << ans << '\n'; } return 0; }

The Forbidden Permutation tutorial 这道题目是一道阅读理解题目，题意略繁琐。因为只能交换相邻的数字，所以问题简化了很多。先判定整个数列是不是 good。然后依次求出每个 $a_i, a_{i+1}$ 变动之后使得 $a_i > a_{i+1}$ 或者 $a_i + d < a_{i+1}$ 的代价，这都可以常数时间内计算出来，第二种情况需要判断可行性，移动 $a_i$ 或者 $a_{i+1}$ 是等价的，求出上界即可，并且这种情况也不需要考虑交叉的情况，$a_i$ 只能往左移动，$a_{i+1}$ 只能往右移动。 // 2023/11/21 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <climits> #include <iostream> #include <iomanip> #include <sstream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <algorithm> #include <utility> #include <functional> 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], p[N], m, d, pos[N]; int main(int argc, const char * argv[]) { #ifdef USE_INPUT_FILE freopen("input.txt", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m >> d; For1(i, 1, n) { cin >> p[i]; pos[p[i]] = i; } For1(i, 1, m) { cin >> a[i]; } bool flag = true; For1(i, 1, m - 1) { int x = pos[a[i]], y = pos[a[i + 1]]; if (x > y || x + d < y) { flag = false; break; } } if (!flag) { cout << 0 << '\n'; continue; } int res = INF; For1(i, 1, m - 1) { int x = pos[a[i]], y = pos[a[i + 1]]; int tmp1 = y - x, tmp2 = abs(x + d + 1 - y); res = min(res, tmp1); int top = x - 1 + n - y; if (top >= tmp2) { res = min(res, tmp2); } } cout << res << '\n'; } return 0; }

Matching Numbers tutorial 等差数列求和可以推导出 $s$ 数列的所有的值，其中 $s_1 = 3(n + 1)/2$，因此 $n$ 只能是奇数。构造解的思路在上面题解的评论区，先构造出和相等的数对，前 $n$ 个数字正序排列，后 $n$ 个数字倒序排列。设 $s$ 数组正中间的值是 $d$，那么只需要交换一些数字构造出 $d+0, d+1, d-1, d+2, d-2, \dots$，奇数增量嵌套构造即可，偶数同理。 // 2023/11/19 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <climits> #include <iostream> #include <iomanip> #include <sstream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <algorithm> #include <utility> #include <functional> 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 = 200010; int t, n; PII a[N]; int main(int argc, const char * argv[]) { #ifdef USE_INPUT_FILE freopen("input.txt", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; if (n % 2 == 0) { cout << "NO\n"; continue; } if (n == 1) { cout << "YES\n1 2\n"; continue; } For1(i, 1, n) { a[i].f1 = 2 * n + 1 - i; a[i].f2 = i; } int top = (n - 1) / 2; int l = 1, r = 1 + top; while (l < r) { swap(a[l].f2, a[r].f2); l++; r--; } l = top + 2, r = n; while (l < r) { swap(a[l].f2, a[r].f2); l++; r--; } cout << "YES\n"; For1(i, 1, n) { cout << a[i].f1 << ' ' << a[i].f2 << '\n'; } } return 0; }

Scoring Subsequences 题目中要找子序列，其实因为给定的数组是单调不减的，因此只需要找数组的后缀即可。计算 $score$ 的时候，下标从后往前计，此时下标往左递增，$a_i$ 往左单调不增，因此 ${a_i}/{i}$ 单调递减，可以二分找到最左边的满足 $a_i \ge i$ 的位置，这就是所求的最长的长度。 // 2023/11/19 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <climits> #include <iostream> #include <iomanip> #include <sstream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <algorithm> #include <utility> #include <functional> 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 n, t, a[N]; int main(int argc, const char * argv[]) { #ifdef USE_INPUT_FILE freopen("input.txt", "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]; } For1(i, 1, n) { if (i == 1) { cout << 1 << ' '; continue; } int l = 1, r = i, mid; while (l < r) { mid = (l + r) / 2; int idx = (1 + i) - mid; if (a[mid] >= idx) { r = mid; } else { l = mid + 1; } } cout << i - r + 1 << ' '; } cout << '\n'; } return 0; }

Ian and Array Sorting tutorial 考虑 $b_i = a_{i + 1} - a_i$，保证 $b_i$ 全部非负就可以满足题意。观察 $b_i$ 的变化规律，奇数位置的 $b_i$ 传递给其它奇数位置的 $b_j$，偶数位置也只能传递给偶数位置。同时，$b_2$ 与 $b_{n-2}$ 可以任意大。所以偶数位置经过分散 $b_2$ 之后可以全部非负。只需要考虑 $n-2$ 的奇偶性，如果 $n-2$ 是偶数，那么剩下的奇数位置的和不会有任何增量，如果奇数位置原来的和为非负，那么可以保证重分布之后所有的元素都为非负。 // 2023/11/19 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <climits> #include <iostream> #include <iomanip> #include <sstream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <algorithm> #include <utility> #include <functional> 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 = 300010; int n, t; ll a[N], b[N]; int main(int argc, const char * argv[]) { #ifdef USE_INPUT_FILE freopen("input.txt", "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 == 2) { if (a[1] <= a[2]) cout << "YES"; else cout << "NO"; cout << '\n'; continue; } For1(i, 1, n - 1) { b[i] = a[i + 1] - a[i]; } if (n % 2 == 0) { ll sum = 0; for (int i = 1; i < n; i += 2) { sum += b[i]; } if (sum >= 0) { cout << "YES"; } else { cout << "NO"; } cout << "\n"; continue; } else { cout << "YES\n"; } } return 0; }