526互联

Educational Codeforces Round 160 (Rated for Div. 2) A~C

发布时间 2023-12-19 14:05:48作者: -37-

A. Rating Increase

题意：

将一个字符串分成两个整数a和b，要求没有前导0，且a < b

思路：

遍历字符串s，若当前位置不是0，则拆分字符串，比较大小

// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
// #include <queue>
// #include <map>
// #include <set>
using namespace std;

#define PIC 3.14159265358979
#define PI acos(-1)

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e3 + 10;
const int mod1 = 1e9 + 7;
const int mod9 = 998244353;
const int INF = 1e9;

void solve() {
    string s; cin >> s;
    int n = s.size();

    for (int i = 1; i < n; i++) {
        if (s[i] != '0') {
            string a = s.substr(0, i);
            string b = s.substr(i, n - i);
            if (atoi(a.c_str()) < atoi(b.c_str())) {
                cout << a << ' ' << b << '\n';
                return;
            }
        }
    }
    cout << -1 << '\n';
    return;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; 
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B. Swap and Delete

题意：

给定一个只包含0和1的字符串，可以进行以下操作：

  1. 删除一个字符串，消耗1金币
  2. 交换任意两个字符，不消耗金币

求将操作后的字符串与原字符串每一位都不相同的最少金币数

思路：

既然可以交换任意两个字符，且不消耗金币，那就说明可以任意排列字符串，那就先记录0和1的个数，在遍历一遍原字符串，原来字符串是0的位置放1，是1的位置放0，最后若是某一个数量不够，那么剩下的只能删除了

// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
// #include <queue>
// #include <map>
// #include <set>
using namespace std;

#define PIC 3.14159265358979
#define PI acos(-1)

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e3 + 10;
const int mod1 = 1e9 + 7;
const int mod9 = 998244353;
const int INF = 1e9;

void solve() {
    string s; cin >> s;
    int n = s.size();

    int n0 = count(s.begin(), s.end(), '0');
    int n1 = count(s.begin(), s.end(), '1');

    for (int i = 0; i < n; i++) {
        bool tag = 0;
        if (s[i] == '0' && n1 > 0) {
            n1--;
            tag = 1;
        }
        if (s[i] == '1' && n0 > 0) {
            n0--;
            tag = 1;
        }

        if (!tag) {
            cout << n1 + n0 << '\n';
            return;
        }
    }
    cout << 0 << '\n';
    return;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; 
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. Game with Multiset

题意：

有m次操作，操作有两种

  1. ADD(x)：在集合中添加\(2^x\)
  2. GET(x)：查询集合中的元素能否相加组成x

空集为0

思路：

贪心，集合中从大到小遍历，若元素比x小则减去x中有该元素的个数和集合中有的个数的最小值乘以该元素，x -= min((x / (1 << i)), mp[i]) * (1 << i)

// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
// #include <queue>
#include <map>
// #include <set>
using namespace std;

#define PIC 3.14159265358979
#define PI acos(-1)

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e3 + 10;
const int mod1 = 1e9 + 7;
const int mod9 = 998244353;
const int INF = 1e9;

void solve() {
    int t; cin >> t;
    map<LL, LL> mp;

    while (t--) {
        LL a, b; cin >> a >> b;
        if (a == 1) {
            mp[b]++;
        } else {
            if (b == 0) {
                cout << "YES" << '\n';
                continue;
            } else {
                for (int i = 30; i >= 0; i--) {
                    if (b >= (1 << i)) {
                        LL cnt = b / (1 << i);
                        b -= min(cnt, mp[i]) * (1 << i);
                    }
                }
                if (b  == 0) {
                    cout << "YES" << '\n';
                    continue;
                }
            }
            cout << "NO" << '\n';
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; 
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}