Posts

Subsequence Addition (Easy Version) tutorial 需要注意到因为 $c_i$ 中元素不超过 $5000$，所以从 $a_i$ 中挑出的子序列的元素的和也不超过 $5000$。因为数组 $c$ 中的元素顺序没有关系，所以可以排序之后从小到大判断 $c_i$ 是否可行。设 $d_s$ 为当前的 $c$ 数组的子序列能够得到的和为 $s$，那么 $d_s = d_s | d_{s - c_i}$，每新加入一个 $c_i$，就用它去更新之前可行的 $d_s$。 这道题目有另外一个解法。观察可以发现如果 $c_i$ 小于当前数组 $c$ 的前缀和 $p[i - 1]$，那么 $c_i$ 一定是可行的，也就是 $c_1, c_2, \ldots, c_{j - 1}$ 的某个子序列的和可以组成 $c_i$。下面用数学归纳法证明。 假设对于长度为 $l$ 的数组 $c$ 上述结论成立：设数组 $c$ 的元素和是 $sum$，那么 $c$ 的子序列的和可以组成 $[1, sum]$ 中的所有数字。设 $1 \le x \le sum$，下面证明在数组 $c$ 中加入 $x$ 之后，数组 $c$ 的子序列的和可以组成 $[1, sum + x]$ 中的所有数字。只需要证明 $[sum + 1, sum + x]$ 中的数字可以被 $c_1, c_2, \ldots, c_l, c_{l + 1}$ 组成即可。 ...

Saving the City tutorial 设 $d[i][1]$ 表示第 $i$ 个位置是激活状态时的最小花费，$d[i][0]$ 表示第 $i$ 个位置是非激活状态时的最小花费，并且规定当 $s[i] = 1$ 的时候，只有 $d[i][1]$ 合法。设计好状态，转移方程就比较好想了。 题解中的贪心做法挺好的。因为对于一段连续的房子，只需要激活其中任何一个即可，所以一段连续的可以看成是一个房子，对于由 $0$ 分隔的相邻的两段连续的 $1$：$[l_1, r_1]$ 和 $[l_2, r_2]$，有两种选择： 用 $2a$ 的代价分别激活 先用 $(l_2 - r_1)\cdot b$ 的代价把两段连接起来，再用 $a$ 的代价激活 比较两种方式，线性扫描即可。 // Date: Mon Dec 18 22:39:07 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()) template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } #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, d[N][2], a, b; string s; int main(void) { #ifdef _DEBUG freopen("1443b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> a >> b >> s; n = SZ(s); memset(d, 0x3f, sizeof d); int res = INF; if (s[0] == '0') { d[0][0] = 0; d[0][1] = a + b; } else { d[0][1] = a; } For(i, 1, n) { if (s[i] == '0') { if (s[i - 1] == '0') { d[i][0] = d[i - 1][0]; d[i][1] = d[i - 1][1] + b; } else { d[i][0] = d[i - 1][1]; d[i][1] = d[i - 1][1] + b; } } else { if (s[i - 1] == '0') { d[i][1] = min(d[i - 1][0] + a, d[i - 1][1]); } else { d[i][1] = d[i - 1][1]; } } } if (s[n - 1] == '1') res = d[n - 1][1]; else res = min(d[n - 1][0], d[n - 1][1]); cout << res << '\n'; } return 0; }

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)$。 ...

Canine poetry tutorial 观察长度为偶数的回文字符串，只需要把中间两个字符破坏掉就可以了。长度为奇数的回文串只需要把中间三个字符组成的回文破坏掉。所以只需要考虑长度为 2 和 3 的回文。对于当前字符 $a_i$，只需要检查 $a_{i - 1}, a_i$ 和 $a_{i - 2}, a_{i - 1}, a_i$ 是否是回文，如果是回文，在 $i$ 这个位置打一个标记。 // Date: Sun Dec 17 22:51:25 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()) template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } #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; int main(void) { #ifdef _DEBUG freopen("1466c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> s; int n = SZ(s), res{}; For(i, 1, n) { if (s[i] == s[i - 1] && s[i - 1] != '-') { s[i] = '-'; res++; } else if (i - 2 >= 0 && s[i] == s[i - 2] && s[i - 2] != '-') { s[i] = '-'; res++; } } cout << res << '\n'; } return 0; }

