Codeforces Round #738 (Div. 2)
2021/8/17 23:06:41
本文主要是介绍Codeforces Round #738 (Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
比赛链接:https://codeforces.com/contest/1559
总体评价:Chinese Round,前四道题目较为简单,后两道貌似难度剧增......
题意基本上是自己写的,也算练练英语吧......如果有语法错误还请海涵。
A
题意
Select an arbitrary interval \([l,r]\)and for all values \(i(0 \leq i \leq r - l)\), replace \(a_{l+i}\) with \(a_{l+i}\)&\(a_{r−i}\) at the same time.This operation can be performed any number of times. Minimize the maximum value in the sequence.
思路
将一个数用二进制表示后,每一位非\(1\)即\(0\)。
根据与运算的性质,两个数相与,对于二进制下都为\(1\)的某一位没有影响。然而如果存在第\(k\)位,一个数为\(1\),另一个为\(0\),那么结果必然会变小。
由于题目未限制与运算的次数,那么只需要让\(ans\)赋上\(a_1\)的值,让\(ans\)依次与之后的每一个数相与即可得到答案。
#include <cstdio> #include <iostream> const int N = 150; using namespace std; int t, n, ans, a[N]; int main() { ios::sync_with_stdio(false); cin >> t; while(t--) { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; ans = a[1]; for(int i = 2; i <= n; i++) ans = ans & a[i]; cout << ans << endl; } return 0; }
B
题意
Given a string containing 'B', 'R', or '?',you need to replace the '?' with 'B' or 'R' to get a new string.
At the same time, you should minimize the number of the ”BB“ and "RR".
思路
找到每个有字母的位置,利用贪心思想向前依次填字母。
需要特殊处理只有一个字母的情况,否则该字母后的"?"无法填上字母。
#include <bits/stdc++.h> const int INF = 1 << 30; const int N = 150; typedef long long ll; using namespace std; struct node { int x, y; }b[N]; int t, n, cnt, num, a[N]; char c; int main() { cin >> t; while(t--) { num = cnt = 0; cin >> n; for(int i = 1; i <= n; i++) { cin >> c; if(c == '?') { a[i] = -1; ++cnt; } else { a[i] = (c == 'B') ? 1 : 2; b[++num] = (node){i, cnt}; cnt = 0; } } for(int i = 1; i <= num; i++) { for(int j = b[i].x - 1; j >= b[i].x - b[i].y; j--) { a[j] = (a[j + 1] == 1) ? 2 : 1; } } for(int i = 1; i <= n; i++) { if(a[i] == 1 || a[i] == 2) a[i] == 1 ? cout << "B" : cout << "R" ; else a[i - 1] == 1 ? (a[i] = 2, cout << "R") : (a[i] = 1, cout << "B"); } cout << endl; } return 0; }
C
题意
Follow the rules to add edges, then find a way which goes through every point exactly once.
思路
简简单单的建图、\(dfs\)。
或者也可以找规律来完成此题。
#include <bits/stdc++.h> const int N = 10050; using namespace std; int t, n, num, a[N], ans[N]; bool flag, vis[N]; vector<int> g[N]; void dfs(int x, int step) { if(step == n && num - 1 == step) { flag = 1; for(int i = 1; i <= num; i++) cout << ans[i] << " "; cout << endl; return ; } for(int i = 0; i < g[x].size() && !flag; i++) { int to = g[x][i]; if(vis[to]) continue; vis[to] = 1; ans[++num] = to; dfs(to, step + 1); num--; vis[to] = 0; } } int main() { cin >> t; while(t--) { cin >> n; for(int i = 1; i <= n - 1; i++) g[i].push_back(i + 1); for(int i = 1; i <= n; i++) { cin >> a[i]; a[i] ? g[n + 1].push_back(i) : g[i].push_back(n + 1); } for(int i = 1; i <= n + 1; i++) { if(flag) break; memset(vis, 0, sizeof(vis)); vis[i] = 1; num = 1; ans[num] = i; dfs(i, 0); } if(!flag) cout << "-1" << endl; for(int i = 1; i <= n + 1; i++) g[i].clear(); memset(vis, 0, sizeof(vis)); flag = 0; } return 0; }
D1
题意
Given two forests(A forest is an undirected graph without cycles (not necessarily connected).), you can add an edge between \(u\) and \(v\)\((u, v \in [1, n])\) in two forests at the same time.Maximum the number of edges they can add, and which edges to add.
思路
考虑到数据范围,一种很暴力的思路就是邻接矩阵存图,\(O(n^2)\)枚举边,每次\(dfs\)判环,然后愉快的Time limit exceeded on pretest 6。
正确做法是不用建图,只需要使用并查集即可,加上路径压缩的并查集可以节省很多时间。
#include <cstdio> #include <cstring> #include <iostream> #include <vector> const int N = 1050; using namespace std; int n, m1, m2, u, v, fa[2][N]; struct node { int x, y; }; vector<node> ans; int get_fa(bool tp, int x) { return x == fa[tp][x] ? x : fa[tp][x] = get_fa(tp, fa[tp][x]); } int main() { ios::sync_with_stdio(false); cin >> n >> m1 >> m2; for(int i = 1; i <= n; i++) fa[0][i] = fa[1][i] = i; for(int i = 1; i <= m1; i++) { cin >> u >> v; fa[0][get_fa(0, v)] = get_fa(0, u); } for(int i = 1; i <= m2; i++) { cin >> u >> v; fa[1][get_fa(1, v)] = get_fa(1, u); } for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { if((get_fa(0, i) != get_fa(0, j)) && (get_fa(1, i) != get_fa(1, j))) { fa[0][get_fa(0, j)] = get_fa(0, i); fa[1][get_fa(1, j)] = get_fa(1, i); ans.push_back((node){i, j}); } } } cout << ans.size() << endl; for(int i = 0; i < ans.size(); i++) cout << ans[i].x << " " << ans[i].y << endl; return 0; }
这篇关于Codeforces Round #738 (Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解