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

太过爱你忘了你带给我的痛 2022-02-20 15:09 300阅读 0赞

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

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

**题目链接：**[Codeforces Round \#551 (Div. 2)][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;
    }

[Codeforces Round _551 _Div. 2]: http://codeforces.com/contest/1153