Codeforces Round #460 (Div. 2) 前三题

Problem A：题目传送门

题目大意：给你N家店，每家店有不同的价格卖苹果，ai元bi斤，那么这家的苹果就是ai/bi元一斤，你要买M斤，问最少花多少元。

题解：贪心，找最小的ai/bi。

#include <cstdio>

using namespace std;

double minn=2e9,x,y,M;

int N;

int read()

{

    char c;while(c=getchar(),c<''||c>'');

    int x=c-'';while(c=getchar(),c>=''&&c<='')x=x*+c-'';

    return x;

} 

inline double min(double x,double y){return x<y?x:y;}

int main()

{

    N=read(),M=read();

        for(int i=;i<=N;i++){

            x=read(),y=read();

            minn=min(minn,M*x/y);

        }

    printf("%.8lf",minn);

    return ;

} 

Problem A

Problem B：题目传送门

题目大意：给一个数字K，求一个第K大的Perfect数，Perfect数指这个数数位上的数字之和为10。

题解：DFS即可。

#include <cstdio>

#include <cstdlib>

using namespace std;

int K,cnt=,a[];

void print(int tot)

{

    for(int i=;i<=tot;i++)putchar(a[i]+'');

    return ;

}

void search(int tot,int now,int less)

{

    if(now==tot){

        cnt++;

        if(cnt==K){print(tot);exit();}

        return ;

    }

    if(now==tot-){a[tot]=less;search(tot,tot,);return ;}

        for(int i=;i<=less;i++){

            a[now+]=i;

            search(tot,now+,less-i);

        }

    return ;

}

int main()

{

    scanf("%d",&K);

    register int i,j;

        for(i=;i<=;i++){

            for(j=;j<=;j++){

                a[]=j;

                search(i,,-j);

            }

        }

    return ;

}

Problem B

Problem C：题目传送门

题目大意：给三个整数N，M，K，表示图的大小为N*M，求能坐的座位有连续K个的方案数。‘*’表示不能坐，“.”表示能坐。

题解：预处理每个点横着有连续几个，竖着有连续几个，然后找到一段连续的最大的点ans+=min(0,W-K+1)。W为这个点的值。K为一时特判，答案为所有能坐的位置总和。

#include <cstdio>

#include <algorithm>

using namespace std;

int N,M,K,ans,cnt;

int a[][];

int ri[][],di[][];

int main()

{

    scanf("%d%d%d",&N,&M,&K);

    register int i,j;

        for(i=;i<=N;i++){getchar();

            for(j=;j<=M;j++){

                char c=getchar();

                if(c=='.')a[i][j]=,cnt++;

            }

        }

    if(K==)return printf("%d",cnt),;

        for(i=;i<=N;i++)

            for(j=;j<=M;j++)

                if(a[i][j])ri[i][j]=ri[i][j-]+,di[i][j]=di[i-][j]+;

        for(i=;i<=N;i++)

            for(j=;j<=M+;j++){

                if(!a[i][j])ans+=(max(,ri[i][j-]-K+));

            }

        for(j=;j<=M;j++)

            for(i=;i<=N+;i++){

                if(!a[i][j])ans+=(max(,di[i-][j]-K+));

            }

    printf("%d",ans);

    return ;

}

Problem C

Codeforces Round #460 (Div. 2) 前三题的相关教程结束。