Strange Birthday Party tutorial 设最优答案中 $k_i$ 和 $k_j$ 收到的礼物价值为 $c_i$ 和 $c_j$，并且 $k_i > k_j, c_i > c_j$。此时把 $c_j$ 给 $k_i$，如果 $c_i > c_{k_j}$，此时 $k_j$ 收到 $c_{k_j}$ 美元，答案更优；如果 $c_i < c_{k_j}$，答案不变。因此把礼物价值小的给尽量大的 $k_i$ 是更优策略。所以按照 $k_i$ 从大到小排序依次送礼物，如果当前礼物下标 $j$ 大于 $c_{k_i}$，此时这个人应该收到 $c_{k_i}$ 的美元，因为此时 $c_{k_i} < c_j$。 // Date: Sun Dec 17 21:46:52 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 all1(a, n) a + 1, a + 1 + n #define SZ(a) int((a).size()) template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } #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 = 300010; int k[N], c[N], t, n, m; int main(void) { #ifdef _DEBUG freopen("1470a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; For1(i, 1, n) cin >> k[i]; sort(all1(k, n), greater<int>()); For1(i, 1, m) cin >> c[i]; ll res = 0; int j = 1; For1(i, 1, n) { if (j < k[i]) { res += c[j++]; if (j > m) j = m; } else { res += c[k[i]]; } } cout << res << '\n'; } return 0; }

Get an Even String 对于中间未成对的字母，当找到一个成对的之后，当前遇到的未成对的全部删除，开始找下一对，这样是最优的。 // Date: Sat Dec 16 22:14: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 = 200010; int t; string s; int main(void) { #ifdef _DEBUG freopen("1660c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> s; bool vis[26]{false}; int res = 0; int n = SZ(s); For(i, 0, n) { int idx = s[i] - 'a'; if (vis[idx]) { For(j, 0, 26) { if (j == idx) continue; else if (vis[j]) res++; } memset(vis, false, sizeof vis); } else { vis[idx] = true; } } For(j, 0, 26) { if (vis[j]) res++; } cout << res << '\n'; } return 0; }

Getting Zero tutorial 由于 $32768 = 2^{15}$，所以答案的上界是 15，猜想先对数字进行加，然后再乘，这样是最优的。假设某次乘操作之后，进行了两次加：$v \to 2v \to 2v + 1 \to 2v + 2$，此时可以替换成 $v \to v + 1 \to 2v + 2$，也就是乘操作之后，不能进行连续的两次加。乘操作之后再紧接着进行一次加操作不是最优的，因为我们得到的数字需要被 $2^{15}$ 整除，加操作破坏了整除性。因此只能先进行连续的加操作，然后是连续的乘操作。设加操作次数是 $i$，乘操作次数是 $j$，那么有 $(x + i) \times 2^{j} \bmod 2^{15} = 0$，$i, j \le 15$。 // Date: Sat Dec 16 20:56:23 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 = 400010, M = 32768; int bfs(int x) { int res = 15; For1(i, 0, 15) { For1(j, 0, 15) { ll tmp = (x + i) * (1 << j) % M; if (tmp == 0) { res = min(res, i + j); } } } return res; } int a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1661b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; while (cin >> n) { For1(i, 1, n) { cin >> a[i]; } For1(i, 1, n) { b[i] = bfs(a[i]); } For1(i, 1, n) { cout << b[i] << ' '; } cout << '\n'; } return 0; }

White-Black Balanced Subtrees 一次 DFS 之后统计出各个节点子树的黑色节点和白色节点的个数。 // Date: Sat Dec 16 10:34: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 = 4010, M = 10010; int h[N], w[N], b[N], t, n; int e[M], ne[M], idx; char color[N]; void Init() { idx = 0; memset(h, -1, sizeof h); memset(w, 0, sizeof w); memset(b, 0, sizeof b); } void Add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int x) { int w1 = 0, b1 = 0; for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; dfs(j); w1 += w[j]; b1 += b[j]; } if (color[x] == 'B') b1++; else w1++; w[x] = w1; b[x] = b1; } int main(void) { #ifdef _DEBUG freopen("1676g.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; Init(); For1(i, 2, n) { int j; cin >> j; Add(j, i); } memset(color, 0, sizeof color); string s; cin >> s; For(i, 0, SZ(s)) { color[i + 1] = s[i]; } dfs(1); int res{}; For1(i, 1, n) { if (w[i] == b[i]) res++; } cout << res << '\n'; } return 0; }

