Algorithm103


又到了周六了。

在这个大家齐聚一堂一(考)起(模)蛤(拟)啤(赛)的日子里,我们进行了第三次模拟赛——Algorithm103.

今天的题难度好大QAQ,一!点!都!不!水!


T1:图论::Floyd-Warshall算法

题目大意:把money分成N份,放到N层的书架上,每层可能有0条、1条或者多条连接线连接比当前层低的某层。任意选择一层开始,只能沿着当前层的某条连接线走向下面的某层,到达这一层后,这层的 money 才能得到。也就是如果拿了一层的 money 后,就可以顺着连接线向下层去拿那层的 money,直到没有连接线停止。
求最多共能拿到多少money.

INPUT OUTPUT
3
12 2 3
20
30
42

这道题非常的裸……看到层与层之间用线连接就明白了这题是要抽象成图的。那么怎么抽象呢?

对于每两层之间的连接,都定义成两个点之间的边。由于连接是单向的,所以这是一个有向有权图。

那么权值如何定义呢?对于每条边,只需定义它的权值为终点的点值就好了(以边权替代点权),然后在计算权值和的时候,直接再加上起点的权值(只需添加这条路径的起点)即可。

这道题最难的其实是读入数据QAQ……其实也不难,一行代表一个节点的出边,那么就使用gets()函数读入一行,然后再进行以字符串方式读数的读入处理。

一定记得把第一行数n后面的'\n'使用getchar()处理一下不然第一次读入的就是'\n'了……

AC.

附代码:

#include <cstdio>
#include <cstring>
#include <algorithm>

int ans,money[110],n,map[110][110];
char a[1000];

void scan()
{
    scanf("%d",&n);
    getchar();
    for(int i=1;i<=n;++i)
    {
        gets(a);
        int len=strlen(a);
        int tmp=1,res=0;
        for(int j=0;j<=len;++j)
        {
            if(a[j]==' '||a[j]=='\0')
            {
                if(tmp==1)
                {
                    ++tmp;
                    money[i]=res;
                    res=0;
                    continue;
                }
                map[i][res]=1;
                ++tmp;
                res=0;
            }
            else
            {
                res=res*10+(a[j]-'0');
            }
        }
    }
}

void floyd()
{
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(map[i][k]!=0&&map[k][j]!=0) map[i][j]=std::max(map[i][j],map[i][k]+map[k][j]);
}

void build()
{
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        {
            if(map[i][j]==1)
            {
                map[i][j]=money[j];
            }
        }
}

int main()
{
    freopen("gift.in","r",stdin);
    freopen("gift.out","w",stdout);
    scan();
    build();
    floyd();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            ans=std::max(ans,money[i]+map[i][j]);
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2:贪心

你可以不会对拍,但是你不可以不会调代码。

题目大意:现在假定一共有 N 个作业,因为每个作业对于某小朋友来说难度都不大,所以某小朋友都可以在一个单位时间内完成,并且某小朋友每个单位时间只能做一门作业,每个作业有一个最晚完成时间和一个重要程度 w[i]。当然即便某小朋友很努力的在做作业,也有的作业因为安排不得当而不能完成。 现在请你帮某小朋友安排合理的作业顺序,使得完成的作业的重要程度和最大。

INPUT OUTPUT
3
2 1.1
1 4.0
2 3.1
7.10

第二题其实并不难……思路又一次对了?初步想的是DP但是后来发现没那么难……我感觉是暴力但实际上我的解法是贪心……

这道题赛后证明有两大错误:

1.数据类型没有用double而用了float.我也不知道我怎么想的选择了float.大概没记错的话是因为看到了“浮点数”三个字……而float实际上不应该用因为精度太低了……赛后进行试验确确实实有两个点是拿来卡float的……

2.关于for循环赋值的边界问题。关于这个事情大概Ciel深有体会吧?

float调成double是很快的,但是for循环边界值的问题楞是和旁边同学(Ciel)debug了半个多小时QAQ最后找老师几分钟就debug出来了真神奇QAQ

一定要会debug啊~

T2改前

#include <cstdio>
#include <algorithm>

struct node{
    int d;
    float w;
}task[10100];

int n,top,q[10100];
float ans;

bool cmp(node a,node b)
{
    if(a.w==b.w) return a.d>b.d;
    return a.w>b.w;
}

int main()
{
    freopen("task.in","r",stdin);
    freopen("task.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%f",&task[i].d,&task[i].w);
    }
    std::sort(task+1,task+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        int s=task[i].d;
        while(s>0&&q[s]!=0) --s;
        if(s!=0) q[s]=i;
        /*
        else
        {
            int k=0x7fffffff;
            float tmp=task[i].w;
            for(int j=1;j<=task[i].d;++j)
                if(tmp>task[q[j]].w)
                {
                    k=j;
                    tmp=task[q[j]].w;
                }
            if(k!=0x7fffffff)
            {
                q[k]=i;
            }
        }
        */
    }
    for(int i=1;i<=n;++i) ans+=task[q[i]].w;
    printf("%.2f",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2改后

#include <cstdio>
#include <algorithm>

struct node{
    int d;
    double w;
}task[10100];

int n,top,q[10100];
double ans;

bool cmp(node a,node b)
{
    if(a.w==b.w) return a.d>b.d;
    return a.w>b.w;
}

int main()
{
    freopen("task.in","r",stdin);
    freopen("task.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%lf",&task[i].d,&task[i].w);
    }
    std::sort(task+1,task+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        int s=task[i].d;
        while(s>0&&q[s]!=0) --s;
        if(s!=0) q[s]=i;
        /*
        else
        {
            int k=0x7fffffff;
            double tmp=task[i].w;
            for(int j=1;j<=task[i].d;++j)
                if(tmp>task[q[j]].w)
                {
                    k=j;
                    tmp=task[q[j]].w;
                }
            if(k!=0x7fffffff)
            {
                q[k]=i;
            }
        }
        */
    }
    for(int i=1;i<=10000;++i) ans+=task[q[i]].w;
    printf("%.2lf",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

AC的代码最终因为疏忽得分50分,还搭进去半个小时Debug


T3:DP

题目大意:已知某小朋友一共有 N 分钟的时间,每分钟他可以 run 或者 rest。若他在第 i 分钟 run,可以跑 出 d[i] 米,同时疲劳度增加 1(初始为 0)。若他在第 i 分钟休息,则疲劳度减少 1。无论何时, 疲劳度都不能超过 M。另外,一旦他开始休息,只有当疲劳度减为 0 时才能重新开始 run。在第 N 分钟后,他的疲劳度必须为 0。求某小朋友最远跑的距离。

INPUT OUTPUT
5 2
5
3
4
2
10
9

这道题——比赛的时候连正解思路都没想出来啊?

没办法,只好用一种万能的解法(似乎),它叫做DFS,又名高级暴力(然后还写挂了QAQ)

不过老师数据弱直接送给我们每人10分~有一个点没有输入,输出为0,我们就莫名其妙的都得了10分o(* ̄▽ ̄*)ブ(写正解的挂了QAQ)


20170717补充

GG……这时间才想起来写

确切来说是自己刷水的时候写SB题WA了没发现哪里有Bug……这道题其实真的特别简单QwQ

不在这里发正解了。请移步传送门

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - Algorithm103


不骗了,不骗了。
A Simple OIer fighting tooth and nail.