CSP JS 游寄

· · 个人记录

Day 0

ZJ。早上写了模板。树剖平衡树线段树合并点分治啥高级算法我就不想去碰了，反正目标是写出一题。

rmq忘掉咋写了，Xjin巨佬贴心辅导。

晚间趁老师不在联合 qeradfzcv，wzcyh 和 xjin 闪击 kfc。老师好像到现在都没发现。

Day 1 AM

睡得不好。十二点惊醒到两点才再次睡着，然后四点半又惊醒。

去考场发现有个人跟我同名，我还问监考老师名字是不是贴错了（（

开了早上的J组。草草看一眼，第一题啥玩意，第二题貌似是数学题，第三题还没看懂题面，第四题貌似是个朴素 dp。

细细看了 t1，观察发现只要特判 a=1 的情况，暴力枚举循环好像最多也就 30 次。直接上了发现大样例全能过，乐。

开了 t2，发现 p_i\times q_i=n_i，p_i+q_i 移一移就解决了。经典形式知二求二，凑个完全平方就解决了。大样例全过了。

怕不太稳又自己造了几个大样例推出来是一样的，就没管了，此时过了半小时。

看懂 t3 是个大模拟。好，看 t4。

t4 一开始看不出做法，先写了个 k=0 的性质，然后写着写着发现 100 分思路好像是一样的，然后把 40 分写完去想 100 ，实现了后发现大样例都能过，乐。造了个数据跑得也比较快，就不管了。

然后一直在写 t3。先想用手写栈，写到一半发现括号很难处理，果断换成 dfs，然后失败了。最后随便写了个 20 分的送分点。

预计得分 100+100+20+100=320，没 AK，我太菜了。感觉会被虐杀。

出去问了巨佬 Zyingyzzz 和 Wenzhou_wwx，发现都被 t3 卡了。 huangrenheluogu大样例全过，预计得分为 400，%%%。

Day1 PM

wzcxh 主张吃kfc。然后中午又吃了kfc，好饱。

看到了不屑于考J组的巨佬 J2a0m0e8s，%%%。

草草看了一眼卷子，什么鬼 t1 图论，t2 貌似是啥博弈，后来才发现不是，t3 图论，t4 树上问题。

开考铃声一响全是键盘声，t1 想这么快的吗。

看了半个小时啥思路都没有。感觉 A 一题的目标实现不了，看 70 分部分分。

也没啥思路。看来只能看 40 分了。

依旧没啥思路。看来只能打 dfs 了。

准备放弃的时候感觉这东西好像能 dp，但因为不能重复想了一个四维 dp 出来。继续观察发现根本不需要用前面状态，于是使用四重循环暴力枚举，外面套了一层 Floyed。预计得分 55。这个时候已经过去一小时半了，看 t2。

多看几眼才发现题目好像就是让你求每一行最小值的最大值，满分是啥神仙做法就不管了，我肯定要把数组建出来。然后就看到了 60 分部分。想到线段树发现空间肯定炸，而且常数巨大还不一定能过。发现这是个静态问题可以用 rmq。非常感谢 Xjin 巨佬昨天帮我复习了 rmq。然后就写了个二维 rmq，期间经历了 n，m 用混的错误。

然后继续看性质分，手模了一下没负数就是找一个 \min 和一个 \max 即可，实现了发现是对的，l=r 只要一维 rmq 就够了。嗯，然后我就写了七个不同的 rmq。预计得分 85。已经两小时四十五分钟。

t3 最主要是理解难。理解完了发现 40 分就是送分题，记录出度即可。然后拿下 40。这时候已经过了三个小时十五分钟。

t2 拿的性质分是最多的，然后手造数据检查，发现输出的很多都是 10000，调试发现它是按 1\times 10000 这样算的。因为我 rand 出的就是在 [1,10000] 的区间。最后发现原因不是程序问题，而是我造的数据区间太大了。浪费了十五分钟。但是也还有收获，在检查程序的时候发现我部分分的数组只开到了 1005，改回来了。

时间不多 t4 写了个树形 dp，预计 44 分。

出去遇到 Zyingyzzz，预计得分 $241$，%%%。 ### 赛后情况 晚上跟qeradfzcv玩了好久的象棋，wzcxh在旁边指手画脚。 老师发了个小图灵的链接在群里，我看了下发现只有 $100+100+30+40=270$。 我看这不对啊，什么鬼 dp 只给了 $40$ 分。 然后老师把源文件发下来。我发现我 t4 交错程序了。我把之前写的 $k=0$ 交上去了，而 $100$ 分的程序好像一直放在桌面测完大样例就没动它......草。 huangrenheluogu挂分了，t1 神秘错误挂了 $20$，t2 神秘错误挂了 $20$，t3 超时挂了 $25$，$t4$ 神秘 RE挂了 $18$ 个点。 Xjin很惨，t4 数组开小挂了 $16$ 个点，t2 神秘错误爆 $0$。只有 $100+$ 了。 qeradfzcv t1 把 $10^9$ 看成 $2^{31}-1$，但是没挂点。洛谷数据太水。 交了一发下午，发现基本符合预期，但 t4 玄学爆 $0$，并且只有我一个人有这种情况。$224->180$，太惨。 又去 infoj 里测了一下发现 t2 只有 $75$ 分。$180->170$。 计蒜客 $55+85+40+0=180

洛谷 55+85+40+0=180

infoj 55+75+40+0=170

(update on 10.30 22:43 t2数据重新传了，测出来是 85 分，infoj 55+85+40+0=180)

(update on 11.2 0:08 t1数据貌似重新上传了，测出来 65 分，乐，洛谷 190 分了)

qeradfzcv t1 奇妙爆 0，149->78

了解到 Wenzhou_wwx 214，%%%

了解到 Zyingyzzz 260，高出预期，%%%

一等线大概在 200+ 吧。Zyingyzzz 安慰我线会在 [150,170]。

update on 10.31 21:14

小图灵ZJ分数线 205，寄。