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

这篇具有很好参考价值的文章主要介绍了[补题记录] 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,你可以将它任意排列,问是否能使得 

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

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。当字符串满足 [补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法,则这个字符串为 good。

你可以将 T 插入 S 的任意位置(也可以不插),问能否使得 S 为 good。

Thought/思路

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

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

当 S 不是 good 时,说明遇到了  [补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法,此时:

  • 如果 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。当字符串满足 [补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法,则这个字符串为 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,它们之间可以连接,则有:

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

若它们不能与城市 1 连接,则有:

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

将三条不等式整合,可得:

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

↓ 

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

↓ 

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

但是 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 后的城市,则有:

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

最后得出:

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法

[补题记录] Codeforces Round 906 (Div. 2)(A~D),补题记录,c++,图论,c语言,动态规划,排序算法,贪心算法文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 935 (Div. 3) - D. Seraphim the Owl (动态规划)

    大家排成 n 人的队列,从 i=1 号开始,向猫头鹰谢拉菲姆请教生命的意义。不幸的是,基里尔当时正忙着为这问题编写传说,所以他来得晚了一些,站在了 n 这个人之后,排在了队伍的最后。基里尔对这种情况完全不满意,于是他决定贿赂一些排在他前面的人。 对于队列中的

    2024年04月17日
    浏览(55)
  • Educational Codeforces Round 161 (Rated for Div. 2) E. Increasing Subsequences 动态规划逼近,二进制拆分补充,注意严格递增

    Problem - E - Codeforces 目录 推荐视频: 题意: 细节(我踩得没什么价值的坑): 思路: 对样例3 (X = 13)做解释: —————— 总思路: —————— 动态规划逼近: —————— 二进制拆分补充剩余: 核心代码:  E_哔哩哔哩_bilibili 其实有一些细节说的不是特别清楚好

    2024年02月22日
    浏览(38)
  • Educational Codeforces Round 161 (Rated for Div. 2) E题 动态规划逼近,二进制拆分补充,注意严格递增strictly increasing

    Problem - E - Codeforces 目录 推荐视频: 题意: 细节(我踩得没什么价值的坑): 思路: 对样例3 (X = 13)做解释: —————— 总思路: —————— 动态规划逼近: —————— 二进制拆分补充剩余: 核心代码:  E_哔哩哔哩_bilibili 其实有一些细节说的不是特别清楚好

    2024年01月24日
    浏览(42)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(54)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(43)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(36)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(43)
  • Codeforces Round 871 (Div. 4)

    给定n个长度为10的字符串,问其与codeforces字符串的对应下标字母不同的个数。 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 给定长度为n的数组,问连续相邻为0的最大长度 维护一个全局最大长度res,和当前连续序列的长度cnt。从前往后扫

    2024年02月03日
    浏览(51)
  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(45)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包