Educational Codeforces Round 132(Div.2)分析

这次的比赛没打，但是自己打估计就是自闭上去的。

A. String Building

题目描述

题目分析

给你三个门，每个门后可能有🔑，一个钥匙开一个对应的门，问你是否有办法把所有的门打开。很简单，就那到🔑开个门，换新钥匙，看看能开几个门就可以了。

标程

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
void solve(){
    int a,b[4];
    scanf("%d%d%d%d",&a,&b[1],&b[2],&b[3]);
    int key=a,cnt=0;
    while(key){
        key=b[key];
        cnt++;
    }
    if(cnt==3){
        puts("YES");
    }
    else{
        puts("NO");
    }
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

B. Also Try Minecraft

题目描述

题目分析

题目说的还是比较清楚的，把minecraft抽象成一个二维世界，只有x和y轴，y轴向下位移会受到摔落伤害，但是上升不会。现在需要执行任务，告诉你每一列的高度，每个任务需要你从一列位移到另一列，问你完成每个任务需要受到多少摔落伤害。

这题也还可以，很难不想到用前缀和的思路去做。但是因为上升不会扣血或者加血，而它又有可能从后面位移到前面，因此我们需要算出两个前缀和，然后相减即可求得每个人物需要的血量，然后不要忘了开long long。

标程

#include<bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;
int a[maxn],b[maxn];
int sum1[maxn],sum2[maxn];
char s[maxn];
int n,q;
void init(){
    sum1[0]=0;
    for(int i=1;i<n;i++){
        sum1[i]=sum1[i-1]+max(a[i]-a[i+1],0ll);
        //printf("%d ",sum1[i]);
    }//putchar(10);
    sum2[n+1]=0;
    for(int i=n;i>1;i--){
        sum2[i]+=sum2[i+1]+max(a[i]-a[i-1],0ll);
        //printf("%d ",sum2[i]);
    }//putchar(10);
}
void solve(){
    
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]); 
    }
    init();
    while(q--){
        int l,r;
        scanf("%lld%lld",&l,&r);
        if(l<r){
            printf("%lld\n",sum1[r-1]-sum1[l-1]);    
        }
        else{//l==8 r==7
            printf("%lld\n",sum2[r+1]-sum2[l+1]);
        }
    }
    
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    //cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

C. Recover an RBS

题目描述

题目分析

这题就是摁贪，从前往后扫一遍计数，当所需的右括号刚好等于问号数量的时候，那就把前面的全部清零，重新计数，看看最后问号数量是否等于左括号的数量即可。那你可能会有疑问，什么时候问号变成左括号呢？问得好，因此我们多出一个，让问号的数量

标程

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int x=0;
int a[maxn],b[maxn];
char s[maxn];
void solve(){
    scanf("%s",s);
    int len=strlen(s);
    int cnt=0,q=0;
    for(int i=0;i<len;i++){
        if(s[i]=='?')q++;
        if(s[i]=='(')cnt++;
        if(s[i]==')')cnt--;
        if(q+cnt==1){
            q=0;
            cnt=1;
        }
    }
    if(cnt==q)puts("YES");
    else puts("NO");
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

总结

还是太菜了qwq