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,你可以将它任意排列,问是否能使得
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。当字符串满足 ,则这个字符串为 good。
你可以将 T 插入 S 的任意位置(也可以不插),问能否使得 S 为 good。
Thought/思路
如果 S 是 good,直接输出答案 YES。
如果 S 不是 good,那么 T 必须要为 good,否则直接输出答案 NO。
当 S 不是 good 时,说明遇到了 ,此时:
- 如果 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。当字符串满足 ,则这个字符串为 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,它们之间可以连接,则有:
若它们不能与城市 1 连接,则有:
将三条不等式整合,可得:
↓
↓
但是 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 后的城市,则有:
最后得出:
↓文章来源:https://www.toymoban.com/news/detail-739485.html
↓
文章来源地址https://www.toymoban.com/news/detail-739485.html
Code/代码
#include "bits/stdc++.h"
#define int long long
struct 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)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!