Codeforces Round 923(Div.3) A~G

2024-02-15 13:20
文章标签 codeforces round div.3 923

本文主要是介绍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 1k的排列。

分析:

对于 1 − k 1-k 1k的数字,如果只在 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 li,jr,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+k1n i i i,每个区间 [ i − i + k − 1 ] [i-i+k-1] [ii+k1]的和中的最大值和最小值相差不超过 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,b1,c+1,d1,a+2,b2,c+2,d2...]即可。

代码:

#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(iai+1,1),i]或者 [ i , m i n ( i + a i − 1 , n ) ] [i,min(i+a_i-1,n)] [i,min(i+ai1,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[i1][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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/711501

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接:点击打开链接 C. 题目链接:点击打开链接 解题思路: 对于给定的字符串,取出现次数最多的字母(可以同时有多个)。由这些字母组成长度为n的字符串,求有多少种组合。最后用数学知识即可。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <climits>

MemSQL Start[c]UP 2.0 - Round 1A(构造)

题目链接:http://codeforces.com/problemset/problem/452/A 解题思路: 打个表暴力查找匹配。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#include <strin

Codeforces Round #281 (Div. 2)A(构造+暴力模拟)

题目链接:http://codeforces.com/problemset/problem/493/A 解题思路: 暴力的判断,分三种情况去判断即可。注意如果之前已经被罚下场后,那么在后面的罚下情况不应该算在输出结果内。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <co

Codeforces Round #182 (Div. 2)A(水题)

题目链接:http://codeforces.com/contest/302/problem/A 解题思路: 只要通过重新排列使区间内和为0即是1,否则是0. 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#inc