2022CCPC绵阳 ACGHM

今天药忘吃喽~ 2024-02-18 11:32 33阅读 0赞

[Dashboard - 2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite - Codeforces][Dashboard - 2022 China Collegiate Programming Contest _CCPC_ Mianyang Onsite - Codeforces]

## C.Catch You Catch Me ##

题意

![a70a16e822374ddba4d85f15a4980573.png][]

思路

首先注意到贡献可以按深度统计，对于每个深度dep，贡献是在dep深度中属于的子树种类数，如果在该深度中子树存在点，那么该子树的贡献就要 + 1

然后发现这样不好统计，那么考虑对于结点1的每一棵子树去统计贡献

对于每一棵子树，贡献就是该子树最深深度 + 1

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr 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 ##

![3ba14baa74584c79b3161101eb9ea158.png][]

思路

注意到每一轮都是较小的那个数被删除，因此每次会删至少一半的数，因此轮数一定很少，暴力模拟即可

#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... ##

题意

![0d7e36de75e842fe927483feabca2aaa.png][]

思路

直接对角线构造即可

#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 ##

![45b4f055da9840cf8912771e5e046dd1.png][]

思路

注意到我们不论是选自己的还是禁用对方的，操作的数一定是最大值，因此一定要从大到小排序

注意到选的数>= 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 long
    
    constexpr 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    ##

题意

![6016d398337c4d38bfc3dc7bdab4903d.png][]

![73e7d81253c14a3486fc04ec60f20656.png][]

思路

![026466bdea4843a098727ec18b763fa5.png][]

#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;
    }

[Dashboard - 2022 China Collegiate Programming Contest _CCPC_ Mianyang Onsite - Codeforces]: https://codeforces.com/gym/104065
[a70a16e822374ddba4d85f15a4980573.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/3880070f86804b70a07cdfeffc410cef.png
[3ba14baa74584c79b3161101eb9ea158.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/afbac7ac3e48405f915bb81a6e7a383a.png
[0d7e36de75e842fe927483feabca2aaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/659a11aff06a4881b21c402648f95c5b.png
[45b4f055da9840cf8912771e5e046dd1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/76e2d726b4ef41fa96b14f0813774879.png
[6016d398337c4d38bfc3dc7bdab4903d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/ab27369342cb4df9acd057c82fdad23d.png
[73e7d81253c14a3486fc04ec60f20656.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/e6ee5647ab3d4cf281c5a25ae5bc3760.png
[026466bdea4843a098727ec18b763fa5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/e6465c8a84f141eb9db0546d4ec323a5.png