CSP2021自闭记

Day1

直接进考场试机,键盘感觉还比较好用,就是这个屏幕一言难尽,长宽比别扭,而且还有人用记号笔在上面写字(虽然没什么影响

发密码前看了下zip,看上去比较正常

然后就开考了,先大致浏览了一遍题目,然后大概感觉 T1 是个贪心之类的东西;T2 显然的区间dp;T3 感觉比较可做,但是由于这题的位置,暂时没有仔细去想;T4 感觉就是个图论相关。但是我是图论渣渣,所以目标就是切掉前三题。

然后就开始细想 T1 刚开始想维护每个位置有多少个飞机,从而算出每个飞机需要第几个廊桥,然后直接枚举分配快速算。写完后发现样例都过不去,仔细一想才明白没有分配到的飞机会一直分配不到。不过又简单想了一下发现用个类似栈的东西维护就好了,然后就写了 set 并很快过了大样例,看大样例有点强度就没去对拍(flag)

大概过去了 30min,去开 T2,先是按照题面模拟出了一个 \(n^4\) 的东西,然后发现第二个样例过不去。仔细分析才发现会算重,然后开始苦想怎么维护才能不重,当时大概感觉是多加一维 0/1 ,然后就写了,但是还是不过,就很自闭,去看 T3

开 T3 的时候已经过了 1h,冷静分析后感觉是个弱智题,但是由于这个题的位置导致我不敢轻易去写,所以就写了个指判能否构造的发现大样例跑过了,顿时感觉这题可能是真正的 T2 。然后就去写构造,调了几个错就过大样例,但还是不怎么放心,所以就去写拍子,在 1.5h 的时候拍上了。

然后接着分析 T2,发现自己有个地方犯傻了,简单改了改就过了前三个样例。然后接着去改成 \(n^3\) ,又调了几个错,卡卡常数就把大样例全过了。

这个时候大概才过了 2h 多一点,因为自认为自己已经过了三个题,所以感觉要起飞了,但是没想到 T4 才是大毒瘤,充分暴露了我是图论渣渣的本质。

(这个 T4 我在剩下的两个小时内,完全没有往最小割这个方向去想,尽管 \(k\le 2\) 就是个裸的最小割)

然后看到 \(k \le 2\) 有一堆分,所以果断去想这档分,分析了一个小时左右大概给转化成了一个最短路问题,于是赶紧去 rush,rush了半个小时就过了大样例,感觉很稳,就没去检查(flag-2)

最后还剩 30min ,由于感觉 T4 想不出来什么东西了,就求稳去拍 T1 ,事实证明这是个非常正确的选择,我 T1 犯傻把某个 \(n\) 给写成了 \(m\) ,然后 \(n \le m\) 的时候没事,然而大样例全部 \(n \le m\)。

然后就结束了。

估分大概 \(100+100+100+45=345\)

Day2

早上一起来写这篇文章的时候,忽然想到 T4 保证的条件是 \(k\le2\) 即可能等于 \(1\),但是我 T4 读入到 \(k \not= 2\) 就给 return 掉了。。

(明明写前想到这点还是忘掉了,看来我真的改不掉丢三落四的习惯/ll)

麻了,估分变成 \(100+100+100+[0,45]=[300,345]\)

上一篇:2021年山东大学程序设计精英挑战赛 真题


下一篇:【ybtoj高效进阶 21254】摆放鞋子(二分图匹配)(网络流)