Codeforces Round #551 (Div. 2)

A. Serval and Bus（水）

题意：n辆公交车，Serval在t时刻到达车站，每辆公交车在si时刻到达，经过di时刻转了一圈；问你Serval上的第一辆车是几号

模拟一下就行了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct node{
    int s,d,id;
}a[maxn];
bool cmp(node a,node b){
    if(a.s==b.s)return a.id<b.id;
    return a.s<b.s;
}
int main(){
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].d;
        a[i].id=i;
        if(a[i].s<t){
            int x=(t-a[i].s)/a[i].d;
            if(x==0)
                a[i].s+=a[i].d;
            else a[i].s+=a[i].d*x;
            while(a[i].s<t)a[i].s+=a[i].d;
        }
    }
    sort(a+1,a+1+n,cmp);
    cout<<a[1].id<<endl;
 
 
    return 0;
}

View Code

B. Serval and Toy Bricks（算是初中的几何题吧）

题意：给你正 侧 上 视图，让你输出这个可能的图形；

解题：先补全整个长方体，然后根据给的一个个去掉就行了

#include <bits/stdc++.h>
using namespace std;
const int maxn=310;
int ans[maxn][maxn];
int a[maxn],b[maxn];
int hh[maxn][maxn];
int n,m,h;
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans[i][j]=h;
        }
    }
}
int main(){
    cin>>n>>m>>h;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>hh[i][j];
            if(hh[i][j]==0)ans[i][j]=0;
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(ans[j][i]>a[i]){
                    ans[j][i]=a[i];
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ans[i][j]>b[i])ans[i][j]=b[i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<ans[i][j]<<‘ ‘;
        }
        cout<<endl;
    }
 
 
 
 
    return 0;
}

View Code

C. Serval and Parenthesis Sequence（水题）

题意：给你一个字符串，只包含 ‘?‘ and ‘(‘  and  ‘)‘ ，‘?‘可以改成‘(‘ or ‘)‘，问你能否在最后才满足括号匹配（n以前不满足括号匹配，到n才满足括号匹配）

解题：统计左括号的个数和右括号的个数，先把问号改成左括号（因为前面如果左括号够多，那么一定在n之前不会满足括号完全匹配），直到左括号等于n/2为止，然后把剩下的全改成右括号，然后判断一下是否满足条件即可；（wa了3次，忘记判断左括号和右括号是否相等在全部改完之后）

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,flag=1;
    string s;
    cin>>n>>s;
    if(n%2)flag=0;
    if(s[0]==‘)‘)flag=0;
    else s[0]=‘(‘;
    int left=0,right=0;
    for(int i=0;i<n;i++){
        if(s[i]==‘(‘)left++;
        else if(s[i]==‘)‘)right++;
    }
    for(int i=0;i<n;i++){
        if(s[i]==‘?‘){
            if(left<n/2)s[i]=‘(‘,left++;
            else s[i]=‘)‘,right++;
        }
    }
    left=0,right=0;
    for(int i=0;i<n;i++){
        if(s[i]==‘(‘)left++;
        else if(s[i]==‘)‘)right++;
        if(left<=right&&i!=n-1){
            flag=0;break;
        }
    }
    if(left!=right)flag=0;
    if(flag){
        cout<<s<<endl;
    }
    else cout<<":("<<endl;
    return 0;
}

View Code

D. Serval and Rooted Tree

题意：给你一颗树，每个结点都有一个操作，取儿子节点的最大值或者最小值当作该节点的值，叶子节点的值为1-k，k为叶子节点的个数，求树根的最大值；

第一眼错误思路：这不是一个线段树吗，直接每个结点存一个最大值最小值，刚要上手的时候，傻逼了，怎么会是线段树。。。每个叶子节点的值是不确定的；

正解：求根节点的最大值，因为所有叶子节点固定，假设答案是x，在取max时只要其中有一个子节点是等于x就可以了，在取min时就要所有子节点都大于x，

所以只要统计这些能走到的叶子节点，就可以解出x，x=k-（所有能走到的叶子节点）+1；这样就可以保证答案最大，其他未走到的节点可以随便安排值；

所有能走到的节点的值一定都是大于等于x的；

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
const int inf=0x3f3f3f3f;
int n,op[maxn],x,k;
int tot,h[maxn],nt[maxn],p[maxn];
int dp[maxn];
void add_edge(int x,int y){
    tot++;
    nt[tot]=h[x];
    h[x]=tot;
    p[tot]=y;
}
void dfs(int x,int fa){
    int flag=0;
    if(op[x]==1)dp[x]=inf;
    for(int j=h[x];j;j=nt[j]){
        if(p[j]!=fa){
            flag++;
            dfs(p[j],x);
            if(op[x]==0)dp[x]+=dp[p[j]];
            else dp[x]=min(dp[x],dp[p[j]]);
        }
    }
    if(!flag)k++,dp[x]=1;
}
int main(){
    cin>>n;
    tot=0;
    for(int i=1;i<=n;i++)cin>>op[i];
    for(int i=2;i<=n;i++){
        cin>>x;
        add_edge(i,x);
        add_edge(x,i);
    }
    dfs(1,-1);
    cout<<k+1-dp[1]<<endl;


    return 0;
}

View Code

 数组开小了，要改成1e7