Codeforces Round 963 (Div. 2)题解

Posted on Edited on

题目链接

本场比赛应该算是今年我打的第一场算法竞赛，也是NOIP2021结束之后难得发挥出来的比赛。ABC都是比较简单的题，D是二分+dp，比较难想

E最终还是不会，疑似是一个高级dp

A.Question Marks

观察样例就能打出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<string>
using namespace std;

signed main(){
    int t;cin >> t;
    while( t -- ){
        string s;int n;cin >> n;cin >> s;
        int a , b , c , d , e;a = b = c = d = e = 0;
        for(int i = 0;i < s.length();i ++){
            if( s[i] == 'A' ) a ++;
            if( s[i] == 'B' ) b ++;
            if( s[i] == 'C' ) c ++;
            if( s[i] == 'D' ) d ++;
            if( s[i] == '?' ) e ++;
        }
        a = max( a-n , 0 );
        b = max( b-n , 0 );
        c = max( c-n , 0 );
        d = max( d-n , 0 );
        //cout << "a: " << a << endl;
        cout << n*4-a-b-c-d-e << endl;
    }
    return 0;
}

B.Parity and Sum

策略是取出最大的奇数，和所有的偶数从小到大进行比较，如果比当前偶数大，那么将最大的奇数+=当前偶数，否则ans需要+1（仅加一次，此时表示当前最大的奇数不如这个偶数大，只需要进行一次最大奇数加上最大偶数的操作（即ans+=1）即可获得可以使任意偶数变为奇数的大数，如果最大的奇数从小到大累加偶数都能比下一个偶数更大则不需要进行这一步操作）

全奇全偶需要特判

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<string>
#include<algorithm>
#define int long long
using namespace std;

int t , n , a[200010];

signed main(){
    cin >> t;
    while( t -- ){
        cin >> n;
        int ans = 0;
        int lag_d = 0;
        for(int i = 1;i <= n;i ++){
            cin >> a[i];
            if( a[i] % 2 == 0 ) ans ++;
            else lag_d = max( a[i] , lag_d );
        }
        sort( a + 1 , a + n + 1 );
        if( ans == n ) ans = 0;
        if( ans ){
            for(int i = 1;i <= n;i ++){
                if( a[i] % 2 == 0 ){
                    if( a[i] > lag_d ){
                        ans ++;
                        //cout << "error: "<< i << " " << a[i] << " " << lag_d << endl;
                        break;
                    }
                    else{
                        lag_d += a[i];
                    }
                } 
            }
        }
        
        cout << ans << endl;
    }
    return 0;
}

C.Light Switches

首先可以确定，最终答案在[最大值,最大值+k]区间，如果这个区间没有答案，那么输出-1

k过大，直接扫肯定会超时；所以根据每个\(a_i\)计算它相应的区间（宽度为k，但是左右区间不同），然后将\(l\)取\(max\)，将\(r\)取\(min\)，如果\(l<r\)那么答案就是\(l\)，否则没有答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<string>
#include<algorithm>
#define int long long
using namespace std;

int t , n , k , a[200010];

signed main(){
    cin >> t;
    while( t -- ){
        cin >> n >> k;
        int maxn = 0;
        for(int i = 1;i <= n;i ++){
            cin >> a[i];
            maxn = max( maxn , a[i] );
        }
        int l , r;l = maxn , r = maxn + k;
        for(int i = 1;i <= n;i ++){
            int rat = (maxn - a[i]) / k;
            if( rat % 2 ) rat ++;
            l = max( a[i] + rat * k , l );
            r = min( a[i] + rat * k + k , r );
        }
        //cout << "demo: "<< l << " " << r << endl;
        if( l >= r ) cout << -1 << endl;
        else cout << l << endl;
    }
    return 0;
}

以下题目结为赛后补题：

D.Med-imize

利用二分中位数，我们可以用 \(log(max(a_i))\) 的代价使中位数由未知变为已知

观察得到一个结论——最终序列的 \(id\) 总是在 \(mod\ k\) 下能填满 \([0,n\%k]\)，以此可以选择出最优化的一组解（正好填满 \([0,n\%k]\) ），即尽量多选大于中位数的选项，如果总共选到大于中位数的数字多余小于的，那么可以判断这组中位数是可以用的

最终输出最大的中位数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#define int long long
using namespace std;

const int N = 5e5;

int t , n , k , a[N+10];
int dp[N+10] , b[N+10];

bool checker( int mid ){
    for(int i = 0;i < n;i ++){
        if( a[i] >= mid ){
            b[i] = 1;
        }
        else{
            b[i] = -1;
        }
    }
    dp[0] = b[0];
    for(int i = 1;i < n;i ++){
        if( i % k == 0 ){#这一组的开头，如果前面的或者当前位置下有1就可以是1
            dp[i] = max( dp[i-k] , b[i] );
        }else{#直接选当前的，i不是第一个循环的话，则可以继承上一个循环的（反正是选最大值）
            dp[i] = dp[i-1] + b[i];
            if( i > k ){
                dp[i] = max( dp[i] , dp[i-k] );
            }
        }
    }
    return dp[n-1] > 0;
}

signed main(){
    cin >> t;
    while( t -- ){
        cin >> n >> k;
        for(int i = 0;i < n;i ++){
            cin >> a[i];
        }
        int l = 1 , r = 1e9;
        while( l <= r ){
            int mid = (l+r)>>1;
            if( checker(mid) ){
                l = mid+1;
            }
            else{
                r = mid-1;
            }
        }
        cout << r << endl;
    }   
    return 0;
}