Codeforces Round 964 (Div. 4)

Codeforces Round 964 (Div. 4)

A Sending Points

B

Big Idea:Two people turn over two cards at random, and find the probability that a turns over a bigger card than b.

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#define ep emplace_back 
using namespace std;

void solve() {
    int ans = 0;
    int a1, b1, a2, b2;
    cin >> a1 >> a2 >> b1 >> b2;
    
    int cnt1 = 0, cnt2 = 0;
    if (a1 > b1)
        cnt1++;
    else if (a1 < b1)
        cnt2++;

    if (a2 > b2)
        cnt1++;
    else if (a2 < b2)
        cnt2++;

    if (cnt1 > cnt2) 
        ans += 2;

    cnt1 = cnt2 = 0;
    if (a1 > b2)
        cnt1++;
    else if (a1 < b2)
        cnt2++;

    if (a2 > b1)
        cnt1++;
    else if (a2 < b1)
        cnt2++;

    if (cnt1 > cnt2) 
        ans += 2;

    cout << ans << "\n";
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C

Topic Overview:Some intervals are blocked Find consecutive intervals Determine whether the longest length can be greater than S

Idea: Ensure that l and r are disjoint, sweep through all the intervals, run two pointers pos1=0, pos2=l.

#include<iostream>
using namespace std;
void solve(){
    int n,s,m;
    scanf("%d%d%d",&n,&s,&m);
    bool ok=0;
    int pos=0;
    for(int i = 0; i < n; ++i){
        int l,r;
        scanf("%d%d",&l,&r);
        int k = l-pos;
        if( k>=s )
            ok=1;
        pos=r;
    }
    if(m-pos>=s) ok=1;
    if(ok) cout<<"YES";
    else cout<<"NO";
    cout<<"\n";
}
int main(){

    int T;
    cin>>T;
    while(T--){
        solve();
    }
}

D

Big Idea:Given a string of characters s t s certain characters can be modified Can we modify s st t by modifying it to be a subsequence of s?

Idea: two pointers to sweep through, ? or can match let the second pointer to run forward, and finally determine the second pointer to run to the end of the

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

void solve(){
    string s,t;
    cin>>s>>t;
    int j=0;

    for(int i = 0; i < (); ++i){
        if(s[i] == '?' ){
            if(j < ()){
                s[i] = t[j];
                ++j;
            }
            else {
                s[i] = 'a';
            }
        }
        else if( s[i] == t[j] and j<()){
            ++j;
        }
    }
    if(j == ()) cout<<"YES"<<"\n"<<s;
    else cout<<"NO";
    cout<<"\n";
}
int main(){
    int _;
    cin>>_;
    while(_ --){
        solve();
    }
}

E:

Question:Write down L,L+1,.... ...R-1,R numbers, manipulate him so that one number is multiplied by three and the other is divided by three. Until all are 0 Find the minimum number of operations

Idea:First let L be 0 ans add the number of operations Observe that [3,8] opt=2, [9,26] opt=3 Just calculate the length of the interval multiplied by the number of times the interval corresponds to the opt.

#include <iostream>
#include <cmath>
#include <cstdio>
#define lld long long
using namespace std;
int f(int x){
    int ans=0;
    while(x!=0){
        x/=3;
        ans++;
    }
    return ans;
}

void solve(){
    int L,R;
    cin>>L>>R;
    int K = f(L);
    int M = f(R);
    lld ans=0;
    int a[50],b[50];
    for(int i=0;i<=32;++i){
        a[i] = pow(3,i);
        b[i] = pow(3,i+1)-1;
    }
    ans+=2*f(L);
    int pos=L+1;
    for(int i=f(L+1) ; i <= M; ++i){
        //printf("ans=%d ",ans);
        int pos2 = b[i-1];
        if(pos2>R){
            
            pos2=R;
            //printf("pos=%d pos2=%d \n",pos,pos2);
            ans+=(pos2-pos+1)*i;
            break;
        }
        else {
            //printf("pos=%d pos2=%d \n",pos,pos2);
            ans+=(pos2-pos+1)*i;
            pos = a[i];
        }
        
    }
    cout<<ans<<"\n";
}

int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}
// 2 3 4 5 6 7 8 9 10 11 12 
// 1 2 2 2 2 2 2 3 3  3   3
// 14+12 = 22

F:

Big Idea.

Thoughts.