Educational Codeforces Round 65 (Rated for Div. 2) A-E

EdGrass / 2023-05-18 / 原文

Educational Codeforces Round 65 (Rated for Div. 2)

A. Telephone Number

void solve(){
    int n=read(),ans=0;
    string s;
    cin>>s;
    for(int i=1;i<=n-10;i++){
        if(s[i-1]=='8')ans=1;
    }
    puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Lost Numbers

纯暴力代码写的很丑（）

int s[7]={0,4,8,15,16,23,42};
void solve(){
    int a,b,c,d;
    cout<<"? "<<1<<" "<<2<<endl;
    cin>>a;
    cout<<"? "<<2<<" "<<3<<endl;
    cin>>b;
    cout<<"? "<<3<<" "<<4<<endl;
    cin>>c;
    cout<<"? "<<4<<" "<<5<<endl;
    cin>>d;
    int n=6;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                for(int h=1;h<=n;h++){
                    for(int p=1;p<=n;p++){
                        for(int q=1;q<=n;q++){
                            if(i!=j&&i!=k&&i!=h&&i!=p&&i!=q){
                                if(j!=k&&j!=h&&j!=p&&j!=q){
                                    if(k!=h&&k!=p&&k!=q){
                                        if(h!=p&&h!=q){
                                            if(p!=q){
                                                if(s[i]*s[j]==a&&s[j]*s[k]==b&&s[k]*s[h]==c&&s[h]*s[p]==d){
                                                    cout<<"! "<<s[i]<<" "<<s[j]<<" "<<s[k]<<" "<<s[h]<<" "<<s[p]<<" "<<s[q]<<endl;
                                                    return ;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C. News Distribution

int p[N], siz[N], cum[N];
int find(int x){ 
    if (p[x] != x) p[x] = find(p[x]);
    return p[x]; 
}
void solve(){
    int n=read(),m=read();
    for (int i = 1; i <= n; i ++ ) {
        p[i] = i;
        siz[i] = 1;
    }     
    for(int i=1;i<=m;i++){
        int k=read();
        int y;
        if(k>0) y=read();
        else continue;
        for(int j=1;j<k;j++){
            int x=read();
            if(find(x)==find(y))continue;
            siz[find(x)] += siz[find(y)];
            p[find(x)] = find(y);
        }
    }
    for(int i=1;i<=n;i++){
        p[find(i)] = find(i);
        cum[p[i]]++;
    }
    for(int i=1;i<=n;i++){
        cout<<cum[p[i]]<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D. Bicolored RBS

这就是一个简单的贪心思路

要把括号分成两组每次把左括号放在较少的一组里起到分摊右括号放在较多的一组里起到消除

int ans[N];
void solve(){
    int n=read();
    string s;
    cin>>s;
    int a=0,b=0;
    for(int i=0;i<n;i++){
        if(s[i]=='('){
            if(a<b){
                a++;
                ans[i]=0;
            }else {
                b++;
                ans[i]=1;
            }
        }else {
            if(b>=a){
                b--;
                ans[i]=1;
            }else {
                a--;
                ans[i]=0;
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<ans[i];
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

E. Range Deleting

本题就是智慧的预处理+双指针

预处理出1-k值的左界和右界（对应代码中的p[i],q[i]）

然后进一步处理出1-i这个范围的右界，和i-k这个范围的左界（对应代码中的p1[i],q1[i]）

接下来用双指针的思想如果q1[l-1]>p1[r+1]说明大于R的值的左界都比小于L的值的右界小说明需要r++

int a[N],p[N],q[N],p1[N],q1[N];
void solve(){
    int n=read(),k=read();
    memset(p,0x3f,sizeof(p));
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(p[a[i]] > 1e9) p[a[i]] = i;
        q[a[i]] = i;
    }
    for(int i=1;i<=k;i++)   q1[i] = max(q1[i - 1],q[i]);
    p1[k] = p[k],p1[k + 1] = 1e9;
    for(int i=k-1;i>=1;i--) p1[i] = min(p1[i + 1],p[i]);
    int r = k - 1,ans = 0;
    while(r >= 1 && q[r] < p1[r + 1]) r--;
    for(int l=1;l<=k;l++){
        if(l > 2 && p[l - 1] < q1[l - 2]) break;
        while(r <= k && (r < l || q1[l - 1] > p1[r + 1]))   r++;
        ans += k - r + 1; 
    }
    write(ans);
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}