专栏首页饶文津的专栏【校赛小分队之我们有个女生】训练赛1

【校赛小分队之我们有个女生】训练赛1

校赛小分队之我们有个女生队——这是我、ljh学长、zk大神组的队,我取得闪亮亮的队名!

第一场训练赛是水题(只要做前四题),但是我做的比较慢,zk可快了,于是我心塞了一晚上。

传送门 密码【123666】

A.【 CodeForces 633A 】Ebony and Ivory

给a、b、c(1 ≤ a, b ≤ 100, 1 ≤ c ≤ 10 000)三个正整数,求关于x和y的方程ax+by=c的非负的整数解。

如果枚举x和y,那要枚举到10000,复杂度是n2 显然会超时。

但是只要枚举其中一个的倍数i,然后看看c-a*i能不能整除b。

或者直接枚举i=1到c,看看是否满足 i能整除a 且 c-i能整除b。

一开始想gcd(a,b)|c 就是gcd整除c,则x、y有整数解,再判断有没有非负整数的解(乱搞),但是失败了,不过后来研究了一下,扩展gcd可以做的(废话)。

因为x最小时,y就最大,只要求出x的最小非负数解,判断y是不是非负的,如果是那么xy就有非负整数解啦。如果不是,那么x更大时,y就更小了,那就不可能有了。

#include<cstdio>
int a,b,c,ok;
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    for(int i=0; i<=c&&!ok; i++)
        if(i%a==0&&(c-i)%b==0)ok=1;
    if(ok)printf("Yes");
    else printf("No");
    return 0;
}

扩展gcd

#include<cstdio>
int a,b,c,x,y,ok;
int exgcd(int a,int b){
    if(b==0){ x=1;y=0; return a;}
    int r=exgcd(b,a%b);
    int t=x;x=y;y=t-a/b*y;
    return r;
}
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    int g=exgcd(a,b);
    if(c%g==0){
        x*=c/g;//ax+by=c的x的解
        b/=g;
        x=(x%b+b)%b; //x的最小非负解
        if(c-a*x>=0) ok=1;//对应的y也非负
    }
    if(ok)printf("Yes");
    else printf("No");
    return 0;
}

B.【 CodeForces 629A 】A Trivial Problem

判断每行每列里共有几对‘C’。直接统计每行有几个,记为a[i],每一列有几个,记为b[i],然后ans+=C(a[i],2)+C(b[i],2)。

一个个字符读取,则每读一行字符前,要getchar吃掉前面一行的回车。

#include<cstdio>
#define N 105
int n,ans;
char c;
int a[N],b[N];
int main()
{

    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        c=getchar();
        for(int j=1; j<=n; j++)
        {
            c=getchar();
            if(c=='C')
            {
                a[i]++;
                b[j]++;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        ans+=a[i]*(a[i]-1)/2;
        ans+=b[i]*(b[i]-1)/2;
    }
    printf("%d",ans);
    return 0;
}

C.【 CodeForces 633B 】A Trivial Problem

求n!后面有m个零的n有几个,按顺序输出。

那就求出n!里面有几个因子5,因子2一定比5多,所以几个5末尾就有几个0。

可以用二分的方法求n,也可以直接求。

下面的代码具体为什么这样,就是这样,不想解释了。

#include<cstdio>
#define ll long long
ll m,l,r;
int main()
{
    while(~scanf("%lld",&m))
    {
        l=m;
        while(l+l/5+l/25+l/125+l/625+l/3125+l/15625+l/78125+l/390625>m)l--;
        if(l+l/5+l/25+l/125+l/625+l/3125+l/15625+l/78125+l/390625<m)printf("0");
        else
        {
            printf("5\n");
            for(ll i=5*l; i<5*l+5; i++)
                printf("%lld ",i);
        }
    }
    return 0;
}

二分,感觉这样挺好。

#include<cstdio>
#define ll long long
ll m,l,r;
int cnt(int a){
    int tol=0;
    //下面这个循环统计了a的阶乘的因子5的次数tol。
    while(a){
        tol+=a/5;//1到a这些数里面有几个是5的倍数。
        a/=5;//这a个能整除5的数都除以5,就变成了1到a/5,再看1到a/5里面有几个是5的倍数。
    }
    return tol;
}
int solve(){
    int l=1,r=m*5+1;
    while(l<r-1){
        int mid=l+r>>1;
        int ans=cnt(mid);
        if(ans<m){
            l=mid;
        }else if(ans>m){
            r=mid;
        }
        else return mid;
    }
    return 0;
}
int main()
{
    while(~scanf("%lld",&m))
    {
        int v=solve();
        if(v){
            while(v%5)v--;
            printf("5\n");
            for(ll i=v; i<v+5; i++)
                printf("%lld ",i);
        }
        else printf("0");
    }
    return 0;
}

 D.【 CodeForces 629B 】Far Relative’s Problem

给你每个朋友有空的时间区间,求来的朋友里 min(男朋友,女朋友)最大的一天。直接统计每天的男女朋友个数。然后枚举每一天找最大值。

#include<cstdio>
#include<algorithm>
#define N 5005
using namespace std;
int n,a[N],b[N],ans;
int l,r;
char c;
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        getchar();
        scanf("%c%d%d",&c,&l,&r);
        if(c=='M')
        {
            for(int j=l; j<=r; j++)
                a[j]++;
        }
        else
        {
            for(int j=l; j<=r; j++)
                b[j]++;
        }
    }
    for(int i=1; i<=366; i++)
    {
        int t=min(a[i],b[i]);
        if(t>ans)ans=t;
    }
    printf("%d",2*ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「POJ - 2318」TOYS (叉乘)

    有一个玩具盒,被n个隔板分开成左到u右n+1个区域,然后给每个玩具的坐标,求每个区域有几个玩具。

    饶文津
  • 【hihocoder 1424】 Asa's Chess Problem(有源汇上下界网络流)

    饶文津
  • 【POJ 3321】Apple Tree

    有n个节点以1为根节点的树,给你树的边关系u-v,一开始每个节点都有一个苹果,接下来有两种操作,C x改变节点x的苹果状态,Q x查询x为根的树的所有苹果个数。

    饶文津
  • HDU4576 Robot(概率)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack
  • 剑指OFFER之重建二叉树(九度OJ1385)

    题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

    用户1154259
  • Python3 基础学习之数值进制转换

        这个函数在上篇里表示强转,并没有输入n这个参数。当n不输入的时候默认是n=10。

    ZY_FlyWay
  • 2019 CCPC 重现赛 1006 基环树

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • 挑战程序竞赛系列(30):3.4矩阵的幂

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • AGC015 C Nuske vs Phantom Thnook(前缀和)

    attack
  • HDU4035 Maze(期望DP)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack

扫码关注云+社区

领取腾讯云代金券