总结 Algorithm102

今天进行了NOIP第二次模拟比赛,即algorithm102……
友情链接:

【题解】国庆节集训Algorithm102 By Tonyzhao
【模拟测试】Algorithm102 By Ciel

测试概况

20161006133856301

话不多说,开始分析题目:

T1 腿

考查知识点:小学奥数
题目大意:一个笼子里面关了鸡和兔子(鸡有2只脚,兔子有4只脚,没有例外)。已经知道了笼子里面脚的总数a,问笼子里面至少有多少只动物,至多有多少只动物.如果没有满足要求的答案,则输出两个0。

水题
因为只有兔子和鸡,所以腿数一定为偶数条,若为奇数,就输出0 0;
最多动物的情况:全是鸡;
最少动物的情况:看看腿数能凑出几只兔子,然后再用鸡填;
AC

#include<cstdio>
#include<algorithm>
using namespace std;
int ans;
int main()
{
    freopen("leg.in","r",stdin);
    freopen("leg.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int m;
        scanf("%d",&m);
        if(m%2==1)
        {
            printf("0 0\n");
        }
        else
        {
            printf("%d %d\n",m/4+m%4,m/2);
        }
    }
}

T2 午睡音乐

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

如图,第一个音阶持续2个时间单位,第二个音阶持续1个时间单位,第三个音阶持续3个时间单位。下面是一些询问和回答:
T2

这道题的本质是在一个递增序列中找到第一个大于x的数;
所以我们想到了二分查找;

AC

#include<cstdio>
#include<algorithm>
using namespace std;
int a[50100];
long long sum[50100];
int n,q;
int fen(int tmp)
{
    int l=1;
    int r=n;    
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(tmp>sum[mid]){l=mid+1;}
        else if(tmp<sum[mid]){r=mid;}   
        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",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=q;i++)
    {
        int nmp;
        scanf("%d",&nmp);
        int ans=fen(nmp+1);
        if(nmp+1==sum[n])ans=n;
        printf("%d\n",ans);
    }
}

T3 线段

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

首先按线段右端点由小到大的顺序排序;
然后动态规划:
F[i]:表示前i个区间所获得的最大价值
F[i]=max{ F[i] , F[j]+w[i] };
其中满足:e[j].y<=e[i].x;
需要注意,j的枚举范围要从0开始,也就是把第i个区间当成第一个选择的区间;

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,ans,f[1010];
struct your 
{ 
    int x,y,z;
}e[1010];
bool cmp(your a,your b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
    }
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(e[j].y<=e[i].x) 
            {
                f[i]=max(f[i],f[j]+e[i].z);
            }
        }
    }
    for(int i=1;i<=n;i++)   
    {
        ans=max(ans,f[i]);
    } 
    printf("%d",ans);
    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注