Constructive Algorithms

Even-Odd XOR 很有意思的一道构造题。奇数位和偶数位的异或和相等，那么整个数组的异或和是 $0$。考虑简单的做法，如果 $a_1, a_2, \ldots, a_{n-1}$ 使用 $[1,n-1]$，那么 $a_n = 1 \oplus 2 \oplus \ldots \oplus (n-1)$，问题是 $a_n$ 可能会和 $[1,n-1]$ 中的某个数字相等。考虑异或运算的性质，令 $a_{n-2} = 2^{23}$，因为 $[1, n-3]$ 的异或和小于 $a_{n-2}$，这可以保证 $a_{n-2}$ 不和前面的数字重复。 同理令 $a_{n-1} = 2^{24}$，那么 $a_n$ 设置成前面所有数字的异或和。这样可以保证所有数字不同，并且所有数字的异或和是 $0$。 // Date: Tue Mar 5 21:55:44 2024 #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; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; 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}, }; 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 nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } 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; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #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; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif void solve() { int n, cur = 0; cin >> n; For1(i, 1, n - 3) { cout << i << ' '; cur = cur ^ i; } int x = (1 << 23), y = (1 << 24); cout << x << ' '; cur = cur ^ x; cout << y << ' '; cur = cur ^ y; cout << cur << '\n'; } int main(void) { #ifdef _DEBUG freopen("1722g.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Color the Picture 观察可以发现，最终答案中连续的相同颜色的列的数量一定大于等于 $2$。按照行染色同理。设颜色 $a_i$ 能够染色的列数是 $b_i = \lfloor \frac{a_i}{m} \rfloor$，需要构造 $b_1 + b_2 + \ldots + b_j = n, b_i \ge 2$。 考虑分解的思想，如果 $n$ 是偶数，设 $b_1 + b_2 + \ldots + b_k = sum$，如果有解，那么要求 $sum \ge n$。如果 $sum$ 是偶数，这意味着，奇数 $b_j$ 的个数为偶数个，如果 $sum > n$，那么把偶数 $b_j$ 拆分成 $2$，奇数 $b_j$ 拆分成若干个 $2$ 和一个 $1$，最后 $1$ 的个数是偶数个，先去掉偶数个 $1$，然后再考虑去掉 $2$，直到 $sum = n$。 用类似的方法可以解决 $n$ 和 $sum$ 的奇偶性的其它三种情况，最终得到答案。这种奇偶性转换和分解的构造思想很常见。 // 2024/1/30 #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; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; 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}, }; 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 nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } 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; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #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; #define dbg(x...) \ cerr << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 100100; ll n, m, a[N], k, b[N]; void solve() { cin >> n >> m >> k; For1(i, 1, k) { cin >> a[i]; } sort(a + 1, a + 1 + k); ll tot = n * m; if (a[k] >= tot) { cout << "Yes\n"; return; } auto check = [&](ll n, ll m) -> bool { ll cnt = 0; bool found = false; For1(i, 1, k) { b[i] = a[i] / n; if (b[i] >= 2) cnt += b[i]; if (b[i] >= 3) found = true; } if (cnt < m) return false; if (m % 2 == 0) return true; return found; }; if (check(n, m) || check(m, n)) { cout << "Yes\n"; } else cout << "No\n"; } int main(void) { #ifdef _DEBUG freopen("input.txt", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

LIS or Reverse LIS? 如果 $a_i$ 出现过 2 次以上，那么只有其中的 2 个对答案有贡献，设这样的是数字个数有 $cnt$，那么它们对答案的贡献是 $cnt$。如果 $a_i$ 出现过 1 次，那么它必定可以出现在两个序列中的其中一个，并且其中的一个数字可以同时出现在两个子序列当中，设出现 1 次的数字个数有 $cnt_1$，那么它们对答案的贡献是 $\lfloor \frac{cnt_1 + 1}{2} \rfloor$ // Date: Mon Jan 22 23:16:11 2024 #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; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; 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}, }; 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 nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } 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; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #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; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, a[N]; void solve() { cin >> n; map<int, int> m; For1(i, 1, n) { cin >> a[i]; m[a[i]]++; } int cnt{}; for (auto &[x, y] : m) { if (y >= 2) cnt += 2; else if (y == 1) cnt++; } int ans = (cnt + 1) / 2; cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1682c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Find The Array tutorial 神奇构造题。 考虑这两个 $b$ 数组 $a_1, 1, a_3, 1, a_5, 1, \ldots$ 和 $1, a_2, 1, a_4, 1, a_6, \ldots$，能够发现的这两个数组中必定有一个符合题意。设 $S_{even}, S_{odd}$ 分别为原数组 $a$ 的偶数位置和奇数位置的元素和，那么其中必有一个 $\le \frac{S}{2}$，利用这一点就可以证明前面两个 $b$ 数组必定有一个满足条件，根据奇偶性判断即可。 // Date: Tue Jan 9 20:32:30 2024 #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; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; 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}, }; 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 nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } 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; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #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; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 100; int a[N]; void solve() { int n; cin >> n; ll sum{}, evens{}; For1(i, 1, n) { cin >> a[i]; sum += a[i]; if (i % 2 == 0) evens += a[i]; } if (evens * 2 <= sum) { For1(i, 1, n) { if (i & 1) cout << a[i] << ' '; else cout << 1 << ' '; } } else { For1(i, 1, n) { if (i & 1) cout << 1 << ' '; else cout << a[i] << ' '; } } cout << '\n'; } int main(void) { #ifdef _DEBUG freopen("1463b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

