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

P4779 【模板】单源最短路径（标准版） $Dijkstra$ 模板，求解单源最短路，复杂度 $O(m \log(n))$，其中 $n$ 为点数，$m$ 为边数。 思想是把已经求出最短距离的点加入到集合中，然后把其它点到起点的距离加入到最小堆中，每次从堆顶取出元素 $i$，用它去做松弛操作，如果能够更新相邻点 $j$，那么把 $j$ 的距离加入到最小堆中。可以保证每次从堆顶取出元素之后，这个元素的最短距离就已经被确定，可以直接把它加入到集合中。 算法要求边权值都是正数。 // Date: Fri Dec 29 11:33:23 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(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 = 100100, M = 200100; int n, m, s, h[N], st[N], dis[N]; int idx, e[M], ne[M], w[M]; void Init() { idx = 0; memset(h, -1, sizeof h); memset(st, 0, sizeof st); memset(dis, 0x3f, sizeof dis); } void Add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } void dijkstra(int s) { dis[s] = 0; priority_queue<PII, vector<PII>, greater<PII>> q; q.push({0, s}); while (nemp(q)) { auto t = q.top(); q.pop(); int base = t.f1, ver = t.f2; if (st[ver]) continue; st[ver] = true; ForE(i, ver) { int j = e[i], tmp = base + w[i]; if (tmp < dis[j]) { dis[j] = tmp; q.push({tmp, j}); } } } } int main(void) { #ifdef _DEBUG freopen("4779.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> s; Init(); For1(i, 1, m) { int a, b, c; cin >> a >> b >> c; Add(a, b, c); } dijkstra(s); For1(i, 1, n) { int tmp = dis[i]; if (tmp == INF) cout << ((1LL << 31) - 1) << ' '; else cout << tmp << ' '; } cout << '\n'; 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; }

Greetings 因为所有人都向右走，速度相同，因此如果两个人都还没有到达终点，那么这两个人不会相遇。只有一种情况会相遇，$i, j$ 两个人满足：$a_i > a_j, b_i < b_j$。可以把所有区间按照左端点从小到大排序，对于每一个 $b_i$，寻找之前所有 $> b_i$ 的区间的个数。把端点离散化之后，把点的值作为下标放到数组中，也就是求数组的后缀和，使用 $n + 1 - b_i$ 转换成求前缀和，可以使用树状数组，点更新、区间查询。 // Date: Thu Dec 28 23:25:57 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define 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, fen[N * 4]; inline int lowbit(int x) { return x & -x; } void update(int pos, int n) { while (pos <= n) { fen[pos]++; pos += lowbit(pos); } } int sum(int pos) { int result = 0; while (pos > 0) { result += fen[pos]; pos -= lowbit(pos); } return result; } int main(void) { #ifdef _DEBUG freopen("f.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; memset(fen, 0, sizeof fen); unordered_map<int, int> mm; int idx = 0; vector<PII> a; VI bv; For1(i, 1, n) { int x, y; cin >> x >> y; a.pb({x, y}); bv.pb(y); } sort(all(bv)); For(i, 0, n) { mm[bv[i]] = ++idx; } sort(all(a)); set<int> s; ll res{}; for (auto &[x, y] : a) { int v = mm[y]; v = idx + 1 - v; int cnt = sum(v); res += cnt; update(v, idx); } cout << res << '\n'; } return 0; }

