文章

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

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

之前一直忘了说。。。＝￣ω￣＝ 我已然逃出了初中，抢回了博客控制权。。。 之前那个妮可厨 z(j)yf 完全不知道怎么用 markdown 啊。。。 真的是！

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

模拟链表实现邻接表 优点： 1. 不用动态申请内存，常数小 2. 没了 下面的代码使用首部插入法。 代码实现： #include <iostream> #include <cstring> using namespace std; static const int nmax= 阅读更多…

单向链表 优点： 1. 比 stl 快得多 2. 插入 O(1) #include <iostream> using namespace std; struct node{int d;node*nxt;node(){d=0,nxt=NULL;}}; struct lst//链表结构体 { 阅读更多…

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

Las Vegas 拉斯维加斯算法是一种随机化算法。总之可以用来骗分。 以下类型的问题可以使用拉斯维加斯算法： 1. 寻找任意一个可行解。 2. 最优解占可行解集的比例较大。 3. 类似质因数分解的单一解问题，可以用此算法一步步得出解。 一般形式 while(!LasVegas()); N 皇后问题 阅读更多…

题意：给定很多个（大概 100 个）矩形，的左上角右下角坐标（不一定为整数），要求它们的面积的并。 分析：这道题的数据非常水，只是 test case 可能会比较多。所以 O(n3) 爆力过不了。只能想想有没有 O(n2log2n) 或者更低的复杂度的算法。很幸运，有两种可行办法（应该说我只想到了这 阅读更多…

这是本蒟蒻有史以来做的第二道线段树的题，竟然调了 3 天。在%%%wangyi%%% 的帮助下终于于 2017 年 4 月 27 日 19 时 10 分 AC。感谢上帝感谢主感谢社会感谢党感谢人民感谢毛主席。。。。 题意：其实这就是一道区间最大最小求和线段树。给定一个矩阵，最多有 20 行，106 阅读更多…