Greedy

阿里马马与四十大盗 首先观察到回血时间是受到的伤害的值。对于连续的一段非零值，中间是不能回血的，只能一次通过，所以对于一段连续的 $a_i$，可以替换成它们的和 $b_i$，如果满足 $b_i < m$，那么有解。 对于前面的 $b_i$ 回血的值是不能跳过的，唯一能跳过的是最后连续的一段，最坏情况下总的回血时间是固定的 $sum$，因此如果让回血时间最小，只需要让最后一段能够跳过的回血时间最长，也就是求数组 $b$ 的最大的后缀和 $post\_sum < m$。 // Date: Fri Jan 5 20:55:42 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 = 100100; int n, m; ll a[N]; void solve() { while (cin >> n >> m) { For1(i, 1, n) cin >> a[i]; vector<ll> b; ll cur = 0, sum = 0; For1(i, 1, n) { sum += a[i]; if (a[i] == 0) { if (cur == 0) continue; else { b.pb(cur); cur = 0; } } else { cur += a[i]; } } bool flag = true; for (auto x : b) { if (x >= m) { flag = false; break; } } if (!flag) { cout << "NO\n"; continue; } ll res = 0; int len = SZ(b); Rof(i, 0, len) { if (res + b[i] >= m) break; res += b[i]; } res = sum - res; res += n - 1; cout << res << '\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; while (T--) { solve(); } return 0; }

Row Major tutorial 设连续的数字 $1, 2, \ldots, c$ 都能整除 $n$，并且 $c + 1 \nmid n$，那么位置为 $1, 2, \ldots, c, c+1$ 的字符都有可能相邻，并且它们任意两个位置都可能相邻。所以答案至少是 $c + 1$，取 $c+1$ 个不同的字母，然后不断重复这 $c + 1$ 个字符，可以发现相同字母的距离是 $k(c + 1)$，因为 $(c + 1) \nmid n$，所以 $k(c + 1) \nmid n$，因此相同字母不可能相邻，所以这个构造满足题意。 // Date: Tue Jan 2 22:51:33 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; 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; cin >> n; string s; if (n == 1) { cout << "a\n"; } else if (n == 2) { cout << "ab\n"; } else { int c = 1; while (n % c == 0) c++; int cur = 0; For(i, 0, n) { s += ('a' + cur); cur = (cur + 1) % c; } cout << s << '\n'; } } int main(void) { #ifdef _DEBUG freopen("1844d.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; }

Romantic Glasses 找到一个区间内的奇数下标元素的和与偶数下标元素的和相等，由于所有元素都为正数，可以把所有的奇数下标的值变成负数，这样如果某个区间的和是 0，就说明区间内奇数和偶数下标的和互为相反数并且绝对值相等。任意区间的和可以使用前缀和求。 // Date: Fri Dec 29 00:21:50 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define 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 = 200010; int t, a[N], n; ll sum[N]; int main(void) { #ifdef _DEBUG freopen("e.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; sum[0] = 0; set<ll> vis; bool flag = false; For1(i, 1, n) { cin >> a[i]; if (i & 1) a[i] = -a[i]; ll tmp = sum[i - 1] + a[i]; if (!flag && (has(vis, tmp) || tmp == 0)) { flag = true; } sum[i] = tmp; vis.insert(tmp); } cout << (flag ? "YES" : "NO") << '\n'; } return 0; }

Jellyfish and Green Apple tutorial 只需要考虑 $n < m$ 的情况，因为要求每个人得到的大小一样，所以每次切割都需要对现有的 $n$ 个全部切一次，也就是每次相当于 $n = 2n$，最终要满足 $m | (n \cdot 2^{k})$，要满足这一点，要求 $m$ 的除了 $2$ 之外的质因子，在 $n$ 中也要有，并且 $m$ 中除了 $2$ 的质因子的乘积能够整除 $n$ 中除了 $2$ 的质因子的乘积。这意味着 $\frac{m}{gcd(m, n)}$ 的质因数只有 $2$，也就是它是 $2$ 的幂次。可以利用这一点来判断是否有解。 接下来考虑最小的操作数。要满足 $m | (n \cdot 2^{k})$，而 $m \le 10^9 < 2^{30}$，所以最多操作 $30$ 次。为了让操作次数最小，每次 $n = 2n$ 之后，如果 $n > m$，那么 $n = n \mod m$，也就是每次都把能平均分的苹果都分下去，只留下不能平均分的，这样可以保证最终 $n = m$，同时每次操作 $n$ 的贡献都小于 $m$。 ...

