Posts

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

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

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

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

Trouble Sort tutorial 只有不同类型的数字才可以交换，考虑两个 $1$ 类型的数字 $x$ 和 $y$，一个 $0$ 类型的数字 $z$，假设它们的顺序是 $x, y, z$，进行如下交换 $(x, z), (y, z), (x, z)$ 之后顺序变成 $y, x, z$，此时交换了 $x, y$ 的位置，并且 $z$ 的位置保持不变。也就是说只要有一个不同类型的数字，同类型的数字之间就可以任意进行交换。因此如果 $0$ 和 $1$ 类型的数字都存在，那么 $0$ 类型的数字之间可以互相交换位置，$1$ 类型的数字之间可以互相交换位置，$0$ 和 $1$ 之间也能互相交换位置，所以任意两个数字都可以互相交换位置，此时有解。如果只有一个类型的数字，那它们都不能交换。 // Date: Tue Dec 12 23:40:46 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 = 510; int t, n, a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1365b.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 cnt0 = 0, cnt1 = 0; For1(i, 1, n) { cin >> b[i]; if (b[i]) cnt1++; else cnt0++; } bool flag = true; if (cnt1 > 0 && cnt0 > 0) flag = true; else { For1(i, 2, n) { if (a[i] < a[i - 1]) { flag = false; break; } } } cout << (flag ? "Yes" : "No") << '\n'; } return 0; }

Social Distance 从左往右扫描维护上一次遇到 $1$ 的位置，如果当前位置 $i$ 是 $0$，并且距离上一次 $1$ 的位置 $pre$ 的距离大于 $k$ 那么这个点可能是可行的，如果后面的 $1$ 和 $i$ 的距离不大于 $k$，再把 $k$ 点变成不可行的，这样找到的可行的点都是尽量靠左的。 // Date: Tue Dec 12 23:08: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, k; string s; bool vis[N]; int main(void) { #ifdef _DEBUG freopen("1367c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k >> s; memset(vis, false, sizeof vis); int pre = -1; For(i, 0, n) { if (s[i] == '1') { if (pre != -1 && i - pre <= k) { vis[pre] = false; } pre = i; } else { if (pre == -1 || i - pre > k) { vis[i] = true; pre = i; } } } int res{}; For(i, 0, n) { if (vis[i]) res++; } cout << res << '\n'; } return 0; }

Prefix Flip (Easy Version) tutorial 最多可以进行 $3n$ 次操作，可以考虑对每个不同的位独立进行操作，如何操作才能只操作一位而又不影响其它位呢？设想要只翻转第 $i$ 位，可以这样操作：先翻转 $[1, i]$，然后翻转 $[1, 1]$，最后翻转 $[1, i]$。这样操作三次，恰好只改变了第 $i$ 位。 // Date: Tue Dec 12 22:47: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 t, n; string a, b; int main(void) { #ifdef _DEBUG freopen("1381a1.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> a >> b; VI res; For(i, 0, n) { if (a[i] != b[i]) { res.pb(i + 1); res.pb(1); res.pb(i + 1); } } int len = SZ(res); if (!len) { cout << len << '\n'; } else { cout << len << ' '; for (auto x : res) { cout << x << ' '; } cout << '\n'; } } return 0; }

Madoka and Childish Pranks 因为操作次数最多有 $nm$ 次，所以可以考虑对每个点操作一次，$0$ 的点不需要操作，剩下的只有 $1$ 的点，为了尽量缩小一次操作影响的范围，可以只考虑比较小的棋盘，大小分别为横向的 $1 \times 2$ 和纵向的 $2 \times 1$。为了不覆盖之前的结果，可以考虑从右下角开始构造，先考虑最后一行，从右往左扫描，遇到 $1$ 就构造一个 $1 \times 2$ 的矩形，这个棋盘就是 $[0, 1]$，遇到 $0$ 就跳过。当遇到第一列的 $1$，需要构造 $2 \times 1$ 的矩形：${0\brack 1}$，只有一种情况可以判定无解：当在第一行并且纵向的矩形无法构造。 // Date: Tue Dec 12 21:38: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 = 110; int t, n, m; char a[N][N], b[N][N]; struct point { PII p1, p2; point(int x1, int y1, int x2, int y2) : p1({x1, y1}), p2({x2, y2}) {} void print() { cout << p1.f1 + 1 << ' ' << p1.f2 + 1 << ' ' << p2.f1 + 1 << ' ' << p2.f2 + 1; } }; int main(void) { #ifdef _DEBUG freopen("1647c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; memset(b, 0, sizeof b); For(i, 0, n) { cin >> a[i]; } bool flag = true; vector<point> res; Rof(i, 0, n) { if (!flag) break; Rof(j, 0, m) { if (a[i][j] != '0') { if (!j) { if (!i) { flag = false; break; } b[i - 1][j] = '0'; res.pb(point(i - 1, j, i, j)); } else { b[i][j - 1] = '0'; res.pb(point(i, j - 1, i, j)); } } b[i][j] = a[i][j]; } } if (!flag) { cout << "-1\n"; continue; } int len = SZ(res); cout << len << '\n'; if (len) { For(i, 0, len) { res[i].print(); cout << '\n'; } } } return 0; }

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

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

Knapsack How to get started with solving Ad-Hoc tasks on codeforces 一道挺有意思的题目，思路推荐上面的博客。 要在数组中找到一些数字，使得它们的和在范围 $[\frac{w}{2}, w]$ 内。首先把 $a_i > w$ 的数字去掉；如果某个数字就在给定的范围内，那么它就是一个解。接下来只需要考虑所有 $a_i < \frac{w}{2}$ 的数字，可以先排序，从小到大考虑累加，如果前缀和能到 $[\frac{w}{2}, w]$ 范围内，那么这个前缀就是一个解。 为什么这么做是对的呢？假设 $a_i + a_{i + 1} \lt \frac{w}{2}$，同时 $a_i + a_{i + 1} + a_{i + 2} > w$，可以得到 $a_{i + 2} > \frac{w}{2}$，这和 $a_{i+2} < \frac{w}{2}$ 矛盾。 // Date: Mon Dec 11 21:10:36 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; pair<ll, int> a[N], b[N]; ll w; int main(void) { #ifdef _DEBUG freopen("1446a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> w; For1(i, 1, n) { cin >> a[i].f1; a[i].f2 = i; } int len = 0; sort(a + 1, a + n + 1); ll top = (w + 1) / 2; VI res; For1(i, 1, n) { if (a[i].f1 > w) continue; if (a[i].f1 <= w && a[i].f1 >= top) { res.pb(a[i].f2); break; } b[++len] = a[i]; } if (nonempty(res)) { cout << SZ(res) << '\n'; for (auto x : res) { cout << x << ' '; } cout << '\n'; continue; } bool flag = false; ll sum = 0, right = -1; For1(i, 1, len) { sum += b[i].f1; if (sum <= w && sum >= top) { flag = true; right = i; break; } } if (!flag) cout << "-1\n"; else { cout << right << '\n'; using PLI = pair<ll, int>; sort(b + 1, b + right + 1, [&](const PLI &x, const PLI &y) { return x.f2 < y.f2; }); For1(i, 1, right) { cout << b[i].f2 << ' '; } cout << '\n'; } } return 0; }

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

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

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