牛客小白月赛42 D 金蛇狂舞

金蛇狂舞

https://ac.nowcoder.com/acm/contest/11219/D

题目给出了 33 个操作。

有朴素做法:暴力枚举所有可能操作,然后判断是否符合条件,还需要预处理阶乘。

这样子时间复杂度为 O(37T)O(3^7T),可以通过。

但是就这么写会挂掉!

因为如果所有操作都是阶乘,那么数字会特别大,然后就挂了。

让我们仔细想想,在什么时候,不需要阶乘操作。

在当前大于 y2y^2 时我们不需要阶乘操作。

因为阶乘操作无意义,与答案相差越来越远。

所以就可以剪枝了,时间复杂度优化很多。

代码。

全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务