CSPS2020玄学记

2020-11-08 18:43:34


坐标JS,NJ,初三。

$\text{Day }-4\sim-1$

应老师要求,停课准备CSP。

在高一训练室膜拜了高一的学长们。(可惜没碰到过djq神仙)

天天打CSP模拟赛,诸多超纲题。(模拟赛考虚树上边双你敢信?)

跟学长尬聊美国大选,我押川普,输了(还好没押钱)

天天刷一天题,晚上精神崩溃只想颓废,没救了没救了。

$\text{Day }0$

不敢开新题了,码码板子。下午突然想起来自己DP太糟糕,就去补DP了。(顺便为自己的DP刷题笔记打个广告)

晚上感觉实在没事干,颓了颓(没救了)

$\text{Day }1$

上午没开新题,写了一份网络流,一份平衡树,一份LCT。LCT的时候评测姬炸了,随机RE,心情很不好。

十一点半就准备吃饭了,啥都不想干。

坐同学的车到了NUAA,实验楼。这时十二点四十。

然后就在大太阳下站了一个小时。对,一个小时。直到一点四十进场。期间拜了拜傅里叶。

看到了gh学长、kyl神仙,还有之前一直没看到过的djq神仙!(虽然没打招呼)

两点进场。那本小宣传册子不给带进去差评。不得不跑出去再把它扔出去。

进场敲了份快读,一份快输,一份前向星,一个Dijkstra,一个匈牙利,一个强连通,半个点双(捂脸,因为没敲完就发题了)

开场看T1。哦,大模拟呀。不慌,感谢出题人施舍,没出什么一点思路都没有的大毒瘤题。同时“儒略”是凯撒的宗族名你们知道吗?精罗狂喜

思路出奇地清晰。先考虑BC的情况,发现 $4713$年是闰年,然后就以 $4$年为周期处理。大约20min写好,测一遍样例1,AC。

再考虑1582年以前的情况。先减去BC时总共的日期数,然后和之前没什么区别。测一下2e6的样例2,AC。

再考虑1582后的情况。原本想了很繁琐的方法,后来想了5min发现只需要将日期加上10天,再减去多闰的12天,就直接统一计算了。仍然和之前没什么区别,只不过先按400年为周期处理即可。

40min时全部敲完,一测样例2AC。再测大样例,发现BC的某些日期会挂(差了几年),稍微瞅两眼发现加减方向错了,50min时T1满分。

然后开T2。一眼看到 $a,q$不同的限制。然后10minAC,弱智题。想了想边界情况,然后测了 $0,0,0,64$的情形。输出 $1$。

然后发现此时答案为 $2^{64}$,爆ull。但只有这一种情况会爆,特判掉了。

这时一看3:40。喝了点水,啃了块牛肉干,开T3。

明显这是个DAG。想了想线段树优化暴力,发现铁定过不去。出去上个厕所静静心。

上完厕所回来5min想到正解——倒着处理操作即可。然后就正一遍拓扑反一遍拓扑完事。此时4:20。

然后啃了块巧克力,开T4。

似乎很像“海盗分金”的经典问题,果断倒着思考。思来想去写了个 $n^2\log n$的使用两个set的算法,一测样例1,2,3全过,看起来没问题。

然后尝试优化,发现根本没必要求出所有的set,只需要一个set从头管到尾即可。于是降到 $n\log n$。一测样例4,AC。此时4:40。

然后稍微想了想,就用一个桶换掉了其中一个set。

没有思路,又去上厕所。回来的路上突然有了思路,然后到大样例上一测,似乎都符合我的猜想——每次最大的蛇吃完最小的蛇后,这剩余的能力值,应是递减的。然后也没多想,就用一个队列换掉了唯一的set,这时达到 $O(n)$。此时5:10。

为了验证我的猜想,果断开始对拍。拍了2k组数据没问题,就放心了。接着拍T3。也没出锅。然后拍T1,AC。此时6:10。

T2不想拍了,开始肉眼查错。没查出错来。直到结束前5min。

我突然发现我T4好像假掉了!(那个贪心,很明显是错的,稍微想想就知道)

没时间改了,也不敢改,就交上去了。估分300——希望CCF数据水罢。

晚上回家测民间数据。LG+信奥题库,双双判我T4满分。

exm?

并且前三题也都没出锅。

说不定这个贪心很难卡呢?

希望有人可以来hack,代码放这儿了。

#include<bits/stdc++.h>
using namespace std;
int T,n,m,a[1010000],b[1010000],c[1010000];
pair<int,int>q[1010000];
bool on[1010000];
void func(){
    for(int i=1;i<=n;i++)on[i]=true;
    for(int i=n,j=1,l=1,r=0,id=n;id>=2;id--){
        pair<int,int>u=make_pair(-1,-1);
        if(i>=j)u=max(u,make_pair(a[i],i));
        if(l<=r)u=max(u,q[l]);
        pair<int,int>v=make_pair(0x3f3f3f3f,0x3f3f3f3f);
        if(i>=j)v=min(v,make_pair(a[j],j));
        if(l<=r)v=min(v,q[r]);
        b[id]=v.second,c[id]=u.second;
        on[b[id]]=false;
        if(l<=r&&u==q[l])l++;else i--;
        if(l<=r&&v==q[r])r--;else j++;
        q[++r]=make_pair(u.first-v.first,u.second);
    }
//  for(int i=1;i<=n;i++){for(set<int>::iterator it=t[i].begin();it!=t[i].end();it++)printf("%d ",*it);puts("");}
    int las=1;
    for(int i=2;i<=n;i++)if(!on[c[i]])while(las<i)on[b[++las]]=true;
    printf("%d\n",las);
}
void read(int &x){
    x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
    read(T),read(n);
    for(int i=1;i<=n;i++)read(a[i]);
    func();
    while(--T){
        read(m);
        for(int i=1,x,y;i<=m;i++)read(x),read(y),a[x]=y;
        func();
    }
    return 0;
}

总结:

本次考试的分数完全是碰运气。我如果T1出个锅debug个1h,T2没看到 $q$不同又没注意到极限数据,T3想不到倒着处理,或者想到了但又debug1h,不就报废了吗?

不是自己真实水平的成绩,不能代表任何东西,特别是T4还是假算法。

还是太弱了呀,以后的考试,命运的天平可就不一定向我倾斜了呀。只有自己实力真的上去了,才能无论是否幸运,都能取得理想的分数。

upd:终于找到hack数据了,牛客数据,T4四十分。

希望CCF数据水罢

upd2:100+100+100+50=350,人没了。