【2021ICPC沈阳】EFBJHL

川长思鸟来 2024-02-20 10:47 48阅读 0赞

**不知道为什么感觉以前的场要比现在的简单一点，虽然这场VP虽然题数到了但是还是差点罚时....**

**现在的有些场感觉连签到都要签半天，比如前几天的ICPC西安和CCPC桂林，看了下题都不简单**

**这场甚至银牌题都没什么思维，只需要算法的板子和一点点思维就能做出来**

[Problems - Codeforces][]

## E. Edward Gaming, the Champion ##

题意

问字符串里面有多少edgnb

思路

直接模拟即可

#include <bits/stdc++.h>
    
    constexpr int N = 1e5 + 10;
    
    void solve(){
    	std::string s;
    	std::cin >> s;
    	int n = s.size();
    	s = " " + s;
    	int ans = 0;
    	for (int i = 1; i + 4 <= n; i ++) {
    		if (s[i] == 'e' && s[i + 1] == 'd' && s[i + 2] == 'g' && s[i + 3] == 'n' && s[i + 4] == 'b') {
    			ans ++;
    		}
    	}
    	std::cout << ans << "\n";
    }
    signed main(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        while(t --) {
            solve();
        }
        return 0;
    }

## F. Encoded Strings I ##

题意

![cd04925977f340e493d6c7f07c69b50d.png][]

思路

n的范围是1000， 因此做法就是直接枚举前缀然后统计最大的编码字符串，直接扔进set即可

#include <bits/stdc++.h>
    
    constexpr int N = 1e5 + 10;
    
    std::string s;
    
    int n;
    int p[N];
    
    void solve(){
    	std::cin >> n >> s;
    	s = " " + s;
    
    	std::set<std::string> S4;
    	for (int i = 1; i <= n; i ++) {
    		std::string t = s.substr(1, i);
    		int m = t.size();
    		t = " " + t;
    		std::map<char, int> last;
    		for (int i = 1; i <= m; i ++) {
    			last[t[i]] = i;
    		}
    		std::set<char> S;
    		for (int i = m; i >= 1; i --) {
    			S.insert(t[i]);
    			p[i] = S.size();
    		}
    		std::string res;
    		for (int i = 1; i <= m; i ++) {
    			res = res + (char)('a' + p[last[t[i]] + 1]);
    		}
    		S4.insert(res);
    	}
    	std::cout << (*S4.rbegin()) << "\n";
    }
    signed main(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        while(t --) {
            solve();
        }
        return 0;
    }

## B. Bitwise Exclusive-OR Sequence ##

题意

![b90682974b434fa6b66259328bbb3607.png][]

思路

位运算的题直接当成01矩阵去看就行

一开始想的做法是直接贪心，对于一个数的第 j 位，如果和这个数的异或为1的个数大于异或为0的个数，那么就把这个数的第 j 位置为 1，这样异或之后0就比1多了

但是这样的正确性不能保证，这样只能保证对于这个数相连的所有数组成的这个集合而言是对的，放在树上其实就是只考虑了结点 u 放出去的边的所有 v构成的这样的集合，没有考虑整棵树

这样的模型显然是要往树上问题考虑的

这些约束条件连边之后，形成了若干棵树，也就是森林，当根结点的值唯一确定了，其他所有结点的值也就确定了

这里做法考虑按位贪心，对于第 j 位，如果置0之后这棵树第 j 位的1比0多，那么这位一定置0，这样就把根的值确定了

那么算出这棵树的所有的结点的值的和什么做法合适呢，考虑变化量， 根节点在全是0和根的值a1 之间的变化量就是所有结点 ^ a1，加上这个变化量即可