Card Game tutorial 可以发现当前面的某个数字被移除后，它后面数字位置的奇偶性都会改变。而后面的数字被移除之后，它前面的数字位置的奇偶性不变，因此可以从后往前考虑。保留 $1, 2$ 两个位置，对于 $i \ge 3$ 的元素，从后往前把奇数位置的正数全部取出来，取完之后，如果新的奇数位置还有正数，那么同样取出来，直到奇数位置不存在正数为止。剩下数字的偶数位置可能有正数，此时只需要考虑 $1, 2$ 两个位置即可，这两个位置移除任意一个，$i \ge 3$ 之后的奇偶性都会改变，偶数位置的正数全部到了奇数位置，此时都可以取走。因此对于 $i \ge 3$ 之后的所有正数，对答案都有贡献。对于 $1, 2$ 分类讨论：$a_1 > 0, a_2 > 0$，依次都取走；$a_1 > 0, a_2 < 0$，只需要取 $a_1$；$a_1 + a_2 > 0$，都取。 // Date: Wed Dec 27 17:16: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()) 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 = 200010; int t, n, a[N]; int main(void) { #ifdef _DEBUG freopen("1882c.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]; ll res = 0; if (n == 1) { if (a[1] > 0) res = a[1]; cout << res << '\n'; continue; } For1(i, 3, n) { if (a[i] > 0) res += a[i]; } if (a[1] >= 0 && a[2] >= 0) res += a[1] + a[2]; else if (a[1] >= 0) res += a[1]; else if (a[1] + a[2] >= 0) res += a[1] + a[2]; cout << res << '\n'; } return 0; }

In Love 要判断是否存在两个区间不相交，只需要找到最小的 $r_i$ 和最大的 $l_j$，如果满足 $r_i < l_j$，那么就存在。 // Date: Wed Dec 27 16:24:53 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) 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 q, l, r; set<int> l_s, r_s; map<int, int> lcnt, rcnt; bool check() { bool mark = false; if (nonempty(r_s)) { auto it = r_s.begin(); int a = *it; auto it1 = l_s.upper_bound(a); if (it1 != l_s.end()) { mark = true; } } return mark; } int main(void) { #ifdef _DEBUG freopen("1883d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); l_s.clear(); r_s.clear(); lcnt.clear(); rcnt.clear(); cin >> q; string op; while (q--) { cin >> op >> l >> r; if (op == "+") { lcnt[l]++; rcnt[r]++; l_s.insert(l); r_s.insert(r); bool mark = check(); cout << (mark ? "YES" : "NO") << '\n'; } else { lcnt[l]--; rcnt[r]--; if (lcnt[l] == 0) { l_s.erase(l); } if (rcnt[r] == 0) { r_s.erase(r); } bool mark = check(); cout << (mark ? "YES" : "NO") << '\n'; } } return 0; }

Dances (Easy version) 对于每个 $a_i$，找到尽量小的 $b_j > a_i$，如果不存在，那么就应该移除。可以把 $a, b$ 排序，二分找 $b_j$。 // Date: Wed Dec 27 15:26:41 2023 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <climits> #include <iostream> #include <iomanip> #include <sstream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <algorithm> #include <utility> #include <functional> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define 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 n, m, a[N], b[N], t; int solve(int x, int l) { int r = n, mid; if (l > r) return -1; while (l < r) { mid = (l + r) / 2; if (b[mid] > x) r = mid; else l = mid + 1; } if (b[r] > x) return r; return -1; } int main(void) { #ifdef _DEBUG freopen("1883g1.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; a[1] = 1; For1(i, 2, n) cin >> a[i]; For1(i, 1, n) cin >> b[i]; sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n); int res = 0, l = 1; For1(i, 1, n) { int pos = solve(a[i], l); if (pos == -1) { res = n - i + 1; break; } l = pos + 1; } cout << res << '\n'; } return 0; }

Smilo and Monsters tutorial 先考虑两个数字的情况，设只有两个数字 $a, b$，不妨设 $(a + b) \mod 2 = 0$，可以猜到当大招的价值是 $x = \frac{a + b}{2}$ 的时候，操作数最小，此时答案是 $ans = x + 1$。下面用反证法，设大招的价值是 $y < x$，那么还剩 $a + b - 2 \cdot y$ 需要平 A，总的代价是 $ans_1 = a + b - 2y + y + 1 = a + b - y + 1 = 2x - y + 1 = x + 1 + (x - y)$，由于 $x > y$，所以 $ans_1 > ans$。 ...

Matching Arrays tutorial 把 $a$ 和 $b$ 都按照从小到大排序，用 $a$ 的后 $x$ 个元素和 $b$ 的前 $x$ 个元素一一匹配，这样可以让 $a_i$ 尽可能比 $b_i$ 大，同时又不会发生「浪费」。接下来让 $a$ 的前 $n - x$ 个元素和 $b$ 的后 $n - x$ 个元素一一匹配，这样可以让 $a_i$ 尽可能比 $b_i$ 小，同时 $b_i$ 也不会发生「浪费」。 // Date: Tue Dec 26 22:59:44 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 = 200010; int t, n, x; PII a[N], b[N]; int main(void) { #ifdef _DEBUG freopen("1896c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> x; For1(i, 1, n) cin >> a[i].f1, a[i].f2 = i; For1(i, 1, n) cin >> b[i].f1; sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n); bool flag = true; For1(i, 1, n) { if (i <= x) { if (a[n - x + i].f1 <= b[i].f1) { flag = false; break; } b[i].f2 = a[n - x + i].f2; } else { if (a[i - x].f1 > b[i].f1) { flag = false; break; } b[i].f2 = a[i - x].f2; } } if (!flag) { cout << "NO\n"; } else { cout << "YES\n"; sort(b + 1, b + 1 + n, [](const PII &x, const PII &y) { return x.f2 < y.f2; }); For1(i, 1, n) { cout << b[i].f1 << ' '; } cout << '\n'; } } return 0; }

