CCF 2020 省选游记

· · 个人记录

SH 省队预定:EFZ 三人,SHS 三人,gyc,jtl,女生名额。

Day\ \ 0

还剩八百个板子没写过。

Day\ \ 1

开题,看到 T1 是个智障题。

T2 刚看的时候感觉有点眼熟,但是没马上做出来。

T3 看了一眼,是我不会的题。

然后用线段树二分写了一下 T1,一小时之后发现这题要求最佳温度的 最大值,然后发现线段树不会做,换成树状数组倍增又码了半小时。

然后看 T2,一开始以为是拉格朗日插值,然后发现这东西不是 m+1 次多项式,只能从组合恒等式开始推,推了一会发现可以 O(m^2),花了十分钟写了一下就过了样例。

T3 一直不会,写了 40 分暴力不知道能拿多少。

预估得分:100+100+40=240

Day\ \ 2

大崩盘。

上场先做做 T1,然后发现十分困难,然后做做 T2,发现也十分困难,然后做 T3,终于觉得 T3 比较简单。

凭记忆打了个 Matrix-Tree 之后调了一会过了样例扔一边了。

然后去做 T1,想了一会发现是个有点智障的状压 DP,但是好像卡空间,稍微调整一下写法把空间压到了 O(2^n)

T2 没做过原题大失败,写了 10 分暴力。

预估得分:100+10+70=180

看了一下大家的代码好像全员会 D2T2,有点恐怖。

如果 D2T2 做出来我应该就可以进省队了,现在就有点说不好,预期得分有点不高不低,可能正好就是省队分数线上下吧(多半是下)。

感觉有点像 CSP 复刻,而且有点原题大战的感觉,反倒没有之前省选的感觉了。

upd(6.23):实际得分 390,好像是可以进 E 了的感觉。

upd(6.26):

实际的省队:A 队是三个 EFZ 和 installb 神,同机房几个没考好的神到 B 队了,E 队完全是 EFZ 的势力/cy,E 队队长不出意外是 glx。

感觉之前有点高估了分数线,本来以为至少要 400 的,现在看起来 SH 只有 4 个人到了 400 分。