CSP2019游记

啊呀呀第一届 CSP 咋这么坑。。。orz

day 0

上午比较放松身心 qwq。下午试机写了两个我容易错的算法 PRST表(这些不是我这个菜B才写的吗!),然后顺手测了测机器的速度,发现跑的飞快 25 亿次加法仅仅要 1.1s~ 另外说下处理器为core i3-4810啥尾号的不清楚,3.7GHz。

晚上时看了看dp相关的内容,之后就睡了。睡得挺香~~

day 1

(到考场前的事情略去)

进了考场把模板打了,然后上了个厕所后回来趴着等待发密码的那一刻。监考老师把密码投出的那一刻,我以最快的速度输入解压了,花了大约30min把注意事项和题目审阅了一下。

T1

这题几乎没怎么想随手一个dfs解决了。我设置了三个状态,好像跟同学写的不太一样但是过了大样例过了不虚。(听说还有人一句话AC,%%%)。可惜没来ull,-5~10pt。

T2

这道题一眼看出要用栈,然后15min切掉了。同上测了大样例不虚(后来听说大样例很恶臭,woc?)。不过后来在洛谷上能A掉。100pts。

T3

当时切了T1非常自信地先开T3,好像是9点开始。这个是CCF种的第一棵树,看了半天也不知道他要我干嘛,节点和数字的关系感觉很乱。好歹要解决subtask吧,一看发现啥玩意?做不动做不动,暴力就10pts,关键最后我还没拿到qwq。到9:50时冒出了一个思路就是把初始状态和结束状态对应的数字连边会构成一个大环,除此之外好像没有发现什么,到10:15时解决T2去了,30分时回来继续瞎推到11:30好像得到了一个性质:就是环上的边指向的两个点在树上的距离之和的总和为2n-2(貌似不是充要条件),反正最后按照这个来暴力假掉了,0pts。(事后发现是拓扑,orz)

Day1期望得分:9095+100+0=190195< 全天下210,zbl。

Day 2

其实感觉这天的题挺不错的,比 D1 要合理些。(难度不会评价)渴望在 D2 翻盘却fst。

T1

又花了 30min 阅读题目,然后 T1 随手想到了 (n^3m) 的 dp,但是人傻不会优化成 (n^2m) 的,于是走上了卡常之路,加上了一堆卡常优化剪枝,然后自己造的满的大样例跑了 3s,感觉 ccf 的搞不好就能过(好像洛谷上过了?ccf 的少爷机给点力 8)。期望得分: 84~100pts。后来知道是背包,感觉血亏此题,不过水平就这样无话可说。

T2

此时又到了 10:00,开 T2。一开始想直接走贪心,就是能拆开就拆开,否则能向前合并就合并,否则新建一组考虑,写法上十分麻烦,因为感觉过不了,想 dp 发现按照值来 dp 很吃内存,于是设状态表示以 i 结尾的和最小的块的起点转移,当然这个块必须有可行解。因为直觉上最后一段总和越小答案越小(考完后好像证掉了),随手写了个 (n^2) 的 dp 看看样例过个掉,发现过了。其实这个 (n^2) 的dp根本跑不满除非很特殊的数据感觉能有至少64pts,而下发的倒数第二组大样例好像是 (n=100000) 的秒过,在洛谷上的跑了 88pts!(PS:牛客上也是 88pts)还没有结束,感觉有线性做法,随手打了个 fi 的表发现这个是增的,这个挺显然,然后状态当 s[i]-s[j]>=s[j]-s[f[j]] 时会有转移 f[i]=j,然后移个项发现 s[i]>=2s[j]-s[f[j]],会转移。这个因为fi增所以可以维护一个与右边式子有关的单调队列就可以线性过了。很遗憾当时已经到了11:00,我便放弃了这道题。期望得分:64~88pts。

T3

感觉换根 dp 搞搞?没时间了。这道题暴力分很足,可我时间紧急就写了 55 分的暴力还调了好久,不过最后调好了,此时还剩 20min。想写 20 分完美树的点,但是没想到树的形态一定或者深度为 log 想了 10min 就扔了,一心妄想 10min 把 T2rush 掉最后 failed。期望得分:55pts。(upd:T3链的数据没清空导致挂了15pts,woc)

Day2期望得分:84100+6488+40=188~228pts

两天估计总分:378~423pts。实际:383,d2t2被卡了。果然翻车了。

Summarize

这次有很多失误:比如说能拿到的暴力分没拿满,程序没细细检查(基本上没时间看,就看了文件名和文件夹),有些能拉开差距的地方没有把握好(虽然我还是很菜),不过 Day2 中扔 T2 做 T3 的做法觉得挺正确的,毕竟就算 T2AC,T3抱灵也不太好。可是T3没清空数组导致的挂分要好好反思呀!

原文地址:https://www.cnblogs.com/ac-evil/p/11884762.html