Codeforces Round 964 (Div.4)题解

Posted on Edited on

题目链接

差一道题就ak了，打代码的速度还是慢了点

F时间不够了，于是随便糊了个时间复杂度不对的算法，结果算法对了，少了个预处理然后就TLE了，赛时没有发现

A.A+B Again?

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
using namespace std;
int t , n;
signed main(){
    cin >> t;
    while( t -- ){
        cin >> n;
        cout << (n/10)+(n%10) << endl;
    }
    return 0;
}

B.Card Game

直接穷举所有可能性即可

思路不是很难，就看如何实现了

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>
#define int long long
using namespace std;

int t , a[5];

signed main(){
    cin >> t;
    while( t -- ){
        for(int i = 1;i <= 4;i ++) cin >> a[i];
        int l , r , ans = 0;
        for(int i = 1;i <= 2;i ++){
            int ii = (i==1)?2:1;
            for(int j = 3;j <= 4;j ++){
                int jj = (j==3)?4:3;
                l = 0 , r = 0;
                if( a[i] > a[j] ) l ++;
                if( a[i] < a[j] ) r ++;

                if( a[ii] > a[jj] ) l ++;
                if( a[ii] < a[jj] ) r ++;

                if( l > r ) ans ++;
                //cout << a[i] << " " << a[ii] << " " << a[j] << " " << a[jj] << endl;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C.Showering

典型贪心（弱化版）

数据范围可以 \(O(nlogn)\)，无脑sort就好了

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
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

const int N = 2e5;
int t , n , s , m;
struct TIME{
    int l , r;
}a[N+10];

bool cmp( TIME x , TIME y ){
    return x.l < y.l;
}

signed main(){
    cin >> t;
    while( t -- ){
        cin >> n >> s >> m;
        for(int i = 1;i <= n;i ++){
            cin >> a[i].l >> a[i].r;
        }
        sort( a + 1 , a + n + 1 , cmp );
        bool flag = 0;
        a[0].r = 0 , a[n+1].l = m;
        for(int i = 1;i <= n+1;i ++){
            if( a[i].l - a[i-1].r >= s ){
                flag = 1;
                break;
            }
        }
        if( flag ) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

D.Slavic's Exam

这里的匹配不需要连续，所以只要有?就直接替换就可以了，多余的?需要替换成任意小写字母

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
#include<iostream>
#include<string>
#define int long long
using namespace std;

int T;
string s , t;

signed main(){
    cin >> T;
    while( T -- ){
        cin >> s >> t;
        int t_top = 0;
        //cout << s.length() << " " << t.length() << endl;
        for(int i = 0;i < s.length();i ++){
            if( t_top == t.length() ){
                if( s[i] == '?' ) s[i] = 'a';
                continue;
            }
            if( s[i] == '?' || s[i] == t[t_top] ){
                s[i] = t[t_top];
                t_top ++;
            }
        }
        if( t_top != t.length() ) cout << "NO" << endl;
        else{
            cout << "YES" << endl;
            cout << s << endl;
        }
    }
    return 0;
}

E.Triple Operations

这道题开始上难度了

先说结论，\(ans=log_3(min(a_i))+\sum log_3(a_i)\)

容易观察到，我们只需要将其中一个数变为0，后续将数字除以3（减小）的时候不会造成其他数字乘以3（增大），我们只需要将最小的数变为0就可以，但是同时也会有另外一个数字增大，这时造成的代价即为\(log_3(min(a_i))\)

现在只需要计算 \(log_3(min(a_i))+\sum log_3(a_i)\) ，即\(log_3l+\sum_l^r log_3(a_i)\)

我们观察到从 \(l\) 到 \(r\) 是单调的，所以利用指数即可在 \(O(logn)\) 求解

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
#include<iostream>
#include<string>
#define int long long
using namespace std;

int T;
int l , r;

int log3( int x ){
    int ans = 0;
    while( x ){
        x /= 3;
        ans ++;
    }
    return ans;
}

int poww( int x ){
    int ans = 1;
    while( x -- ){
        ans *= 3;
    }
    return ans;
}

signed main(){/*
    for(int i = 1;i <= 100;i ++){
        cout << i << " | " << log3(i) << endl;
    }
    return 0;*/
    cin >> T;
    while( T -- ){
        cin >> l >> r;
        /*
        int ans = log3(l);
        for(int i = l;i <= r;i ++){
            ans += log3(i);
        }*/
        int ans = log3(l)+log3(r) , log_i , jumper;
        for(int i = l;i <= r;i ++){
            log_i = log3(i);
            jumper = poww( log_i );
            //cout << "jumper: " << jumper  << " |ans: " << ans << endl;
            if( jumper < r ) ans += (jumper-i)*log_i , i = jumper-1;
            else ans += (r-i)*log_i , i = r;
        }
        cout << ans << endl;

    }
    return 0;
}

F.Expected Median

假设 \(1\) 有 \(x\) 个，\(0\) 有 \(y\) 个，那么 $ans=(C_xi+C_y{k-i}) $，即从 \(x\) 中选 \(i\) 个，从 \(y\) 中选 \(k-i\) 个的所有可能，其中 \(i\) 需要满足 从 \(x\) 中取出的元素多余从 \(y\) 中取出（即 \(1\) 比 \(0\) 多，这样的中位数才能是 \(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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<string>
#define int long long
using namespace std;

const int N = 2e5 , p = 1e9+7;
int T , n , k;
int a[N+10];
int num_0 , num_1;
int jc[N+10];

void init(){
    jc[0] = 1;
    for(int i = 1;i <= N;i ++){
        jc[i] = jc[i-1]*i;
        jc[i] %= p;
    }
    return ;
}

int qpow(long long a, int b) {
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}

int inv( int x ){
    return qpow( x , p-2 );
}

int C( int nn , int mm ){
    int ans = 1;
    ans *= jc[nn];
    ans %= p;
    ans *= inv(jc[mm]);
    ans %= p;
    ans *= inv(jc[nn-mm]);
    ans %= p;
    return ans;
}

signed main(){
    init();
    cin >> T;
    while( T -- ){
        cin >> n >> k;
        num_0 = num_1 = 0;
        for(int i = 1;i <= n;i ++){
            cin >> a[i];
            if( a[i] ) num_1 ++ ; else num_0 ++;
        }
        int ans = 0;
        for(int i = min(num_1,k);i>k/2 and (k-i)<=num_0;i --){
            //cout << num_0 << " " <<  k-i << " " << num_1 << " " << i << endl;
            ans += C( num_0 , k-i ) * C( num_1 , i );
            ans %= p;
        }
        cout << ans << endl;
    }
    return 0;
}

G1.Ruler (easy version)

简单的二分法

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>
#define int long long
using namespace std;

const int N = 2e5 , p = 1e9+7;
int T , t;

int ef( int l , int r ){
    if( l == r ) return l;
    int mid = (l+r)>>1;
    cout << "? " << mid << " " << mid << endl;
    cout << flush;
    int t;
    cin >> t;
    //int redder = mid + ( mid>=100?1:0);
    //t = redder*redder;
    if( t == (mid+1)*(mid+1) ) return ef( l , mid );
    else return ef( mid+1 , r );
}

signed main(){
    cin >> T;
    while( T -- ){
        int ans = ef( 2 , 999 );
        cout << "! " << ans << endl;
        cout << flush;
    }
    return 0;
}

G2.Ruler (hard version)

三分法，写法有很多，七次询问可以确定一个数即可

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
#include<iostream>
#include<string>
#define int long long
using namespace std;

const int N = 2e5 , p = 1e9+7;
int T , t;

int ef( int l , int r ){
    if( l == r ) return l;
    int mid_l = l+(r-l)/3 , mid_r = l+(r-l)/3*2;
    cout << "? " << mid_l << " " << mid_r << endl;
    cout << flush;
    int t;
    cin >> t;/*
    int lll = mid_l + ( mid_l>=700?1:0);
    int rrr = mid_r + ( mid_r>=700?1:0);
    t = lll*rrr;*/
    if( t == (mid_l+1)*(mid_r+1) ) return ef( l , mid_l );
    else if( t == (mid_l)*(mid_r+1) ) return ef( mid_l+1 , mid_r );
    else return ef( mid_r+1 , r );
}

signed main(){
    cin >> T;
    while( T -- ){
        int ans = ef( 2 , 999 );
        cout << "! " << ans << endl;
        cout << flush;
    }
    return 0;
}