Algorithm106


今天进行了两场比赛——常规比赛Algorithm106以及喜闻乐见?(什么鬼)的Zero I水题欢乐赛。

作为高一年级第二梯队每周最盛大的信息学比赛Algorithm10x系列竞赛以其较为严谨认真,严肃活泼,严格苛刻(什么鬼)的竞赛风格和风趣幽默的题目成为最受瞩目,最受欢迎也是最正式的竞赛。


T1:数论::线性筛素数

题目大意:求正整数集中第n个素数。其中n<=100000

数论裸题,直接上线性晒素数,时间复杂度O(n),不过据说朴素的算法也能AC……数据真是彪悍QwQ

AC.

附代码:

#include <cstdio>

int prime[150100],cnt,n,i=1;
bool notprime[1500100];

int main()
{
    freopen("prime.in","r",stdin);
    freopen("prime.out","w",stdout);
    scanf("%d",&n);
    while(1)
    {
        ++i;
        if(!notprime[i])
        {
            ++cnt;
            prime[cnt]=i;
            if(cnt==n)
            {
                printf("%d",prime[n]);
                fclose(stdin);
                fclose(stdout);
                return 0;
            }
        }
        for(int j=1;j<=cnt;j++)
        {
            if(i*prime[j]>1500000) break;
            notprime[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

T2:拓扑排序

题目大意:给你M条信息。第i条信息由2个正整数描述:(Ai Bi),表示Ai号按钮应该在Bi号按钮前被按下。如果能够按顺序按下按钮请输出“OK”。如果给定的信息有误,请输出有多少个按钮不能被确定按下的顺序。

其中,2<M,N<=100000    1<=Ai,Bi<=N

拓扑排序真的好难……当时练习的还是少考试的时候连<queue>队列优化都忘了搞得我直接上O(n^2)扫描式算法qwq还好数据弱(为什么这次数据都这么弱qwq) 只是TLE了一个点啊

90/100.

附改后代码:

大坑待补

T3:多重背包

题目大意:一个背包容量为V,有许多物品,其中一些只能拿一件,一些可以拿不限次数多件,一些最多只能拿限制次数件。问获得的最大价值。

这道题裸的多重背包,01背包和完全背包写函数,有限制的物品就二进制拆分掉直接调用01背包函数就可以了,非常快QwQ

AC.

附代码:

#include <cstdio>
#include <algorithm>

int ans,n,value,v,w,m,f[200100];

void infinity37(int a,int b)
{
    for(int i=a;i<=value;++i)
    {
        if(f[i-a]!=0||i-a==0) f[i]=std::max(f[i],f[i-a]+b);
    }
}

void one(int a,int b)
{
    for(int i=value;i>=a;--i)
    {
        if(f[i-a]!=0||i-a==0) f[i]=std::max(f[i],f[i-a]+b);
    }
}

void apart(int a,int b,int c)
{
    int tot=1,tmp=0;
    while(tot<c)
    {
        one(a<<tmp,b<<tmp);
        ++tmp;
        tot+=(1<<tmp);
    }
    tot-=1<<tmp;
    if(tot<c)
    {
        tmp=c-tot;
        one(a*tmp,b*tmp);
    }
    return;
}

int main()
{
    freopen("mix.in","r",stdin);
    freopen("mix.out","w",stdout);
    scanf("%d%d",&n,&value);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&v,&w,&m);
        if(m==1) one(v,w);
        else if(m==-1) infinity37(v,w);
        else apart(v,w,m);
    }
    for(int i=1;i<=value;++i) ans=std::max(ans,f[i]);
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

写在后面

Algorithm106是有史以来我最接近AK的一场考试(捂脸)也是第一次全场最佳(捂脸)也是对一周之后NOIP最大的鼓励了吧(捂脸

希望今后的比赛之中能够加强代码能力,提高题目分析能力,在今后的比赛和一周之后的NOIP中发挥更好的成绩!


为什么客官不去看看同日进行的Zero I水题欢乐赛呐(#手动滑稽)

顶上就是传送门,看啥看,快点啊!

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

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


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