Venus 的博客

Venus 的博客

CSP 2020 - 过去的终结,未来的伊始

posted on 2020-09-29 20:45:09 | under 未分类 |

今年估计就 AFO 了,我太难了

Day $-\infty$

马上就要初赛了,估计初赛就 AFO 了。
在 Sooke 的怂恿下开始打国集作业,然后发现会做的非常少,只能挑简单的口胡。
我好菜啊。

Day $-\infty + C$

月考班里第 10,进步很大。
今天考初赛。
估分 77~80,感觉要无。

Day $-\infty+C'$

分数线 71.5,苟住了。

Day $-1$

回家 van 了一下,第二天困得要死,问题不大。

Day $0$

鉴于教练认为大早上赶过去会让我们全体阵亡,于是选择前一天晚上去。
然而没带电脑,没东西 van,忧伤。
紫金港校区离文渊有十几公里,xdm 不能过来 van 了,忧伤 +1。
晚上在酒店餐厅里自习,看了看代码,点了几杯奶茶,美汁汁。
某知名 OIer 过来跟我们说了两句赛前语,然后就去睡了。
室友和某个憨批在房间里玩妹抱(黄油),声音调最大,震撼我妈。

Day $1$

早上嫖了某人的电脑,打了一把无限火力,萨勒芬妮不好玩。
然后就是吃饭,午睡,比赛。
进考场,桌子上几乎没有能放东西的地方,挺难受的。
等待开题,然后解压密码打错了(人生第一次)。

然后看题。


T1:儒略日。
看标题我以为是某游戏的什么内容,结果一看题面笑不出来了。
出题人我 xxx。

想了一下,公元前特殊判断,那我就先跳到公元前 $1$ 年再判到公元后。于是写了一堆大力特判。

    if(Y==-4 && n>=365) Y++,n-=365;
    if(Y==-3 && n>=365) Y++,n-=365;
    if(Y==-2 && n>=365) Y++,n-=365;
    if(Y==-1 && n>=366) Y=1,n-=366;

突然想到我公元前四年一跳效率太低了,于是先 $10^3$,再 $10^2$,再四年一跳,优秀的效率。

    d=366*250+365*750;
    while(n>=d && Y<-1000) Y+=1000,n-=d;

    d=366*25+365*75;
    while(n>=d && Y<-100) Y+=100,n-=d;

    d=365*3+366;
    while(n>=d && Y<-4)
    {
        n-=d;
        Y+=4;
    }

公元后,要考虑 1582 年?那先跳到 1500 年吧。

    d=365*75+366*25;
    while(n>=d && Y<1501)
    {
        n-=d;
        Y+=100;
    }

如果是 1501~1600 特判一下吧,好处理一点。

    d=365*75+366*25-10;
    if(n<=d)//Í£ÁôÔÚ 1501.1.1 ~ 1601.1.1 ÖÐ 
    { ...

后面?大力跳! $10^8$ ~ $10^4$。
然后发现自己忘记 $y\equiv 0\pmod{400}$ 也是闰年,又调了一会儿,总算好了。最后用很丑的代码算出具体天数,解决。
用时: $\text{2 h 15 min}$。
用时太长导致后面时间不够,而且少加了一个等号导致民间数据会少 $60$ 分,搞得我心态很崩(具体是在 $1582.11.1$ 会输出成 $1582.10.32$)。


T2:动物园。
看了一眼,表示想骂人,讨厌二进制。
突然想到:如果可以判断出哪个二进制位能不能取,记其为 $p$,最后答案不就是 $2^p-n$ 吗?好像有道理。
想了一下,如果一个位置没有限制,或者前面有动物选过这个位置了,那就可以取。这样的思路貌似是没有毛病的?于是很快写好了,过了大样例。

    for(reg int i=0;i<k;i++)
    {
        if(t[i] || !f[i])
        {
            if(!ans) ans=2ull;
            else ans=ans*2ull;
            //cout<<ans<<endl;
        }
    }

突然发现会爆 $\text{ull}$,于是加了个特判。

    if(ans==0 && k==64) cout<<"18446744073709551616"<<endl;

赛后发现这个特判是错的……因为没有 $-n$……
然后就没管这道题。赛后出来突然很慌:我好像没有考虑某一个二进制位的限制可能会被另一个二进制位满足!这种时候这位也是要取的!(同学:我用 map 被卡了,应该用 hash 的)结果后来仔细看了下题面:数据保证所有 $a_i$ 互不相同,所有的 $q_i$ 互不相同
好嘛,白担心一场。《关于我想打骗分程序却是正解这档事》。

用时: $\text{40 min}$。


至此已经没什么时间了,后面题的思路就非常乱了,大家做题的时候一定要理清思路,留够时间啊……


T3:函数调用。
第一眼:数据结构?终于有数据结构了?
第二眼:区间乘?忘了怎么写,不过貌似可以离线?
第三眼:这函数 3 是什么东西?
想了一下,调用函数是一个 DAG,然而想不到什么算法。拓扑?那是什么?
暴力滚粗。

用时: $\text{30 min}$


T4:贪吃蛇。
留给这题的时间不多了!【不是】
想了一下貌似可以 set 维护每次调最大,次大,最小判断吃不吃。
这时候突然想到,如果最大的吃了最小的能被次大吃,次大也需要考虑它吃掉之后会不会被次次大吃,这样套娃没完没了啊……不过用 set 维护貌似照样能拿到不错的成绩。
就在这个时候,时间马上就没了,set 还写挂了,那叫一个气哟。
最气的是后来我还发现,每组数据读入的是 $k$,不是 $n$……

    Read(Time);
    while(Time--)
    {
        Read(n);
                ...

好嘛,估计是爆零了。

用时:剩下的。

总结:码力太弱。

然后就回家了,晚上快乐地和 xdm 开黑,然后回归 whk。

自测:洛咕 / 牛客:175,XJ:200,ZH:155。
快乐。

Day $?$

官方数据出了, $100+100+35+20=255$,官方数据贼水的年代又来了,爷青回。
T1 和 T2 一共能被卡 90 分,CCF 一分没卡掉,佩服。
T4 根本就是错的,CCF 也没卡,佩服。

总之分数高了是件好事。
虽然大家都高。