一月17日新生冬季练习赛解题报告H.龟兔赛跑

H是最后加上的一个题  看起来很厉害还5秒  其实如果做过类似的题的话就一点都不难了

今天的比赛就从最后加上的H题开始写吧

H.龟兔赛跑

Time Limit: 5000 MS

Memory Limit: 65536 K

 

Total Submit: 12 (9 users)

Total Accepted: 3 (3 users)

Special Judge: No

 

Description

乌龟和兔子赛跑,他们跑5个回合。他们跑的速度分别为v1, v20<=v<=50),但是每次跑的时候,由于天气的缘故,他们跑的速度并不稳定,为了使比赛更加公平,作为裁判的狐狸决定采用积分制来判定乌龟和兔子比赛的胜负。狐狸首先为每天的天气打分w,然后看乌龟和兔子跑的速度。一场比赛的得分,我们这样计算,首先,我们把乌龟和兔子的速度相减并平方,然后乘上天气分,这个得分记为比赛日状况分。然后,当天的比赛状况分乘以各自的速度,就是各自的得分。经过5轮比赛过后,裁判狐狸宣布,乌龟和兔子打成平局!乌龟和兔子都很奇怪,因为没有哪一天他们是打成平局的,怎么最后居然是平局。可是乌龟和兔子都不记得他们当时跑的速度了。于是乌龟和兔子找狐狸问,要他说出每一天兔子比乌龟快多少(全都是泪啊)。狐狸心想,那瞎掰一个就行了呗~那么请问,狐狸最多可以瞎掰出多少种情况呢?

Input

多组测试数据
每组测试数据为5个数wi,为第i天的天气分数(-100<wi<100)

Output

对于每组数据,输出可以瞎掰的情况的数量。

Sample Input

12 -34 -24 19 -35

Sample Output

1540

 

Submit

Message

 

这个题如果当时仔细读题的话应该也能做出来的   但是读题太匆忙的话就只能是像我一样读错题意调试半天调不出来。哎,不说了,全是泪啊

 

此题有五层for循环  直接做会超时的  所以我们选择用3for循环把数据储存起来,用两层for循环判断  数字有没有出现过   至于判断的手段自然很多:

Map很慢  也可以hash  当然最坑的是有个童鞋直接存在数组里也过了   实在不想说什么了

 

 

其实后台数据太水了,先写一个用map 四秒多过得代码   额  四秒多.......

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<map>

using namespace std;

 

map<int,int>mp;

 

int main()

{

    int a,b,c,d,e;

    while(cin>>a>>b>>c>>d>>e)

    {

        mp.clear();

        int sum=0;

        for(int i=-50;i<=50;i++)

        {

            if(i==0)

                continue;

            for(int j=-50;j<=50;j++)

            {

                if(j==0)

                    continue;

                for(int k=-50;k<=50;k++)

                {

                    if(k==0)

                        continue;

                    int x=i*i*i*a+j*j*j*b+k*k*k*c;

                    mp[x]++;

                }

            }

        }

        for(int i=-50;i<=50;i++)

        {

            if(i==0)

                continue;

            for(int j=-50;j<=50;j++)

            {

                if(j==0)

                    continue;

                int x=-1*i*i*i*d-j*j*j*e;

                    sum+=mp[x];

            }

        }

        cout<<sum<<endl;

    }

    return 0;

}

代码就不解释了    

 

接下来看另一种思路:

用比较省时的hash来做  当然还有小的惊喜哦

 

 

 

 

 

这是彭彪童鞋的代码:

AC代码:

 

#include <stdio.h>

#include <cstring>

#include <algorithm>

#define fabs(x) ((x)<0?(-x):(x))

const int maxn = 250001;

struct Hash

{

     Hash(){key=0,sum = 0;}

     int key;

     int sum;

}hash[maxn];

 

int main()

{

    int i, j, k;

    int a1, a2, a3, a4, a5;

    int _tmp, tmp, tmp1, tmp2, ans;

    int calCube[100];

    for(i = -50; i < 0; ++i)

        calCube[i+50] = i*i*i;

    for(i = 1; i <= 50; ++i)

        calCube[i+49] = i*i*i;

 

    while(scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5)!=EOF){

        memset(hash,0,sizeof(hash));

        tmp=ans=0;

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

             tmp=calCube[i]*a1;

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

                tmp1=tmp+calCube[j]*a2;

                tmp2=fabs(tmp1)%maxn;

                while(hash[tmp2].key!=tmp1&&hash[tmp2].sum!=0)

                    tmp2=(tmp2+1)%maxn;

                if(hash[tmp2].key==tmp1){

                    hash[tmp2].sum++;

                }

                else{

                    hash[tmp2].key =tmp1;

                    hash[tmp2].sum =1;

                }

            }

        }

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

            _tmp = calCube[i]*a3;

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

                tmp = _tmp+calCube[j]*a4;

                for(k = 0; k < 100; ++k){

                    tmp1 = tmp + calCube[k]*a5;

                    tmp2 = fabs(tmp1)%maxn;

                    while(hash[tmp2].key!=-tmp1&&hash[tmp2].sum!=0)

                        tmp2=(tmp2+1)%maxn;

                    ans+=hash[tmp2].sum;

                }

            }

        }

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

    }

    return 0;

}

 

这是我ac的更牛叉

#include<iostream>

#include<string.h>

using namespace std;

 

const long long int maxn=100*100+10;

 

long long int hashbox[maxn];

 

long long int num[maxn];

 

long long int Find(long long int n)

{

     int key=n%maxn;

    while(1)

    {

        if(hashbox[key]==-1||hashbox[key]==n)

            return key;

        key=(key+1)%maxn;

    }

}

 

int main()

{

    long long int n,a,b,c,d,e;

    std::ios::sync_with_stdio(false);

    while(cin>>a>>b>>c>>d>>e)

    {

        memset(num,0,sizeof(num));

        memset(hashbox,-1,sizeof(hashbox));

        for(int i=-50;i<=50;i++)

        {

            if(i==0)continue;

            for(int j=-50;j<=50;j++)

            {

                if(j==0)continue;

                long long int xx=i*i*i*a+j*j*j*b;

                if(xx<0)

                    xx=-xx;

                long long key=Find(xx);

                hashbox[key]=xx;

                num[key]++;

            }

        }

        long long int ans=0;

        for(int i=-50;i<=50;i++)

        {

            if(i==0)

                continue;

            for(int j=-50;j<=50;j++)

            {

                if(j==0)

                    continue;

                for(int k=-50;k<=50;k++)

                {

                    if(k==0)

                        continue;

                    long long int xx=-1*i*i*i*c-j*j*j*d-k*k*k*e;

                    if(xx<0)

                        xx=-xx;

                    long long int key=Find(xx);

                    ans+=num[key];

                }

            }

        }

        cout<<ans/2<<endl;

    }

    return 0;

}

抓住了 i既有+又有-而且相等这个特性  所以加起来色结果要除以二

一月17日新生冬季练习赛解题报告H.龟兔赛跑

上一篇:程序人生,人生程序。(面向对象的奇葩理解)


下一篇:Tar打包、压缩与解压缩到指定目录的方法