Codeforces Round 944 (Div.4)

5月10日 Codeforces 实战记录。（0 -> 656）

第一次Codeforces试水，AC数7/8。
比赛跳转：Codeforces Round 944 (Div. 4)

题解

A. B. E.

随题意模拟即可，不做赘述。

C. Clock and Strings

题意：判断环中两连线是否相交

分析：先锁定一条连线，再判断另一条边的两端点是否在连线同侧。

完整代码：

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int t = read();
    while(t--){
        int a = read(), b = read(), c = read(), d = read();
        
        int mn = min(a, b), mx = max(a, b);
        
        bool flag1 = 0, flag2 = 0;
        
        if(mn < c && c < mx) flag1 = 1;
        if(mn < d && d < mx) flag2 = 1;
        
        if(flag1 ^ flag2)
            cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }

    return 0;
}

补充解法

官方题解给出了一种很美妙的解法，直接用字符串模拟了两条连线的相对方位：

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int t = read();
    while(t--){
        int a = read(), b = read(), c = read(), d = read();
        
        string s;
        for (int i = 1; i <= 12; i++) {
            if (i == a || i == b) {s += "a";}
            if (i == c || i == d) {s += "b";}
        }
        
        cout << (s == "abab" || s == "baba" ? "YES\n" : "NO\n");		
    }
    return 0;
}

D. Binary Cut

题意：通过剪切01序列，使其成为升序。

分析：先将所有01序列拆分成仅含0或仅含1的序列，再至多合并一对形如 0..0 与1..1 的序列，即出现 01 时 cnt--。

完整代码：

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int t = read();
    while(t--){
        string s; cin >> s;
        int cnt = 0;
        char last = ' ';
        for(int i = 0; i < s.length(); i++){
            if(s[i] != last){
                cnt ++;
                last = s[i];
            }
        }
        for(int i = 0; i < s.length() - 1; i++){
            if(s[i] == '0' && s[i + 1] == '1'){
                cnt--;
                break;
            }
        }
        cout << cnt << '\n';
    }

    return 0;
}

F. Circle Perimeter

题意：找出距离原点距离在 [r, r + 1) 内的整点个数。

分析：简化为4 * (第一象限与x轴正半轴格点数)

搜索时，对x轴上每一个i ，最高点 up 满足 i * i + up * up < (r + 1) * (r + 1)，最低点 down 满足 i * i + down * down >= r * r，化简后 O(1) 找出 up down ，计数 up - down + 1 个格点即可。

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

signed main() {
    int t = read();
    while (t--) {
        int r = read();
        int cnt = 0;

        int le = r * r;
        int ri = le + r + r + 1;

        for (int i = 1; i <= r; i++) {
            int up = ceil(sqrt((ri - i * i))) - 1, down = ceil(sqrt((le - i * i)));
            cnt += up - down + 1;
        }

        cout << cnt * 4 << '\n';
    }

    return 0;
}

G. XOUR

题意：对二进制表示下，仅有最后两位不同的数记为一组，各组内排序。

实现：直接用map将除去后两位的值映射到优先队列自动排序即可。

完整代码：

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    vector<int> a(n);
    map<int, priority_queue<int, vector<int>, greater<int>>>mp;
    for(int i = 0; i < n; i++){
        a[i] = read();
        mp[a[i] >> 2].push(a[i]);
    }
    for(int i = 0; i < n; i++){
        cout << mp[a[i] >> 2].top() << ' ';
        mp[a[i] >> 2].pop();
    }
    cout << '\n';
}

int main(){
    int t = read();
    while(t--)
        solve();
    return 0;
}