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

[原创]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;
}