NOIP 2016酱油记


NOIP2016终于结束了。
成绩还没有正式下来,但是已经本地测评了……
挂了。挂了就挂了吧,反正都那样了qwq
可是据说高二学长们有的有遗憾?为他们默哀……

今年的题比之前的难到不知道哪里去了……本来说好的D1各种愉快怎么变成了炒鸡难……今天本来是希望愉愉快快的答题结果变成了骗分大赛……不管了,总之这次还是可以的吧没有遗憾了……只是发现了打脸的事情?

NOIP在即,现在是时候复(学)习STL了——这是一款可以极大压缩代码量的神器,可以轻松地调试(虚无……)

——NOIP倒计时两天关于STL的复习(就这么多,未更)

说好的学习STL,重点学习<priority_queue>的呢……对不起Eolv大爷你教我来着可是我极其不熟练,比赛的时候不敢用……

哎……言归正传,路还是要走的嘛……

注意:这不是题解!我的知识水平还没掌握AK所需知识点!

NOIP 2016酱油记


Day 1

D1T1:喜闻乐见大水题

第一题本来就是喜闻乐见的嘛……(捂脸)

题目大意:有n个玩具小人围成一圈, 已知它们的职业和朝向。现在第1个玩具小人告诉小南一个包含m条指令的谜題, 其中第z条指令形如“左数/右数第s个玩具小人”。你需要输出依次数完这些指令后,到达的玩具小人的职业。

样例
INPUT OUTPUT
7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2
writer

这道题水模拟嘛~~注意如果%完之后小于等于0的话呢需要加上n补回来~

据说有的大爷也没考虑到%之后如果是0的时候要变成n于是大爷们“身败名裂”嘿嘿嘿

AC.

附重制代码:

#include <cstdio>
#include <cstring>

struct p{
    bool face;
    char job[20];
}person[100100];
int n,m,a,s,nowp=1;

void toyfind(bool way,int dis)
{
    if(way)
        {
            if(person[nowp].face) nowp-=dis;
            else nowp+=dis;
        }
    else
        {
            if(person[nowp].face) nowp+=dis;
            else nowp-=dis;
        }
    nowp%=n;
    if(nowp<=0) nowp+=n;
    return;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d%s",&person[i].face,&person[i].job);
    while(m)
    {
        --m;
        scanf("%d%d",&a,&s);
        toyfind(a,s);
    }
    printf("%s\n",person[nowp].job);
    return 0;
}

 


D1T2:骗分::链式前向星+DFS寻径法

D1考完之后抱怨题恶心的同时顺道刷一刷知乎哈~发现有人已经发骗分版题解了~第二题骗分正解就是链式前向星+DFS寻径,过不了几个点但是绝对是性价比高(就会这么写)的QwQ

我的想法很简单咯:对于每一个玩家,通过记忆化DFS确定每个玩家的路径,然后每秒确认一下是否有观察员该秒在那个点就可以了呢~

测试结果应该是20/100分左右?暴力的结果就是TLE嘛~这道题6,7,8三个点树退化成了一条链……似乎可以再多骗些分?当时没细想(样例都过了炒鸡开心的说~)

附部分分重制代码:

#include <cstdio>
#include <cstring>

int top,n,m,to[101000],head[101000],next[101000],u,v,w[101000],s,t,route[101000],ans[101000];
bool flg,use[101000];

void dfs(int depth)
{
    if(flg) return;
    if(route[depth]==t)
    {
        flg=true;
        return;
    }
    for(int i=head[route[depth]];i;i=next[i])
    {
        if(!flg&&!use[to[i]])
        {
            use[to[i]]=true;
            route[depth+1]=to[i];
            dfs(depth+1);
            use[to[i]]=false;
        }
    }
}

void edgeadd(int from,int topoint)
{
    ++top;
    to[top]=topoint;
    next[top]=head[from];
    head[from]=top;
}

void calc()
{
    memset(route,0,sizeof route);
    memset(use,0,sizeof use);
    flg=false;
    route[0]=s;
    use[s]=true;
    dfs(0);
    for(int i=0;route[i];++i)
    {
        //printf("%d ",route[i]);
        if(w[route[i]]==i)
        {
            ++ans[route[i]];
            //printf("%d %d %d\n",i,route[i],w[route[i]]);
        }
    }
    //printf("\n");
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        edgeadd(u,v);
        edgeadd(v,u);
    }
    for(int i=1;i<=n;++i) scanf("%d",&w[i]);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&s,&t);
        calc();
    }
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
    return 0;
}

 


