Codeforces Round #721 (Div. 2)

A.And Then There Were K

题意: 给定 n,求满足 n \ AND \ (n-1)\ AND \ (n-2) \cdot \cdot \cdot AND \ (k) = 0 最小k的值。

Solution: 假设n的最高位位 t, 答案就是2^t-1

Code:

int t, n;

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        int cnt = 0;
        while(n){
            n /= 2;
            cnt ++;
        }
        cout << (1 << (cnt - 1)) - 1 << endl;
    }
    return 0;
}

B1.Palindrome Game (easy version)

题意:
给定一个 01 回文字符串,两个人 A,B 交替操作,A先手。
有两种操作:
1.花费 1 将某个 0 变成 1
2.花费 0 将字符串逆序,但是下一个人操作不能再逆序。
全部变为 1 时结束。
问两人最终花费大小。

Solution:
如果单独 10, 那么显然 B 获胜。
如果全是 0, n 为奇数则是 A 获胜,否则 就是 B 获胜。
其他情况下:
如果 n 是偶数,则 B 获胜
否则:在 n 奇数的情况下,A 获胜的情况只有中间是 00 的个数不是 1。其余都是 B 获胜。

Code:

int t, n;
string s;

int main(){
    cin >> t;
    while(t --){
        cin >> n >> s;
        int c1 = 0, c0 = 0;
        for(int i = 0; i < n; i ++){
            if(s[i] == '1') c1 ++;
            else    c0 ++;
        }
       if(c0 == n){
            if(n == 1)  puts("BOB");
            else{
                puts(n & 1 ? "ALICE" : "BOB");
            }
        }
        else{
            if(n & 1){
                if(s[n / 2] == '0' && c0 != 1) puts("ALICE");
                else    puts("BOB");
            }
            else{
                puts("BOB");
            }
        }
    }
    return 0;
}

B2.Palindrome Game (hard version)

题意:
hard版本与easy版本区别就是输入的是 01 字符串。

Solution:
先求出变成回文字符串的距离 sum
sum = 0 就是easy版本。
sum >= 2A必胜。
sum = 10 的个数为 2 时为平局,否则就是 A 必胜。

Code:

int t, n;
string s;

void solve(){
    int c1 = 0, c0 = 0;
    for(int i = 0; i < n; i ++){
        if(s[i] == '1') c1 ++;
        else    c0 ++;
    }
    if(c0 == n){
        if(n == 1)  puts("BOB");
        else{
            puts(n & 1 ? "ALICE" : "BOB");
        }
    }
    else{
        if(n & 1){
            if(s[n / 2] == '0' && c0 != 1) puts("ALICE");
            else    puts("BOB");
        }
        else{
            puts("BOB");
        }
    }
}

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        cin >> s;
        int sum = 0;
        for(int i = 0; i < n / 2; i ++){
            if(s[i] != s[n - i - 1])    sum ++;
        }
        if(sum == 0)    solve();
        else if(sum >= 2)   puts("ALICE");
        else{
            int c1 = 0, c0 = 0;
            for(int i = 0; i < n; i ++){
                if(s[i] == '1') c1 ++;
                else    c0 ++;
            }
            if(c0 == 2) puts("DRAW");
            else    puts("ALICE");
        }
    }
    return 0;
}

Sequence Pair Weight

题意:
给你一个数组,让你求每一个子段里面一共有多少的pair。

Solution:
找规律发现一对 (x,y) ,每对对答案的贡献为 x * (n - y + 1)

Code:

int t, n;
int a[N];
P b[N];

void solve(){
    for(int i = 1; i <= n; i ++){
        b[i].first = a[i];
        b[i].second = i;
    }
    sort(b + 1, b + n + 1);
    ll ans = 0;
    for(int i = 1; i <= n; i ++){
        if(b[i].first == b[i + 1].first){
            ll res = b[i].second;
            while(b[i].first == b[i + 1].first && i + 1 <= n){
                ans += (1ll * n - b[i + 1].second + 1) * res;
                i ++;
                res += b[i].second;
            }
        }
    }
    printf("%lld\n", ans);
}

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i = 1; i <= n; i ++){
            cin >> a[i];
        }
        solve();
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注