本文主要是介绍Codeforces Round 923(Div.3) A~G,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
A.Make it White (模拟)
题意:
给一个字符串 s s s,找出最左边的 B B B和最右边的 B B B,以这两个字母为左右端点的区间包含有多少个字母。
分析:
按照要求,遍历一遍字符串找到左右端点即可。
代码:
#include <bits/stdc++.h>using namespace std;void solve() {int n;cin >> n;string s;cin >> s;int pos1 = 0, pos2 = n - 1;for (int i = 0; i < n; i++) {if (s[i] == 'B') {pos1 = i;break;}}for (int i = n; i >= 0; i--) {if (s[i] == 'B') {pos2 = i;break;}}cout << max(0, pos2 - pos1 + 1) << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}
B.Following the String (贪心)
题意:
给出一个长度为 n n n的数组 a a a, a i a_i ai表示 j < i j < i j<i的 s i = s j s_i=s_j si=sj出现的个数。询问是否存在字符串 s s s符合这个数组。
分析:
枚举 26 26 26个字母,每次贪心地放入字母即可。
代码:
#include <bits/stdc++.h>using namespace std;void solve() {int n;cin >> n;string ans;vector<int> cnt(27, 0);for (int i = 0; i < n; i++) {int x;cin >> x;for (int j = 0; j < 26; j++) {if (cnt[j] == x) {++cnt[j];ans += char('a' + j);break;}}}cout << ans << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}
C. Choose the Different Ones! (贪心)
题意:
给一个长度为 n n n的数组 a a a,一个长度为 m m m的数组 b b b,和一个偶数 k k k,询问能否从两个数组各取出 k / 2 k/2 k/2个数字,组成一个 1 − k 1-k 1−k的排列。
分析:
对于 1 − k 1-k 1−k的数字,如果只在 a , b a,b a,b中的一个数组中出现,那么就必须取,计算拿完这样的元素需要多少次,是否满足两个数组拿取的次数都满足小于等于 k / 2 k/2 k/2,其余元素随便取即可。
代码:
#include <bits/stdc++.h>using namespace std;
map<int, int> map1, map2;void solve() {int n, m, k, x;map1.clear();map2.clear();cin >> n >> m >> k;int cnt1 = k / 2, cnt2 = k / 2;for (int i = 1; i <= n; i++) {cin >> x;map1[x]++;}for (int i = 1; i <= m; i++) {cin >> x;map2[x]++;}int flag = 0;for (int i = 1; i <= k; i++) {if (!map1.count(i) && !map2.count(i)) {flag = 1;break;} else if (map1.count(i) && !map2.count(i)) {cnt1--;} else if (map2.count(i) && !map1.count(i)) {cnt2--;}}if (cnt1 < 0 || cnt2 < 0 || flag)cout << "NO" << endl;elsecout << "YES" << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}
D.Find the Different Ones! (思维)
题意:
给一个长度为 n n n的数组 a a a, m m m次询问,每次询问给出一个区间 [ l , r ] [l,r] [l,r],询问是否有 i , j i,j i,j满足以下条件:
- l ≤ i , j ≤ r , a i ≠ a j l \le i,j\le r,a_i \neq a_j l≤i,j≤r,ai=aj
如果存在输出 i , j i,j i,j。
分析:
l e f t [ i ] left[i] left[i]维护 i i i左边第一个和自己不同的元素,每次询问判断是否 l e f t [ r ] < l left[r] < l left[r]<l 即可。
代码:
#include <bits/stdc++.h>using namespace std;
const int MAXN = 2e5 + 5;
int a[MAXN], left1[MAXN];void solve() {int n, q, l, r;cin >> n;left1[1] = 0;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 2; i <= n; i++) {if (a[i] != a[i - 1])left1[i] = i - 1;elseleft1[i] = left1[i - 1];}cin >> q;for (int i = 1; i <= q; i++) {cin >> l >> r;if (left1[r] < l)cout << -1 << " " << -1 << endl;elsecout << left1[r] << " " << r << endl;}cout << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}
E.Klever Permutation (思维)
题意:
给定两个整数 n , k n,k n,k,询问是否存在满足以下条件的合法排列:
- 对所有满足 i + k − 1 ≤ n i+k-1 \le n i+k−1≤n的 i i i,每个区间 [ i − i + k − 1 ] [i-i+k-1] [i−i+k−1]的和中的最大值和最小值相差不超过 1 1 1。
分析:
设每个区间的和为 s [ i ] s[i] s[i],那么需要构造成$s[i]-s[i-1]=1,s[i]-s[i]=-1 $交替这种形式。设前 4 4 4个元素为 a , b , c , d a,b,c,d a,b,c,d,那么可以想到如下构造: [ a , b , c , d , a + 1 , b − 1 , c + 1 , d − 1 , a + 2 , b − 2 , c + 2 , d − 2... ] [a,b,c,d,a+1,b-1,c+1,d-1,a+2,b-2,c+2,d-2...] [a,b,c,d,a+1,b−1,c+1,d−1,a+2,b−2,c+2,d−2...]即可。
代码:
#include <bits/stdc++.h>using namespace std;
const int MAXN = 2e5 + 5;
int ans[MAXN];void solve() {int n, k;cin >> n >> k;int flag1 = 1, num = 1, now = 1;while (now <= k) {if (flag1) {for (int i = now; i <= n; i += k) {ans[i] = num;++num;}} else {for (int i = now + ((n - now) / k) * k; i >= 1; i -= k) {ans[i] = num;++num;}}flag1 ^= 1;++now;}for (int i = 1; i <= n; i++)cout << ans[i] << " ";cout << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}
F.Microcycle (图论)
题意:
给出一张 n n n个点, m m m条边的无向简单图,图不一定联通,在其中寻找包含最小边的环,输出最小边的边权和环上的所有节点。
分析:
从小到大枚举边权,用并查集判断两个点是否在一个集合内,如果在,证明找到了在环内的最小边,从这两个点中任选一点出发开始 b f s bfs bfs,搜索并记录路径即可。
代码:
#include <bits/stdc++.h>using namespace std;
const int MAXN = 5e5 + 5;
vector<int> g[MAXN];struct Node {int w, u, v;friend bool operator<(const Node &a, const Node &b) {if (a.w != b.w)return a.w > b.w;return a.u < b.u;}
} edge[MAXN];int fa[MAXN];int get(int x) {if (fa[x] != x)fa[x] = get(fa[x]);return fa[x];
}void solve() {int n, m;vector<int> ans;queue<int> q;cin >> n >> m;for (int i = 1; i <= n; i++)g[i].clear();for (int i = 1; i <= n; i++)fa[i] = i;for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;edge[i] = {w, u, v};g[u].push_back(v);g[v].push_back(u);}sort(edge + 1, edge + m + 1);int a, b, tmp = 1e9;for (int i = 1; i <= m; i++) {auto [w, u, v] = edge[i];int tmp1 = get(fa[u]);int tmp2 = get(fa[v]);if (tmp1 == tmp2 && w < tmp) {a = u, b = v;tmp = w;}fa[tmp1] = tmp2;}q.push(a);vector<int> Depth(n + 1, 0);while (q.size()) {auto u = q.front();q.pop();for (auto v: g[u]) {if (Depth[v])continue;if (u == a && v == b)continue;if (v == a)continue;Depth[v] = Depth[u] + 1;q.push(v);}}int dep = Depth[b], fr = b;while (dep) {ans.push_back(fr);for (auto v: g[fr]) {if (Depth[v] == dep - 1) {dep--;fr = v;break;}}}ans.push_back(a);cout << tmp << " " << ans.size() << endl;for (auto v: ans)cout << v << " ";cout << endl;
}int main() {int T = 1;cin >> T;while (T--) {solve();}return 0;
}
G.Paint Charges (dp)
题意:
给定 n n n个格子, a i a_i ai表示这个格子可以使用的颜料数量。每次操作可以选定一个格子,并选择将 [ m a x ( i − a i + 1 , 1 ) , i ] [max(i-a_i+1,1),i] [max(i−ai+1,1),i]或者 [ i , m i n ( i + a i − 1 , n ) ] [i,min(i+a_i-1,n)] [i,min(i+ai−1,n)]的格子涂色,每个格子可以被涂色多次,询问将 [ 1 , n ] [1,n] [1,n]所有格子都涂上颜色的最少操作次数。
分析:
设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示当使用前 i i i个元素,最左侧未填充位置是 j j j ,最右侧已填充位置是 k k k,所需要的最小操作数。有以下三种情况:
- 不进行操作的状态转移: d p [ i ] [ j ] [ k ] = m i n ( d p [ i ] [ j ] [ k ] , d p [ i − 1 ] [ j ] [ k ] ) ; dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]); dp[i][j][k]=min(dp[i][j][k],dp[i−1][j][k]);
-
向左填充的状态转移,需要根据 i , j , k , l i,j,k,l i,j,k,l大小进行讨论。
-
向右填充的状态转移,需要根据 i , j , k , r i,j,k,r i,j,k,r大小进行讨论。
代码:
#include <bits/stdc++.h>using namespace std;
const int INF = 0x3f3f3f3f;
int a[105];
int dp[105][105][105];void solve() {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 0; i <= n; i++) {for (int j = 1; j <= n + 1; j++) {for (int k = 0; k <= n; k++) {dp[i][j][k] = INF;}}}dp[0][1][0] = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n + 1; j++) {for (int k = 0; k <= n; k++) {dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);int l = max(i - a[i] + 1, 1);if (l <= j) {int tmp1 = max(i, k);dp[i][tmp1 + 1][tmp1] = min(dp[i][tmp1 + 1][tmp1], dp[i - 1][j][k] + 1);}int r = min(i + a[i] - 1, n);if (j < i) {dp[i][j][max(k, r)] = min(dp[i][j][max(k, r)], dp[i - 1][j][k] + 1);} else {int tmp1 = max(k, r);dp[i][tmp1 + 1][tmp1] = min(dp[i][tmp1 + 1][tmp1], dp[i - 1][j][k] + 1);}}}}cout << dp[n][n + 1][n] << endl;
}int main() {int T = 1;cin >> T;while (T--) {solve();}return 0;
}
赛后交流
在比赛结束后,会在交流群中给出比赛题解,同学们可以在赛后查看题解进行补题。
群号: 704572101,赛后大家可以一起交流做题思路,分享做题技巧,欢迎大家的加入。
这篇关于Codeforces Round 923(Div.3) A~G的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!