Math | Xueyang Liu

CodeForces 1459B Move and Turn

Move and Turn tutorial 当 $n$ 为偶数时，水平方向走的步数是 $k = \frac{n}{2}$，水平方向的位置有 $k + 1$ 种：左走 $0$ 步，右走 $k$ 步左走 $1$ 步，右走 $k - 1$ 步 … 左走 $k$ 步，右走 $0$ 步竖直方向同理。此时答案为 $k^2 = (\frac{n}{2})^2$。当 $n = 2k + 1$ 为奇数时，分两种情况：水平方向 $k$ 步，竖直方向 $k + 1$ 步。水平方向 $k + 1$ 步，竖直方向 $k$ 步。先考虑第 1 种情况，最终在水平方向的位置可能为：$k, k - 2, k - 4, \ldots$，可以发现和 $k$ 的奇偶性相同，所以两种情况是不重合的。第 1 种情况的答案是 $(k + 1)(k + 2)$，所以两种情况总共 $2(k + 1)(k + 2)$。 ...

CodeForces 1594E1 Rubik's Cube Coloring (easy version)

Rubik’s Cube Coloring (easy version) 根节点有 6 种选择，其他节点都有 4 种选择，其他节点的个数是 $2^p - 1 - 1$，所以结果是 $6 \cdot (2^p - 2)$，快速幂。 // Date: Fri Dec 15 23:02:49 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 ll qmi(ll a, ll n, ll m) { if (a == 0 || m == 1) return 0; ll res = 1; while (n) { if (n & 1) res = res * a % m; a = a * a % m; n >>= 1; } return res; } int main(void) { #ifdef _DEBUG freopen("1594e1.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int k; while (cin >> k) { ll n = (1LL << k) - 2; cout << qmi(4, n, MOD) * 6 % MOD << '\n'; } return 0; }

CodeForces 1560D Make a Power of Two

Make a Power of Two tutorial 由于只能往原数字的后面追加数字，也就是原来的数字中，每一位的顺序不会发生改变，所以想到用 2 的幂次去匹配给定的 $n$，也就是求 $n$ 和 $2^k$ 的最长公共子序列。接下来需要考虑 $2^k$ 的最大值，设数字 $n$ 的长度是 $d$，那么答案的上界是 $d + 1$，因为我们总可以把 $n$ 中的数字全部删除，然后追加一个数字 $1$。设 $n$ 变成 $2^k$ 的操作数是 $ans(n, 2^k)$，那么有 $ans(n, 2^k) \le d$，最坏情况下，要匹配 $2^k$ 需要在 $n$ 后面追加 $d$ 位，也就是 $2^k$ 的最大位数是 $2d$，由于 $n < 10^{9}$，$d = 9$，所以 $2^k$ 的最大位数是 18。 // Date: Fri Dec 15 21:20: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; string s; string a[70]; int solve(string &s, string &t) { int len1 = SZ(s), len2 = SZ(t); int j = 0, i = 0; for (; i < len2; ++i) { while (j < len1 && t[i] != s[j]) ++j; if (j == len1) break; ++j; } --i; int match_cnt = i + 1; return len1 - match_cnt + (len2 - match_cnt); } int main(void) { #ifdef _DEBUG freopen("1560d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; For(i, 0, 63) { ll x = (1LL << i); a[i] = to_string(x); } while (t--) { cin >> s; int res = INF; For(i, 0, 63) { int tmp = solve(s, a[i]); res = min(res, tmp); } cout << res << '\n'; } return 0; }

CodeForces 1521B Nastia and a Good Array

Nastia and a Good Array tutorial 观察到 $\gcd(i, i + 1) = 1$，可以利用这一点来构造，先找到数组最小的值 $a_{pos}$，对于第 $i$ 个位置 $a_i = a_{pos} + abs(pos - i)$，这样可以保证任意两个相邻的位置的 $gcd(a_j, a_{j + 1}) = 1$，由于 $a_{pos}$ 是最小的，每次操作可以让 $a_{pos}$ 的位置保持不变。 // Date: Fri Dec 15 10:43:00 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 = 500010; int t, n, a[N]; struct point { int i, j, x, y; }; int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } int main(void) { #ifdef _DEBUG freopen("1521b.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]; } vector<point> res; PII mi{INF, -1}; For1(i, 1, n) { if (a[i] < mi.f1) { mi = {a[i], i}; } } bool flag = true; For1(i, 1, n - 1) { if (gcd(a[i], a[i + 1]) > 1) { flag = false; break; } } if (flag) { cout << "0\n"; continue; } For1(i, 1, n) { if (i == mi.f2) continue; res.pb({i, mi.f2, mi.f1 + abs(i - mi.f2), mi.f1}); } int len = SZ(res); cout << len << '\n'; if (len) { for (auto e : res) { cout << e.i << ' ' << e.j << ' ' << e.x << ' ' << e.y << '\n'; } } } return 0; }

CodeForces 1603A Di-visible Confusion

