[补题记录] Codeforces Round 906 (Div. 2)（A~D）

2023-11-02 17:52
文章标签 记录 codeforces round div 补题 906

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

URL：https://codeforces.com/contest/1890

目录

A

Problem/题意

Thought/思路

Code/代码

B

Problem/题意

Thought/思路

Code/代码

C

Problem/题意

Thought/思路

Code/代码

D

Problem/题意

Thought/思路

Code/代码

A

Problem/题意

给出一个数组 A，你可以将它任意排列，问是否能使得 

A_i + A_{i+1}=A_{i+1}+A_{I+2}=K

Thought/思路

化简题目给的要求，我们可以发现：

  • a1 = a3、a3 = a5；
  • a2 = a4、a4 = a6；

因此只要有第三种数出现，肯定不对。

两种数的数量不等，也不对。

特别要注意，只有一种数则直接正确。

Code/代码

#include "bits/stdc++.h"int n, a[107];void solve() {std::cin >> n;std::set <int> num;std::map <int, int> cnt;bool flag = true;for (int i = 1; i <= n; ++ i) {std::cin >> a[i];num.insert(a[i]);if (num.size() > 2) {flag = false;} else {cnt[a[i]] ++;}}if (num.size() == 1) {std::cout << "Yes\n";return;}if (flag) {int a = *num.begin(); num.erase(a);int b = *num.begin();if (n % 2 == 1) {if (std::abs(cnt[a] - cnt[b]) == 1) {std::cout << "Yes\n";} else {std::cout << "No\n";}} else {if (cnt[a] == cnt[b]) {std::cout << "Yes\n";} else {std::cout << "No\n";}}} else {std::cout << "No\n";}
}signed main() {int t; std::cin >> t;while (t--) {solve();}
}

B

Problem/题意

给出 2 个 01 字符串 S、T。当字符串满足 S_i \neq S_{i+1}，则这个字符串为 good。

你可以将 T 插入 S 的任意位置（也可以不插），问能否使得 S 为 good。

Thought/思路

如果 S 是 good，直接输出答案 YES。

如果 S 不是 good，那么 T 必须要为 good，否则直接输出答案 NO。

当 S 不是 good 时，说明遇到了  S_i = S_{i+1} = 0/1，此时：

  • 如果 Si = 0，那么 T 必须要满足头尾都是 1；
  • 如果 Si = 1，那么 T 必须要满足头尾都是 0；

所以可以得出：

  • 若 T 头尾不相同，直接输出答案 NO；
  • 若需要插入时，Si != T[0]，直接输出答案 NO；

经过以上判断后，则输出 YES。

Code/代码

#include "bits/stdc++.h"int n, m;
std::string s, t;void solve() {std::cin >> n >> m;std::cin >> s >> t;bool flag = true;for (int i = 0; i <= n - 2; ++ i) {if (s[i] == s[i + 1]) {flag = false;}}if (flag) {std::cout << "YES\n";return;}for (int i = 0; i <= m - 2; ++ i) {if (t[i] == t[i + 1]) {std::cout << "NO\n";return;}}if (t[0] != t[m - 1]) {std::cout << "NO\n";return;}for (int i = 0; i <= n - 2; ++ i) {if (s[i] == s[i + 1]) {if (s[i] == t[0]) {std::cout << "NO\n";return;}}}std::cout << "YES\n";
} signed main() {int t; std::cin >> t;while (t --) {solve();}
}

C

Problem/题意

给出 1 个 01 字符串 S。当字符串满足 S_i \neq S_{n - i + 1}，则这个字符串为 good。

你可以将 "01" 插入 S 的任意位置（也可以不插），位置可以从 0 开始。

问能否使得 S 为 good。

若能，输出插入序列，若不能，输出 -1。

Thought/思路

因为要求对称位置不相等，所以 n 为奇数时，直接输出 -1。

因为每次插入的是 01，因此若一开始 01 数量不相等，直接输出 -1。

考虑到，若当前 i 之前的位置，都已经与对称位置不同，那么在 [i, n - i + 1] 中任意位置插入，都不会对前面的插入有影响，因此我们直接 L、R 双指针判断即可。

当对称位相等时，说明需要插入 01，此时有：

  • 若 S[L] = 1，说明必须将 01 插入到 L 的左边；
  • 若 S[L] = 0，说明必须将 01 插入到 R 的右边；

插入后就是移动 L、R，以及拼接新字符串了，可以自己想一下。

Code/代码

