cspsj2022-游寄

· · 个人记录

上午 rp++，下午 rp--。

普及两个半小时切穿。

T1 直接暴力加特判。T2 解方程求根公式算一下。T3 先给表达式除括号外的元素赋值，然后按建笛卡尔树的方法建出表达式树，然后随便算。T4 枚举左右端点，用最长不降子序列的方法找连接这两个点最多能包含多少点，加上 k 和 x_t-x_s+y_t-y_s+1 比较一下，直接算是 n^3 常数小应该 ok，也可以优化到 n^2\log。

下午提高状态比较迷，可能是中午没睡觉的原因。

题都读完后去想 T1，无果， 开始敲暴力，结果由于某种未知原因，n^4 暴力写挂了，大样例错了，先交了上去，看下一题。

10.31 upd: 其实是dfs建图的原因，dfs建图会导致有些点到原点的距离算长，一些该连的边没连上，只限制深度没用，昨天晚上洗澡的时候突然想到 qwq（话说这种错解 infoj 和洛谷都能估到 70 令我很诧异）

T2 看一眼就大概有了可行的思路，但是要分很多类讨论，它是一个静态 RMQ，考场上没想起来 st 表然后就写了棵线段树上去，加上分类讨论总共敲了差不多 7KB 结果大样例没过，检查了好久没查出来。然后发现把线段树部分改成暴力，大样例过了，说明分类讨论没问题，线段树细节错了，于是决定写一个对拍找一个好看一点的样例，没想起来 system() 中比较两个文件的关键字，直接用 vscode 的文件比较工具手动对拍了。好在没几次就找到了一个数据很小的样例，顺着样例往回找，发现是我线段树的 pushup() 细节错了。

应该是由于这四句格式相同，直接复制了下来，结果细节改漏了导致的。

所以代码平移有风险，复制粘贴需谨慎。

然后再改出来了一个不同不痒很好找的错误，时间只剩下 15 分钟多了，感觉后面两题没救了，T3 直接输出了一个 YES 看看能不能骗到分就回去看 T1 了，结果还是没查出暴力哪错了，随便加了个时间性剪枝就跑了。最终估分 玄学暴力+100-玄学卡常+玄学骗分。

最后考场不能憋尿，容易眼瞎。

pj不出所料阿克；tg175，后来想了想发现 T1 我的写法相当于暴力加上了一个玄学剪枝，对了 75\%，不知道有没有 1=