【算法】素数筛 O(nloglogn)

素数筛 当遇到要求 1~n 之间的素数时,最纯的方法是 $n^2$的,稍微聪明点的是 $n√n$的。 遇到 $10^6$或者更大的数据时就挂了。 所以我们需要学习素数筛,可以在接近线性的时间内筛出素数。 这里我只说(会)最好背的一种筛法,复杂度为 $O(nloglogn)$ 代码很简洁,四行。 其中 阅读更多…

Three_C 比赛解题报告–by litble

考试的时候 cy 走进来说:今天提高组模拟,题目很水,请认真对待。 然后…… 我 tm 还真信了 T1 题目:有一排硬币堆, 两个人轮流取硬币。每个选手随机取最左边或者最右边的一堆硬币。求先手期 望取得的硬币数。 硬币堆数<=1000, 数据组数<=1000 60 分 阅读更多…

【题解】请柬 最短路 卡常 LUOGU – 1342

1. 题目 传送门= ̄ω ̄= 题目大意:给你一张有向图,求点 1 到其他点和其他点到点 1 的最短路长度之和。 节点数、边数在 10^6 以内 题解 此题卡常。 用真正链表会超时,因为真链表会动态申请空间。 stl 更不用说。 得用模拟链表。 至于思路,很简单,建立反向图,在原图、反向图上分别跑一下 阅读更多…

【算法】块状链表

块状链表 大概就长这样。。。 不难发现块状链表就是一个链表,每个节点指向一个数组。 我们把原来长度为 n 的数组分为√n 个节点,每个节点对应的数组大小为√n。 所以我们这么定义结构体,代码见下。 其中 sqn 表示 sqrt(n) 即√n,pb 表示 push_back,即在这个 node 中加入 阅读更多…