A
题面
给定一个长为 \(n\) 的数组 \(a\) 和一个整数 \(x\)，每次操作可以将 \(a\) 中相邻两个数替换为他们之间的某个数，问最后有没有可能剩下的数大小为 \(x\)。
\( 1 \le n \le 100 \\ -10^9 \le a_i \le 10^9 \\ -10^9 \le x \le 10^9 \)
解析
考虑最大的数，它可以和两边的数替换为它本身，最小的数同理，所以我们可以将除了最大最小两个数之外的数全消去，只要 \(x\) 在他们之间就可以剩下 \(x\)，反之则不可。
代码
#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){int n;cin >> n;vector <int> v(n);int maxl = -2147483647;int minl = 2147483647;for(int i = 0; i < n; i++){cin >> v[i];maxl = max(maxl, v[i]);minl = min(minl, v[i]);}int x;cin >> x;if(minl <= x && x <= maxl){cout << "Yes\n";}else{cout << "No\n";}}return 0;
}
B
题面
给定一个长为 \(n\) 的严格递增的数列 \(a\)，求在 \(a\) 中找出两个数 \(x\)，\(y\) 使得 \(x \lt y\) 且 \(y \mod {x}\) 为偶数，否则输出 \(-1\)。
\( 2 \le n \le 10^5 \\ 1 \le a_1 \lt a_2 \lt ... \lt a_n \le 10^9 \\ \sum{n} \le 10^5 \)
解析
如果 \(a\) 中有至少两个偶数那么输出这两个偶数即可。
下面考虑全是奇数的情况（如果有 \(1\) 个偶数暂且忽略掉它），两个奇数相减就是偶数，这是最朴素的想法，其实想要达成这一点，只要 \(y \lt 2x\)，最优的一定是相邻的两个奇数满足这个条件，但是如何保证一定有这样一对相邻奇数呢，注意到题目中对数的大小有了限定 \(a_n \le 10^9\)，这保证了如果所有相邻的奇数都不满足这个条件，那么任意一对相邻的奇数，都有 \(2x + 1 \le y\)，从而 \(a_n + 1 \ge 2 ^ {n - 1}(a_1 + 1) \ge 2^n\) 这在 \(n \ge 30\) 的时候是不可能的，因此我们只需要在 \(n\) 比较小的时候 \(n^2\) 遍历，比较大的时候找满足条件的相邻奇数对即可。
时间复杂度 \(O(n)\)。
代码
#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){int n;cin >> n;vector <int> v(n), a, b;for(int i = 0; i < n; i++){cin >> v[i];if(v[i] & 1) a.push_back(v[i]);else b.push_back(v[i]);}if(b.size() > 1){cout << b[0] << ' ' << b[1] << '\n';}else{if(n <= 100){int tag = 0;for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)if((v[j] % v[i]) % 2 == 0){cout << v[i] << ' ' << v[j] << '\n';tag = 1;goto END;}END:;if(!tag) cout << -1 << '\n';}else{int siz = a.size();for(int i = 0; i < siz - 1; i++){if((v[i + 1] % v[i]) % 2 == 0){cout << v[i] << ' ' << v[i + 1] << '\n';break;}}}}}return 0;
}
C
题面
有 \(n\) 把剑和 \(m\) 只怪物，每把剑有伤害 \(a\)，怪物有血量 \(b\)，当且仅当剑的伤害不小于怪兽的血量的时候能将其击杀，击杀怪物还有回馈值 \(c\)，如果 \(0 \lt c\)，那么击杀怪物后会回馈一把伤害为 \(\max{(a,c)}\) 的剑，每把剑只能使用一次，问最多能击杀多少只怪物。
\( 1 \le n,m \le 2 \times 10^5 \\ 1 \le a_i \le 10^9 \\ 1 \le b_i \le 10^9 \\ 0 \le c_i \le 10^9 \\ \sum{n} \le 2 \times 10^5 \\ \sum{m} \le 2 \times 10^5 \)
解析
考虑贪心的来做，我们可以将没有回馈的怪物放到最后来击杀，考虑有回馈的怪物，只要击杀它那么回馈的剑的伤害一定不低于击杀它所用的剑的伤害，因此，我们尽可能用伤害低的剑去击杀怪物，这样能保证我们最后剩下的剑的伤害尽可能的高，这一部分用大根堆维护即可。
时间复杂度 \(O(n \log{n} + m \log{m})\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){int n, m;cin >> n >> m;vector <int> a(n, 0);vector <pii> b(m);priority_queue <int, vector <int>, greater <int>> q;for(int i = 0; i < n; i++){cin >> a[i];q.push(a[i]);}vector <int> c;vector <pii> d;for(int i = 0; i < m; i++)cin >> b[i].first;for(int i = 0; i < m; i++){cin >> b[i].second;if(b[i].second){d.push_back(b[i]);}else{c.push_back(b[i].first);}}sort(d.begin(), d.end(), [&](pii x, pii y){if(x.first == y.first) return x.second > y.second;return x.first < y.first;});int siz = d.size();vector <int> e;int ans = 0;for(int i = 0; i < siz; i++){while(!q.empty() && q.top() < d[i].first){e.push_back(q.top());q.pop();}if(!q.empty()){int x = q.top();x = max(d[i].second, x);q.pop();q.push(x);ans++; }}while(!q.empty()){e.push_back(q.top());q.pop();}sort(e.begin(), e.end());sort(c.begin(), c.end());int siz1 = e.size(), siz2 = c.size();int i = 0, j = 0;while(i < siz1 && j < siz2){if(e[i] >= c[j]){ans++;j++;i++;}else{i++;}}cout << ans << '\n';}return 0;
}
D
题面
给定两个长为 \(n\) 的字符串 \(s\) 和 \(t\)，以及一个整数 \(k_{max}\)，每次操作可以将字符串 \(s\) 变为一个新字符串 \(s'\)，其中对每个 \(1 \le i \lt n\)，\(s'_i = s_i\) 或 \(s'_i = s_{i - 1}\)。输出一个操作方案使得能在不超过 \(k_{max}\) 次操作内将 \(s\) 变为 \(t\)，如果不能则输出 \(-1\)。
\( 1 \le \sum{n \times k_{max}} \le 10^6 \)
解析
每次操作相当于将一些字符向后传递而另一些不变，如果不考虑次数的限制，那么 \(s\) 能变成 \(t\) 的一个显然的必要条件是对每个 \(0 \le j \lt n\)，都存在 \(0 \le i \le j\)，使得 \(t_j = s_i\)，我们称之为配对。
那么什么时候 \(s\) 不能变成 \(t\) 呢？考虑这样一个情况：
\(s_{i_1} = t_{j_1}\)，\(s_{i_2} = t_{j_2}\)，\(i_1 \lt i_2\)，\(j_2 \lt j_1\)，那么在字符向后传递的时候，\(s_{i_1}\) 想要传递到 \(j_1\) 的位置必定会经过 \(j_2\)，从而会将这一位覆盖掉。
据此，我们知道了 \(s\) 想要变成 \(t\) 一定会存在一个配对方式使得 \(t\) 的每个字符都能在 \(s\) 中有与之配对的字符，且这些配对不产生上面的交叉的情况，这可以从后往前遍历一遍完成判断。
再考虑最少的操作方式，可以贪心的找。我们在找一个 \(t\) 中一个字符的配对时优先找离他最近的，这样二者之间的距离就是需要操作的次数。
时间复杂度 \(O(n \times k_{max})\)。
代码
#include <bits/stdc++.h>
using namespace std;void solve(){int n, k;cin >> n >> k;string s, t;cin >> s >> t;if(s[0] != t[0]){cout << -1 << '\n';return;}vector <int> pre(n, 0);int idx = n - 1;int maxl = 0;for(int i = n - 1; i; i--){if(idx > i) idx = i;while(idx > 0 && s[idx] != t[i])idx--;if(s[idx] == t[i])pre[i] = idx,maxl = max(maxl, i - idx);else{cout << -1 << '\n';return;}}if(maxl > k){cout << -1 << '\n';return;}cout << maxl << '\n';for(int i = 1; i <= maxl; i++){for(int j = n - 1; j; j--){if(pre[j] != j){pre[j]++;s[j] = s[j - 1];}}cout << s << '\n';}
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--) solve();return 0;
}
E
题面
给定一个有 \(n\) 个节点 \(m\) 条边的图，点从 \(1\) 开始编号，允许有自环与重边，每条边有一个权值 \(w_i\)，边的索引从 \(1\) 到 \(m\) 编号，你可以无限次进行如下操作：
当你在点 \(x\) 处时，
-
选择一个与 \(x\) 相连的点 \(y\)，从 \(x\) 移动到 \(y\) 并标记这条边，花费 \(w_i\)。
-
选择任意一个点 \(y\)，直接从 \(x\) 移动到点 \(y\)，你可以任选路径，花费为该路径上边的索引最大的边的权值。
现在你在 \(1\) 号节点，求标记所有的边并回到 \(1\) 号节点的最小花费。
\( 1 \le n \le 10^6 \\ 0 \le m \le 10^6 \\ 1 \le w_i \le 10^9 \\ \sum{n} \le 10^6 \\ \sum{m} \le 10^6 \)
解析
其实一开始看到这道题很奇怪，它的操作 \(2\) 没有选择最大边权而是选择了索引最大的边的权值，这看起来很不自然。
首先我们要标记所有边，那么最小值一定不低于 \(\sum_{i = 1}^{m}{w_i}\)，要取到这个下界需要能恰好遍历整个图一遍，这变成了一个一笔画问题。
由一笔画定理，我们可以在一个图的节点的度全为偶数时遍历这个图并回到起点，也可以在恰有两个节点的度为奇数时从一个点出发遍历整个图回到另一个点。
因此，这道题的关键就在于将所有度为奇数的点配对，然后用操作 \(2\) 将所有配对联通起来，操作 \(2\) 的代价就是所有的额外的代价。
再回来看操作 \(2\) 的代价，其实我们可以构建一个重构树，按索引从小到大加边，由重构树的性质，对两个节点 \(u\)，\(v\)，他们的 \(lca\) 为 \(f\)，那么 \(u\) 到 \(v\) 最大索引为 \(f\) 或其祖先。
因此，我们可以预处理重构树上的点到根节点的最小权值然后贪心的配对即可。
时间复杂度 \(O(n\alpha(n))\)。