[原创]Google Code Jam 2017 Round 1B [B-large不会]

Tabris

CSDN思维套题

发布于：2017年4月23日

次浏览

[原创]Google Code Jam 2017 Round 1B [B-large 不会]

2017-04-23 04:05:38 Tabris_ 阅读数：991

博客爬取于 2020-06-14 22:40:54
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70481823

A. Steed 2: Cruise Control

————————————————————————————————————————————
一个人要从 0 骑马到 D，路上可能有多个骑马者，为了表示尊重，后面追过来的马不能超过前面的马，要减速到与前面的马相同的速度，现在问你这个人最开始的速度为多大的时候能保证在整个过程中不会超过别人，

很明显的二分答案。

注意浮点型二分的次数即可。
判断的时候只要判断中间有没有马在这个人到 D 的时候还没有到达 D 就行了。。

附本题代码
————————————————————————————————————————————


int _,d,n;

int k[10000],s[10000];

bool check(double x){
    double t = 1.0*d/x;
    for(int i=1;i<=n;i++){
        if(t*s[i]+k[i] + 1e-8 <=d*1.0) return false;
    }
    return true;
}

int main(){
    freopen("A-large (1).in","r",stdin);
    freopen("A-large (1).txt","w",stdout);
    int kcase = 0;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&d,&n);
        for(int i=1;i<=n;i++)       scanf("%d%d",&k[i],&s[i]);

        double l=0,r=1e15,mid;
        for(int i=0;i<300;i++){
            mid = (r+l)/2;
            if(check(mid))l=mid;
            else  r=mid;
        }
        printf("Case #%d: ",++kcase);
        printf("%.6lf\n",l);
    }

    return 0;
}

B. Stable Neigh-bors

————————————————————————————————————————————
这个大数据的我不会做，,

就是一种东西的头发空有 6 种颜色的可能其中有红，黄，蓝，橙色，紫色，绿色
橙色 = 红 + 黄
紫色 = 红 + 蓝
绿色 = 黄 + 蓝

现在有相同颜色的两个东西不能挨着，（注意：像橙色和红色这种也不能挨着，），问你存不存在一个排列，使得 N 各这些东西能够围城一圈。
给了你每个颜色的东西有多少个。

大数据没搞
我就不会图论，怎么建图实在弄不明白，然后水了发小数据
小数据就很好写了
只有 RYB 三种颜色，只要不相同就能挨着，
那么考虑不可能的情况就是当其中两种小的个数和小于最大的那个的个数，这样的话一定会有同色挨着的。

然后对于可行的时候我们只要在颜色最大的那个基础上进行插入另外两种颜色就好了，
一种从左边开始挨个插，另一种从右边开始挨个插就好了，

附小数据代码
————————————

int _,n,r,o,y,g,b,v;
int flag ;
void dfs(int t,string s,int m,int R,int G,int B){
//    puts("--");
    if(flag==0) return ;
    if(n==m&&flag) {
        if(s[0]!=s[n-1]){
            flag = 0;
            cout<<s<<endl;
        }
    }
    for(int i=1;i<=3&&flag;i++){
        if(i==t) continue;
        if(i==1&&R)s+="R",dfs(i,s,m+1,R-1,G  ,B  );
        if(i==2&&G)s+="G",dfs(i,s,m+1,R  ,G-1,B  );
        if(i==3&&B)s+="B",dfs(i,s,m+1,R  ,G  ,B-1);
    }
}

void dfs1(int R,int Y,int B){
    string s="";
    for(int i=1;i<=R;i++){
        s+="R";
        if(i<=Y) s+="Y";
        if(i+B>R) s+="B";
    }
//    printf("%d *1 ",s.size());
    cout<<s<<endl;
}

void dfs2(int R,int Y,int B){
    string s="";
    for(int i=1;i<=Y;i++){
        s+="Y";
        if(i<=R) s+="R";
        if(i+B>Y) s+="B";
    }
//    printf("%d *2 ",s.size());
    cout<<s<<endl;
}

void dfs3(int R,int Y,int B){
    string s="";
    for(int i=1;i<=B;i++){
        s+="B";
        if(i<=Y) s+="Y";
        if(i+R>B) s+="R";
    }
//    printf("%d *3 ",s.size());
    cout<<s<<endl;
}

int main(){
    freopen("B-small-attempt2.in","r",stdin);
    freopen("B-small-attempt2.txt","w",stdout);
    int kcase = 0;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);

        scanf("%d%d%d%d%d%d",&r,&o,&y,&g,&b,&v);
//        printf("%d: %d %d %d %d %d %d\n",n,r,o,y,g,b,v);
        int a[4];

        a[0]=r;
        a[1]=y;
        a[2]=b;

        sort(a,a+3);printf("Case #%d: ",++kcase);
        if(a[0]+a[1]<a[2]) puts("IMPOSSIBLE");
        else {
            flag = 1;
                 if(r>=y&&r>=b) dfs1(r,y,b);
            else if(y>=r&&y>=b) dfs2(r,y,b);
            else if(b>=y&&b>=r) dfs3(r,y,b);
        }

    }

    return 0;
}

C. Pony Express

————————————————————————————————————————————
给你 N 的 N 个城市上每个有一匹马（马最多能走E_i，速度是S_i）到每个城市可以选择换马或者不换马然后 Q 次询问问你从点u到点v 最快的时间

数据范围很小，尤其是N\leq100 ，很明显的提示了 floyd

我们可以这样做，先对距离进行 floyd，找到两点间的最短距离，

然后根据这个距离和E_i的关系确定一个最少时间的图，对其跑 floyd，就是我们所有的结果了，查询的时候 O(1)查询就好了。

附本题代码
————————————————————


int _,n,q;
double d[111],s[111];
double a[111][111],b[111][111];
int main(){
    freopen("C-large-practice.in","r",stdin);
    freopen("C-large-practice.txt","w",stdout);

    int kcase = 0;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&q);

        for(int i=1;i<=n;i++)    scanf("%lf%lf",&d[i],&s[i]);

        LL x;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                scanf("%lld",&x);
                if(x==-1) x=1000000000000000000ll;
                a[i][j]=1.0*x;
                if(i==j) a[i][j]=0.0;
            }

        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(a[i][j]>a[i][k]+a[k][j])
                        a[i][j]=a[i][k]+a[k][j];

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(a[i][j]==1.0*1000000000000000000ll) b[i][j]=a[i][j];
                else if(a[i][j]<=d[i]) b[i][j]=a[i][j]/s[i];
                else b[i][j]=1.0*1000000000000000000ll;
            }

        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(b[i][j]>b[i][k]+b[k][j])
                        b[i][j]=b[i][k]+b[k][j];

        printf("Case #%d:",++kcase);
        for(int i=1,u,v;i<=q;i++){
            scanf("%d%d",&u,&v);
            printf(" %.6lf",b[u][v]);
        }puts("");

    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

谷歌

[原创]第十五届北京师范大学程序设计竞赛 [(6+1)/11,待补]

[原创]第十五届北京师范大学程序设计竞赛 [(6+1)/11，待补] 2017-04-24 01:09:43 Tabris_ 阅读数：695 博客爬取于 2020-06-14 22:40:5...

[原创]第十四届浙江省赛 ZOJ 3962~3965 【E,F,G,H】 (其他并不准备补。)

[原创]第十四届浙江省赛 ZOJ 3962~3965 【E,F,G,H】 (其他并不准备补。) 2017-04-22 23:30:04 Tabris_ 阅读数：829 博客爬取于 2020-...