Codeforces#441 Div.2 四小题

A. Trip For Meal

小熊维尼喜欢吃蜂蜜。他每天要在朋友家享用N次蜂蜜，朋友A到B家的距离是 a ，A到C家的距离是b ，B到C家的距离是c （A- >Rabbit B- >Owl C ->Eeyore），他不能连续两顿饭都在同一位朋友家里蹭

他现在位于A的家里，请问他一天最少要跑多少路。

当然是要找一条最短的路折返跑了啊,是不是很简单。

#include<bits/stdc++.h>

using namespace std;

int N,a,b,c;

int main()

{

    cin>>N>>a>>b>>c;

    if        (N==)printf("0\n");

    else if    (N==)printf("%d\n",min(a,b));

    else if (N>=){

        int k=min(a,b);

        if(k<=c)

            printf("%d\n",(N-)*k);

        else     printf("%d\n",k+(N-)*c);

    }

    return ;

}

B. Divisiblity of Differences

给你一个有N个元素的可重集合，你需要找出一个含k个元素的子集，使里面的数两两的差都能被m整除

差 + 整除 -> 同余 -> 子集中的数对m同余

每个数都mod m 然后枚举余数就好了。

#include<bits/stdc++.h>

using namespace std;

int N,M,K,a[],vis[],ans=-;

int main()

{

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

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

        scanf("%d",&a[i]);

        vis[a[i]%M]++;

    }

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

        if(vis[i]>=K){

            ans=i;

            break;

        }

    }

    if(ans!=-){

        printf("Yes\n");

        for(int i=;i<=N&&K;i++)

            if(a[i]%M==ans)printf("%d ",a[i]),K--;

        printf("\n");

    }

    else printf("No\n");

}

C. Classroom Watch

先定义一个f(x) ， f(x)的值就是 x的每一位加在一起在加上它本身 f(123)=1+2+3+123=129

给你一个int范围内的整数N，求满足f(x)=N 的x有多少和这些x的值

最多就十位数各数位的数加在一起也超不过100 于是就枚举 N-100~N 的所有数

#include<bits/stdc++.h>

using namespace std;

int N,ans[],cnt;

void judge(int x)

{

    int sum=x,i=x;

    while(i){

        sum+=i%;

        i=i/;

    }

    if(sum==N)ans[++cnt]=x;

}

int main()

{

    scanf("%d",&N);

    for(int i=N->=?N-:;i<=N;i++){

        judge(i);

    }

    printf("%d\n",cnt);

    for(int i=;i<=cnt;i++)

        printf("%d\n",ans[i]);

    return ;

}

D. Sorting the Coins

每次就是寻找最后一个O前面有多少x ，很容易，看到有人拿树状数组什么的其实没必要，这个尤其好维护，而且很水

#include<bits/stdc++.h>

using namespace std;

int N,a[],vis[],ans;

int main()

{

    scanf("%d",&N);

    printf("1 ");

    int zer=N;

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

        scanf("%d",&a[i]);

        vis[a[i]]=;

        if(a[i]>zer){

            printf("%d ",ans+);

        }

        else{

            ans++;

            while(vis[zer])ans--,zer--;

            printf("%d ",ans+);

        }

    }

    return ;

}

巴特西

Codeforces#441 Div.2 四小题

Codeforces#441 Div.2 四小题

A. Trip For Meal

B. Divisiblity of Differences

C. Classroom Watch

D. Sorting the Coins

最新文章

热门文章