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;
}
