国庆节集训Algorithm101


额……博客终于写些有用的了哈(ε=ε=ε=┏(゜ロ゜;)┛
今天进行了NOIP第一次模拟比赛……题目(似乎)并不是NOIP提高组的难度,只是体验一下比赛的状态……不过,题还是有难度的(虽然我考试刚读完题时不这么想QAQ)

Algorithm 101

全局信息

 

题目名 文件名 时间限制 内存限制
减法 sub.cpp/in/out 1s 128M
晚餐 dinner.cpp/in/out 1s 128M
乐高山上的士兵 lego.cpp/in/out 1s 128M

总得分:200’/300’


T1:真·裸·弱·高精度减法

题目梗概:计算A-B的值,其中 1<=A<=10^1000, 0<=B<=A。

Input:A B

Output:A-B

样例

Input Output
10
1
9

高精度减法本来是一道非常难的题……但是限制了a>b>0之后就没什么难度了……

这道题涉及的借位计算原来没有写过(而且还没好好学过小学数学QAQ),然后这道题我就用了一种递归借位完全模拟数学借位方式的方法进行运算……虽然最后也是对的但是显然不是正解(正解怎么可能用递归借位……万一爆栈就显得很尴尬了……)

void borrow(int x)
{
    //由第x位向前借位直接更改高精度数a的递归函数
    if(a[x+1]!=0)
    {
        --a[x+1];
        a[x]+=10;
        return;
    }
    else
    {
        borrow(x+1);
        --a[x+1];
        a[x]+=10;
        return;
    }
}

之后好久才明白其实可以不用纯数学模拟借位……应该直接向前借位,哪怕前一位会变成负数。因为a恒大于b,所以a的第x+1位变成负数后还会向前借位,不会导致出现其他的问题……

void borrow(int x)
{
    --a[x+1];
    a[x]+=10;
    return;
}

为了防止前缀零的出现,我使用了ans[0]来记录高精度整数ans的长度,从前往后第一个不是0的数即为最高位。但是这种方法无法解决ans==0时的情况……

于是,本题90分,10分的a==b特判分丢掉了……

在高精度减法计算时,一定要特判当A==B即ans==0的特殊情况!!!!

改后AC。

附改后代码:

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

int a[1010],b[1010],ans[1010];
char input[1010];

void in()
{
    scanf("%s",input);
    a[0]=strlen(input)-1;
    for(int i=0;i<=a[0];++i)
    {
        a[i+1]=input[a[0]-i]-'0';
    }
    scanf("%s",input);
    b[0]=strlen(input)-1;
    for(int i=0;i<=b[0];++i)
    {
        b[i+1]=input[b[0]-i]-'0';
    }
    ++a[0],++b[0];
}

void calc()
{
    for(int i=1;i<=a[0];++i)
    {
        if(a[i]>=b[i]) ans[i]=a[i]-b[i];
        else
        {
            --a[i+1];
            a[i]+=10;
            ans[i]=a[i]-b[i];
        }
        if(ans[i]!=0) ans[0]=i;
    }
}

int main()
{
    freopen("sub.in","r",stdin);
    freopen("sub.out","w",stdout);
    in();
    calc();
    if(ans[0]==0) ans[0]=1;
    for(int i=ans[0];i>0;--i) printf("%d",ans[i]);
    return 0;
}

T2:(简单?)·DP

题目梗概:对于每一个需要决策的步骤i,都可以选择A,花费时间a[i],或者B,花费时间b[i],而如果由A切换至B或由B切换至A则需要花费c[i]时间,问如何决策使最终总时间最短。(最开始选择A,即对于i=1,可直接选择A或者花费c[1]时间切换至B)

题目摘要(人话):某小朋友吃饭,从第一道吃到最后一道菜,在开吃之前他把筷子拿在手里。 对于第 i 道菜,如果使用勺子吃会花费时间 Ai,如果使用筷子吃会花费时间 Bi,如果吃这道 菜时需要交换勺子和筷子的话,则交换所耗费的时间 Ci。注意不能一道菜同时使用勺子和筷子。求他吃完所有菜所需要的最短时间。

Input:第一行是一个整数 n,表示有 n 道美味。 之后 n 行,每行三个整数 Ai,Bi,Ci。含义如题目描述。

Output:最短时间。

样例

Input Output
2
2 4 2
7 3 1
7

DP有的很难有的很简单……这次考试的第二题就属于(似乎)(看起来)(基本上)简单的类型。

题目涉及选择两种方案中的一种。于是决定使用两个数组来存储在此判定流程中选择第一种方案和第二种方案的最优方案。递推完成DP。

AC。

附代码:

#include <cstdio>
#include <algorithm>

int n,a[10100],b[10100],c[10100];
int f1[10100],f2[10100];

int main()
{
    freopen("dinner.in","r",stdin);
    freopen("dinner.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    }
    f1[1]=c[1]+a[1];
    f2[1]=b[1];
    for(int i=2;i<=n;++i)
    {
        f1[i]=std::min(f1[i-1]+a[i],f2[i-1]+c[i]+a[i]);
        f2[i]=std::min(f1[i-1]+c[i]+b[i],f2[i-1]+b[i]);
    }
    printf("%d",std::min(f1[n],f2[n]));
    return 0;
}

h2>T3:"困难"·DFS

题目梗概:提供一个地图,在此地图中找到山顶的个数。(注:一个山顶是由一个或者多个连续的点构成的,并且与山顶相连的点的高度都小于山顶的高度。如果两个点相连,则这两个点的行的差都不超过 1,列的差也不超过 1。)

题目摘要(人话):某小朋友用lego板建造了好多大山,问有多少个山顶。假设 lego 大板是 N(1<=N<=100)行和 M(1<=M<=100)列,每个点都有一个高度为 H (0<=H<=10000)当然高度为0表示地面,不能称之为山顶。一个山顶是由一个或者多个连续的点构成的,并且与山顶相连的点的高度都小于山顶的高度。如果两个点相连,则这两个点的行的差都不超过 1,列的差也不超过 1。

Input:第一行:两个由空格隔开的正整数 N 和M。接下来的N行,每行有M个由空格隔开的整数。第i行第j列的整数表示这个点(i,j) 的高度。

Output:一行一个整数,表示山顶个数。

样例

Input Output
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
3

这道题似乎没读懂的说……然后就WA了好多,只对了一个点。10/100分。

这道题……我似乎没有读懂关于山顶的定义……山顶:对于每个山峰(群),可能有多个山顶,而且每个山顶的面积与高度可能不相等。

这道题我当时的思路是:使用一个num数组记录每个高度共有多少个点,每次DFS一个山峰前memset num数组为0,DFS中记录num[i]最大的i值,DFS结束之后最大i的num[i]就是山顶个数了。

但是这样求出的实际上是山顶总面积,而非山顶个数。无奈样例数据弱,所以也没有及时发现更改啊555~

(更正:连山顶面积都不是ans。ans是本山峰中最高点的面积,但是一座山峰可能有数个山顶,而且每个山顶的面积和高度都可以不相同

全题修改前代码如下:

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

int maxnum,num[10100],n,m,h[110][110],ans,da[]={1,1,1,-1,-1,-1,0,0},db[]={0,1,-1,0,1,-1,1,-1};
bool finish[110][110];

void dfs(int x,int y)
{
    finish[x][y]=true;
    num[h[x][y]]++;
    maxnum=std::max(maxnum,h[x][y]);
    for(int i=0;i<8;++i)
    {
        int a=x+da[i],b=y+db[i];
        if(a>0&&a<=n&&b>0&&b<=m&&!finish[a][b]&&h[a][b]!=0) dfs(a,b);
    }
    return;
}

int main()
{
    freopen("lego.in","r",stdin);
    freopen("lego.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j) scanf("%d",&h[i][j]);
    }
    for(int i=1;i<n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(h[i][j]!=0&&!finish[i][j])
            {
                memset(num,0,sizeof num);
                maxnum=0;
                dfs(i,j);
                ans+=num[maxnum];
            }
        }
    }
    printf("%d",ans);
    return 0;
}

赛后讲题过程中,终于明白原来读错了题,正解应该是这样的:

DFS函数携带返回值,返回值数据类型为Bool,返回值为true则此点为山顶,返回值为false则此点不是山顶。

对于每个点,搜索与其相邻的点(共8个),如果发现与其相邻的点中有比它高的点,说明这个点不是山顶,返回false;如果发现有比它低的点,并不能说明什么,不做处理(代码中不判断是否小于该点,见代码);

而最后当DFS结束后返回的值即为此点是否为山顶。DFS函数开始时,需要对finish[x][y] (Bool)赋值true,表示该点已经搜索到。而每次main函数中执行DFS结束后如果返回值为true则++ans,如为false不予理睬。

因为在搜索和它同样高度的点的时候和它高度一样的点已经做标记了(DFS函数开始时标记该点),所以不会出现重复++ans的情况。

这样似乎就能改成AC?尝试ing……

(改完之后只对两个点……后来发现搜索遍历的时候行数写的是小于号(迷之小于号)之后就少遍历整整一行……)

改后AC。

(这道题数据比较弱……有一种特判所有点都是0时因为没有山峰所以没有山顶啊……改完之后成功卡掉std和std2哈哈哈哈哈ε=ε=ε=┏(゜ロ゜;)┛)

附改后代码:

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

int maxnum,num[10100],n,m,h[110][110],ans,dx[]={1,1,1,-1,-1,-1,0,0},dy[]={0,1,-1,0,1,-1,1,-1};
int da[8]={1,1,0,-1,-1,-1,0,1};
int db[8]={0,1,1,1,0,-1,-1,-1};
bool finish[110][110];

bool dfs(int x,int y)
{
    finish[x][y]=true;
    bool tmp=true;
    for(int i=0;i<8;++i)
    {
        int a=x+da[i],b=y+db[i];
        if(a>0&&a<=n&&b>0&&b<=m)
        {
            if(h[a][b]==h[x][y]&&!finish[a][b]) tmp=tmp&dfs(a,b);
            if(h[a][b]>h[x][y]) tmp=false;
        }
    }
    return tmp;
}

int main()
{
    freopen("lego.in","r",stdin);
    freopen("lego.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&h[i][j]);
    for(int i=1;i<=n;++i)//千万要写"<="!!!!!!!!!!
    {
        for(int j=1;j<=m;++j)
        {
            if(!finish[i][j]&&h[i][j]!=0)
            {
                ans+=dfs(i,j);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

 


后记

本次考试第一题疏忽了特判……做题时一定要想好临界情况和特判情况,防止出现卡特判的情况。

第三题没读明白……如果题目改成最高山顶的面积我就对了(好牵强)考试时一定要读明白题,万万不可理解错题意导致不应该的丢分。


在最后……

T3按照我那种写法即使加上等于号似乎也是10分……(内心平衡了)

啊对对对还有好多童鞋也写了题解(发完链接就跑路23333)

  1. 【模拟测试】Algorithm101 -- By Ciel
  2. 对于algorithm101的总结 -- By SuperBia_zyb

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

转载:转载请注明原文链接 - 国庆节集训Algorithm101


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