Bicycles tutorial 点的数量 $n \le 1000$，边的数量 $m \le 2000$，然后再记录一下到达每个点的时候的速度 $s_i$，而 $s_i \le 1000$，因此点数最多有 $10^6$ 个。然后使用 $Dijkstra$ 得到 $dis[n][s_i]$，其中 $1 \le s_i \le 1000$，在里面找到最小值。 // Date: Fri Dec 29 12:04:17 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 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 ll INF = 0x3f3f3f3f'3f3f3f3f, MOD = 1e9 + 7; 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()) 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 using PLI = pair<ll, int>; const int N = 1100, M = 1100 * 2; int t, n, m, h[N], g[N][N], s[N]; int idx, e[M], ne[M], w[M]; struct point { ll val; int ver, s0; point(ll _val, int _ver, int _s0) : val(_val), ver(_ver), s0(_s0) {} bool operator>(const point &rhs) const { return val > rhs.val; } }; void Init() { idx = 0; memset(h, -1, sizeof h); memset(g, 0x3f, sizeof g); } void Add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } ll dijkstra() { priority_queue<point, vector<point>, greater<point>> q; q.push({0, 1, s[1]}); map<PII, ll> dis; dis[{1, s[1]}] = 0; set<PII> vis; while (nemp(q)) { auto t = q.top(); q.pop(); ll base = t.val; int ver = t.ver, sv = t.s0; if (has(vis, PII(ver, sv))) continue; vis.insert(PII(ver, sv)); ForE(i, ver) { int j = e[i], svj = min(sv, s[j]); PII pj = PII(j, svj); ll tmp = base + sv * w[i]; if (!has(dis, pj) || tmp < dis[pj]) { dis[pj] = tmp; q.push(point(tmp, j, svj)); } } } ll res = INF; For1(i, 1, 1000) { PII p = PII(n, i); if (dis.find(p) != dis.end()) { res = min(res, dis[p]); } } return res; } int main(void) { #ifdef _DEBUG freopen("g.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { Init(); cin >> n >> m; For(i, 0, m) { int a, b, c; cin >> a >> b >> c; Add(a, b, c); Add(b, a, c); } For1(i, 1, n) { cin >> s[i]; } cout << dijkstra() << '\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$。 ...

Iva & Pav tutorial 由于 $f(l, r) = a_l \And a_{l + 1} \ldots \And a_{r}$ 是有单调性的，因此可以考虑二分答案。接下来是如何快速求 $f(l, r)$，可以按位考虑，对每一个二进制位，计算区间内这个二进制位为 1 的个数，如果恰好等于区间的长度，说明区间内所有数字的这位都为 1，累加到答案中。数区间内 1 的个数可以使用前缀和快速得到。 // Date: Wed Dec 27 23:50: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()) 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, q, a[N], d[N][35], l, k, n; int check(int l, int r) { int res = 0; For(j, 0, 32) { int cn = d[r][j] - d[l - 1][j]; if (cn == r - l + 1) { res += (1 << j); } } return res; } int main(void) { #ifdef _DEBUG freopen("1878e.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]; } cin >> q; For(j, 0, 32) d[0][j] = 0; For1(i, 1, n) { int tmp = a[i]; For(j, 0, 32) { int cnt = 0; if (tmp & 1) cnt = 1; tmp >>= 1; d[i][j] = d[i - 1][j] + cnt; } } while (q--) { cin >> l >> k; int r = n, mid; int le = l; while (le < r) { mid = (le + r + 1) / 2; if (check(l, mid) >= k) le = mid; else r = mid - 1; } if (check(l, le) >= k) cout << le; else cout << -1; cout << ' '; } cout << '\n'; } return 0; }

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

Add, Divide and Floor tutorial 因为操作不会影响元素的顺序，所以可以把数组排序，经过一系列操作，使得最小值和最大值相等。设最小值和最大值分别是 $a, b$，考虑 $b - a$ 的值经过一次操作后的变化 $\lfloor\frac{b + x}{2}\rfloor - \lfloor \frac{a + x}{2} \rfloor$，枚举 $a, b$ 的奇偶性，观察发现 $b - a$ 最好情况下变成 $\frac{b - a}{2}$，当 $a$ 为奇数时，令 $x = 1$，否则令 $x = 0$。 // Date: Mon Dec 25 23:28:12 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("1901c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; int miv = INF, mav = -INF; For1(i, 1, n) { cin >> a[i]; miv = min(miv, a[i]); mav = max(mav, a[i]); } VI res; while (miv != mav) { if (miv & 1) { res.pb(1); miv = (miv + 1) / 2; mav = (mav + 1) / 2; } else { res.pb(0); miv /= 2; mav /= 2; } } int len = SZ(res); cout << len << '\n'; if (len <= n && len) { cout << res << '\n'; } } return 0; }