Practice.
A. Game with Board
题意
给定 \(n\) 个 \(1\)，定义操作为选定至少两个相同的数，将其从序列中移除，并插入他们的和。
对于 \(Alice\) 和 \(Bob\) 之间的博弈，规定 \(Alice\) 先手，当某个玩家 无法 执行操作时，该玩家 获胜。
输出最后获胜的玩家。
思路
首先，如果 \(n\) 比较大的时候，\(Alice\) 就可以选择 \(n - 2\) 个 \(1\)，这样 \(Bob\) 只能将剩余的两个 \(1\) 选上，最后序列剩余两个不同的数，从而 \(Alice\) 必胜。
上面的必胜策略需要保证 \(n - 2 > 2\)，也就是 \(n > 4\) 的时候 \(Alice\) 有必胜策略。
我们不难发现，当 \(2 \leq n \leq 4\) 的时候，无论 \(Alice\) 怎么选，最后 \(Bob\) 一定会无法操作，因而 \(Bob\) 必胜。
因而，判断 \(n\) 的大小即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
cout << (n > 4 ? "Alice" : "Bob") << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}不要看错题（
B. Keep it Beautiful
题意
给定一个序列，定义满足下面任意一个条件的序列是美丽的：
整个序列不递减；
从头开始选择一段连续的子序列，将其和剩余的子序列交换位置，得到的新序列不递减
现在，给定一个操作序列，定义操作如下：
给定一个数 \(x\)，如果将其插入到当前序列的最后，得到的新序列是美丽的，那么执行插入操作，否则不插入。
对于每一次操作，输出是否可以操作成功，用二进制字符串表示。
思路
显然，我们分讨模拟即可。
我们维护当前序列的头 \(st\) 和尾 \(ed\) 对应的数值，如果我们没有交换过位置，那么我们只需满足 \(x \geq ed\)。
那如果不满足，我们就需要交换位置，显然要满足条件的话，我们就只能把 \(x\) 作为新序列的头，把前面的全都移到后面去。因而，如果之前就执行过交换操作，这次插入操作就失败了。
那么，如果交换过位置，且满足 \(x \geq ed\)，我们就需要添加一个条件 \(x \leq st\)，保证交换后依然美丽。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int st;
cin >> st;
int ed = st;
n --;
cout << 1;
bool f = false;
while(n --){
int x;
cin >> x;
if(x >= ed){
if(f && x > st) cout << 0;
else{
cout << 1;
ed = x;
}
}else{
if(!f && x <= st){
cout << 1;
f = true;
ed = x;
}else cout << 0;
}
}
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}模拟模拟
C. Ranom Numbers
题意
给定一个由 "\(A\)", "\(B\)", "\(C\)", "\(D\)", "\(E\)" 组成的字符串，其中 \(ABCDE\) 对应的值分别为 \(1, 10, 100, 1000, 10000\)，因而五个字符具有大小关系。
给定字符串的值的运算方式：
遍历每一位的字符。如果该字符 小于等于 后面的所有字符，那么取正号，否则取负号。将每一位乘上符号后累加得到字符串的值。
现在，需要选择一个字符，将其修改为任意五个字符的其中一个，输出修改后的最大值。
思路
由后面的状态约束前面的状态，我们不难想到 \(dp\)。
为了方便，我们不妨反转字符串，这样我们就可以从前往后递推了。
如上，我们可以定义一个三维 \(dp\)，\(dp[i][mx][c]\) 表示第 \(i\) 位在前面所有字符的最大值是 \(mx\) 且前面是否有修改的状态下的最大值，\(c\) 表示前面是否修改过。
那么，我们只需枚举第 \(i\) 位置放什么字符，以及前面是否有出现修改，因而可以得出第 \(i\) 位置是否 可以 并 需要 修改，并更新前 \(i\) 个字符的最大值。
最后，\(dp[n]\) 的所有状态的最大值就是答案。
当然，因为只有相邻的两个 \(dp[i]\) 有递推关系，所以我们用两个 \(dp\) 数组也是可以的，从而优化空间复杂度。
时间复杂度：\(O(10n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const vector<int> p = {1, 10, 100, 1000, 10000};
void solve() {
string s;
cin >> s;
reverse(all(s));
int n = s.size();
s = "#" + s;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(5, vector<int>(2, -inf)));
dp[0][0][0] = 0;
for(int i=1;i<=n;i++){
int self = s[i] - 'A';
for(int mx = 0; mx < 5; mx ++){ //枚举前面的最大值
for(int c = 0; c <= 1; c ++){ //前面有没有改过
for(int now = 0; now < 5; now ++){ //当前位置填什么
if(now != self && c == 1) continue;
int mx2 = max(mx, now),
ok = (now != self || c == 1) ? 1 : 0;
dp[i][mx2][ok] = max(dp[i][mx2][ok], dp[i - 1][mx][c] + (now >= mx ? 1 : -1) * p[now]);
}
}
}
}
int ans = -inf; //玛德蠢了打了个0
for(int mx = 0; mx < 5; mx ++){
for(int c = 0; c <= 1; c ++){
ans = max(ans, dp[n][mx][c]);
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}第一眼读假，草
D. Pairs of Segments
找个时间再做，待补充