Codeforces Round #530 (Div. 2) 解题报告

A

题目大意: 有一个高h重w的雪球从山上滚下来,每下降一米，重量+=高度，中间会碰到两个石头，碰到后雪球减去石头的重量，问到达高度为 0 是重量为多少

小于0则看做0

模拟题……

#include <cstdio>

int w,h;
int u1,u2,d1,d2;

int main(){
    scanf("%d%d%d%d%d%d",&w,&h,&u1,&d1,&u2,&d2);
    while(h){
        w+=h;
        if(h==d1) w-=u1;
        if(h==d2) w-=u2;
        if(w<0) w=0;
        h--;
    }  
    printf("%d",w);
}

B

现在需要画$n$个正方形，问最少需要几个单位线段可以保证画出来的$n$个正方形的每条边都可以通过已有线段平行得到

贪心就对了

#include <cstdio>
#include <cmath>

int n,tmp,ans;

int main(){
    scanf("%d",&n);
    tmp=std::sqrt(n);
    if(n%tmp==0){
        printf("%d",tmp+(n/tmp));
        return 0;
    }
    else {
        ans=tmp+(n/tmp);
        printf("%d",ans+1);
    }
}

C

给你一个字符串，如果一个字母后跟的是 * 表示这个字母可以被删除，保留或重复多次，如果跟的是 ? 表示这个字母可以被删除或者保留，如果都不是，则表明其必须留在原位置

贪心题目，比较原字符串长度与要求的长度，然后分段讨论

#include <cstdio>
#include <cstring>

int k,len,zlen,sfcnt,tmp;
bool sf,cd;
char s[1000];

int main(){
    scanf("%s",s+1);
    scanf("%d",&k);
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(s[i]>='a'&&s[i]<='z') 
            zlen++;
        if(s[i]=='?') sfcnt++;
        if(s[i]=='*') {cd=true;sfcnt++;}
    }
    if(zlen>k){
        if(sfcnt<zlen-k){
            printf("Impossible");
            return 0;
        } 
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            if(s[i+1]=='?'||s[i+1]=='*'){
                if(zlen>k) {zlen--;sfcnt--;}   
                else printf("%c",s[i]);
            } 
            else printf("%c",s[i]);
        }
    } 
    else if(zlen==k){
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else printf("%c",s[i]);
        }
    }
    else if(zlen<k){
        if(!cd){
            printf("Impossible");
            return 0;
        }
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else if(s[i+1]=='*'){
                printf("%c",s[i]);
                while(1){
                   if(zlen>=k) break;
                   printf("%c",s[i]);
                   zlen++;
                } 
            }
            else printf("%c",s[i]);
        } 
    }
}

D

现在已知树的形态与奇数深度点到根的长度（最短路径所经过的边的边权和）

因为交叉未知……所以直接贪心！！！

#include <cstdio>
#include <cstdlib>

inline int Min(int a,int b){return a<b?a:b;}

const int N=1e5+2e4;
const int INF=2147483640;

int n,v;
long long sum=0;
int s[N],a[N],son[N];

// edge start 
struct edge{
    int to,next;
}e[N<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end

void dfs(int now,int val){
    if(s[now]<=-1){
        int tmp=INF;
        for(int i=ehead[now];i;i=e[i].next){
            tmp=Min(s[e[i].to],tmp); 
        }
        if(tmp==INF) return ;
        tmp-=val;a[now]=tmp;
        for(int i=ehead[now];i;i=e[i].next){
            s[e[i].to]-=val+a[now];
        }
        for(int i=ehead[now];i;i=e[i].next){
            dfs(e[i].to,val+a[now]);
        }
        return ;
    }
    a[now]=s[now];
    for(int i=ehead[now];i;i=e[i].next){
        dfs(e[i].to,val+a[now]);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&v);
        add_edge(v,i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        if(s[i]!=-1&&s[i]<s[1]){
            printf("-1");
            return 0;
        }
    }
    dfs(1,0);
    sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            printf("-1");
            return 0;
        }
        sum+=a[i];
    }
    printf("%lld",sum);
}