当前位置：首页 > news >正文

Educational Codeforces Round 160 (Div. 2) A~C(D,E更新中...)

news 2025/6/27 20:12:38

A.Rating Increase（思维）

题意：

给出一个仅包含数字的字符串 $s$ ，要求将该字符串按以下要求分成左右两部分 $a, b$ ：

两个数字均不包含前导 $0$
两个数字均大于 $0$
$b > a$

如果有多个答案，输出任意一个均可。

分析：

既然题目要求 $b > a$ ，且不能包含前导 $0$ ，那么，将字符串中第一个数字以及之后的连续的 $0$ 分配给 $a$ ，剩余部分属于 $b$ ，然后判断 $b$ 是否大于 $a$ 即可。

注：使用字符串比较时要注意不能直接使用 $>$ 进行比较，否则比较的是两个字符串的字典序，而不是数字大小。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5e2;vector<int> V[30];void solve() {string s;cin >> s;string a = "", b = "";int i, len = s.size();for (i = 0; i < len; i++) {if (i != 0 && s[i] != '0') break;a.push_back(s[i]);}for (; i < len; i++) {b.push_back(s[i]);}if (b.size() > a.size() || (b.size() == a.size() &&  a < b)) {cout << a << ' ' << b << endl;} else {cout << "-1" << endl;}
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

B.Swap and Delete（思维）

题意：

给出仅包含 $01$ 的字符串 $s$ ，在若干次操作该字符串变为字符串 $t$ :

花费一个金币，并删除字符串中一个字符
免费操作，任意交换字符串中的字符

问，最少花费多少金币，能够使得最后的得到的字符串 $t$ 与原字符串 $s$ 中等长的前缀字符串相同下标的元素全部不同。

分析：

既然操作2不需要花费金币，那么肯定要尽可能的使用操作二。

因此，先记录字符串 $s$ 中 $1$ 和 $0$ 的数量，然后从前往后判断，如果当前 $s_i = 1$ ，那么就把后面的 $0$ 交换过来，并将记录的 $0$ 数量减一，如果交换前发现此时后面已经没有 $0$ 了，那么无论怎么交换，均无法使得这个位置上的元素与原字符串 $s$ 不同，因此所有后面的字符均需使用操作 $1$ 删除，共消耗 $n - i$ 个金币。

$s_i = 0$ 的情况同理。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5e2;void solve() {string s;cin >> s;int n = s.size();int one = 0, zero = 0;int ans = n;for (int i = 0; i < n; i++) {if (s[i] == '0') {zero++;} else {one++;}}for (int i = 0; i < n; i++) {if (s[i] == '1') {if (zero == 0) {cout << n - i << endl;return;}zero--;} else {if (one == 0) {cout << n - i << endl;return;}one--;}}cout << 0 << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

C.Game with Multiset（数学）

题意：

给出一个允许装下重复元素的集合，并有以下两种操作：

ADD x:将 $2^{x}$ 放入集合
GET w:询问能否取出集合中的若干元素，满足这些元素的总和为 $w$

分析：

对于操作 $1$ ，使用数组 $c n t [i]$ 表示存放的 $2^{i}$ 的元素数量。

对于操作 $2$ ，从大到小遍历集合中的元素，通过运算得到当前剩余数字还能减去多少 $2^{i}$ ，并尽可能多的减去 $2^{i}$ 。如果遍历结束后剩余数字为 $0$ 表示可以组成，不为 $0$ 表示不能组成。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5e2;int mul_set[35];void add(int x) {mul_set[x]++;
}void get(int x) {for (int i = 29; i >= 0; i--) {int cnt = x / (1 << i);//计算最多能减去多少个x -= min(cnt, mul_set[i]) * (1 << i);//注意减去的数量不能比集合中存的数量多}if (x == 0) cout << "Yes" << endl;else cout << "No" << endl;
}int main() {int Case;cin >> Case;while (Case--) {int op, x;cin >> op >> x;if (op == 1) add(x);else get(x);}return 0;
}