2022 CCPC Mianyang
简记情况
是就柿火红猕猴果队的第一次训练赛！大概做了三个小时，过了CGH，卡在AM。
C直接做，G直接模拟，H构造。
5题是 银or铜。
A. Ban or Pick, What's the Trick 记忆化搜索/动态规划
Solution
思路
注意到，每次pick 或 ban 都应该选择 己方 or 对方分数最高的英雄。
模拟的时候想的是一个贪心：如果己方分数最高的英雄 > 对方，则 pick，否则 ban。其实也许可以说是一个明显的错误贪心？因为有很多小数据的反例（如下）。
Example 1.
2 1
85 50
19 16
A选了85之后，B选19比禁50更好
Example 2.
3 1
84 53 8
83 29 18
A一开始应该禁83而不是选84,因为A如果禁83，然后无论B选29还是禁84，A最后的答案都会更佳
考虑 dp/记忆化搜索 ，设 \(f[r][pa][pb]\)表示现在到 \(r\) 回合，\(a\) 选了 \(pa\) 个英雄，\(b\) 选了 \(pb\) 个英雄之后的答案。注意它记的不是在前面的 \(r\) 个回合里分别选 \(pa\) 和 \(pb\) 个英雄之后的答案；而是在前 \(r\) 个回合分别选 \(pa\) 和 \(pb\) 的前提下，后面的回合里二者都做最优选择的答案。
转移：
无非是从 \(pick\) 和 \(ban\) 这两种情况转移。
若 \(r\) 是 \(a\) 的回合，则 \(f[r][pa][pb]\)，可以从 \(f[r+1][pa][pb]\) （选择了 \(ban\)）和 \(f[r+1][pa+1][pb]\)（选择了 \(pick\)） 转移。
注意转移条件（具体见代码）。特别说明的是，若 \(a\) 已经 \(pick\) 了 \(k\) 个英雄，那么他直接 \(ban\) 肯定是更优的。
Tips:
注意到 \(k\) 的范围非常小，如果是之前 \(O(n)\) 的贪心策略，则 \(k\) 没必要这样限制范围。由此应该推测复杂度里是带 \(k\) 的，也就是说应该考虑记录与 \(k\) 有关的状态。
Code
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N = 1e5 + 2, K = 12;
const ll inf = 1e18;
int n, k, a[N], b[N];
ll f[N * 2][K][K];
ll dfs(int r, int pa, int pb) { //round pick_a pick_b
if (r == 2 * n + 1) return 0; //边界
if (f[r][pa][pb] != -1) return f[r][pa][pb];
int ta = (r - 1) / 2 - pb + pa, tb = r / 2 - pa + pb; //tot_a tot_b
if (r % 2) { //现在是a的回合
ll ret = -inf;
if (tb < n) //b还有没被选且没被禁的英雄
ret = dfs(r + 1, pa, pb);
if (pa < k && ta < n) //a还有可以选的英雄
ret = max(ret, dfs(r + 1, pa + 1, pb) + a[ta + 1]);
return f[r][pa][pb] = ret;
}
else { //现在是b的回合
ll ret = inf;
if (ta < n) //a还有没被选且没被禁的英雄
ret = dfs(r + 1, pa, pb);
if (pb < k && tb < n) //a还有可以选的英雄
ret = min(ret, dfs(r + 1, pa, pb + 1) - b[tb + 1]);
return f[r][pa][pb] = ret;
}
}
int main() {
cin >> n >> k;
for (int i = 1;i <= n;++i) cin >> a[i];
for (int i = 1;i <= n;++i) cin >> b[i];
sort(a + 1, a + n + 1, greater<int>()); //从大到小排序
sort(b + 1, b + n + 1, greater<int>());
memset(f, -1, sizeof(f));
cout << dfs(1, 0, 0) << endl;
return 0;
}
M. Rock-Paper-Scissors Pyramid 栈
Solution1
注意到 ：
① ..SSPP...PPS.. 这样的可以直接用一个 ...S... 替换
② PP....S...... 可以替换成 S.....
③ .......S...P 可以替换成 .......S
tutorial 说用一个栈维护，没太get，后续看了别的题解，感觉应该是 Solution2 的实现是一样的！
Solution2
注意到对于 SPRSPR 这样的序列（每个都被左边的打败），答案是 S。
考虑维护一个栈，从栈底到栈顶满足上述条件。如何维护：若当前遍历到 \(c\)，则 \(c\) 与栈顶元素比较，如果不被打败，则弹出栈顶，一直到栈空或能打败栈顶。然后将 \(c\) 加入栈。
感觉本质和 Solution1 是一个意思。
Solution3
网上看的一个贪心做法，here ，感觉有点抽象（打败前一个就上一层，最后值最大的也就是最高层的答案）。
Code
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 5;
string s;
char stack[N];
int top;
bool comp(char x, char y) {
if (x == 'R' && y == 'S') return 1;
if (x == 'S' && y == 'P') return 1;
if (x == 'P' && y == 'R') return 1;
return 0;
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> s;
top = -1;
int len = s.length();
for (int i = 0;i < len;++i) {
int c = s[i];
while (top >= 0 && comp(c, stack[top])) --top;
stack[++top] = c;
}
cout << stack[0] << endl;
}
return 0;
}