Codeforces Round #551 (Div. 2) （A,B,C）-蒲公英云

Codeforces Round #551 (Div. 2) （A,B,C）

一开始做出来两道题，提交第三题一直wa,就在这个时候A题突然被人hack了，啊啊啊~我是猪吗？！A题也能错！

刚刚看A题的时候，才发现怎么代码里还有一个n—，什么鬼？！一定是昨天不清醒，导致最后rating又掉了11，下一场加油，让rating快点涨上去。不说了，补题。

题目链接：Codeforces Round #551 (Div. 2)

A. Serval and Bus

遍历一遍，让Serval同学等待时间最短的那班车的编号，如果多种结果，任选一种输出。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,t,s,d,k,ans,tmp;
    scanf("%d%d",&n,&t);
    scanf("%d%d",&s,&d);
    //n--;    //hack点 
    ans=1;
    if(t<=s){
        k=s-t;
    }else{
        if((t-s)%d==0) k=0;
        else k=d-(t-s)%d;
    }
    for(int i=2;i<=n;i++){
        scanf("%d%d",&s,&d);
        if(t<=s){
            tmp=s-t;
        }else{
            if((t-s)%d==0) tmp=0;
            else tmp=d-(t-s)%d;
        }
        if(tmp<k){
            ans=i;
            k=tmp;
        }
    }
    printf("%d\n",ans);
    return 0;
}

B. Serval and Toy Bricks

题意：给你主视图，左视图，俯视图，让你输出满足这三种情况的立体图形。

思路：从俯视图出发，任何一个位置的高度取决于主视图和左视图中高度较小值，想到这点，这个题就迎刃而解了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int a[maxn],b[maxn],c[maxn][maxn];
int main(){
    int n,m,h;
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&c[i][j]);
            if(c[i][j]==1){
                c[i][j]=min(b[i],a[j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j==m) printf("%d\n",c[i][j]);
            else printf("%d ",c[i][j]);
        }
    }
    return 0;
}

C. Serval and Parenthesis Sequence

一开始做这道题的时候思路也不是很严谨，所以导致第6个测试点就过不了了。

题意：先说一个概念，正确的括号序列就是每个左括号都有一个右括号和它匹配，右括号也没有多余的。给你一个序列，问你在它的前缀都不是正确的括号序列的情况下，它有没有可能是正确的括号序列？是的话任选一中满足要求的匹配情况输出，否则输出“:(”。

思路：一开始，我就想只要第一个括号是左括号，最后一个括号是右括号，且最左边的括号和最右边的括号相匹配，那么整个序列的前缀就不是正确的括号序列，这一点是满足要求的。具体如何实现呢？输入序列的第一个字符和最后一个字符特判，然后看里面还得插入多少个左括号，原则就是能插左括号就插左括号。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3*1e5+10;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int len;
    string t;
    cin>>len;
    cin>>t;
    bool flag=true;
    if(len%2==1||t[0]==')'||t[len-1]=='(') flag=false;
    if(flag){
        t[0]='(';
        t[len-1]=')';
        int rc=0;  //右括号的数量
        int lc=0;  //左括号的数量 
        for(int i=1;i<len-1;i++){
            if(t[i]==')') rc++;
            else if(t[i]=='(') lc++;
        }
        if(rc>(len-2)/2||lc>(len-2)/2) flag=false;
        lc=(len-2)/2-lc;  //还需要添加lc左括号 
        if(flag){
            int L=0;  //[1,i-1]中还未匹配的左括号的数量 
            for(int i=1;i<len-1;i++){
                if(t[i]=='('){
                    L++;    
                }else if(t[i]==')'){
                    if(L!=0){
                        L--;
                    }else{
                        flag=false;
                        break;
                    }
                }else if(t[i]=='?'){
                    if(lc){
                        t[i]='(';
                        lc--;
                        L++; 
                    }else if(L!=0){
                        t[i]=')';
                        L--;
                    }else{
                        flag=false;
                        break;
                    }
                }
            }
            //if(L!=0||lc!=0) flag=false;
        }
    }
    if(flag) cout<<t<<endl;
    else cout<<":("<<endl;
    //cout<<t<<endl;
    return 0;
}