Codeforces Round 970 (Div. 3)（A~H)

2024-09-04 22:20
文章标签 codeforces round div 970

本文主要是介绍Codeforces Round 970 (Div. 3)（A~H)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

​​​​​题目链接​​​​​​​​​​​​​​​​​​​​​

A

当 a 为奇数的时候，无论如何配对都无法将最后一个 1 减去；
当 a 为偶数的时候，b 也偶数，自然可以内部通过加减操作变成 0；当 b 为奇数的时候，只有当 a = 0 的时候，无法变成 0，因为 a 为偶数，且不为 0，那么一定可以拿出两个 1 和 b 中的一个配对，然后 a 和 b 都为偶数了。

代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;void slove()
{int a, b; cin >> a >> b;if (a & 1) cout << "No" << endl;else if (a == 0 && b & 1) cout << "NO" << endl;else cout << "YES" << endl;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) slove();return 0;
}

B

首先判断长度 n 是否可以构成一个正方形；字符串映射为一个二维矩阵，外围为 1，中间全都为 0，那么可以暴力枚举这个二维矩阵，判断该单元格是否为最外围的格子的依据是：判断 i、j 是否等于 1 或 a （a 为这个正方形的边长，设字符串下标从 1 开始）

代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;void slove()
{int n; cin >> n;string str; cin >> str;str = " " + str;int len = sqrt(n);if (len * len != n) { cout << "NO" << endl; return; }bool flag = true;for (int i = 1; i <= len; i++){for (int j = 1; j <= len; j++){if (i == 1 || i == len || j == 1 || j == len){if (str[(i - 1) * len + j] != '1')flag = false;}else if (str[(i - 1) * len + j] != '0')flag = false;}}if (flag) cout << "YES" << endl;else cout << "NO" << endl;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) slove();return 0;
}

C

为了使得数组长度更长，数组中的元素值需要尽可能小。
第一个条件是数组中的元素需要升序，第二个条件是相邻元素的差值也得升序。
为了使长度最长，第一个元素自然等于 L，差值也需要尽可能小且升序，那么只能是公差为 1 的等差数列。
设长度为 n，那么等差数列的项数为 n - 1，且 a1 = L，an <= R。

 可以使用二分求解 n，当然也可以根据数据范围暴力枚举 n。

二分代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;void slove()
{int a, b; cin >> a >> b;int l = 1, r = 1e9;while (l < r){int mid = l + r + 1>> 1;if ((LL) mid * (mid - 1) <= 2 * (b - a)) l = mid;else r = mid - 1;}cout << l << endl;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) slove();return 0;
}

暴力代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;
using LL = long long;void slove()
{LL l, r; cin >> l >> r;LL y = 2 * (r - l);LL x = sqrt(y);LL res = 0;for (int i = x; i <= 1e5; i++)if ((LL) i * (i - 1) <= y)res = i;cout << res << endl;
}  int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) slove();return 0;
}

D

对于任意 i，可以到达 a[i] 位置，记录 i 可以到达的位置，将这些位置看作一个集合，以集合中任意一个为起点，且可以到达集合中任意一个位置，那么也可以得到集合中所有的黑色。
使用并查集，使用一个 cnt 数组记录以 i 为根节点的集合中有多少黑色，每次在合并节点的时候维护 cnt 数组
注意：下标需要从 1 开始

代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
using LL = long long;const int N = 2e5 + 10;
int p[N], cnt[N];int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}void slove()
{memset(cnt, 0, sizeof cnt);int n; cin >> n;for (int i = 0; i <= n; i++) p[i] = i;vector<int> a(n + 10);for (int i = 1; i <= n; i++) cin >> a[i];string str; cin >> str;str = " " + str;for (int i = 1; i <= n; i++)cnt[i] = str[i] == '0';for (int i = 1; i <= n; i++){int pa = find(i), pb = find(a[i]);if (pa != pb){p[pa] = pb;cnt[pb] += cnt[pa];}}for (int i = 1; i <= n; i++){int pa = find(i);cout << cnt[pa] << " ";}cout << endl;}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) slove();return 0;
}

E

