2020/10/19 随笔
今日总结
上午大概开考前 40 分钟口胡完了所有题目的做法（包括我看错题面的 T3）。
本着锻炼码力的想法开始上手了 T1，大概考虑枚举断点和左右两边选取多少个方格，然后先预处理了一大堆的东西，发现其实有一部分并不必要，然后计算代价时，一开始没考虑到断点的情况需要讨论，样例一直没调过。大概写 50 分钟才过了大样例。
T1 调了这么久感觉很自闭，本来感觉 T2 是一个 dp 不会很难写，发现需要分类讨论的情况太多了。一开始打算设计 表示枚举到第 位放着什么类型的格子 ，结果写到一半发现有一部分的转移还依赖于第 位的格子。此时不太明白到底从哪里转移过来（从 还是 ），索性把代码删了把 dp 状态改换为记录当前两位放着的格子类型搭配。写完后小样例过大样例错，手造了几组小样例把自己卡掉后，发现是预处理出现了小偏差，改完后就过了大样例。此时已经 10:40。
T3 火急火燎的直接上手代码，一开始把题面中子串看成子序列了，于是选择树状数组维护前缀取 max 优化 dp 转移。第一遍由于没太理清转移上的思路，写到一半不知道怎么写了，调着调着代码越写越丑，最后忍住心痛又把代码删了。这时我还没发现题意看错了，于是重新整理了下思路继续开动码力，写到 11:20 时终于写完了，小样例一拍直接过，大样例却比答案大了几十倍。。这时才发现是子串而不是子序列（当时人都傻了），赶紧重新读了 n 遍题确定没有题意问题后，发现这题的做法比之前的更浅显。大概先预处理出每个点向左和向右最远能到达的点，再枚举修改点的位置。要注意的细节是此时的点是否能够修改，以及我们不能最优修改后的其他修改方案。但是依旧没想清思路以为预处理需要单调栈或者悬线法，写完后发现小样例过不了，才发现预处理的信息出错了。。赶紧改正过来就过了大样例，此时已经 11:45 了。最后一题还没开始写。。
T4 一开始想的最久，大概想了一个主席树的做法，但是有点忘记怎么写了。。看着旁边的 cz 在狂码离线树状数组，感觉不太懂。考完发现之所以离线是需要离散化。而主席树因为没有离散化而动态开点可以被卡空间。。考场上写了会主席树板子就没写了。
T3 因为细节挂了 10 分，总分 290 被爆踩了。。
T4 其实推式子时有一个细节没处理好，下午一直在调都没过。。
总结如下：
- 码力太差了，真的需要训练，最好是 cf 或者限时训练；
- 码题前一定想好细节上的处理，不然重构代码更浪费时间；
- 主席树等一些工业化技巧一定要能熟练运用；
- 想题码题一小时，不如读题一分钟；
- 主席树不需要离散化可以动态开点，但是空间开销可能被卡。
下午就只更正了考试题。
晚上继续了昨晚写了一半的 P4899 [IOI2018] werewolf 狼人：记录详情；
以及记录思路的博客地址 P4899 [IOI2018] werewolf 狼人。
明日计划
- 上午考试一定不犯之前犯过的错误；
- 下午更正时间不超过 1 个小时；
- 把数位 dp 板块搞完；
- 开始图论整体部分学习。