Educational Codeforces Round 75 (Rated for Div. 2)

Educational Codeforces Round 75 (Rated for Div. 2)

A. Broken Keyboard

• 思路：最开始没搞清楚题意瞎搞 只需要判断前后两连续字符是否相同 不同则将前一个存入vector中 排序去个重输出即可

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

int t;
string s;
vector<char> res;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t -- ){
        cin >> s;
        if (s.length() == 1){
            cout << s[0] << "
";
            continue;
        }
        res.clear();
        int i = 1;
        if (s[0] != s[1])
            res.push_back(s[0]);
        else
            i = 2;
        for (; i < s.length(); i ++ ){
            if (s[i] == s[i + 1])
                i ++ ;
            else
                res.push_back(s[i]);
        }
        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());
        for (int i = 0; i < res.size(); i ++ )
            cout << res[i];
        cout << "
";
    }
    return 0;
}

B. Binary Palindromes

• 思路：当时想了一个错误的贪心思路 直接统计0 1的个数 然后先分配偶数长度的串 然后分配奇数长度的串 写了很长的模拟 最后wa了 只要有奇数长度的串或者0或1的个数是奇数就输出(n) 否则输出(n - 1)就行辽

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 60;

int q, n, cnt0, cnt1, cnt, len;
string s;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> q;
    while (q -- ){
        cnt = 0, cnt0 = 0, cnt1 = 0;
        cin >> n;
        for (int i = 1; i <= n; i ++ ){
            cin >> s;
            len = s.size();
            if (len & 1)
                cnt ++ ;
            for (int j = 0; j < len; j ++ ){
                if (s[j] == '0')
                    cnt0 ++ ;
                else
                    cnt1 ++ ;
            }
        }
// debug        cout << cnt0 << " " << cnt1 << "
";
        if (cnt || (cnt0 % 2 == 0))
            cout << n << "
";
        else
            cout << n - 1 << "
";
    }
    return 0;
}

C. Minimize The Integer

• 思路：奇数串儿和偶数串儿的顺序是不会改变的 用俩string分别存奇数串儿和偶数串儿 然后分别从前往后比较大小 小的存在前面即可

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

int t;
string s;

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t -- ){
        cin >> s;
        string ans;
        string odd, even;
        for (int i = 0; i < s.length(); i ++ ){
            if (s[i] & 1)
                odd.push_back(s[i]);
            else
                even.push_back(s[i]);
        }
        for (int k = 0, i = 0, j = 0; k < s.length(); k ++ ){
            if (i == odd.size()){
                ans.push_back(even[j]);
                j ++ ;
            }
            else if (j == even.size()){
                ans.push_back(odd[i]);
                i ++ ;
            }
            else{
                if (odd[i] >= even[j]){
                    ans.push_back(even[j]);
                    j ++ ;
                }
                else{
                    ans.push_back(odd[i]);
                    i ++ ;
                }
            }
        }
        cout << ans << "
";
    }
    return 0;
}

D. Salary Changing

• 思路：贪心 + 二分 先以左端点从大到小排序 然后二分找中间值即可(cmp函数l写成r debug已知没找到 然后疯狂wa

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int t, n;
ll s, ans;

struct Seg{
    ll l, r;
}seg[N];

inline bool cmp(Seg s1, Seg s2){
    if (s1.l == s2.l)
        return s1.r > s2.r;
    return s1.l > s2.l;
}

inline bool check(ll x){
    ll cnt = n / 2 + 1, sum = 0;
    for (int i = 1; i <= n; i ++ ){
        if (seg[i].l <= x && seg[i].r >= x && cnt){
            sum += x;
            cnt -- ;
        }
        else{
            sum += seg[i].l;
            if (seg[i].l > x)
                cnt -- ;
        }
    }
    if (cnt)
        return false;
    return sum <= s;
}

inline ll calc(){
    ll l = seg[n / 2 + 1].l + 1, r = s;
    ll mid;
    while (l <= r){
        mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t -- ){
        cin >> n >> s;
        for (int i = 1; i <= n; i ++ )
            cin >> seg[i].l >> seg[i].r;
        sort(seg + 1, seg + n + 1, cmp);
        ans = calc();
        cout << ans << "
";
    }
    return 0;
}