还有就是判无解，并不是存在环就是无解，如果存在环且异或值围着环算起来没问题也是有解的

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 2e5 + 10;
    
    std::vector<int> V[N];
    std::vector<std::pair<int, int> > adj[N];
    
    int n, m;
    int pre[N], pre2[N];
    int st[N];
    
    void dfs(int u, int s) {
    	for (auto [v, w] : adj[u]) {
    		if (st[v]) {
    			if ((pre[u] ^ w) != pre[v]) {
    				std::cout << -1 << "\n";
    				exit(0);
    			}
    		}else {
    			st[v] = 1;
    			pre[v] = pre[u] ^ w;
    			V[s].push_back(v);
    			dfs(v, s);
    		}
    	}
    }
    void solve(){
    	std::cin >> n >> m;
    	bool ok = true;
    	for (int i = 1; i <= m; i ++) {
    		int u, v, w;
    		std::cin >> u >> v >> w;
    		adj[u].push_back({v, w});
    		adj[v].push_back({u, w});
    	}
    
    	int ans = 0;
    	for (int i = 1; i <= n; i ++) {
    		if (!st[i]) {
    			st[i] = 1;
    			dfs(i, i);
    			int a1 = 0;
    			for (int j = 30; j >= 0; j --) {
    				int s = 0;
    				for (auto x : V[i]) {
    					if ((pre[x] >> j) & 1) {
    						s ++;
    					}
    				}
    				if (s > V[i].size() - s) a1 += (1 << j);
    			}
    			int res = a1;
    			for (auto x : V[i]) {
    				res += (pre[x] ^ a1);
    			}
    			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;
    }

## J. Luggage Lock ##

题意

![f0a5807593414e89a56a77b479319c9c.png][]

思路

直接BFS即可，注意多测，因此需要BFS预处理dis数组，直接算即可

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 2e5 + 10;
    
    std::string a, b;
    std::queue<std::string> q;
    std::map<std::string, int> vis, dis;
    
    int n;
    
    char calc(char x, int ty) {
    	if (ty == 0) {
    		if (x == '0') x = '9';
    		else x = (char)(x - 1);
    	}else {
    		if (x == '9') x = '0';
    		else x = (char)(x + 1);
    	}
    	return x;
    }
    void bfs(std::string u) {
    	std::string t = u;
    	t = " " + t;
    	q.push(t);
    	vis[t] = 1;
    	while(!q.empty()) {
    		std::string x = q.front();
    		q.pop();
    		for (int l = 1; l <= 4; l ++) {
    			for (int r = l; r <= 4; r ++) {
    				std::string v = x;
    				for (int j = l; j <= r; j ++) {
    					v[j] = calc(v[j], 0);
    				}
    				if (!dis.count(v)) {
    					dis[v] = dis[x] + 1;
    					q.push(v);
    				}
    
    				v = x;
    				for (int j = l; j <= r; j ++) {
    					v[j] = calc(v[j], 1);
    				}
    				if (!dis.count(v)) {
    					dis[v] = dis[x] + 1;
    					q.push(v);
    				}
    			}
    		}
    	}
    }
    void solve(){
    	std::cin >> a >> b;
        a = " " + a;
        b = " " + b;
    	std::string c = " 0000";
    	for (int i = 1; i <= 4; i ++) {
    		c[i] = (b[i] - '0' - (a[i] - '0') + 10) % 10;
    		c[i] = c[i] + '0';
    	}
    	std::cout << dis[c] << "\n";
    }
    signed main(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
    	bfs("0000");
    	std::cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

## H. Line Graph Matching ##

题意

![9137b9451c62489ba9502fab1238c410.png][]

思路

首先根据定义，问题转化成 用相邻边 把整个图占满的权重之和

显然如果边数为偶数，直接就是边权之和，那么边数是奇数呢

奇数的情况我们需要考虑不占一条边，把其他的占满，很自然地想到了枚举这条边

但事实上这条边需要满足一些条件，如果这边断开之后变成两个连通块了，这两个连通块的边数都必须是偶数，而不能是奇数+奇数。如果不是割边，那就没问题，直接不选这条边即可

那不就是割边吗，我们只需要在跑割边的过程中把连通块的边数统计一下，标记一下哪些边是合法的， 统计哪条边是合法边中边权最小的即可，然后减掉这个边就是答案了

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 2e5 + 10;
    
    std::vector<std::pair<int, int> > adj[N];
    
    int n, m;
    int idx = 0;
    int mi = 1e9;
    int cnt[N];
    int dfn[N], low[N];
    
    void tarjan(int u, int fa) {
        dfn[u] = low[u] = ++ idx;
        for (auto [v, w] : adj[u]) {
            if (!dfn[v]) {
                tarjan(v, u);
                cnt[u] += cnt[v] + 1;
                low[u] = std::min(low[u], low[v]);
                if (low[v] > dfn[u]) {
                    if (cnt[v] % 2 == 0) {
                        mi = std::min(mi, w);
                    }
                }else {
                    mi = std::min(mi, w);
                }
            }else if (dfn[v] < dfn[u] && v != fa) {
                cnt[u] ++;
                mi = std::min(mi, w);
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
    void solve(){
        std::cin >> n >> m;
        int ans = 0;
        for (int i = 1; i <= m; i ++) {
            int u, v, w;
            std::cin >> u >> v >> w;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
            ans += w;
        }
        tarjan(1, 0);
        if (m & 1) ans -= mi;
        std::cout << ans << "\n";
    }
    signed main(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        while(t --) {
            solve();
        }
        return 0;
    }

## L. Perfect Matchings ##

题意

![71b8a94f23a24e38be0a3424f3f0da06.png][]

思路

首先 删边 其实可以看作是给这些边 染色，这样能直观一点

那么其实就是染了一棵树，然后让我们在求没被染的边中选 n 条边使得这些边之间没有公共顶点 的 方案数

正着难求，我们考虑容斥，即总方案数 - 不合法方案的并集

容斥的话，考虑在树上选了 k 条边的方案数，这样是 (-1)^k \* val

这个val考虑树上背包

设 dp\[u\]\[v\]\[0/1\] 为 u这棵子树中，选了 v 条边，u结点是否是边的一部分的方案数，转移就是 dls 那个树上背包的转移

不过要分和根结点连的那条边是否被选，如果被选的话 u 和 v 都不能被选，然后和根连着的那条边单独计算，详细看代码

然后要在非树的部分选边，这个算组合数即可

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 4e3 + 10;
    constexpr int mod = 998244353;
    
    std::vector<int> adj[N];
    
    int n;
    int sz[N];
    int dp[N][N][2];
    int p[N];
    
    void dfs(int u, int fa) {
        sz[u] = dp[u][0][0] = 1;
        for (auto v : adj[u]) {
            if (v == fa) continue;
            dfs(v, u);
            for (int k = sz[u] / 2; k >= 0; k --) {
                for (int l = sz[v] / 2; l >= 0; l --) {
                    if (l > 0) {
                        dp[u][k + l][0] += dp[u][k][0] * (dp[v][l][0] + dp[v][l][1]) % mod, dp[u][k + l][0] %= mod;
                        dp[u][k + l][1] += dp[u][k][1] * (dp[v][l][0] + dp[v][l][1]) % mod, dp[u][k + l][1] %= mod;
                    }
                    dp[u][k + l + 1][1] += dp[u][k][0] * dp[v][l][0] % mod, dp[u][k + l + 1][1] %= mod;
                }
            }
            /*for (int i = 0; i <= sz[u] + sz[v]; i ++) {
                dp[u][i][0] = tmp[i][0];
                dp[u][i][1] = tmp[i][1];
            }*/
            sz[u] += sz[v];
        }
    }
    void solve(){
        std::cin >> n;
        for (int i = 1; i <= 2 * n - 1; i ++) {
            int u, v;
            std::cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        p[0] = 1;
        for (int i = 1; i <= n; i ++) {
            p[i] = p[i - 1] * (2 * i - 1) % mod;
        }
        dfs(1, 0);
        
        int ans = 0;
        for (int i = 0; i <= n; i ++) {
            if (i & 1) ans -= (dp[1][i][0] + dp[1][i][1]) * p[n - i] % mod;
            else ans += (dp[1][i][0] + dp[1][i][1]) * p[n - i] % mod;
            ans = (ans % mod + mod) % mod;
        }
        std::cout << ans << "\n";
    }
    signed main(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problems - Codeforces]: https://codeforces.com/gym/103427/problems
[cd04925977f340e493d6c7f07c69b50d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/10a6420b328f4b1abccec0e3c26c99c4.png
[b90682974b434fa6b66259328bbb3607.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/298e6f1b4c1a47fb809eb997ca9bdccb.png
[f0a5807593414e89a56a77b479319c9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a18963ec10a445b8a99b3c00b6dfce89.png
[9137b9451c62489ba9502fab1238c410.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/1dae01973c314a218ffc0798f16f00a1.png
[71b8a94f23a24e38be0a3424f3f0da06.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/d6570ee778a8488aa1f786eb4fdae340.png