一个蒟蒻的博客

一个蒟蒻的博客

随便逛逛呀

CSP J/S 游记

posted on 2020-11-08 15:48:25 | under 未分类 |

这个题出的挺好的啊挺好的 哪天我当面认识下出题人


Day -1

同考场大佬狂码树链剖分
左边大佬:你在写 $fhq-treap$ 啊 不好用
我:????
右边大佬:我这个树链剖分居然没有压到100行以内 真是罪孽 我:???????????
于是这个蒟蒻回家狂学树链剖分
晚上9:00 复习 $kmp$ 复习 扫描线
一个都没考
晚上睡不着 愣是睡不着


Day 1

注意 Day 0不存在 就是说 Day 1前面就是 Day -1

早上考PJ有点紧张
T1:貌似奇数无解 不敢特判 还是谨慎一点 搞个二进制分解看看有没有1 再 $sort$

T2:蛤?动态维护集合 第 $k$ 大值?$fhq-treap$ !!!
过了 $2min$ 算了 别写了 我觉得还是树状数组二分吧(
码码码码码码码码
样例没输出 算了 我去再瞄一眼题目
取值范围 $600$ ? 算了下 $O(600n)$ 够了够了 开个桶(

T3:哇好恶心 不会真给同学预测了是个表达式栈吧 看见各种运算规则 我有种不好的预感
哦 给你后缀表达式啊 那没事了
我考虑建棵树 开个栈一遍维护一遍建树 &()……&*……&……

$40min$ 后.... !样例没输出
$5min$ 后 改了一堆 ?怎么树根不唯一?
$5min$ 后 太好了过了 测样例 Present Pass(

T4:看了一眼 哇 $dp$ 板子 再看一眼
本以为是青铜 没想到是王者 先考虑暴力 $dp$ 以列为阶段 $O(mn^2)$ 很好 一下就过了(
再考虑优化 emmmmm 有了!拆成两个 $dp$ 一次从下往上扫 一次从上往下扫 最后合并成一个答案(当前点最大)
改改改改!过了!钛好了(

最后10min 我搞了组样例(T4)

3 3
1 -100 -1
-100 100 -1
1 1 1

$dp$ 输出 $102$ ???!!! 仔细一看 初值炸了 赶紧把第一列的初值改了 过了! 真就是


下午:
密码:他山之石 可以攻玉
他山之题 可以攻心
看着第一题的题题面就知道前方高能 .....
看了 $10$ 遍题目后 我准备写个阴间玩意
$2h$ 后 这个样例 $2$ 的第三个 $r_i$ 是什么鬼????
算了弃疗

看T2
考虑暴力 枚举每个动物编号 搞定(

看T3
诶 是个数据结构 来劲了!
先打了个暴力 然后看了看 区间乘 单点加 很好 线段树(

最后几分钟看了看 T4
写假了 可恶啊

这个儒略日啊 是真的恶心
出考场的时候旁边一大佬说他写了 $3h$ 的 T1 写出来了 (希望他不要 $fst$ )其他都没看 疯狂捶胸顿足中
旁边的大佬说写了个线段树合并 (汗)
但是说也没调出T1 (笑)