D1T3:骗分大赛重点题(据说)

这道题据说是骗分大赛高潮题啊~貌似只有20多分骗不得?总之各种特殊数据啊~骗分骗得特别爽~

不过我骗得一点都不开心(雾)

特判没有换教室次数的情况,只能换一次教室的情况,还有只有一个时间段上课(即不需要在教室间穿梭,路程==0,答案==0.00的情况),k[i]==1即100%可以申请到调整教室的情况就可以了……

结果概率算不明白了(大雾)那就抛弃k[i]==1,好,那也是30分啊(注:后进行测试得分28)可是floyd也挂了(巨雾)

于是,60分(保守预计)的骗分就被我活生生搞成了4分(雾)

Floyd为什么我要初始化成0x7f……(抱头痛哭?

附4分和28分(预估)代码:

//NOIP2016-D1T3 by TonyZhao

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

int n,m,v,e,c[2100],d[2100],a,b,w,map[2100][2100];
double k[2100];
bool flgk=true;

void floyd()
{
    for(int k=1;k<=v;++k)
        for(int i=1;i<=v;++i)
            for(int j=1;j<=v;++j) map[i][j]=std::min(map[i][j],map[i][k]+map[k][j]);
}

void m0calc()
{
    long long ans=0;
    floyd();
    for(int i=2;i<=n;++i)
    {
        int tx=c[i-1],ty=c[i];
        ans+=map[tx][ty];
    }
    printf("%lld.00",ans);
    return;
}

void m1calc()
{
    floyd();
    long long stdans=0;
    for(int i=2;i<=n;++i)
    {
        int tx=c[i-1],ty=c[i];
        stdans+=map[tx][ty];
    }
    double ans=0.00;
    for(int i=1;i<=n;++i)
    {
        int tmp=c[i];
        c[i]=d[i];
        floyd();
        long long res=0;
        for(int j=2;j<=n;++j)
        {
            int tx=c[j-1],ty=c[j];
            res+=map[tx][ty];
        }
        c[i]=tmp;
        ans+=k[i]*res;
        ans+=(1.00-k[i])*stdans;
    }
    printf("%lf",ans);
    return;
}

int main()
{
    freopen("classroom.in","r",stdin);
    freopen("classroom.out","w",stdout);
    memset(map,0x7f,sizeof map);
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(int i=1;i<=v;++i) map[i][i]=0;
    for(int i=1;i<=n;++i) scanf("%d",&c[i]);
    for(int i=1;i<=n;++i) scanf("%d",&d[i]);
    for(int i=1;i<=n;++i)
    {
        scanf("%lf",&k[i]);
        if(k[i]<0.9999999) flgk=false;
    }
    for(int i=1;i<=e;++i)
    {
        scanf("%d%d%d",&a,&b,&w);
        if(a==b) continue;
        if(map[a][b]>w)
        {
            map[a][b]=w;
            map[b][a]=w;
        }
    }
    if(n==1)
    {
        printf("0.00");
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    if(m==0)
    {
        m0calc();
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    if(m==1)
    {
        m1calc();
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    m1calc();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

 

//NOIP2016-D1T3 by TonyZhao

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

int n,m,v,e,c[2100],d[2100],a,b,w,map[2100][2100];
double k[2100];
bool flgk=true;

void floyd()
{
    for(int k=1;k<=v;++k)
        for(int i=1;i<=v;++i)
            for(int j=1;j<=v;++j) map[i][j]=std::min(map[i][j],map[i][k]+map[k][j]);
}

void m0calc()
{
    long long ans=0;
    floyd();
    for(int i=2;i<=n;++i)
    {
        int tx=c[i-1],ty=c[i];
        ans+=map[tx][ty];
    }
    printf("%lld.00",ans);
    return;
}

void m1calc()
{
    floyd();
    long long stdans=0;
    for(int i=2;i<=n;++i)
    {
        int tx=c[i-1],ty=c[i];
        stdans+=map[tx][ty];
    }
    double ans=0.00;
    for(int i=1;i<=n;++i)
    {
        int tmp=c[i];
        c[i]=d[i];
        long long res=0;
        for(int j=2;j<=n;++j)
        {
            int tx=c[j-1],ty=c[j];
            res+=map[tx][ty];
        }
        c[i]=tmp;
        ans+=k[i]*res;
        ans+=(1.00-k[i])*stdans;
    }
    printf("%lf",ans);
    return;
}

int main()
{
    memset(map,0x3f,sizeof map);
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(int i=1;i<=v;++i) map[i][i]=0;
    for(int i=1;i<=n;++i) scanf("%d",&c[i]);
    for(int i=1;i<=n;++i) scanf("%d",&d[i]);
    for(int i=1;i<=n;++i)
    {
        scanf("%lf",&k[i]);
        if(k[i]<0.9999999) flgk=false;
    }
    for(int i=1;i<=e;++i)
    {
        scanf("%d%d%d",&a,&b,&w);
        if(a==b) continue;
        if(map[a][b]>w)
        {
            map[a][b]=w;
            map[b][a]=w;
        }
    }
    if(n==1)
    {
        printf("0.00");
        return 0;
    }
    if(m==0)
    {
        m0calc();
        return 0;
    }
    if(m==1)
    {
        m1calc();
        return 0;
    }
    m1calc();
    return 0;
}

 


难度[D1]>难度[D2]?

似乎是的。

可是D2也没拿什么分……(哭


Day 2

D2T1:数论(讲过的?)

这是一个凄惨的故事QAQ

早在两年前,老师就已经讲过数论的知识:比如说飞妈费马小定理和什么组合数问题啥的哈QAQ

当时的表情就是一脸%+一脸懵逼蛤~

于是,比赛的时候就一脸WTF,坚信着D2比D1难的我似乎D2分数比D1还少啊QwQ(不高兴

骗分呗qwq据说某Superbia小同学模拟分数约分骗分骗到好多啊(捂脸)我竟然笨到去预!处!理!阶乘,天真的以为这样会很快(捂脸)比赛出来才恍然大悟:啊!10!就快爆int了啊!我竟然预处理2000!使用int……

于是,这道题欢快的得到了2个点貌似?(哭

代码丑哭,正解待补。


D2T2:<priority_queue>

不说啥了……满满的都是泪啊555~~~

这道题写法巨多~对于想骗分的人来说这其实是一个裸的STL题~

可是,我的STL还没复习完……我知道应该用eolv大爷教我的priority_queue,可是它的STL成员函数被我无情的遗忘了(哭),我还同时忘记了关于时间问题的优化(化增为减,除了被切的虫子都加,那么就单独让被切的虫子减,此时相对关系是一样的),于是似乎分数并不高……代码还死长死长的浪费了我好多时间~

比赛时我的写法是开始先std::sort一下,然后每次把最后的提出来切开,再模拟冒泡排序把切完的两个长度排回到指定位置……

附STL重制代码:

//NOIP2016-D2T2 ViolentSearch by TonyZhao

#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>

int tmp,n,m,q,u,v,t,a[1000100],timek;
double p;
std::priority_queue<int> pq;

int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=(u*1.00)/(v*1.00);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&tmp);
        pq.push(tmp);
    }
    for(int i=1;i<=m;++i)
    {
        int target=pq.top();
        target+=timek;
        if(i%t==0) printf("%d ",target);
        pq.pop();
        int x=(int)floor(target*p),y=target-x;
        timek+=q;
        x-=timek;
        y-=timek;
        pq.push(x);
        pq.push(y);
    }
    printf("\n");
    while(!pq.empty())
        {
            if((m+n-pq.size()+1)%t==0)printf("%d ",pq.top()+timek);
            pq.pop();
        }
    return 0;
}

 


D2T3并不会~就不写了(捂脸


写在后边

这次因为过于紧张发生了好多差错……比如说价值20分的Floyd初始值问题,价值15分+好几十分钟的STL问题,价值好多好多分的数论不复习问题?

据说学长也发生了这样的情况……

这次比赛后一定要加快效率,不浪费时间,用接下来一年的时间产出更多更高效的代码,提升自己的水平,征战OI之巅!

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

转载:转载请注明原文链接 - NOIP 2016酱油记


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