【CF】Educational Codeforces Round 116 (Rated for Div. 2) A & B

赛事链接：https://s.heyiqi.cc/bkr

A. AB Balance

分析

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string str;
        cin >> str;
        int n = str.size();
        bool flag = true;
        char last = str[0];
        for (int i = 1; i < n; i++) {
            if (str[i] != last) {
                flag = !flag;
                last = str[i];
            }
        }
        if (flag) {
            cout << str << endl;
        } else {
            cout << str.substr(0, n - 1) << (str[n - 1] == 'a' ? 'b' : 'a') << endl;
        }
    }
}

B. Update Files

分析

代码

解法1：模拟（超时）

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, c;
        cin >> n >> c;
        ll cp = 1, ans = 0;
        while (n > cp) {
            int cur = cp < c ? cp : c;
            if (cur == c) {
                if ((n - cp) % c == 0) {
                    ans += (n - cp) / c;
                } else {
                    ans += (n - cp) / c + 1;
                }
                break;
            }
            cp += cur;
            ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

解法2：二分

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
int t;
ll n, k;
ll p2[N];

void init() {
    p2[0] = 1;
    for (int i = 1; i < 64; i++) {
        p2[i] = p2[i - 1] * 2;
    }
}

int main() {
    cin >> t;
    init();
    while (t--) {
        cin >> n >> k;
        int l = 0, r = 63;
        while (l < r) {// 刚好小于等于的
            int mid = (l + r + 1) / 2;
            if (p2[mid] > k) r = mid - 1;
            else l = mid;
        }
        if (p2[l + 1] <= n) {
            ll yu = n - 1 - (p2[l + 1] - 1);
            ll ans = (l + 1) + (yu + (k - 1)) / k;
            // cout<<l<<" "<<yu<<" "<<ans<<endl;
            cout << ans << endl;
        } else {
            //找第一个大于的 l+1
            int ll = 0, rr = 63;
            while (ll < rr) {
                int mid = ll + rr >> 1;
                if (p2[mid + 1] < n) ll = mid + 1;
                else rr = mid;
            }
            if (n == 1) cout << 0 << endl;
            else cout << ll + 1 << endl;
        }
    }
}