rainman's blog

学海无涯,回头是岸

NOIP2018游记

BGM: 风华正茂

Day -x

  • 10.31停掉了晚自习,因为周围人不太理解的缘故,并没有停课。只是停了晚自习,却感觉不能不用功——“看啊,这就是那个没上晚自习竞赛也一塌糊涂的家伙”。那些全面停课搞竞赛的会面临很大的压力吧?

  • 10.31晚,写 $lca$ 题,二分思路非常显然,但是 $check()$ 很不好写,效率奇低,怀疑人生。

  • 11.02。颓颓颓,2010年关押罪犯那题怎么那么难啊..谁说敌人的敌人就是朋友的,敌人的敌人也可以是敌人啊...mdzz心态再一次炸了,一开始还以为这是一道傻逼题,思路都对,结果细节不会写。

  • 看了 $cdcq$ 的NOI2017游记,大概我们都是带着风险与遗憾走过这条路的吧。

  • 他们说同校的已经在吊打 $zcy$ 了(这什么操作..?dalao1

  • 11.03。数据结构好难啊QAQ,自闭了。群里怎么都在讨论计算几何啊..老咸鱼不会啊..

  • 洛谷月赛凉凉,第一题没看到数据范围,以为数据很大,一直在草稿纸上推推推..总觉得斐波那契对M取模的周期可以推出来............一小时后....算了还是暴力吧...AC?!!

  • 第二题...非常明显的贪心不知道为什么没看出来...可能是我考试的时候就是会智商下降。题面看了一眼:woc这不是我才学过的DAGdp?好简单....:

//code by rainman
#include<cstdio>
#include<iostream>
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;

int n,h[310];
int graph[310][310];
bool vis[310];

inline void init()
{
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            int temp=(h[i]-h[j])*(h[i]-h[j]);
            graph[i][j]=graph[j][i]=temp;
        }
    }
}

int dp(int s)
{
    vis[s]=true;
    int temp=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i])continue;
        if(i==s)continue;
        temp=MAX(temp,dp(i)+graph[s][i]);
        vis[i]=false;
    }
    return temp;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    init();
    cout<<dp(0);
    return 0;
}

TLE,没考虑复杂度就交题,该打。

  • 第四题看起来不可做啊,还是看第三题好了...

  • 字符串我一直用string类啊,这数据用string怕是输入就很慢,还是看一下怎么scanf字符串吧..颓颓颓....30min后,噫我会了#于是开始状态压缩...一直写到比赛结束..没写完QAQ

总结:考试的经验不足啊,暴力还是要好好打的,不能期望太高肝正解...【pd好像就是想肝正解然后凉凉qwq】不熟悉的算法不要用,还不如打暴力,随机算法不要轻易使用,对于我这种不熟的人来说,随机算法很容易爆零。

PS:后来第二题我很愉快的用 $dijkstra$ 过了:

//rainman recode it
#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;

#define int LL
const int N=350,M=210000;
int head[N],tot,done[N],a[N];
long long dis[N];

struct Edge{
    int v,next;
    long long w;
}e[M];

struct node{
    int u,dist;
    bool operator<(const node& v)const
    {
        return dist<v.dist;
    }
};

inline void addedge(int u,int v,long long w)
{
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot;
}

inline void dijkstra(int s)
{
    priority_queue<node> qwq;
    for(int i=0;i<=310;i++)dis[i]=-1;
    dis[s]=0;
    node t, t1;
    t.u=s;t.dist=0;
    qwq.push(t);

    while(!qwq.empty())
    {
        t=qwq.top();qwq.pop();
        if(done[t.u])continue;
        done[t.u]=1;

        for(int i=head[t.u];i;i=e[i].next)
        {
            int v=e[i].v;
            long long w=e[i].w;
            if(dis[v]<dis[t.u]+w)
            {
                dis[v]=dis[t.u]+w;
                t1.dist=dis[v];
                t1.u=v;
                qwq.push(t1);
            }
        }
    }
}       

#undef int
int main()
{
#define int LL
    int n;scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
        addedge(i,j,(a[i]-a[j])*(a[i]-a[j]));
        addedge(j,i,(a[i]-a[j])*(a[i]-a[j]));
    }

    for(int i=1;i<=n;i++)
    {
        addedge(0,i,a[i]*a[i]);
        addedge(i,0,a[i]*a[i]);
        addedge(i,n+1,0);
    }

    dijkstra(0);

    printf("%lld\n",dis[n+1]);
    return 0;
}
  • 就要全市统考了,在复赛之前,但是并不想复习。

  • 我要凉。

Day -1

  • 数学凉,果然文化课颓废如我、不写题抄作业就会造成能力不足。

  • 语文感觉尚可,除去名句默写(错了一堆)。作文是任务驱动型,感觉非常舒服,对不积累作文素材的我来说,已经是轻拍了。感觉一堆人作文跑题了QAQ另外这次语文是我书写最工整的一次...

Day 0

  • 早上考物理化学,下午英语。考英语的时候已经不太想考了。

  • 6:44的火车,晚上到南京。火车上并没有复习什么东西,打打tarjan,lca电脑就没电了。找zty聊了一会题目,主要是数论之类的。

  • 因为统考的缘故被迫跳过南京面基环节。

  • 方便面这种难吃的东西在火车上闻起来,(╯▽╰)好香~~。

  • 收到很多人的祝福,zxx(物竞),Capella,(好像还有lhy?)...以及空间里各种励志的说说,信竞圈的关系真的巨好,非常开心。

Day 1

  • 没睡好,前所未有的压力。旁边的呼噜声很大,心情很烦躁,很久没有睡着,可能一直到了凌晨3点。

  • 7:00起床,早饭后和zty,zyl去南航。南航建筑很丑。

  • 考场条件比预料中的好,windows+linux虚拟机的配置,我不会用linux。

  • 第一题爆炸,写了很糟糕的做法,大概50-60分的样子,没有想到线性时间的做法,惨惨。

  • 第二题爆炸,应该说是,考试策略的问题吧...哎...zty写了暴力做法,估计是30分,我只是特殊情况估计是15分,真的应该写暴力的。

  • 第三题才是真的爆炸,明明练了这么久的图论题,结果还是只拿了20分。题目一眼看上去是二分,但是check()不好写,只拿了 $m=1$ 的二十分,其实还有树退化成链的情况,以1为根的情况还可以拿不少分,但是..哎...没拿到。

  • 总结一下,Day 1完挂。要是明天拿到140分,才有省一。瞬间虚了,再说了,一开始目标并不是省一啊。

  • 下午颓了很久,我的人生一片灰暗。

  • 其他人的情况:Capella和himself65完挂。发挥不出平时水平已经是我的常态了——这当然是我为自己实力差找的借口。

Day 2

  • 考炸了,不想多说什么。

  • 第一题基环树的情况没弄出来。应该只有60分。

  • 第二题手算了一些小数据,推了一个多小时,放弃。交了手算数据的表。

  • 第三题他们都说是动态DP?我yy了一个线性预处理常数回答的做法,感觉正确性没什么大问题(?)然而没有码完QAQ感觉应该能过的...不过就算能过也未必码完就是正确,说不定还要调好长时间,菜啊。

  • 大起大落的心理路程,我要是最后一题写出来就国一了,写不出来连省一都没有,抱着这种心态写了120+行,没写完。

  • 南京的鸭子还行。


AFO,goodbye OI.


2018-10-31 18:40:51 in 生活