GDKOI 2021 打 Fe 游记

LinkZelda · 2021-02-07 10:18:34 · 个人记录

## Day 1 上午第一眼看题，发现题面都好简洁呀。 - **T1** 题意是找任意一种对图的割边方案，要求边数不小于总边数的 $\dfrac 1 2

人均 AC 的一道题，然而我就只会暴搜，然后有个二分图的部分分，就随便 bfs 一下。

一眼看上去，要求区间最小值，果断打了一个 st 表暴力，然后想着自己能想出来，推了一会后发现比较麻烦，然后就跳下一题了。

看到题意，是字符串题：求多次询问区间最长回文子串。很好我就学过 kmp ,但是想了一下发现，貌似这样做比暴力还劣，就打了暴力 \dots

题面给了一些结点的信息，要求所有可能的二叉树的美观度（题目对这个有定义，大概就是每个点的美观度和它的左子树的叶结点个数有关）。

然后，我在剩下的 1.5h 里，都在画样例的二叉树，最后这题还是不会 awa 。

day1就这样结束了，还好我暴力没写挂 50+20+10+0，排名 203

Day 2

第一题期望看上去式子貌似比较简单，但是推出来貌似有后效性，我就移了个项，貌似是对的（讲题时说的第二个做法和我的一样 qwq ）。可惜的是，最终没码出来，暴力都没写出来。。

看上去是要维护有向图内每个 scc 的编号最小的点，果断打了一个 tarjan 暴力。然后，就没有然后了。

看上去又和回文子串有关系，考虑昨天 T3 的马拉车，可惜我没有去学，本以为昨天考过今天不会再考。

最终写了一个朴素的 n^2 dp ，拿到了暴力分。

直接对题目进行了模拟，然后我试着找了一下性质，结果拍的时候发现是错的，结果还是把模拟交了上去。

day2 感觉排名比昨天好了一点，虽然还是只拿到了暴力分 0+40+40+30 ，rk142 。

最后的一天，题目都非常的恶心，然后出题人的 T2 数据过水，n^2 过了 50000 ，大部分人都拿到这 60。

其他题的话，考场上一直打暴力，结果还是无济于事 awa 。

同分的人好多，60pts 可以从rk101排到200多好像。

这次所有题都打了暴力，三天总分 250pts ，排名是 139,压线拿到了 2= ，不过打稳自己的代码确实是一件很重要的事，尤其像 day2 前两题直接不给大样例的时候，一点要好好检查自己的代码，理清思路。

但是这次考试显示出了我的弊端，就是不肯想正解，只会打暴力。这样的习惯去到更高阶的竞赛中一定会凉的，以后做题一定要多锻炼思维，争取自己想，自己码，过了题之后再去看题解找更好的做法。