假装自己过了 2 个题。
【HT-082-Div.2】核桃CSP-S组模拟赛
链接:link
题解:
时间:4h (2025.10.17 08:00~12:00)
题目数:4
难度:
A | B | C | D |
---|---|---|---|
\(\color{#FFC116} 黄\) | |||
*1400 |
估分:100 + 30 + 30 + 40 = 200
得分:
Rank:
场祭
读 AB。
A 大水题,20min 切掉了。
B 一眼 dp,令 \(f_{i,j}\) 为前 \(i\) 个,有 \(j\) 个还原点,且 \(i\) 必须被翻转的方案数,然后尝试转移,发现要考虑的东西不少,因为在选了上一个状态 \(f_{p,*}\) 之后,包含 \(i\) 的被翻转区间的左端点可以是 \((p,i]\) 中的任意一个位置,然后还要考虑 \(j\) 的限制,挺麻烦的,得到了一个复杂度过于可怕的方程(\(c_{l,r}\) 表示翻转 \([l,r]\) 得到的还原点个数):
而且根本不好优化,不过想了想发现直接枚举 \(p,q\) 就可以不需要枚举 \(x\) 了,得到:
然后发现似乎后面那个 \(\sum\) 可以前缀和优化?令 \(s_{i,j,p} = \sum _{q=p+1} ^{i} f_{p,j-c_{q,i}-(q-p-1)}\),那么 \(s_{i,j,p}\) 似乎是可以从 \(s_{i,j,p+1}\) 递推过来的?
没管,先写了个不优化的 \(O(n^4)\) dp,然后发现过样例了,于是开始写优化,写写写没过样例,哦原来不可以这样,因为 \(p\) 是会影响每一项的。
不会了。不过为什么不给高复杂度正解的部分分啊喂!
考虑到 \(k=0\) 可以砍掉一个 \(n\),所以这个 dp 应该有 30pts。然后 \(a_i\) 两两不同的不会,\(k=n\) 好像会,不过就 10pts 等最后写吧(
读 CD。
欸这个 D 怎么给了 40pts 的暴力高消!这么好!
不过还是先写 C,注意到操作次数不会太多,所以直接模拟,期望能拿到 \(\ge\) 30pts 吧。
写 D,不过大样例,回去看看题面发现 \(a_i,c_i\) 可能相等,哦又过不去另一个样例了,继续看题面发现没有规定不存在自环(,改了就过样例了。
10min 摆了。
补题
天依宝宝可爱!