UOJ Logo Cyanic的博客

博客

标签
暂无

#338. 【清华集训2017】小 Y 和地铁 std 挂了 以及一些情况说明

2019-12-03 22:43:33 By Cyanic

Hack

其实,这道题在数据范围和时间限制的设置上不太合理。

常见做法的复杂度是 $O(T \cdot 2^{n/2} \cdot n)$, $O(T \cdot 2^{n/2} \cdot \log n)$ 或者 $O(T \cdot 2^{n/2} )$(可能要预处理一些东西,这是一个 例子)。

这差不多是 $4 \cdot 10^{8}$ 左右,时限只给了$2$ 秒... 但是对于官方数据加上 now >= ans 优化遍历到的状态就很不满了(不加这个优化大概率会 TLE)。

捂脸熊

但是加上各种优化之后,单组数据的 dfs 的调用次数仍然可以卡到 3500000 次以上,常数最小的代码也要跑至少 $3.5$ 秒。

UOJ 上的std 为了防止被卡常,实现的是模拟退火。这个正确性不大靠谱,本来打算卡 TLE 的 Hack 变成了 WA...

所以有什么比较好的解决方案吗?

思考熊

共 1 篇博客