Educational Codeforces Round 60 (Rated for Div. 2) 解题报告

A. Best Subsegment

给定一串数列, 求区间最大平均值

显然,最大的区间平均值可以就是数列中最大的那个,然后基于最大的点想两边枚举区间长度

#include <cstdio>
#include <algorithm>
inline int Max(int a, int b){return a > b? a: b;}
const int N = 1e5 + 1e4;
int n, max, max_id, len, rig, max_len;
int a[N];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        if(a[i] > max)
            max = a[i];
    }
    for(int i = 1; i <= n; i++){
        if(a[i] == max && ( a[i - 1] != max || i == 1 ) ){
            rig = i; len = 0;
            while( a[rig] == a[i] && rig <= n ){
                rig++; len++;
            }
            max_len = Max(len, max_len);
        }
    }
    printf("%d", max_len);
}
继续阅读“Educational Codeforces Round 60 (Rated for Div. 2) 解题报告”

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

A Got Any Grapes?

顺序判断即

比赛的时候忘记写 else 既然 PP 了,然后就 FST

#include <cstdio>
int an,dm,mi;
int gr,pu,bl;
int main(){
    scanf("%d%d%d", &an, &dm, &mi);
    scanf("%d%d%d", &gr, &pu, &bl);
    if(an > gr) {
        printf("NO\n");
        return 0;
    }
    else gr -= an;
    if(pu + gr < dm){
        printf("NO\n");
        return 0;
    }
    else {
        if(pu <= dm) {dm -= pu; pu = 0;}
        else {pu -= dm; dm = 0;}
        if(gr < dm) {
            printf("NO\n");
            return 0;
        }
        else gr -= dm;
    }
    if(gr + pu + bl < mi) printf("NO\n");
    else printf("YES\n");
}
继续阅读“Codeforces Round #538 (Div. 2) 解题报告”

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);
}
]]>