Codeforces Round 944 (Div. 4)

A. My First Sorting Problem

思路：

• 直接从小到大输出即可

时间复杂度：\(O(1)\)

void solve() {
    int x, y;;
    std::cin >> x >> y;
    std::cout << std::min(x, y) << " " << std::max(x, y) << "\n";
}

B. Different String

思路：

• 找到第一个不一样的字符对即可

时间复杂度：\(O(n)\)

void solve() {
    std::string s;
    std::cin >> s;

    int n = s.size();

    char x = s[0];
    bool ok = false;
    for (char &c : s) {
        if (x != c) {
            ok = true;
            std::swap(s[0], c);
            break;
        }
    }
    if (ok) {
        std::cout << "YES\n";
        std::cout << s << "\n";
    } else {
        std::cout << "NO\n";
    }
}

C. Clock and Strings

思路：

• 先把头尾固定，然后找分别在两边的情况和近乎平行的情况

时间复杂度：\(O(1)\)

void solve() {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;

    if (a > b) std::swap(a, b);
    if (c > d) std::swap(c, d);

    if (b < c || (b > d && a < c) || (a > c && d > b) || d < a) {
        std::cout << "NO\n";
    } else {
        std::cout << "YES\n";
    }
}

D. Binary Cut

思路：

• 首先找到最长的 \(01\) 子串，然后分别找连续子段 \(0\) 的个数和连续子段 \(1\) 的个数，然后加起来就是 \(ans\)

时间复杂度：\(O(n)\)

void solve() {
    std::string s;
    std::cin >> s;

    int n = s.size();

    int max = 0;
    int l = -1, r = -1;
    for (int i = 0; i < n; i++) {
        int j = i;
        int zero = 0, one = 0;
        while (s[j] == '0') {
            j++;
            zero++;
        }
        while (s[j] == '1') {
            j++;
            one++;
        }
        if (zero + one > max && zero != 0 && one != 0) {
            max = zero + one;
            l = i, r = j - 1;
        }
    }
    int ans = 1;
    if (l == -1 && r == -1) {
        ans = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            bool ok = false;
            while (j < n && s[j] == '0') {
                j++;
                ok = true;
            }
            if (ok) {
                ans++;
                i = j - 1;
            }
        }
        for (int i = 0; i < n; i++) {
            int j = i;
            bool ok = false;
            while (j < n && s[j] == '1') {
                j++;
                ok = true;
            }
            if (ok) {
                ans++;
                i = j - 1;
            }
        }
    } else {
        for (int i = 0; i < l; i++) {
            int j = i;
            bool ok = false;
            while (j < l && s[j] == '0') {
                j++;
                ok = true;
            }
            if (ok) {
                ans++;
                i = j - 1;
            }
        }
        for (int i = 0; i < l; i++) {
            int j = i;
            bool ok = false;
            while (j < l && s[j] == '1') {
                j++;
                ok = true;
            }
            if (ok) {
                ans++;
                i = j - 1;
            }
        }
        for (int i = r + 1; i < n; i++) {
            int j = i;
            bool ok = false;
            while (j < n && s[j] == '0') {
                j++;
                ok = true;
            }
            if (ok) {
                ans++;
                i = j - 1;
            }
        }
        for (int i = r + 1; i < n; i++) {
            int j = i;
            bool ok = false;
            while (j < n && s[j] == '1') {
                j++;
                ok = true;
            }
            if (ok) {
                ans++;
                i = j - 1;
            }
        }
    }
    std::cout << ans << "\n";
}

E. Find the Car

思路：

• 本题的精度卡的好严，我分析一下卡精度的地方：
  1. 对于一个式子，要先乘后减，这样减少精度丢失
  2. 在一个式子上进行强转，会有精度丢失
• 然后这题主要就是二分求解，比赛的时候状态好差，后面都没写出来，唉，菜就多练

时间复杂度：\(O(q \times logn)\)

void solve() {
    int n, k, q;
    std::cin >> n >> k >> q;

    std::vector<i64> a(k + 1), b(k + 1);
    for (int i = 1; i <= k; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= k; i++) {
        std::cin >> b[i];
    }

    while (q--) {
        int d;
        std::cin >> d;

        int p = std::lower_bound(a.begin() + 1, a.end(), d) - a.begin();
        if (a[p] == d) {
            std::cout << b[p] << " ";
            continue ;
        }
        i64 ans = b[p - 1] + 1.L * (d - a[p - 1]) * (b[p] - b[p - 1]) / (a[p] - a[p - 1]);
        std::cout << ans << " ";
    }
    std::cout << "\n";
}

F. Circle Perimeter

思路：

• 要找 \(r \le \sqrt{x^2 + y^2} \le r+1\) 的整数坐标的点数，感觉这个 \(OJ\) 一般给你一个公式，你都需要把它转换一下，我们把它转换为 \(r^2 \le x^2 + y^2 \le (r+1)^2\)，然后 \(x\) 和 \(y\) 的范围最大是 \(r\)，然后我们枚举 \((x + y)^2\) 的范围，从 \(-r\) 一直枚举到 \(r\)，每次求在 \(\sqrt{r^2 - (x^2 + y^2)} \le number \le \sqrt{(r + 1)^2 - (x^2 + y^2)}\) 里点的个数，然后累计求和就行，这个求的是半个圆形的个数，所以要 \(\times 2\)，然后 \(-1\)，这样就是一整个圆形中满足 \(r \le \sqrt{x^2 + y^2} \le r+1\) 的点的个数

时间复杂度：\(O(2r)\)

void solve() {
    int r;
    std::cin >> r;

    i64 ans = 0;
    for (i64 i = -r; i <= r; i++) {
        i64 small = 1LL * r * r - i * i;
        i64 big = 1LL * (r + 1) * (r + 1) - i * i - 1;
        ans += 2 * static_cast<i64>(sqrtl(big) - ceil(sqrtl(small)) + 1);
    }
    std::cout << ans - 2 << "\n";
}

G. XOUR

题目大意：如果两个数 \(a_i \oplus a_j \lt 4\)，那么这两个数可以交换位置，将这个序列的字典序变为最小的。

思路：

• 对于 \(a_i \oplus a_j \lt 4\)，那么一定只是这两个数的最后两位不一样，假定一个数的数位有 \(n\) 位，那么，我们将前 \(n-2\) 位相同的分到一组内，然后，对这一组升序排序，最后输出把原来同一组内的数字，按照升序替换到原位置即可，最后的答案就是字典序最小的

时间复杂度：\(O(nlogn)\)

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::map<int, std::vector<int>> mp;
    for (int i = 0; i < n; i++) {
        mp[a[i] >> 2].push_back(i);
    }
    std::vector<int> ans(n);
    for (auto [v, x] : mp) {
        auto b = x;
        std::sort(b.begin(), b.end(), [&](int i, int j) {
            return a[i] < a[j];
        });
        for (int i = 0; i < b.size(); i++) {
            ans[x[i]] = a[b[i]];
        }
    }
    for (auto x : ans) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}