放在 luogu 上,一直没有粘过来,现在粘一下,acw 的中文字好丑啊。以下是原文。
我是星,利剑开刃寒光锋芒的银星,绝不消隐。
开坑。
Day -inf
停课,开始颓废。
咋么一直做普及卷子,差评。
Day -2
我擦终于有 S 卷子了,诶 T2 是不是暴力枚举加拉插可以 $\mathcal O(k^32^k)$ 爆草,好的不会写。好的大家 T3 输出 $n-1$ 获得 70,心态爆了。NaCl 对于我和 lottle1212 的 T1 没 A 行为进行了态度教育,然后发现是评测爆了。【数据删除】。
Day -1
连 pj 的卷子都没 ak,真的是 【数据删除】。
出发杭州。傻逼酒店噪音老响,noip 不去那了。
Day 0
上午 pj。
我草 T1,T2 是不是【数据删除】啊,诶诶诶 T3 这不分讨嘛。1h 写完。
开 T4,感觉时间没了要输了。看见 $r \le 100$,直接想分层图,然后挂了。但是发现可以直接 DP,令 $f_{i,j},g_{i,j}$ 表示前 $i$ 轮,以序号 $j$ 开头/结尾的序列是否可行。完了在想 $f_{i,j}$ 咋么最优转移玩到了单调队列,还剩 1.5h 发现是可行性的,【数据删除】。于是飞快码完,11:00 了,测完过了小样例,以为翻了。测大样例,我草 11s,ccf 我和你爆了。摆烂。拍了 T3 发现了 2008...8
的错误。
估分 $100+100+100+60$,实际 $360$。
我以为是 ccf 卡常,结果过了一周发现是我多测没离散化导致复杂度退化,【数据删除】。
吃完饭发现大家 T4 都没 A,感觉良好。$\\$
下午 tg。我草 T1 是不是模拟啊,T2 是不是二分贪心就好了啊,好像不用浮点诶,公式 $v^2-v_0^2=2as$ 好用啊。写写写,一小时都过了。【数据删除】。然后开 T3,DP 诶!首先打出 $50$ 的简单暴力,令 $f_{i,j}$ 表示钦定 $i$ 是红,上一个蓝是 $j$ 的方案数。有转移 $f_{i+1,i} \gets f_{i,j}+[w_{i+1}=w_j]w_j,f_{i+1,j} \gets f_{i,j}+[w_{i+1}=w_i]w_i$。
这玩意咋么这么像 at_dp_w 啊?果断动用套路。
发现若 $j \not = i-1$,则 $f_{i,j}=f_{i-1,j}+[w_i=w_{i-1}]w_i$。否则有 $f_{i,i-1}=\max\limits _ {k} f_{i-1,k}+[w_i==w_k]w_k$。是一个全局加,全局 $\max$,但是有颜色相同单点加,我草不会,弃了。写 T4,题目在说什么?题目在说什么?题目在说什么?oh,很快会了 $\mathcal O(mn^2)$ 的暴力,分析下发现不确定一定选,确定的看情况选。诶,过了 $n,m \le 5000$,摆了。最后发现特殊性质 A 的 $n,m \le 10^5$ 就是先把全局处理完就好。摆摆摆,随着 18:30 的结束指令截止,我的 OI 生涯又少了一年。估分 $100+100+50+48$,实际 $298$。
分析了下 T4 的复杂度,最多 $\mathcal O(\log n)$,所以其实是 $\mathcal O(Tnm \log n)$ 的。
同时发现 T3 只要我把 $f_{i,j}$ 改为 $f_{i,w_j}$ 就可以秒了,悲痛。
接下来,该准备 NOIP 了。$\\$
考场 Code。