当前位置：首页 > news >正文

20260302 模拟测总结

news 2026/3/26 18:11:19

Preface

考的最差的一次。嗯对但是 T3 T4 其实也没那么难吧？？？

哦哦哦我 T3 怎么差一步就想出来了，哦哦哦我 T4 怎么都发现值域有诈了。我还是做不出来呢。

这么菜。

T1

估分	得分	挂分
$100$	$100$	$0$

按照题意模拟然后弄出四个字符串，判非空求出密码等级，最后输出的时候记得空串要变成 (Null)。

T2

估分	得分	挂分
$100$	$100$	$0$

我怎么并查集都用上了 /咦

考虑对一个位置出发能到达的所有其他位置连边，于是最后会形成 $cnt$ 个连通块并且这些连通块一定都是数组中某一段连续的区间，于是答案就是 $cnt-1$。求方案的时候你就从小到大枚举 $x$，挨个判断下如果让 $p_x$ 增加那么连边 $x \to p_x+1 $ 会不会让连通块数量减少，会的话就连否则就不连。

然后就做完了。

upd：赛后才知道，由于这些连通块一定是数组中某一段连续的区间，所以你用数组什么的搞搞也是可以的，~~但是个人觉得用并查集方便很多 awa~~。

T3

估分	得分	挂分
$20$	$20$	$0$

老师：$40$ 分……啊，是一个 $O(n^2)$，我们可以用二分图……
我们：？？？超纲了？
老师：接下来讲正解……其实和 $O(n^2)$ 的很相似的，还是二分图……
我们：？？？这还是普及组吗？？？

噢没事，不需要二分图的。对你没听错不需要的。

我们考虑对每个 $a_i$ 做质因数分解，然后去除 $a_i$ 中完全立方数的所有因子——换句话说，就是对 $a_i$ 质因数分解后的结果中的所有指数 $\bmod 3$。以下提到的 $a_i$ 就都是去除过后的 $a_i$ 了。

这样一通操作下来，对于一个 $x$，我们就可以很快的算出 $x'$ 是其对应的能凑成完全立方数的唯一解。

于是我们使出 STL 大法，开一个桶 map 存下每个 $a_i$ 的个数，再开一个标记数组记录每个数有没有被处理过——当然你对 $a$ 做一次去重也是一样的效果。处理数 $x$ 时，先特判 $x$ 是不是 $1$，因为 $1$ 的对应凑成完全立方数的解也是 $1$，多个 $1$ 放一块就炸了，所以 $1$ 只能取一个；不是 $1$，就求出 $a$ 中 $x$ 的个数和 $x'$ 的个数，取 $\max$ 加进那个社团，因为我们要尽可能最大化社团总人数。

然后就做完了。

T4

估分	得分	挂分
$50$	$50$	$0$

？？？说好的行末加了多余空格会保龄的呢？？？怎么大家都拿到分了？？？

那我这种特意判了的岂不是吃亏了！/fn /fn /fn

枚举右端点 $r$，先实时更新单调栈（两个，一个维护的是后缀最大值，一个维护的是后缀最小值）。由于 $a_i$ 的值域范围实在太小了只有 $100$，故两个单调栈中最多也只可能分别有 $100$ 个元素。

由于右端点是固定的，根据单调栈中存储的信息，我们可以把取 $l \in [1,r]$ 的 $l$ 分成至多 $200$ 类，每一类都是一个区间 $[x,y]$ 并且其区间 $\min$ 和 $\max$ 值都是固定的。而右端点也知道了，对应的区间就知道了，区间长度也知道了，什么都知道了，然后差分随便弄弄做就完了。

处理的时候还是有一些小细节的，记着想清楚再写。