考试心得3

2024/9/15

link：https://www.gxyzoj.com/d/hzoj/contest/66b0925b7509073c6b14ab11/problems

考试时感觉眼睛想流眼泪，感冒还没好（ 做梦一样考完了

还挺后悔的，暴力分很多，T3打了1.5小时0蛋，发现自己就不应该写二分啊

T1，暴力40分走人，不会状压dp，考完后看着wsq的代码一点一点理解了，但预处理挺奇妙的。我何时才能自己推出状压式子啊，阿布，是何时才能想出状态设定啊，没底气。。。

T2，暴力40分走人。貌似是细节题，不想改。但最后改完辣！

T3，前两道题加起来一个半小时就打完了，此题暴力却搞了甚久，始终认为它是二分，导致写得全错了。本来想挽救一下，但实在没想到真的就是无脑枚举啊！考后改了改（指改了1小时）就拿到79分的好成绩，加上map的优化（指无脑记录重复数据）即可获得99pts！！虽然这一分让我调了2个小时，但真的，双哈希也能卡过啊！！！这个题告诉我们：宁可打无脑暴力，也不能空手而归，还有，自己曾经总结的哈希区间求值是从1开始的！！！一定要看仔细！！！

T4没时间了，10分就丢了。又又又......又垫底了。T-T

2024/9/16

link：https://www.gxyzoj.com/d/hzoj/contest/66e776d4f8a2945801bcd317/problems

祝wsq生日快乐，可惜她没来

但波波买了奶茶，还是挺好的（不甜

今天挂38pts，垫底again，就是说四五十分就差了20个人左右，分差头一次真么紧。

省流：打暴力的两天。

T1，数据大水题。原题好像是dp和线段树，应该挺难的，但由于是波波的随机化数据，很简单的能被HACK的代码也能A，但自己因为手造的数据卡了两个小时，100->82，，，

T2，考场暴力数组开大TLE，20->0，正解是dfs+线段树查询，还挺简单的，自己始终卡在一个地方：(id+1)>>1不能写成(id|1)>>1，原先线段树这么写是因为乘过2后必然是偶数，加1就相当于或1，但这里的+1就不能这么写，卡了俩小时，，，，

2024/9/22

link：https://www.gxyzoj.com/d/hzoj/contest/66b0c7117509073c6b151321/problems

表示自己大部分时间都去搞T2样例了，导致T1的50分没整出来。本来T1写的16pts的 \(O(n^3)\)，挺无语的，不知道为啥自己枚举完区间还要遍历一遍，考场代码改两行就50，啊。更无语的是，我加了个错误的优化，导致我原来的16pts都没有了，啊啊啊

T1是线段树，其实考场上想的错误的优化是能延伸到正解的。预处理 \(1-n\) 的mex值后，从一个区间转移到下一个区间时，如果下一个区间的mex值大于前一个区间，那么这个区间的mex值就要变小，所以要区间修改、查询、求和，用线段树，但考场上我想错了。

T2，考场上不知道推了多久才推出来样例，发现是贪心后狂写。喜提64pts，考后，把中间找到合法区间起始点的循环改成一层，开个 long long 就过了。然后又试了试，把考场交的第一版代码开个 long long 也过了，就是说你一定要相信波波的数据qwq

感觉T3还是挺抽象的，但看完Dyc的题解后好像好懂了一些，结合着luogu题解勉强看懂，挺巧妙的

2024/9/28

link：https://www.gxyzoj.com/d/hzoj/contest/66f746c1f8a2945801c53a36

改完T2精神状态极差，我考场上为什么还自信的认为我A了？

T1，考场上第一次推出dp式子！但我用在线编译发现，它好像会RE，然后就把数组开到1000，就只剩40了。考后把自己定义的dp数组拆成两个就不会RE了（本质上应该是滚动数组优化），然后就A了。

T2，大型分讨现场。考场上自信满满地打了一个半小时，一行一行地对大样例，一点一点改，加各种特判，本来觉得应该没问题了，结果0。发现大样例最后一个多数出了一个数，改后就是40了。自己再改了改，到55就上不去了。然后看dyc的代码，发现自己应该把特判的内容写到填数的过程里，写了写，到70,70 70 70 一直都是70，死活上不去了，最后 \(wme\) 学姐（太感谢她了，否则我可能到晚上都调不出来了）给我说了说，我懂了，分类讨论时 当前位如果是0 且不能删去，开头的指针应往后移一位，但加上这个还是65，显示 User output longer than standard answer. 最后发现没有判断没有删除的情况，加上终于A了，真服了（很抱歉自己写得像个流水账

2024/10/2

link：https://www.gxyzoj.com/d/hzoj/contest/66e55d2ef8a2945801ba51a6

自闭了。牙疼。想去打J。不是很想写总结。

2024/10/3

link：https://www.gxyzoj.com/d/hzoj/contest/66fd3b02f8a2945801ca8d1e

还是来写了。

T1，不会用fc，一个一个调大样例，感觉眼睛要废掉了，z[i]=0依然没有写出来，才发现n的长度为1000。

T2，60%的数据很可做，写了个记搜后一直调不出来，调了1小时，果然似了。下考后把传送门的入口和出口换了一下，就60了，发现自己用的是填表法却写成了刷表法，zz极了。

T3，Solution:

容易发现这是一个与斜率有关的题目，这种题目通常通过维护凸包，或者李超树维护
跨过\(p_i\)的区间容易转化为：以\(p_i\)为右端点的最优+以\(p_{i}+1\)为左端点的最优
两个问题同理，以右端点为例
设\(sa_i=\sum_{j=1}^i a_j\)，\(sb_i=\sum_{j=1}^ib_j\)
最优即\(\max_{1\leq l\leq r}\{(sa_{r}-sa_{l-1})-k(sb_{r}-sb_{l-1})\}\)
即\(sa_r-k\cdot sb_{r}-\min_{0\leq l<r}\{ksb_{l}-sa_l\}\)，离线之后李超树维护直线即可
时间复杂度为\(O(n\log n)\)，常数略大，空间复杂度为\(O(n)\)

看不懂，去学李超树。

2024/10/4

link：https://www.gxyzoj.com/d/hzoj/contest/66ae19497509073c6b126cb8

有没有人能讲讲考试数组应该开多大啊？开小RE，开大还RE

爆零就爆零，天天好心情