啊啊啊第一次上 200 /oh
25noip二十连测day6
链接:link
题解:题目内
时间:4.5h (2025.10.21 13:40~18:10)
题目数:4
难度:
A | B | C | D |
---|---|---|---|
\(\color{#F39C11} 橙\) | |||
*1200 |
估分:100 + 72 + 35 + ? = 207 + ?
得分:100 + 72 + 35 + 0 = 207
Rank:61/131
场祭
读题。
开 A,发现似乎很简单,注意到答案一定形如 AAAABBBBABABAB 的形式,就做完了,直接枚举即可。
先不写了,应该是很好写的,继续开 B,显然是 dp,但是发现无论怎么样都逃脱不了要记录两个 \(O(n)\) 或 \(O(V)\) 的状态,于是放弃思考,去进行一个部分分的想,随便搞搞写出来了一个 \(O(nV^2)\) 的 dp,非常优秀,足足有 72pts。
写写写,过样例了。
10min 把 A 写了。
甚至只过了不到 2h。所以有足够的时间去打 CD 的暴力和特殊性质了。
然后发现似乎只会暴力,D 甚至不知道暴力对不对,所以先把 C 的暴力打了。然后继续研究 C,发现可以转化成把所有满足 \(a_i + a_j \ge d\) 的 \((i,j)\) 连边,得到一个图,求删掉最少条边使图成为一个二分图,或者说在二分图左右两边中间保留尽可能的多的边。这样似乎 \(d \le 3\) 就可以做了,可以发现实际上只有 \(0,1,2,3\) 这 \(4\) 种不同的点,然后 \(3\) 一定会产生贡献,所以把 \(1,2\) 分到两边一定是最优的,而 \(0\) 显然放在 \(3\) 少的那一边更优。
注意到是 \(d \le 3\) 而不是 \(d = 3\),所以还需要把 \(d = 0,1,2,3\) 都分讨一遍 /tuu,不过还好,因为 \(1,2\) 都可以直接枚举,毕竟 \(n \le 1000\) 嘛。然后写到 \(3\) 的时候发现过不去样例,于是不想了直接枚举去了,算了下 \(5000 / 1000 \times 333^3 \approx 1.8 \times 10^8\),常数不大 1s 挺能过的,写了之后对着暴力拍出来几个 corner case 就过大样例了。
D 直接爆搜,过掉了 3 个样例,应该能有一些分。
补题
哦 D 看来数据比较强,都 T 飞了呢。
天依宝宝可爱!