烙饼 tutorial 设 $a_i$ 的和是 $sum$，每个机器的平均使用时间是 $avg = \lceil \frac{sum}{m} \rceil$，如果 $mx = max(a_i) > avg$，此时最优策略是让 $mx$ 一直在一台机器上，因为移动它不会让结果更好，此时的总时间就是 $mx$。如果 $mx \le avg$，此时总时间是 $avg$，从第一个机器开始考虑，因为 $a_i \le mx \le avg$，因此可以把 $a_i$ 放在第一个机器上，如果第一个机器还有剩余时间，把剩余的时间给 $a_{i + 1}$，然后对第二个机器，从时间 $0$ 开始，把 $a_{i + 1}$ 剩余的时间用完，此时可以保证 $a_{i + 1}$ 在两个机器上的时间是不会重合的，如果重合，这意味着 $a_{i + 1}$ 占用了前一个机器的后半段时间和后一个机器的前半段时间，并且这两段时间的和大于 $avg$，这和假设矛盾。因此每个 $a_i$ 最多产生两个记录。 接下来考虑为什么是取上整：$avg = \lceil \frac{sum}{m} \rceil$。如果 $sum \% m \ne 0$，此时意味着存在一个 $a_i$ 还有剩余时间 $r_i, 1 \le r_i \lt m$，设 $avg_1 = \lfloor \frac{sum}{m} \rfloor$。一种方案是在最后一个机器上一直等 $a_i$ 完成，此时总时间是 $avg_1 + r_i$。另一种方案是把 $r_i$ 均摊到 $m$ 个机器上，也就是每个机器多用 $1$ 单位的时间，实际时间是 $avg_1 + 1$，并且总的可用时间多了 $m$，能够保证 $(avg_1 + 1) \cdot m \gt sum$，也就是一定可以完成所有的 $a_i$。 ...

Mathematical Problem 用函数 $\_solve$ 把长度为 $1, 3, 5, 7$ 满足题目要求的数字打表打出来，能够发现频繁出现了 $1, 6, 9$ 和 $9, 6, 1$，只是中间添加了一些 $0$，原因是 $13^2$ 和 $31^2$ 计算的过程中没有进位，因此 $103^2$ 和 $301^2$ 在计算的过程中也没有进位。同时考虑到尾部添加偶数个 $0$ 也满足要求，再加上 $196$ 就可以凑够长度 $n$。 // Date: Sun Dec 31 11:33:41 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; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const ll INFL = 0x3f3f3f3f'3f3f3f3f; 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}, }; 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 nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } 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; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #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; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif bool check(ll x) { ll k = sqrtl(x); return k * k == x; } void solve() { int n; cin >> n; if (n == 1) { cout << "1\n"; return; } int k = (n - 3) / 2; For1(i, 0, k) { string y = string(i, '0'), y2 = string(n - 3 - i * 2, '0'); cout << "1" + y + "6" + y + "9" + y2 << '\n'; cout << "9" + y + "6" + y + "1" + y2 << '\n'; } cout << "196" + string(n - 3, '0') << '\n'; } void _solve() { int n; cin >> n; map<string, vector<ll>> m; For1(i, 1, 100000) { ll j = ll(i) * i; string js = to_string(j); sort(all(js)); m[js].pb(j); } for (auto &[s, vc] : m) { int len = SZ(s); if (SZ(vc) >= len && (len & 1) && (len == n)) { cout << "len = " << len << " : " << vc << '\n'; } } } int main(void) { #ifdef _DEBUG freopen("d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Training Before the Olympiad 发现只需要考虑数组中的奇数元素，每次 $B$ 操作最多会让结果减一，那么 $A$ 操作的目的是尽量减少奇数的个数，每次操作选择两个奇数操作就可以消除这两个奇数。$B$ 操作的时候尽量选择一个奇数和一个偶数，就可以尽量让结果变小。因此每一轮操作最多消除掉三个奇数，同时让结果比最优结果少 $1$，最终如果剩下 $1$ 个奇数，那么结果还要再减一。 // Date: Sun Dec 31 00:50: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; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const ll INFL = 0x3f3f3f3f'3f3f3f3f; 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}, }; 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 nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } 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; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #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; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 100010; int a[N], n; void solve() { cin >> n; int odd = 0; ll sum{}; For1(i, 1, n) { cin >> a[i]; sum += a[i]; if (a[i] & 1) odd++; if (i == 1) { cout << a[i] << ' '; continue; } int mk = odd / 3, mo = odd % 3; ll res = sum - mk; if (mo == 1) res--; cout << res << ' '; } NL; } int main(void) { #ifdef _DEBUG freopen("c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