Milena and Admirer tutorial 考虑两个数字的情况，可以发现尽量把 $a_i$ 分解成 $\frac{a_i}{2}$ 是最优的，推广可以猜到，如果要把 $a_i$ 分解成 $k$ 个数字，其中 $k > 2$，那么每个数字的大小是 $\frac{a_i}{k}$，也就是分解得到的数字尽量接近。注意这里不能取余，因为取余不是最优的，它会让第一个数字过小。 // Date: Tue Dec 26 13:51:13 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 = 200010; int t, n, a[N]; ll res; int main(void) { #ifdef _DEBUG freopen("1898b.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 cur = a[n]; res = 0; Rof1(i, 1, n - 1) { if (cur == 1) { res += a[i] - 1; } else if (a[i] > cur) { int y = (a[i] + 1) / 2; if (y <= cur) { cur = a[i] / 2; res++; } else { y = cur; if (a[i] % y) { int cnt = a[i] / y; res += cnt; cur = a[i] / (cnt + 1); } else { res += a[i] / y - 1; cur = y; } } } else { cur = a[i]; } } cout << res << '\n'; } return 0; }

Array and Operations tutorial 为了让分数最小，需要把大的元素消除掉。消除的操作和元素的顺序没有关系，所以把原数组从小到大排序，把最大的 $2k$ 的元素消除掉。为了使得消除的分数最小，对这 $2k$ 个元素排序之后，前 $k$ 个元素和后 $k$ 个元素一一匹配，这样做的目的是使得分子比分母小的数对尽可能多。 // Date: Thu Dec 21 23:15:54 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 = 110; int t, n, a[N], k; int main(void) { #ifdef _DEBUG freopen("1618d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k; For1(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n); int res = 0, len = n - 2 * k; VI b; For1(i, 1, n) { if (i <= len) { res += a[i]; } else { b.pb(a[i]); } } For(i, 0, k) { res += b[i] / b[i + k]; } cout << res << '\n'; } return 0; }

Another Permutation Problem tutorial 可行的排列的形式是 $1, 2, 3, \ldots, k, n, n - 1, n - 2, \ldots, k + 2, k + 1$。这种形式的排列有 $n$ 个，暴力求出来取最大值。不过并不知道怎么证明，只能打表找规律。 // Date: Wed Dec 20 22:50: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 int t, n; int main(void) { #ifdef _DEBUG freopen("1859c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; ll res{}; For1(i, 1, n) { int sum = -1, start = n - i + 1, ma = -1; ll tmp{}; For1(j, 1, n) { int x; if (j < start) { x = j * j; } else { if (sum == -1) sum = j + n; x = j * (sum - j); } tmp += x; ma = max(ma, x); } tmp -= ma; res = max(res, tmp); } cout << res << '\n'; } return 0; }

LuoTianyi and the Table tutorial 可以发现最终结果只和 $a[1][1], a[1][2], a[2][1]$ 有关，因为所有的以 $(1, 1)$ 为左上角的矩形都至少经过 $a[1][2]$ 或者 $a[2][1]$ ，所以把 $a[1][1]$ 作为最大值，其它两个点作为最小的两个值；或者把 $a[1][1]$ 作为最小值，其它两个点作为最大的两个值。这两种情况分别计算，并不是等价的。设 $n > m$，那么最大差的个数是 $n(m - 1)$ 或者 $m(n - 1)$，因为 $n > m$，所以 $m(n - 1) > n(m - 1)$。 // Date: Wed Dec 20 21:02:01 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 = 10010; int t, a[N], n, m; int main(void) { #ifdef _DEBUG freopen("1825b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> m; int m1 = n * m; For(i, 0, m1) { cin >> a[i]; } sort(a, a + m1); int x = a[m1 - 1], y = a[0], y1 = a[1], d1 = x - y, d2 = x - y1; if (n < m) swap(n, m); ll res = d1 * (n - 1) * m + d2 * (m - 1); x = a[0], y = a[m1 - 1], y1 = a[m1 - 2], d1 = y - x, d2 = y1 - x; ll res1 = d1 * (n - 1) * m + d2 * (m - 1); res = max(res, res1); cout << res << '\n'; } return 0; }