首页 > 其他分享 >Educational Codeforces Round 160 (Rated for Div

Educational Codeforces Round 160 (Rated for Div

时间:2024-01-26 19:13:55浏览次数:25  
标签:std boy Educational Rated int Codeforces while Lazy cnt

A Rating Increas

题目大意

给定一个数字,让我们拆分成两个数,这两个数满足以下条件:

  1. a < b.
  2. 两个数没有前缀0.

问:输出满足条件的数a , b.

解题思路

直接暴力循环这个数的位数次,若满足a < b,再判断两个数的位数和是否与拆分前相同.

代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve() {
    int n, cnt = 1, k = 0;
    std::cin >> n;
    int s = n;
    while (s) {
        k++;
        s /= 10;
    }
    int t = k;
    while (k--) {
        int w = n;
        int a = w / cnt, b = w % cnt;
        int x = a, y = b;
        int s1 = 0, s2 = 0;
        while (x) {
            s1++;
            x /= 10;
        }
        while (y) {
            s2++;
            y /= 10;
        }
        if (a < b && s1 + s2 == t) {
            std::cout << a << " " << b << endl;
            return;
        }
        cnt *= 10;
    }
    std::cout << -1 << endl;
}

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

B Swap and Delete

题目大意

给一个01字符串s,现在有以下操作:

  1. 交换s[i],s[j],此操作花费为0.
  2. 删除s[i],此操作花费一个金币.

将修改后的字符串记录为t.
问:至少花费多少金币,使得t[i] != s[i] (0 <= i <= t.size()).

解题思路

我们可以记一下有多少个0 和多少个1,
然后我们遍历一次字符串,check当前0的个数是否大于1的总数和当前1的个数是否大于0的总数

代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve() {
    std::string s;
    std::cin >> s;
    int s0 = 0, s1 = 0;
    for (auto i: s)
        s0 += (i == '0'), s1 += (i == '1');
    int cnt0 = 0, cnt1 = 0, ans = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        cnt0 += (s[i] == '0'), cnt1 += (s[i] == '1');
        if (s0 >= cnt1 && s1 >= cnt0)
            ans = std::max(ans, i + 1);
    }
    std::cout << (int) s.size() - ans << endl;
}

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

C Game with Multiset

题目大意

有两种查询类型:

  1. ADD x,即在集合中添加2^x的元素.
  2. GET w,即询问集合中的某子集之和,能否等于w.

解题思路

很显然,本题考查位运算,用数组模拟,其中cnt[i]表示集合中2^i的元素个数.

代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> cnt(32, 0ll);
    auto calc = [&](int x) {
        for (int i = 31; i >= 0; i--) {
            int l = 0, r = cnt[i], s = 0;
            while (l <= r) {
                int mid = (l + r + 1) >> 1;
                if (mid * (1 << i) <= x)
                    s = mid, l = mid + 1;
                else
                    r = mid - 1;
            }
            x -= (1 << i) * s;
        }
        std::cout << (x == 0 ? "YES" : "NO") << endl;
    };
    while (n--) {
        int t, v;
        std::cin >> t >> v;
        if (t == 1)
            cnt[v]++;
        else
            calc(v);
    }
}

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

标签:std,boy,Educational,Rated,int,Codeforces,while,Lazy,cnt
From: https://www.cnblogs.com/Lazyboyjdj/p/17990495

相关文章

  • Educational Codeforces Round 161 (Rated for Div
    ATrickyTemplate题目描述给一个数字n和三个长度为n的字符串a,b,c。找一个模板使得字符串a,b匹配,而c不匹配,是否存在这样一个模板.匹配的定义是:当模板字母为小写时,两个字符串字符相同,为大写时,两个字符不同,这样的两个字符串则匹配解题思路我们可以直接得出当a字符串......
  • hey_left 17 Codeforces Round 817 (Div. 4)
    题目链接A.把标准字符串和输入字符串排序,看是否相等#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;voidsolve(){intn;cin>>n;stringt;cin>>t;strings="Timur";sort(s.begin(),s.end());......
  • hey_left 16 Codeforces Round 827 (Div. 4)
    题目链接A.判最大的数是不是另外两个数的和#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;voidsolve(){inta,b,c;cin>>a>>b>>c;cout<<(max({a,b,c})==a+b+c-max({a,b,c})?"YES":"......
  • Codeforces 1667E Centroid Probabilities
    这个连边方式就可以理解为\(1\)为根,点\(u\)的父亲\(fa_u\)满足\(fa_u<u\)。重心有不止一种表示法,考虑用“子树\(siz\ge\lceil\frac{n}{2}\rceil\)最深的点”来表示重心。令\(m=\lceil\frac{n}{2}\rceil\),\(f_i\)为节点\(i\)的\(siz\gem\)的方案数。考虑枚......
  • Codeforces Round 920 (Div. 3)
    赛时过了A~E,表现分1738。感觉D~G都挺有意义拿出来说的。[D]VeryDifferentArray首先一个贪心的猜想是:如果A和B长度相同,那一个顺序一个逆序应该是最优的情况。思考下如何证明这个猜想。假如A和B的长度均为2,易证\(A_1\)<\(A_2\),\(B_1\)>\(B_2\)时最优......
  • CodeForces 1667E Centroid Probabilities
    洛谷传送门CF传送门首先需要了解重心的三种定义:删掉一个点后剩下子树大小\(\le\frac{n}{2}\)的点\(\sum\limits_{i=1}^n\text{dis}(u,i)\)最小的点最深的\(sz_u\ge\left\lceil\frac{n}{2}\right\rceil\)的点这道题我们使用第三种定义,也就是要统计\(i\)为最......
  • Codeforces round 919 (div2)
    Problem-A-Codeforces暴力枚举就可以;#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;vector<int>a;intn;signedmain(){int_;cin>>_;while(_--){a.clear();cin>>n;......
  • hey_left 15 Codeforces Round 835 (Div. 4)
    题目链接A.总和-最小值-最大值即为中间数#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){inta,b,c;cin>>a>>b>>c;cout<<a+b+c-min({a,b,c})-max({a,b,c})<<'\n';}signedmain(){io......
  • Codeforces Round 170 (Div. 1)A. Learning Languages并查集
    如果两个人会的语言中有共同语言那么他们之间就可以交流,并且如果a和b可以交流,b和c可以交流,那么a和c也可以交流,具有传递性,就容易联想到并查集,我们将人和语言看成元素,一个人会几种语言的话,就将这些语言和这个人所在的集合合并,最后求一下人一共在几个连通块中,连通块的个数-1就是答案,......
  • CodeForces 1010F Tree
    洛谷传送门CF传送门educational的。另一道类似的题是[ABC269Ex]Antichain(但是我还没写)。考虑令\(b_u=a_u-\sum\limits_{v\inson_u}a_v\)。那么\(\sum\limits_{i=1}^nb_i=a_1=x\),且\(\foralli\in[1,n],b_i\ge0\)。所以最后连通块内有\(y\)个点,那......