Dashboard - 2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite - Codeforces
C.Catch You Catch Me
题意
思路
首先注意到贡献可以按深度统计，对于每个深度dep，贡献是在dep深度中属于的子树种类数，如果在该深度中子树存在点，那么该子树的贡献就要 + 1
然后发现这样不好统计，那么考虑对于结点1的每一棵子树去统计贡献
对于每一棵子树，贡献就是该子树最深深度 + 1
#include <bits/stdc++.h>#define int long longconstexpr int N = 2e5 + 10;
constexpr int mod = 1e9 + 7;std::vector<int> adj[N];int n;
int res = 0;void dfs(int u, int dep, int fa) {res = std::max(res, dep);for (auto v : adj[u]) {if (v == fa) continue;dfs(v, dep + 1, u);}
}
void solve() {std::cin >> n;for (int i = 1; i <= n - 1; i ++) {int u, v;std::cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}int ans = 0;for (auto v : adj[1]) {res = 0;dfs(v, 1, 1);ans += res;}std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}G. Let Them Eat Cake
思路
注意到每一轮都是较小的那个数被删除，因此每次会删至少一半的数，因此轮数一定很少，暴力模拟即可
#include <bits/stdc++.h>void solve(){int n;std::cin >> n;std::vector<int> a(n);for(int i = 0; i < n; i ++) {std::cin >> a[i];}std::vector<int> cur;int num = 0;int L = n;while(L > 1){num ++;cur = std::vector<int>();for(int i = 0; i < a.size(); i ++) {if(i == 0 && a[i] > a[i + 1]) cur.push_back(a[i]); else if(i == n - 1 && a[i] > a[i - 1]) cur.push_back(a[i]); else if(a[i] > a[i + 1] && a[i] > a[i - 1]) {cur.push_back(a[i]);}}L = cur.size();a = cur;}std::cout << num << "\n";
}
signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}H.Life is Hard and Undecidable, but...
题意
思路
直接对角线构造即可
#include <bits/stdc++.h>void solve(){int n;std::cin >> n;std::cout << 2 * n - 1 << "\n";for (int i = 1; i < 2 * n; i ++) {std::cout << i << " " << i << "\n";}
}
signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}A. Ban or Pick, What's the Trick
思路
注意到我们不论是选自己的还是禁用对方的，操作的数一定是最大值，因此一定要从大到小排序
注意到选的数>= k了之后不能再选数
注意到k <= 10，因此状态数不会很多
考虑DP，看看状态数会有多少
设dp(x, i, j)为，已经进行了x轮，A选了i个数，B选了j个数，的最大得分差（这里指A - B)
状态数为 1e5 * 10 * 10，很够，因此一定就是这个做法
记忆化所有比较好写，我们去考虑记忆化搜索
先看代码
#include <bits/stdc++.h>#define int long longconstexpr int N = 2e5 + 10;
constexpr int mod = 998244353;
constexpr int Inf = 1e18;int n, k;
int a[N], b[N];
int dp[N][12][12];int dfs(int tot, int cnta, int cntb) {if (tot == 2 * n) return 0;if (dp[tot][cnta][cntb] != -Inf) return dp[tot][cnta][cntb];int ra = cnta + tot / 2 - cntb;int rb = cntb + (tot + 1) / 2 - cnta;if (tot % 2) {int res = Inf;if (cntb < k && ra + rb <= 2 * n) res = std::min(res, dfs(tot + 1, cnta, cntb + 1) - b[rb + 1]);res = std::min(res, dfs(tot + 1, cnta, cntb));return dp[tot][cnta][cntb] = res;}else {int res = -Inf;if (cnta < k && ra + rb <= 2 * n) res = std::max(res, dfs(tot + 1, cnta + 1, cntb) + a[ra + 1]);res = std::max(res, dfs(tot + 1, cnta, cntb));return dp[tot][cnta][cntb] = res;}
}
void solve(){std::cin >> n >> k;for (int i = 1; i <= n; i ++) {std::cin >> a[i];}for (int i = 1; i <= n; i ++) {std::cin >> b[i];}std::sort(a + 1, a + 1 + n, std::greater<int>());std::sort(b + 1, b + 1 + n, std::greater<int>());for (int i = 0; i <= 2 * n; i ++) {for (int j = 0; j <= k; j ++) {for (int l = 0; l <= k; l ++) {dp[i][j][l] = -Inf;}}}std::cout << dfs(0, 0, 0) << "\n";
}
signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}记忆化搜索有几个要点：
1.出口：就是轮数到达最多轮数的时候是出口，即 tot == 2 * n
2.return dp
3.考虑决策，描述出目标状态
第3点最为重要，决策需要分类讨论当前是A操作还是B操作
如果是A操作，决策就是选一个a或者禁用一个b，如果是B操作，决策就是选一个b或者禁用一个a
M. Rock-Paper-Scissors Pyramid
题意
思路
#include <bits/stdc++.h>bool check(char x, char y) {if (x == y) return true;if (x == 'R') return y == 'P';if (x == 'S') return y == 'R';if (x == 'P') return y == 'S';return false;
}
void solve(){std::string s;std::cin >> s;int n = s.size();std::stack<char> S;S.push(s[0]);for (int i = 1; i < s.size(); i ++) {while(!S.empty() && check(S.top(), s[i])) S.pop();S.push(s[i]);}while (S.size() > 1) S.pop();std::cout << S.top() << "\n";
}
signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}
