3.27考试小记

一天考了两场……

上来先看第一题,发现题目中有一个LIS,然而我并不知道它是何物,看了一会没看出来LIS是啥就先放着了,第二题读完发现是原题,而且还不是特别费码力那种,开心。第三题读完发现还是原题,难道这场是信心赛?

于是先打最好打的第三题,打完之后发现图建对了,边权建错了,有点小慌,想了一会没想出来,就先放着了,然后去打第二题,按照之前的打法打完了调了一会就过了,本来想对拍一下保险一点,然而并不会造数据,好尴尬……于是接着做第三题,又推了一会推出来了边权,样例都过了,这次也会造数据,然而并不会写通用暴力,感觉更尴尬了……于是剩下的时间全部用来做第一题,然后就不断地去猜lis到底是啥,用有道搜也搜不出来,然后猜s是string,l是longest,就是i不知道,于是现场枚举了一下最长……串有什么,发现好像是最长上升子序列,于是就按照最长上升子序列去做这道题,打完了爆搜加了几个剪枝,发现n<=12的点得话m>=4还是可以跑过的,然后就准备去想一下正解,然而并没有想出来就结束了……

估分:30+100+100,实际60+100+100,可能这次脸白吧,剪枝过了n<=12.这场考试基本就是T1会造数据会打暴力不会写正解,T2会写暴力会写正解不会造数据,T3会造数据会打正解不会写暴力……

下午来了之后又考了一场。

第一题上来看起来好复杂的样子,好像判一个入度大小就可以拿到n<=1000的分啊?第二题好像是一道树上DP,50分好像还是很好拿的。T3好像是一道数据结构,暴力分很容易,然而剩下的并没有什么思路。于是先去打一下第一题,打起来才意识到不能只判入度,会有环的情况,然后之前50分的幻想就破灭了,先打完30分再说吧。打完之后就去看第二题,打完了50分暴力之后开始想能不能二分答案或者三分物流中心数或者三分到物流中心的最短距离或者直接树上DP,想了一会前几个方案都想不出来,于是就开始往普通树上DP上想,一开始想的是f[i][j]表示到i最近的物流中心距离为j时的答案,然而并不好转移。又想根据50分暴力推正解,发现50分暴力的每一个转移点有规律,然后开始打表,然而并没有什么用,于是弃坑。第三题打完暴力之后就去想正解,到最后40分钟想到了对每一条重链建一个动态开点线段树,然后每个链里面建一个树状数组套主席树,理论(nlogn^2),然而由于时间问题,树状数组套主席树还没打完就结束了。

估分:30+50+30,实际27+50+50,第一题可能是被卡常或其他原因,第三题暴力多跑了20分。