数位 DP

堪堪能接受的一场。前两题一个半小时左右做完,后两题实在没什么思路,打完所有可能的暴力之后跑路了。

他们告诉我题目名称可以从上到下连起来读。

一句话题解

A – (种)菜

可以发现,假若同时有 ai,ai+1\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}ai+1,ai+2a_{i+1},a_{i+2} 都可合并,则取 ai,ai+2a_i, a_{i+2} 中任意一个合并之后,质因数集合总是变为原来的超集,另外一项仍可合并。

故而可以贪心合并所有合法的邻项,最终检查是否仅剩一项即可。注意到 [1,700][1,700] 仅含 125125 个质因数,故可以用 std::bitset 保存每一项的质因子集合。复杂度 O(128nω)O(\frac{128n}{\omega})赛时竟然还开了数组保存每个质因子的实际指数! (更多…)

More
  • 2022年10月26日