开考
没有一道题一眼,感觉要没,不好搞。开考就一直看 T1,想出来 20pts 暴力解法,之后就一直停滞不前,尤其是 T3 直接蒙了。
想了一个多小时还没开始写,感觉真的没了。
开写
T1 暴力先放放,去搞 T2,很快写出来但是被自己证伪了,于是去看 T3。想出来一个完完全全的大搜索但是感觉连部分分都拿不到,有跳到 T4,感觉像性质题?手模了一会样例(还发现个错误)又被自己假了。
感觉大难临头,但是我又想到了 dp 这个东西,以前考试的时候好像从来没有正式的过一道 dp?T2 感性说服自己搞了个贪心(想起来很正确),3min 光速写完,自测和样例都过,稍微好点,看 T1。
T1 想到了实现方法,但是 \(\mathcal{O}(n^2)\) 怎么也不会优化,只有 20pts,汗流浃背。
T3 又想到建边跑最长路,又被自己假掉了。
最后半个小时 T4 蒙了一个递归,没调出来,交卷了。
这次没忘 freopen。
出分
120pts,符合估计,但是太烂了……听说第四题暴力因为数据过水可以拿 70pts。但是不会暴力,感觉越来越废了。
不过 T2 能写出 dp 可不可以算一个小小的突破?
知识纰漏
T1 其实思想一致,但是方法不一样,虽然枚举所有点是 \(\mathcal{O}(n^2)\),但是我只要反过来去枚举符合要求的位置就可以了。
T3 也是 dp,但是真的看不出来,知道之后迅速切掉,这是一个问题。
T4 不会写暴力很悲哀,虽然不会树套树但是会线段树上二分,为什么会挂?因为我根本就没想到线段树。
策略得失
先去写 T2 是正确的,但是 T1 没切是不正确的。
发现好像对自己来说难度不在实现上,而是如何想到这个知识点,不会转化也不会判断。
也不能完全说是思维题,就是需要转化的那种。
总结
其实这种思维题个人不太擅长(光码是完全没有问题的),所以以后的重点应该放在怎么其想到而不是着急实现。
发现自己容易忽略 dp,用不到数据结构或者图论的时候就会慌,但是没想到有个在夹缝中的四不像动态规划,难在状态转移,可以去认真发掘题目性质说不定会有新的发现。
改进方案
CF 上有很多脑筋急转弯,指定计划一周几套,每道题最少 30min 之后再去看题解。
提升码力(尤其是暴力),要是在连暴力都写不出来就真的挂 \(0\) 了。
https://www.xinyoudui.com/ac/contest/774001BE0000410025FADB6/problem/11456