[补题记录] Educational Codeforces Round 160 (Rated for Div. 2)（A~C）

URL：https://codeforces.com/contest/1913/problem/D

目录

A

Problem/题意

Thought/思路

Code/代码

B

Problem/题意

Thought/思路

Code/代码

C

Problem/题意

Thought/思路

Code/代码

---

A

Problem/题意

给一个长度最长为 8 的字符串，将其分割成两部分，求是否存在无前导零的两个数 a、b，且 a < b。

Thought/思路

模拟。

Code/代码

#include "bits/stdc++.h"

void solve() {
	std::string s; std::cin >> s;

	bool flag = false;
	for (int i = 1; i < s.length(); ++ i) {
		int a = std::stoi(s.substr(0, i));
		int b = std::stoi(s.substr(i, s.length() - i));
		if (a < b and s[i] != '0') {
			std::cout << a << " " << b << "\n";
			flag = true;
			break;
		}
	}

	if (!flag) {
		std::cout << "-1\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();
	return 0;
}

B

Problem/题意

给一个 01 字符串 s，进行下面两个操作：

• 删除 s 中任意一个字符，代价为 1；
• 交换 s 中任意两个字符，代价为 0；

操作后获得字符串 t，问最小的操作代价，能使得 t 的每一位不等于 s 的每一位。

Thought/思路

因为删除 s 中的字符后，得到的 t 会变短，所以我们最后一定是考虑前某几位。

那么就可以先保证前面的字符相反，当遇到某个字符，没有足够的 0 或 1 可以填补时，就说明最长的 t 就到这了。

Code/代码

#include "bits/stdc++.h"

void solve() {
	std::string s; std::cin >> s;

	int n1 = 0, n0 = 0;
	for (int i = 0; i < s.length(); ++ i) {
		if (s[i] == '1') n1 ++;
		if (s[i] == '0') n0 ++;
	}

	std::string t = "";
	for (int i = 0; i < s.length(); ++ i) {
		if (s[i] == '0') {
			if (n1 > 0) {
				t += "1";
				n1 --;
			} else {
				t += "0";
				n0 --;
			}
		} 
		if (s[i] == '1') {
			if (n0 > 0) {
				t += "0";
				n0 --;
			} else {
				t += "1";
				n1 --;
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < s.length(); ++ i) {
		if (s[i] == t[i]) {
			ans = s.length() - i;
			break;
		}
	}

	std::cout << ans << "\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();
	return 0;
}

C

Problem/题意

给一个空的可重复集合，有 2 种询问：

ADD v，向集合中添加 pow(2, v)；

GET w，询问集合中是否有子集可以求和等于 w；

Thought/思路

由 v 的范围可以想到需要从位来分析。

一个基础的想法是，要满足 w 能求和出来，则 w 的每一位为 1 的位置，集合中必须要有数在这一位为 1。

那么问题就是，当处理了第 i 位后，怎么做出 i + 1 等等更高位的判断。

我们只需要在处理完第 i 位后，将第 i 位多余的 1，进位到 i + 1 位，这代表着 i + 1 位可以的得到这么多的补充，这样就可以保证，某一位一定是基于最优的情况下去判断的。

Code/代码

#include "bits/stdc++.h"

int num[31];

void solve() {

	int t, v; std::cin >> t >> v;
	if (t==1) {
		int value = std::pow(2, v);
		for (int i = 0; i < 30; ++ i) {
			int k = (value >> i) & 1;
			if (k == 1) num[i] ++;
		}
	}
	
	if (t==2){
		bool flag = true;
		std::vector <int> tmp(31, 0);
		for (int i = 30; i >= 0; -- i) {
			tmp[i] = num[i];
		}
		for (int i = 0; i < 30; ++ i) {
			int k = (v >> i) & 1;
			if (k == 1) {
				if (tmp[i] >= 1) {
					tmp[i] --;
				} else {
					flag = false;
					break;
				}
			}
			tmp[i + 1] += tmp[i] / 2; // 给下一位增加
		}
		if (flag) std::cout << "YES\n";
		else std::cout << "NO\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();
	return 0;
}