#include "bits/stdc++.h"int n;
std::string s;void solve() {std::cin >> n >> s;s = "#" + s;if (n % 2 == 1) {std::cout << -1 << "\n";return;}std::map <int, int> cnt;for (int i = 1; i <= n; ++ i) {cnt[s[i] - '0'] ++;}if (cnt[0] != cnt[1]) {std::cout << -1 << "\n";return;}std::vector <int> ans;int l = 1, r = n;while (l + 1 != r) {if (s[l] == s[r]) {if (s[l] == '1') {ans.push_back(l - 1);std::string a = s.substr(1, l - 1);std::string b = s.substr(l, n - l + 1);//std::cout << "a=" << a << " b=" << b << " ";s = "#" + a + "01" + b;l ++;r += 2; r --;}else if (s[l] == '0') {ans.push_back(r);std::string a = s.substr(1, r);std::string b = s.substr(r + 1, n - (r + 1) + 1);//std::cout << "a=" << a << " b=" << b << " ";s = "#" + a + "01" + b;r += 2; r --;l ++;}n += 2;} else {l ++;r --;}//std::cout << "l=" << l << " r=" << r << " s=" << s << "\n";}std::cout << ans.size() << "\n";for (auto x : ans) std::cout << x << " ";std::cout << "\n";
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);int t; std::cin >> t;while (t --) solve();
}

D

Problem/题意

一个国家有 N 个城市，每个城市有 Ai 人，现在要为这个国家修路，当我们想连接城市 i 和城市 j 时，有一个整数 C，需要满足：

  • 令城市 i 和它已经连通的城市，总人口为 Si；
  • 令城市 j 和它已经连通的城市，总人口为 Sj；
  • 当 Si + Sj >= i * j * C 时，则可以在 i 和 j 之间修路；

问能否将 N 个城市连通。 

Thought/思路

很容易想到，当我们使用城市 1 去连接其他城市时，更加容易成功。

需要考虑的是：怎么知道用 1 连接完它能连接的城市后，就已经是最大能连接的数量了。

假设现在有城市 X、Y，它们之间可以连接，则有：

A_X + A_Y \geqslant X * Y *C

若它们不能与城市 1 连接，则有：

A_X + A_1 < X*C

A_Y + A_1 < Y*C

将三条不等式整合，可得：

A_X +A_Y+ 2*A_1 < C*(X+Y)

↓ 

X*Y*C+ 2*A_1 < C*(X+Y)

↓ 

X*Y+ \frac{2*A_1}{C} < X+Y

但是 X、Y 显然是大于 1 的，该不等式不成立。

因此 X、Y 若能连接，则它们一定可以和城市 1 相连。

回到我们最开始的想法：使用城市 1 去连接其他城市时，更加容易连接成功。因此我们可以使用 i * C - A[i] 升序排序，排在前面的更容易与 1 相连。

假设此时 1 已经连接了一些城市，遇到一个城市 M，若 1 不能与城市 M 相连，那么就一定失败了，因为：

  • 若 M 都不能与 1 相连，那 M 后面的城市也一定不能与 1 相连；
  • 既然 M 后面的城市连 1 都连不上，那么肯定也连不上 1 已经连上的城市；

这也是可以证明的，根据上面的条件，假设 M 不能与 1 相连，N 为 M 后的城市，则有：

M < N

A_M + A_1 < M * C

N*C-A_N\geq M*C-A_M

最后得出：

A_N + A_1 < A_N +M*C-A_M

↓

A_N+A_1< A_N + N*C-A_N

↓

A_N+A_1< N*C

Code/代码

#include "bits/stdc++.h"#define int long longstruct node {int id, v;bool operator < (const node &t) const {return v < t.v;}
};int n, c, a[200007];void solve() {std::cin >> n >> c;std::vector <node> s(n + 1);for (int i = 1; i <= n; ++ i) {std::cin >> a[i];s[i] = {i, i * c - a[i]};}std::sort(s.begin() + 2, s.end());int sum = a[1];bool flag = true;for (int i = 2; i <= n; ++ i) {int id = s[i].id;sum += a[id];if (sum < id * c) flag = false;}	if (flag) std::cout << "YES\n";else std::cout << "NO\n";
}signed main() {int t; std::cin >> t;while (t --) solve();return 0;
}

这篇关于[补题记录] Codeforces Round 906 (Div. 2)（A~D）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...
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
阅读更多...
记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪（un-tracking）文件重新跟踪（re-tracking）文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法，现在我们已经有了一个仓库，并从这个仓
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
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
阅读更多...
perl的学习记录——仿真regression

perl的学习记录——仿真regression

1 记录的背景 之前只知道有这个强大语言的存在，但一直侥幸自己应该不会用到它，所以一直没有开始学习。然而人生这么长，怎就确定自己不会用到呢？ 这次要搭建一个可以自动跑完所有case并且打印每个case的pass信息到指定的文件中。从而减轻手动跑仿真，手动查看log信息的重复无效低质量的操作。下面简单记录下自己的思路并贴出自己的代码，方便自己以后使用和修正。 2 思路整理 作为一个IC d
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2