国庆节集训Algorithm102


两天之后(对就是今天),我们进行了国庆节集训的第二次测试——Algorithm102。

Algorithm 102

全局信息

题目名 文件名 时间限制 内存限制
leg leg.cpp/in/out 1s 128M
music music.cpp/in/out 1s 128M
long long.cpp/in/out 1s 128M

总得分:190’/290’


T1:鸡兔同笼问题(小学奥数?)

题目梗概:一个笼子里面关了鸡和兔子(鸡有 2 只脚,兔子有 4 只脚,没有例外)。已经知道了笼子里面 脚的总数 a,问笼子里面至少有多少只动物,至多有多少只动物。

Input:第 1 行是测试数据的组数 n,后面跟着 n 行输入。每组测试数据占 1 行,每行一个正整数 a。

Output:输出包含 n 行,每行对应一个输入,包含两个正整数,第一个是最少的动物数,第二个是最多 的动物数,两个正整数用一个空格分开。如果没有满足要求的答案,则输出两个 0。

样例

INPUT OUTPUT
2
3
20
0 0
5 10

这道题……只能毫不谦虚地说真·水题……

直接上数学算法,算法时间复杂度O(1)……

8:00开始测试,8:12完工,8:30搞了个小测试(对拍?)把数据范围内所有可能性都过了一遍,(似乎)十分完美。

AC。

附代码:

#include <cstdio>

int n,a;

int main()
{
    freopen("leg.in","r",stdin);
    freopen("leg.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a);
        if(a%2!=0)
        {
            printf("0 0\\n");
            continue;
        }
        if(a%4==0)
        {
            printf("%d %d\\n",a>>2,a>>1);
            continue;
        }
        printf("%d %d\\n",(a+2)>>2,a>>1);
    }
    return 0;
}

T2:二分查找·前缀和

题目大意:老师会弹奏一些单调的音阶组成的音乐。已知第 i 个音阶要弹奏 bi 次,才会弹奏下一个音阶,总共有 N 个音阶。老师会从第 0 时刻开始弹奏,小朋友们听着单调的音阶就会慢慢入睡。 现在有 Q 个询问,询问时间段[T, T+1)内老师弹奏的是第几个音阶?

样例:

INPUT OUTPUT
3 2
2
1
3
1
2
1
2

这道题是一道比较裸(还行挺难的)一道二分查找题……

这道题我们都不敢用STL的upper_bound和lower_bound做啊……怕老师卡STL啊……(还记得某同学跟我们说自己就不写二分查找的题了因为可以用STL23333)

只能手写二分啊……

这道题有一点比较有趣就是当某个b[i]==0的时候会出现一些神奇的二分查找错误(前缀和出现重复的情况),但是这道题的数据范围已经确定没有b[i]==0了……于是便有人(比如我)神奇的WA了一个点……后来才发现数据出现问题去掉了这个点,于是满分就减去了10分,我也因此获得了满分(开心)

得分:90/100 —> 90/90(测试数据出错)

附代码(必须得试试STL啊嘿嘿嘿)

#include <cstdio>

int t,n,q,b,sum[50100];

int find(int target)
{
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(sum[mid]>target) r=mid;
        else if(sum[mid]<target) l=mid+1;
        else return mid;
    }
    return l;
}

int main()
{
    freopen("music.in","r",stdin);
    freopen("music.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&b);
        sum[i]=sum[i-1]+b;
    }
    for(int i=1;i<=q;++i)
    {
        scanf("%d",&t);
        printf("%d\\n",find(t+1));
    }
    return 0;
}

STL据说效率不行……真正比赛的时候还得用上面的似乎(哭)

for(int i=1;i<=q;++i)
{
scanf("%d",&t);
int ans=std::upper_bound(sum+1,sum+n+1,t+1)-sum;
if(sum[ans-1]>=t+1) --ans;
printf("%d\\n",ans);
}

T3:DP

题目梗概:对于每个线段都有不同的价值,且两端都是整数坐标。**想从 N 条线段中挑选出若干条,并且这些线段不出现覆盖(端点可以重合),使得这些线段的价值总和最大。

这道题其实并不难……algorithm101中DP题的AC给了我很大的信心,很快就想到了正解,开始码……

然而……然而……

for(int i=1;i<=n;++i)
{
    scanf("%d%d%d",&str[i].l,&str[i].r,&str[i].v);//读入结构体
    f[i]=str[i].v;//对f数组赋初值
}
std::sort(str+1,str+n+1,cmp);//更改结构体排列顺序而f数组照旧(哭

在读入结构题时,直接开始对f数组赋值(f数组初值为该结构体所表示的线段的价值),然后,我就把结构体sort了……改变了结构体的顺序,但是f数组还是原来的样子……

AC的代码最终因为疏忽得分0分

来让我们交换一下顺序,先进行排序后O(n)赋值……

这道题就这样A了……

附:T3改后代码(不要问我为什么痛哭流涕)

#include <cstdio>
#include <algorithm>

struct node{
    int l,r,v;
} str[1100];

int cmp(node x,node y)
{
    return x.l<y.l;
}

int n,ans,f[1010];

int main()
{
    freopen("long.in","r",stdin);
    freopen("long.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&str[i].l,&str[i].r,&str[i].v);
        //f[i]=str[i].v;
    }
    std::sort(str+1,str+n+1,cmp);
    for(int i=1;i<=n;++i) f[i]=str[i].v;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<i;++j)
        {
            if(str[j].r<=str[i].l)
            {
                f[i]=std::max(f[i],f[j]+str[i].v);
            }
        }
    }
    for(int i=1;i<=n;++i) ans=std::max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

写在后面

我还需要加强代码的严谨性与稳定性。嗯。

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

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


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