Yet Another Problem About Pairs Satisfying an Inequality 先找到所有 $a_i < i$ 的元素放到数组 $b$，数组根据 $a_i$ 排序，再对每个 $b_i$ 找到第一个大于 $i$ 的元素，可以使用 upper_bound。另外， lower_bound 可以找到第一个 $\ge$ 给定元素的位置。 // Date: Sat Dec 16 09:52:26 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]; vector<PII> b; int main(void) { #ifdef _DEBUG freopen("1703f.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; b.clear(); For(i, 0, n) { cin >> a[i]; if (a[i] < i + 1) { b.pb({a[i], i + 1}); } } ll res = 0; if (b.empty()) { cout << "0\n"; continue; } sort(all(b)); for (auto &[x, y] : b) { auto it = upper_bound(b.begin(), b.end(), PII{y, INF}); if (it != b.end()) { res += b.end() - it; } } cout << res << '\n'; } return 0; }

Hamiltonian Wall 可以发现从一个 B 开始，只能向右、上、下走，并且应该优先走上、下的情况，这样才不会出现重复走到 B 的情况。由于起点不确定，但是只有两个。两次 DFS 就可以了，搜索完之后检查是不是所有的 B 都访问到了。 // Date: Sat Dec 16 09:14:16 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] = { {1, 0}, {-1, 0}, {0, 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; bool vis[2][N]; char a[2][N]; bool check(int x, int y) { return x >= 0 && x < 2 && y >= 0 && y < n && a[x][y] == 'B' && !vis[x][y]; } void dfs(int x, int y) { vis[x][y] = true; int x1, y1; For(i, 0, 3) { x1 = x + dir[i][0]; y1 = y + dir[i][1]; if (check(x1, y1)) { dfs(x1, y1); return; } } } int main(void) { #ifdef _DEBUG freopen("1766c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> a[0] >> a[1]; memset(vis, false, sizeof vis); bool flag = true; dfs(0, 0); For(i, 0, 2) { For(j, 0, n) { if (a[i][j] == 'B' && !vis[i][j]) { flag = false; break; } } if (!flag) break; } if (flag) { cout << "YES\n"; continue; } memset(vis, false, sizeof vis); flag = true; dfs(1, 0); For(i, 0, 2) { For(j, 0, n) { if (a[i][j] == 'B' && !vis[i][j]) { flag = false; break; } } if (!flag) break; } cout << (flag ? "YES" : "NO") << '\n'; } return 0; }

Game with Reversing 可以观察到 Bob 操作的奇偶性，如果 Bob 操作奇数次，那么两个字符串使用逆序比较；如果 Bob 操作偶数次，那么两个字符串使用正序比较。Alice 和 Bob 轮流操作，Alice 先操作，只需要统计正序比较和逆序比较两个字符串不同字符的个数，确定 Alice 的操作次数，然后再根据奇偶性确定 Bob 操作次数。 // Date: Sat Dec 16 08:36: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 int tc, n; string s, t; int main(void) { #ifdef _DEBUG freopen("1834c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> tc; while (tc--) { cin >> n >> s >> t; int cnt = 0, cnt1 = 0; For(i, 0, n) { if (s[i] != t[i]) cnt++; } for (int i = 0, j = n - 1; i < n; i++, j--) { if (s[i] != t[j]) cnt1++; } int res = INF; if (cnt & 1) { if (cnt > 0) res = min(res, cnt - 1 + cnt); } else { res = min(res, cnt + cnt); } if (cnt1 & 1) { res = min(res, cnt1 + cnt1); } else { if (cnt1 > 0) res = min(res, cnt1 - 1 + cnt1); else res = min(res, 2); } cout << res << '\n'; } return 0; }

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

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

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

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$。 ...