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

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$:

1. 花费一个金币，并删除字符串中一个字符

2. 免费操作，任意交换字符串中的字符

问，最少花费多少金币，能够使得最后的得到的字符串$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（数学）

题意：

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

1. ADD x:将$2^x$放入集合

2. GET w:询问能否取出集合中的若干元素，满足这些元素的总和为$w$

分析：

对于操作$1$，使用数组$cnt[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;
}

D,E 更新中…

学习交流

以下为学习交流QQ群，群号： 546235402，每周题解完成后都会转发到群中，大家可以加群一起交流做题思路，分享做题技巧，欢迎大家的加入。