竞赛1s时,根据时间复杂度选择算法

n < 200, 可以选择复杂度为O(n^3)的算法。例:dp, floyd
n < 5000, 可以选择复杂度为O(n^2)的算法。例:dp, Dijkstra, 朴素版Prim
n < 1e6, 可以选择复杂度为O(nlogn)或者O(n^2logn)的算法。例:sort, 线段树, 树状数组, set, mmap, spfa, 凸包, 二分
n < 1e7, 可以选择复杂度为O(n)的算法。例:哈希, 双指针, kmp, AC自动机, 部分sort, 树状数组, spfa
n < 1e8, 可以选择复杂度为O(n)的算法。例:双指针, kmp, AC自动机, 线性筛
n < 1e9, 可以选择复杂度为O(√n)的算法。例:判断质数n < 1e18, 可以选择复杂度为O(logn)的算法。例:二分, 欧几里得算法, 幂运算
此外
128MB
开int数组约1e7~1e8;
二维数组最大4000*4000
全部评论

相关推荐

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