Di-visible Confusion tutorial 基本是把 tutorial 翻译了一下。从前往后消除，对于 $a_i$ 如果能找到 $[2, i + 1]$ 中的某个数字 $k \bmod a_i \ne 0$，那么这个数字就可以被消除。用数学归纳法证明，假设所有的 $a_i$ 都满足上述条件并且前 $n - 1$ 个数字都能被消除，假设 $a_n$ 被消除是所在的位置是 $k’$，当前 $n - 1$ 个数字消除到剩下 $k - 1$ 个数字的时候，此时 $a_n$ 是第 $k$ 个，此时它可以被消除，所以前 $n$ 个数字都能被消除。因此所有数字都能被消除。假设 $a_i$ 能被 $[2, i + 1]$ 中的任何一个数字整除，那么 $a_i \ge lcm(2, 3, \ldots, i + 1)$，又由于 $lcm(2, 3, \ldots, 23) > 10^9 > a_i$，假设当 $i \ge 22$ 的时候，$[2, i + 1]$ 中所有的数字都能整除 $a_i$，这说明 $a_i > 10^9$，这和 $a_i$ 的题目中的范围矛盾，所以当 $i \ge 22$ 的时候 $[2, i + 1]$ 中必定存在某个 $k$ 使得 $k \bmod a_i \ne 0$。 ...

CodeForces 1601A Array Elimination

Array Elimination 按位考虑，先只考虑一位，假设所有数字的第 $i$ 个二进制位为 $1$ 的个数是 $m$，如果想要把这 $m$ 个数字的这一位全部清零，所选择的 $k$ 一定满足 $k \vert m$，其它位同理。假设每个二进制位上为 $1$ 的个数是 $m_1, m_2, m_3, \ldots$，那么最终可选的 $k$ 满足 $k \vert \gcd(m_1, m_2, m_3, \ldots)$。得到 $k$ 之后，$k$ 的所有的因子也满足题意。另外一个特殊情况数组全部为零，此时 $k$ 取 $[1, n]$。 // Date: Wed Dec 13 22:45:15 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[35]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main(void) { #ifdef _DEBUG freopen("1601a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; memset(b, 0, sizeof b); For1(i, 1, n) { cin >> a[i]; For(j, 0, 31) { if ((1 << j) & a[i]) b[j]++; } } int sum = 0; For(j, 0, 31) { sum += b[j]; } if (!sum) { For1(i, 1, n) { cout << i << ' '; } cout << '\n'; continue; } int g = -1; For(j, 0, 31) { if (!b[j]) continue; if (g == -1) { g = b[j]; continue; } g = gcd(g, b[j]); } if (g == 1) { cout << "1\n"; } else { VI res; for (int i = 1; i * i <= g; ++i) { if (g % i == 0) { int j = g / i; if (j != i) { res.pb(i); res.pb(j); } else { res.pb(i); } } } sort(all(res)); for (auto x : res) { cout << x << ' '; } cout << '\n'; } } return 0; }

CodeForces 1617C Paprika and Permutation

Paprika and Permutation tutorial 对于恰好就在 $[1, n]$ 范围内的数字，可以不用操作。因为一次的模数 $x$ 是任意取的，考虑 $a_i \bmod x$ 的取值范围，当 $a_i < x$ 的时候，$a_i \bmod x = a_i$；当 $a_i > x$ 时，$a_i \bmod x \le \lfloor \frac{a_i - 1}{2} \rfloor$，同时也能发现此时 $a_i \bmod x$ 的值域恰好是 $[1, \lfloor \frac{a_i - 1}{2} \rfloor]$ 中的所有整数。所以把剩余的 $a_i$ 从小到大排序之后，计算出值域，检查它们能不能生成 $[1, n]$ 中剩余的值即可。 // Date: Wed Dec 13 22:08:34 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], c[N]; bool vis[N]; int main(void) { #ifdef _DEBUG freopen("1617c.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]; } int len = 0; memset(vis, false, sizeof vis); For1(i, 1, n) { if (a[i] >= 1 && a[i] <= n && !vis[a[i]]) { vis[a[i]] = true; } else { b[++len] = a[i]; } } int len1 = 0; For1(i, 1, n) { if (!vis[i]) { c[++len1] = i; } } sort(b + 1, b + 1 + len); bool flag = true; For1(i, 1, len) { int top = (b[i] - 1) / 2; if (top < c[i]) { flag = false; break; } } if (flag) cout << len << '\n'; else cout << "-1\n"; } return 0; }

CodeForces 1607D Blue-Red Permutation

Blue-Red Permutation tutorial 设蓝色的 $x’$ 最终转换成 $x$，红色的 $y’$ 最终转换成 $y$，并且 $x > y$，那么有 $y’ <= y < x <= x’$，也就是说 $x$ 可以由 $y’$ 转换过来，$y$ 可以由 $x’$ 转换过来。也就是说我们总可以让红色转换到的数字大于蓝色转换到的数字，而不改变结果。把蓝色和红色分别排序，蓝色转换成 $[1, n]$ 的前半段，红色转换成后半段。 // Date: Wed Dec 13 21:40:02 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], c[N]; string s; int main(void) { #ifdef _DEBUG freopen("1607d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For(i, 0, n) { cin >> c[i]; } cin >> s; int len1 = 0, len2 = 0; For(i, 0, n) { if (s[i] == 'B') b[++len1] = c[i]; else a[++len2] = c[i]; } sort(b + 1, b + 1 + len1); sort(a + 1, a + 1 + len2); bool flag = true; For1(i, 1, len1) { if (b[i] < i) { flag = false; break; } } if (!flag) { cout << "NO\n"; continue; } For1(i, 1, len2) { if (i + len1 < a[i]) { flag = false; break; } } cout << (flag ? "YES" : "NO") << '\n'; } return 0; }

CodeForces 1612C Chat Ban

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; }

CodeForces 1746C Permutation Operations

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; }

CodeForces 1737B Elas Fitness and the Luxury Number

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; }

CodeForces 1778B The Forbidden Permutation

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; }

CodeForces 1788C Matching Numbers

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; }

CodeForces 1794C Scoring Subsequences

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; }

CodeForces 1815A Ian and Array Sorting

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; }