A
题意
给一串只包含 (1,2) 的数，找到最小的 (k) 使得 (prod_{i=1}^k a_i = prod_{i=k+1}^n a_i) 。
题解
知识点：枚举。
因为只有 (1,2) ，所以考虑左右两边 (2) 的个数即可。
时间复杂度 (O(n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; int a[1007]; bool solve() { int n; cin >> n; int cnt = 0; for (int i = 1;i <= n;i++) cin >> a[i], cnt += a[i] == 2; if (cnt & 1) return false; int cntt = 0; for (int i = 1;i <= n;i++) { cntt += a[i] == 2; if (cntt == cnt - cntt) { cout << i << 'n'; break; } } return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << 'n'; } return 0; } B
题意
给定 (n) ，找到 (a,b) 满足 (a+b = n) 且 (a,b) 各自数位之和相差不超过 (1) 。
题解
知识点：构造。
我们对 (n) 的每位数拆分，若为偶数直接对半分，若为奇数则对半分后交替取大小部分。
时间复杂度 (O(n))
空间复杂度 (O(1))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; bool solve() { int n; cin >> n; int a = 0, b = 0; bool f = 0; int base = 1; while (n) { int val = n % 10; int x = val / 2, y = val - val / 2; if (x != y) { if (f) swap(x, y); f ^= 1; } a += x * base; b += y * base; n /= 10; base *= 10; } cout << a << ' ' << b << 'n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << 'n'; } return 0; } C
题意
将长为 (2n) 的排列中的数，两两配对 ({(a_1,b_1),cdots ,(a_n,b_n)})，使得 ({ a_1+b_1,cdots , a_n+b_n }) 满足从小到大排序后是连续上升的整数。
题解
知识点：构造。
(sum_{i=1}^{2n} i = n(2n+1)) ，构造 (n) 对后平均值是 (2n+1) ，为了保证数对是连续上升的，一定从 (2n+1) 开始两侧同时扩展。
(n) 为偶数时，一共有偶数对无法做到两侧同时扩展的，所以无解。
(n) 为奇数时，只需构造 ((1,2n),cdots (n,2n-leftlfloor dfrac{n}{2} rightrfloor)) 以及 ((2,2n-leftlfloor dfrac{n}{2} rightrfloor - 1),cdots ,(n-1,2n - 2leftlfloor dfrac{n}{2} rightrfloor)) 即可。
时间复杂度 (O(n))
空间复杂度 (O(1))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; bool solve() { int n; cin >> n; if (!(n & 1)) return false; cout << "YES" << 'n'; for (int i = 1;i <= n;i += 2) cout << i << ' ' << 2 * n - i / 2 << 'n'; for (int i = 2;i <= n;i += 2) cout << i << ' ' << 2 * n - n / 2 - i / 2 << 'n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << 'n'; } return 0; } D
题意
给定坐标轴上 (n) 个点，坐标为 (x_i) ，选中不少于 (2) 个点，可以进行一场游戏。
对于一场游戏，每个点在开始前会固定移动方向，移动方向为离自己最近的另一个点的方向，若两个方向最近的点距离一样，则往左边走。游戏开始后，每个点在碰到另一个点后会立刻停止。一场游戏的价值为，游戏最后存在点的不同的坐标个数。
问，对于所有选点方案，都进行一场游戏后的价值总和。
题解
知识点：枚举，组合数学。
每个贡献一定由一组相邻的且开始后相互靠近的点对产生，对于不相邻的点对他们不会产生任何贡献。因此，考虑枚举所有点对，计算满足相邻且开始后会相互靠近的方案数，求和便是答案。
对于一组点对 ((i,j)) ，令 (d = x_j - x_i) ，可以用二分计算出最后一个小于 (x_i-d) 的位置 (l) ，和第一个大于等于 (x_j+d) 的位置 (r) ，于是 ([1,l],[r,n]) 的点能保证 ((i,j)) 两点相互靠近产生一次贡献，这些点可选可不选，共计产生 (2^{l+n-r+1}) 的贡献。
时间复杂度 (O(n^2 log n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; const int P = 1e9 + 7; int x[3007]; int p[3007]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1;i <= n;i++) cin >> x[i]; p[0] = 1; for (int i = 1;i <= n;i++) p[i] = 2LL * p[i - 1] % P; int ans = 0; for (int i = 1;i <= n;i++) { for (int j = i + 1;j <= n;j++) { int d = x[j] - x[i]; int l = lower_bound(x + 1, x + n + 1, x[i] - d) - x - 1; int r = lower_bound(x + 1, x + n + 1, x[j] + d) - x; (ans += p[l + n - r + 1]) %= P; } } cout << ans << 'n'; return 0; } E
题意
给定一个数组 (a_i) 。设段的集合 (S) 满足：
- 元素形式为段 ([x,y]) ，其中 (1leq xleq yleq n) 。
- 所有段没有交集，即任意两个段 (A ,B) 不存在 (x) 满足 (x in A) 且 (x in B) 。
- 所有段 ([x,y]) 满足 (sum_{i=x}^y a_i geq 0) 。
一个段集合 (S) 的价值为，所有其中元素段长度的和，即 (sum_{[x,y] in S} (y-x+1)) 。
求对于数组 (a_i) 所有可能的 (S) 的价值最大值。
题解
知识点：线性dp，树状数组，离散化。
设 (s_i) 为 (sum_{j=1}^i a_j) 。
设 (f_i) 为 ([1,i]) 中 (S) 价值的最大值。有转移方程：
- 若不选 (a_i) ，则 (f_i = max(f_i,f_{i-1})) 。
- 若选 (a_i) ，则考虑 (j in [0,i-1]) 满足 (s_i - s_j geq 0) 中找到 (f_j + i -j) 的最大值。
对于2，朴素递推是 (O(n^2)) 的，考虑用数据结构优化。
注意到 (f_j + i - j) 中 (i) 是定值，我们只需要知道满足 (s_j leq s_i) 的 (j) 中 (f_j-j) 的最大值即可。为了方便找到 (s_j leq s_i) ，我们可以用一个以 (s_i) 作为下标，能查询前缀最大值的数据结构，树状数组和权值线段树都可以。其中，因为我们要求的是最大值，所以对于不同的 (j) 若有相同的 (s) ，我们取最大的 (f_j-j) 作为 (s) 对应的值不影响结果。
这里值域太大了但个数不多，可以离散化处理一个值的排名到值的映射，就可以利用排名作为下标。
时间复杂度 (O(n log n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> struct Fenwick { int n; vector<T> node; Fenwick(int _n = 0) { init(_n); } void init(int _n) { n = _n; node.assign(n + 1, T::e()); } void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; } T query(int x) { T ans = T::e(); for (int i = x;i >= 1;i -= i & -i) ans += node[i]; return ans; } }; struct T { int val; static T e() { return { (int)-1e9 }; } T &operator+=(const T &x) { return val = max(val, x.val), *this; } }; template<class T> struct Discretization { vector<T> uniq; Discretization() {} Discretization(const vector<T> &a) { init(a); } void init(const vector<T> &a) { uniq = a; sort(uniq.begin() + 1, uniq.end()); uniq.erase(unique(uniq.begin() + 1, uniq.end()), uniq.end()); } int get(T x) { return lower_bound(uniq.begin() + 1, uniq.end(), x) - uniq.begin(); } }; ll s[200007]; int dp[200007]; int pos[200007]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1;i <= n;i++) cin >> s[i], s[i] += s[i - 1]; Discretization<ll> dc(vector(s, s + n + 2)); for (int i = 0;i <= n;i++) pos[i] = dc.get(s[i]); Fenwick<T> fw(dc.uniq.size() - 1); dp[0] = 0; fw.update(pos[0], { dp[0] - 0 }); for (int i = 1;i <= n;i++) { dp[i] = max(dp[i - 1], fw.query(pos[i]).val + i); fw.update(pos[i], { dp[i] - i }); } cout << dp[n] << 'n'; return 0; } 
