Educational Codeforces Round 160 (Rated for Div. 2)

发布时间:2023年12月20日

在这里插入图片描述

Educational Codeforces Round 160 (Rated for Div. 2)

Educational Codeforces Round 160 (Rated for Div. 2)

A. Rating Increase

题意:给定一个由数字字符组成的字符串,且无前导零,将其分割成ab两部分,b不能有前导零,拆分后的数字a是否可以严格小于数字b

思路:数据很小,可以暴力拆分,数字|字符串操作均可。这里是尽可能将数字靠前分割来判断分割后的两字符串。

AC code:

void solve(){
    string s; cin >> s;
    string cnt = "";
    int pos;
    cnt += s[0];
    for(int i = 1; i < s.size(); i ++){
        
       if(s[i] != '0'){
            pos = i;
            break;
       }
       cnt += s[i];
    }
    string tt = "";
    for(int i = pos; i < s.size(); i ++)
    tt += s[i];
    if(tt == cnt || tt.size() < cnt.size() || tt.size() == cnt.size() && tt < cnt){
        cout << "-1" << endl;
        return;
    }
    cout << cnt << " "<< tt << endl;
}

B. Swap and Delete

题意:给定01二进制字符串s,现在有两种操作:

  • 删除任一字符,成本为1;
  • 交换相邻的任意字符,成本为0;

将操作后的字符串定为t,字符串t与原字符串s左对齐对每一位进行比较,若均不相等则t为好字符串,空字符串默认为好字符串;

求操作的最小成本。

思路:首先分别记录01字符的数量,然后遍历字符串s,遍历时需要记录走过的可以交换的0和1,若前方有可交换的字符时,就减去该字符,否则查看剩余01字符,选择交换然后同时减去两字符并将当前字符记录到交换字符中。

AC code:

void solve(){
    string s; cin >>  s;
    n = s.size();
    int zero = 0, one = 0;
    for(int i = 0; i < n; i ++){
        if(s[i] == '0') zero ++;
        else one ++;
    }
    int cnt_0 = 0, cnt_1 = 0;
    for(int i = 0; i < n; i ++){
        if(s[i] == '0'){
            if(cnt_1){
                cnt_1 --;
            }else if(one){
                one --;
                zero --;
                cnt_0 ++;
            }else{
                cout << n - i << endl;
                return;
            }
        }else{
            if(cnt_0){
                cnt_0 --;
            }else if(zero){
                one --;
                zero --;
                cnt_1 ++;
            }else{
                cout << n - i << endl;
                return;
            }
        }
    }
    cout << 0 << endl;
}

C. Game with Multiset

题意:最初有一个空集,需要处理两种操作:

  • 在集合中添加 2 x 2^x 2x
  • 查询是否存在集合中的和为v

思路:位运算,每次添加的元素均为二进制的x位,记录二进制中存入的位,当查询时只需要从后往前遍历二进制数,看当前位存储的是否足够,不够就*2累加到下一位尝试减去。

AC code:

map<int, int> mp, cnt;
 
void solve(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        int t, v; cin >> t >> v;
        if(t == 1){
            mp[v] ++;
        }else{
            int now = 0;
            for(int i = 30; i >= 0; i --){
                int pos = v >> i & 1;
                pos += now * 2;
                if(mp[i] < pos) now = pos - mp[i];
                else now = 0;
            }
            if(now) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
    }
}
文章来源:https://blog.csdn.net/maisui12138/article/details/135092321
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。