最多只能执行删除操作一次，且最后字符串长度必须为偶数，所以删除操作在长度为奇数时执行。
当长度为偶数时，不执行删除操作。那么不需要替换的是出现次数最多的字母。
当长度为奇数时，必须执行删除操作。  枚举删除的位置 i，i 之前的奇偶不需要转变， i 之后的奇数位置变为偶数位置，偶数位置变为奇数位置。
 

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
using LL = long long;void slove()
{int n; cin >> n;string str; cin >> str;if (n & 1){vector<vector<int>> pre(2, vector<int>(26));vector<vector<int>> suf(2, vector<int>(26));for (int i = n - 1; i >= 0; i--)suf[i % 2][str[i] - 'a']++;int ans = 1e9;for (int i = 0; i < n; i++){suf[i % 2][str[i] - 'a']--;int res = n;for (int k = 0; k <= 1; k++){int maxv = 0;for (int j = 0; j < 26; j++){maxv = max(maxv, pre[k][j] + suf[1 - k][j]);  // 后面奇偶互换}res -= maxv;}pre[i % 2][str[i] - 'a']++;ans = min(ans, res);}cout << ans << endl;}else{vector<vector<int>> a(2, vector<int>(26));for (int i = 0; i < n; i++)a[i % 2][str[i] - 'a']++;int res = n;for (int i = 0; i <= 1; i++){int maxv = 0;for (int j = 0; j < 26; j++)maxv = max(maxv, a[i][j]);res -= maxv;}cout << res << endl;}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) slove();return 0;
}

F

这题就是一个逆元的使用，主要溢出就行

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7;LL inv(LL a)
{LL res = 1;int k = MOD - 2;while (k){if (k & 1) res = res * a % MOD;a = a * a % MOD;k >>= 1;}return res;
}void slove()
{int n; cin >> n;LL m = 0;vector<int> a(n + 10);for (int i = 0; i < n; i++) {cin >> a[i];m += a[i];}LL res = 0;for (int i = 0; i < n; i++){m -= a[i];res = (res + (m % MOD)* (LL) a[i] % MOD) % MOD;}LL Q = ((LL) n * (n - 1) / 2) % MOD;cout << (res * inv(Q) % MOD) << endl;
}int main()
{int t; cin >> t;while (t--) slove();return 0;
}

G

进行任意次操作之后，最小可以得到一个由最大公约数 g 的整数倍数组。
为了求得最小mex，需要尽量将数组中的元素不重复的最小，那么就是由 g 构成的整数倍数组
相邻两个元素相差 g - 1 个元素，那么可以枚举得到最小 mek。
需要特别处理只有一个元素的情况。

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}int main()
{int t; cin >> t;while (t--) {int n, k; cin >> n >> k;vector<LL> a(n + 10, 0);int g = 0;for (int i = 0; i < n; i++){cin >> a[i];g = gcd(g, (int) a[i]);}if (n == 1){if (a[0] >= k)cout << k - 1 << endl;else {cout << k << endl;}continue;}for (int i = 0; i < n; i++)a[i] = (LL) i * g;LL res = 0;for (int i = 1; i < n; i++){if (k <= g - 1) break;k -= g - 1;res = a[i];}cout << res + k << endl;}return 0;
}

H

对于任意一个数组中的大于 x 元素，可以执行任意次减 x 的操作，那么最后的结果是 mod(x) 的值。为了使中位数最小，自然每一个元素都得减 x 直至最小，所以中位数的取值范围 = [0, x - 1]。

二分答案，当 mid 前面的元素个数大于数组长度的一半时，可以缩小 r。更加题目定义，当数组长度为偶数时，中位数取后面那个，那么二分目标值 t = n / 2 + 1。

求某个值前面的元素个数，可以使用前缀和。预处理每一个元素出现的次数，再枚举 n，因为 a[i] <= n；计算出现次数的前缀和。
由于最终出现的次数是基于 mod(x)，那么可以分段处理，枚举每一段的起点，也就是说 x 的整数倍。

代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;void slove()
{int n, q; cin >> n >> q;vector<int> a(n + 10, 0);vector<LL> cnt(n + 10, 0);for (int i = 0 ; i < n; i++){cin >> a[i];cnt[a[i]]++;}for (int i = 1; i <= n; i++){cnt[i] += cnt[i - 1];}vector<int> res(n + 10, 0);for (int x = 1; x <= n; x++){int l = 0, r = x;while (l < r){int mid = l + r >> 1;LL c = cnt[mid];for (int k = 1; k * x <= n; k++){c += cnt[min(k * x + mid, n)] - cnt[k * x - 1];}int tmp = n / 2 + 1;if (c < tmp) l = mid + 1;else r = mid;}res[x] = r;}while (q--){int x; cin >> x;cout << res[x] << " ";}cout << endl;}int main()
{int t; cin >> t;while (t--) slove();return 0;
}

这篇关于Codeforces Round 970 (Div. 3)（A~H)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1137193。

相关文章

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

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)小记

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凸包 （最终写法）

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 判断多边形是否在凸包内

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

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

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
阅读更多...
CSS实现DIV三角形

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor
阅读更多...
创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;
阅读更多...
Codeforces Round 971 (Div. 4) (A~G1)

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>
阅读更多...
CF#271 (Div. 2) D.（dp）

CF#271 (Div. 2) D.（dp）

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/474/problem/D We s
阅读更多...
CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/488/problem/B There
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2