ABBC or BACB tutorial 对于连续的 $A$，可以使用左边的 $B$ 消除，同时把 $B$ 右移；也可以使用右边的 $B$ 消除，同时把 $B$ 左移。 先考虑什么情况下不能完全消除，字符串的形式应该类似这样：$AAABAAABAAABAAA$，也就是 $x$ 个单独的 $B$，把所有的 $A$ 分成了 $x + 1$ 段，此时只能消除 $x$ 段 $A$，为了获取最大价值，应该留下最小的那段连续的 $A$。 然后考虑什么情况下可以完全消除，只需要在上面的字符串的基础上，添加一个「多余的」$B$ 即可，它的作用只是用来消除最后剩下的那段 $A$，添加方式有三种：在字符串的最开始，在字符串的最后，紧挨着现有的 $B$ // Date: Thu Dec 28 22:27: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()) 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 = 200100; int n, t, a[N]; string s; int main(void) { #ifdef _DEBUG freopen("1873g.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> s; n = SZ(s); int idx = 0, cnt = 0; bool flag = false; For(i, 0, n) { if (s[i] == 'B') { if (!flag) { if ((i == 0) || (i == n - 1) || (i + 1 < n && s[i + 1] == 'B')) { flag = true; } } if (cnt) { a[++idx] = cnt; cnt = 0; } } else { cnt++; } } if (cnt) a[++idx] = cnt; ll sum = 0; int mi_x = INF; For1(i, 1, idx) { sum += a[i]; mi_x = min(mi_x, a[i]); } if (flag) cout << sum; else cout << (sum - mi_x); cout << '\n'; } return 0; }

Theofanis’ Nightmare tutorial 假设数组分成 3 组，每组的和分别是 $c_1, c_2, c_3$，那么有： $$\begin{equation} ans = 1 \cdot c_1 + 2\cdot c_2 + 3 \cdot c_3 \ = (c_3 + c_2 + c_1) + (c_3 + c_2) + (c_3) \end{equation}$$ 可以发现是后缀和的形式，要使得总和最大，只需要把后缀和为正的累加起来即可。 // Date: Sat Dec 23 16:21:56 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define 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, a[N]; ll p[N]; int main(void) { #ifdef _DEBUG freopen("1903c.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(p, 0, sizeof p); Rof1(i, 1, n) p[i] = p[i + 1] + a[i]; ll ans = p[1]; For1(i, 2, n) { if (p[i] > 0) { ans += p[i]; } } cout << ans << '\n'; } return 0; }

Coin Rows tutorial 挺有趣的一道题。 这题并不能简单地 DP 做，不能最大化 Alice 的收益，此时 Bob 的收益并不是最小。 观察 Alice 的路径，形式是 $Z$ 字型。此时 Bob 只能选择上侧或者下侧，上侧是第一行的后缀和，下侧是第二行的前缀和，只需要让它们的最大值最小即可，线性扫一遍。 // Date: Thu Dec 21 20:11:59 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, a[5][N]; ll d[5][N]; PII p[5][N]; int main(void) { #ifdef _DEBUG freopen("1555c.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, 2) { For1(j, 1, n) { cin >> a[i][j]; } } ll res = INF; memset(d, 0, sizeof d); Rof1(i, 1, n) { d[1][i] = d[1][i + 1] + a[1][i]; } For1(i, 1, n) { d[2][i] = d[2][i - 1] + a[2][i]; } For1(i, 1, n) { ll tmp = max(d[1][i + 1], d[2][i - 1]); 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; }

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