NOI及NOIP需要知道的与自己的心得

1 Webb.S 一、（搜索）双向广度搜索

广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。

范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。 问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点所连接的两条路径所拼成的路径就是最优解。 对广度搜索算法的改进：

１。添加一张节点表，作为反向扩展表。

２。在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。

３。在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时 与之相同。

对双向广度搜索算法的改进：

略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。

二、（搜索）分支定界

分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。

范例：在一个商店中购物，设第I种商品的价格为Ci。但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。

问题分析：显然，折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数向零递减搜索，设A为以打完折扣后优惠的价格，C为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中a为下一个折扣的折扣率。如当前已是最后一个折扣，则a=1。 对回溯算法的改进：

１。添加一个全局变量BestAnswer，记录当前最优解。

２。在每次生成一个节点时，计算其预期值，并与BestAnswer比较。如果不好，则调用回溯过程。

三、（hash）KR算法——字符串匹配

KR算法对模式串和循环中每一次要匹配的子串按一定的hash函数求值，如果hash值相同，才进一步比较这两个串是否真正相等。

举例说一下KR算法吧：在我写的这个总结中，各个算法使用的例子都一样，随便找的； 模式串 pattern=\ 文本串 text=\pattern 长度记 pattern_len

1

2 Webb.S

预备阶段就是计算pattern的hash，长度为6，那么hash_pattern='p'*2^5+'a'*2^4+'p'*2^3+'p'*2^2+'a'*2^1+'r'*2^0

当然，这里使用的是字符的ascii值

也计算text前六个字符的hash，我们记第一个为hash_text[0]

然后就开始向前移动了，在移动时，要重新计算当前与模式串对应的串的hash值，这个工作叫rehash

初始化 i=0

如果 hash_pattern与hash_text[i]相等，返回 i

如果不等 计算新的hash值，就是text[i..i+patten_len]的hash， 当然这里不会像第一次那样全部计算，方法是

上一次计算的值减去上一次匹配时串的第一个字符乘以 2^pattern_len ,然后乘以2，再加上新加入比较的字符值

根据公式可以很清晰看出来。

就是减去计算中的第一项，把剩下的乘以2，然后在末尾加入新增的字符值

四、（图论）Floyd求最小环

floyd求最小环是一种相对效率较高的算法。它的改进算法就是在外层循环n次，每一次都用k作中转点求出一个最短路，为下一次求最小环做好了准备。核心代码如下： min:=1 shl 30;

for k:=1 to n do begin for i:=1 to k-1 do for j:=1 to k-1 do

if (i<>j)and(f[i,j]+map[k,i]+map[j,k]

if (i<>j)and(i<>k)and(k<>j) and(f[i,k]+f[k,j]

对于求最小环部分，可以这样来理解，当前的f[i,j]是用1...k-1作中转点求出来的，那么必然最短路不包含k点，现在如果i,j到k有边，且构成的环更优，那么更新min。还有点需要注意就是方向性，因为在有向图中边是单向的，所以需要最小环的构成情况：

min=f[i,j]+map[j,k]+map[k,i] 首先f[i,j]是i到j的最短路，然后j到k有边，k到i有边，构成环。

对于floyd求最短路部分，当前已经用k作中转点求出了最小环，那么现在的k已经失去了作中转点的作用，于是可以构成最短路的一部分，为下一次用k+1作中转点求出最短路。

这两个部分就是floyd求最小环的精华所在，每次的floyd都为下次求min做好了铺垫，不多不少，没有冗余，很完美的算法。

五、（优化）位运算

=== 1. and运算 ===

and运算通常用于二进制取位操作，例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该

2

3 Webb.S

数为奇数.

=== 2. or运算 ===

or运算通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。 === 3. xor运算 ===

xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。

xor 运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a xor b) xor b = a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值，得到1314520，于是她就明白了我的企图。

=== 4. shl运算 ===

a shl b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，那么100 shl 2 = 400。可以看出，a shl b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。

通常认为a shl 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。

定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 - 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用shl来定义Max_N等常量。 === 5. shr运算 ===

和 shl相似，a shr b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用shr 1来代替div 2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的mod运 算，效率可以提高60%。

功能 | 示例 | 位运算 --------------------------------+---------------------------------------+-------------------- 去掉最后一位 | (101101->10110) | x shr 1 在最后加一个0 | (101101->1011010) | x shl 1 在最后加一个1 | (101101->1011011) | x shl 1+1 把最后一位变成1 | (101100->101101) | x or 1 把最后一位变成0 | (101101->101100) | x or 1-1 最后一位取反 | (101101->101100) | x xor 1

把右数第k位变成1 | (101001->101101,k=3) | x or (1 shl (k-1))

把右数第k位变成0 | (101101->101001,k=3) | x and not (1 shl (k-1)) 右数第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1)) 取末三位 | (1101101->101) | x and 7

取末k位 | (1101101->1101,k=5) | x and (1 shl k-1) 取右数第k位 | (1101101->1,k=4) | x shr (k-1) and 1 把末k位变成1 | (101001->101111,k=4) | x or (1 shl k-1) 末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1) 把右边连续的1变成0 | (100101111->100100000) | x and (x+1) 把右起第一个0变成1 | (100101111->100111111) | x or (x+1)

3

4 Webb.S

把右边连续的0变成1 | (11011000->11011111) | x or (x-1)

取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1 去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1))

最后这一个在树状数组中会用到。

和 普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件 下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色 的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所 有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变 化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后 全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。

六、（数据结构）树状数组

用lowbit函数维护了一个树的结构 那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，

支持随时修改某个元素的值，复杂度也为log级别。

来观察这个图：

令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：

4

5 Webb.S

C1 = A1

C2 = A1 + A2 C3 = A3

C4 = A1 + A2 + A3 + A4 C5 = A5

C6 = A5 + A6 C7 = A7

C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ...

C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16

这里有一个有趣的性质：

设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，

所以很明显：Cn = A(n – 2^k + 1) + ... + An

算这个2^k有一个快捷的办法，定义一个函数如下即可： int lowbit(int x){ return x&(x^(x–1)); }

当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可： step1: 令sum = 0，转第二步；

step2: 假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步； step3: 令n = n – lowbit(n)，转第二步。

可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明： n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。

那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。

所以修改算法如下（给某个结点i加上x）： step1: 当i > n时，算法结束，否则转第二步；

step2: Ci = Ci + x， i = i + lowbit(i)转第一步。

i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。

对于数组求和来说树状数组简直太快了!

七、（数论）快速幂

把b转换成2进制数

该2进制数第i位的权为a^（2^(i-1)） 例如

a^11=a^(2^0+2^1+2^3) 11的二进制是1 0 1 1

11 = 2^3*1 + 2^2*0 + 2^1*1 + 2^0*1

so:我们将a^11转化为算a^(2^0)*a^(2^1)*a^(2^3)

5

6 Webb.S

快速幂可以用位运算这个强大的工具实现 b and 1 //也就是取b的二进制最末位 b shr 1 //就是去掉b的二进制最末位

有了这个强大的工具，快速幂就好实现了！ var

a,b,n:int64;

function f(a,b,n:int64):int64; var

t,y:int64; begin

t:=1;y:=a; while b<>0 do begin

if (b and 1)=1 then t:=t*y mod n;

y:=y*y mod n; //这里用了一个很强大的技巧,y*y即求出了 a^（2^(i-1)） ←不知道这是什么的看原理 b:=b shr 1; end; exit(t); end; begin

read(a,b,n); // n是模 write(f(a,b,n)); end.

八、（STL）multiset多重集合容器

multiset多重集合容器与set集合容器类似，也是采用红黑树组织元素数据，只是该容器允许将重复的元素键值插入，而set不允许。其基本使用方法见下例：

1 #include 2 #include 3 using namespace std; 4 5 int main() 6 { 7 multiset ms; 8 ms.insert(10); 9 ms.insert(10); 10 ms.insert(13); 11 ms.insert(11); 12 ms.insert(13); 13 ms.insert(12); 14 ms.insert(13);

15 ms.erase(10);//删除键值为10的元素 16 multiset::iterator i;

17 for(i=ms.begin();i!=ms.end();i++)//打印全部元素

6

7 Webb.S

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

cout<<*i<<' '; cout<

multiset::iterator ii=ms.find(v); if(ii!=ms.end()) cout<<*ii<

//查找所有相同元素 v=11;

pair::iterator,multiset::iterator> p=ms.equal_range(v);

cout<<\大于等于第一个元素的为 \ cout<<\大于11的第一个元素为：\

ms.erase(p.first,p.second);//删除迭代器区间[p.first,p.second]上的所有元素

for(i=ms.begin();i!=ms.end();i++)//打印全部元素 cout<<*i<<' '; cout<

for(i=p.first;i!=p.second;i++) cout<<*i<<' '; cout<

cout<<\等于13的个数：\ ms.clear();//清除全部元素 system(\ return 0; }

结构体也可以使用multiset容器，请看下例：

1 #include 2 #include 3 using namespace std; 4 5 struct Person //定义结构体 6 { 7 int id; 8 char *name; 9 char *addr; 10 int age; 11 }; 12

13 struct PersonOrder//此为比较函数，按id号大小比较 14 {

15 bool operator()(const Person &p1,const Person &p2) 16 {

17 return p1.id

7

8 Webb.S

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

int main() {

Person PersonArray[]={ {3,\张三\浙江\ {4,\李四\北京\ {5,\王二\上海\ {1,\高强\广州\ {2,\刘文\新疆\ {6,\赵强\福建\ };

//创建了multiset容器ms，容器内元素数据以id进行键值比较 multiset

ms(PersonArray,PersonArray+6,PersonOrder()); Person temp={9,\ ms.insert(temp);//插入新元素

cout<<\容器是否为空：\ multiset::iterator i;//定义游标i

for(i=ms.begin();i!=ms.end();i++)//顺序输出记录 cout<<(*i).id<<' '<<(*i).name<<' '<<(*i).addr<<' '<<(*i).age<

cout<<\学生人数：\ ms.clear();//清除全部元素

getchar(); return 0; }

九、（STL）priority_queue优先队列容器

优先队列也是一种从一端入队，另一端出队的队，不同于一般队列的是，队列中最大的元素总是位于队首位置，因此，元素的出队并非按照先进先出的要求，将最先入队的元素出队，而是将当前队列的最大元素出队。

优先队列容器使用的堆排序算法，每次将最大值出列。时间复杂度为O(nlogn)。

参考程序： 1 #include 2 #include 3 #define STACK_SIZE 100 4 using namespace std; 5 6 int main() 7 { 8 priority_queue q; 9 q.push(93); 10 q.push(5); 11 q.push(2); 12 q.push(33);

8

9 Webb.S

13 14 15 16 17 18 19 20 21 22 23 24

q.push(52); q.push(12);

cout<<\元素个数为：\ while(!q.empty()) {

cout<

q.pop();//出队列要先判断是否为空 }

system(\ return 0; }

十、（图论）网络流

15.1 网络流初步

Ford-Fulkerson算法 O(C(V+E))

DFS找到可行流。加反向边。继续DFS，共C次。

-----

Edmonds-Karp 最短增广路算法 O(VE2) BFS找到可行流。加反向边。继续BFS。

15.2 最大流

15.2.1 Dinic算法

Dinic 算法 O(≤V2E)

BFS进行标层。DFS找到可行流。

返回到最上层的流路径中的向下流量为0的点。

做类似EK的操作。继续DFS。

当回到原点不能再DFS的时候，结束DFS。

再次进行BFS标层。当汇点不能标到层次的时候。结束算法。

15.2.2 Sap算法

Sap 算法 O(<

DFS找到可行流。若一个点无法前进，则修改编号。 重新编为它的下面的最小值+1。（即他能到的最小的点）

当找到可行流后，也要增加反向边。

----- Gap优化

将编号统计到一个数组。

若存在断层，即有的编号不存在。

退出求最大流程序。

-----

15.2.3 有上下界的最大流

统计每点的最低入流量与最低出流量。

增加两个虚拟源点与汇点。

连接虚拟源点->点，流量为该点最低入流量。 连接点->虚拟汇点，流量为该点的最低出流量。

连接原始汇点->原始源点，流量为+∞。 将两点之间的流量改为最大流量-最小流量。

做虚拟源点->虚拟汇点的最大流。 对于与虚拟点连接的边不用反向边。

核对所有必要边的流量是否为0，若有>0的则无解。

当得到最大流以后，将与虚拟点连接的边去掉。

9

10 Webb.S

再去掉原始汇点->原始源点的边。 对于剩下的图中再求最大流，得到流值。

对于连接到汇点的点，流量改成前面求得的流量+流向汇点最低流。

把这些连接到汇点的点的流量相加，和就是所求最大流。

15.4.1 最短路增广费用流

将两点之间的费用转化成两点之间的距离。

通过SPFA找到一条可行的最短流。

增加反向边，寻找最短流时该边权值为负。

最后的费用为Σ(每次的距离*流量)。

十一、（DP）RMQ——ST

RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。

来看一下ST算法是怎么实现的(以最大值为例）：

首先是预处理，用一个DP解决。设a是要求区间最值的数列，f表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出f其实就等于a。这样，Dp的状态、初值都已经有了，剩下的就是状态转移方程。我们把f平均分成两段（因为f一定是偶数个数字），从i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1为一段(长度都为2^（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。f就是这两段的最大值中的最大值。于是我们得到了动规方程F[i，j]=max（F[I,j-2],F[i+2^(j-1),j-1]）. F[i,0]=a[i](边界条件) 接下来是得出最值，也许你想不到计算出f有什么用处，一般毛想想计算max还是要O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间[2，8]的最大值，就要把它分成[2,5]和[5,8]两个区间，因为这两个区间的最大值我们可以直接由f[2，2]和f[5，2]得到。扩展到一般情况，就是把区间[l，r]分成两个长度为2^n的区间（保证有f对应）。直接给出表达式： k:=[ln(r-l+1)/ln(2)];

ans:=max(F[l，k],F[r-2^k+1,k]);

这样就计算了从i开始，长度为2^k次的区间和从r-2^k+1开始长度为2^k的区间的最大值（表达式比较烦琐，细节问题如加1减1需要仔细考虑 部分核心代码：

read(n, q);

for i := 1 to n do read(d[i, 0]);

for j := 1 to trunc(ln(n) / ln(2)) do for i := 1 to n - 1 shl j + 1 do d[i,j] := max(d[i,j-1], d[i+1 shl (j-1),j-1]); for i := 1 to q do begin read(a, b); k := trunc(ln(b - a + 1) / ln(2)); rmq := max(d[a, k], d[b - 1 shl k + 1, k]); writeln(rmq); end;

10

11 Webb.S 十二、（图论）Tarjan

其实，tarjan算法的基础是DFS。我们准备两个数组Low和Dfn。Low数组是一个标记数组，记录该点所在的强连通子图所在搜索子树的根节点的Dfn值（很绕嘴，往下看你就会明白），Dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。根据以下几条规则，经过搜索遍历该图（无需回溯）和对栈的操作，我们就可以得到该有向图的强连通分量。

数组的初始化：当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。 堆栈：每搜索到一个点，将它压入栈顶。

当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’不在栈中，p的low值为两点的low值中较小的一个。

当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个。

每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。

继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。

由于每个顶点只访问过一次，每条边也只访问过一次，我们就可以在O（n+m）的时间内求出有向图的强连通分量。 program tarjan; var

v,f:array[1..100]of boolean; dfn,low:array[1..100]of integer;

a:array[0..100,0..100]of integer; //边表 i,j,n,m,x,y,deep,d:integer; stack,ln:array[1..100]of integer; function min(x,y:longint):integer; begin

if x>y then exit(y) else exit(x); end;

procedure print(x:integer); //出栈，打印 begin

while stack[deep]<>x do begin

write(stack[deep],' '); f[stack[deep]]:=false; dec(deep); end;

writeln(stack[deep]);

f[stack[deep]]:=false; //去除入栈标记

11

12 Webb.S

dec(deep); end;

procedure dfs(x:integer); var

i:integer; begin

inc(d); //时间

dfn[x]:=d; //规则1 low[x]:=d;

inc(deep); //栈中元素个数 stack[deep]:=x; //规则2 f[x]:=true;

for i:=1 to a[x,0] do if not v[a[x,i]] then begin

v[a[x,i]]:=true; dfs(a[x,i]);

low[x]:=min(low[a[x,i]],low[x]); //规则3 end

else if f[a[x,i]] then

low[x]:=min(low[x],dfn[a[x,i]]); //规则4 if dfn[x]=low[x] then //规则5 print(x); end;

begin

readln(n,m);

fillchar(a,sizeof(a),0); for i:=1 to m do begin

readln(x,y); //读入图 inc(a[x,0]); a[x,a[x,0]]:=y; end;

for i:=1 to n do if not v[i] then begin

v[i]:=true;

dfs(i); //更换起点，规则6 end; end.

12

13 Webb.S 十三、（图论）次短路径

次短路径可以看作是k短路径问题的一种特殊情况，求k短路径有Yen算法等较为复杂的方法，对于次短路径，可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。

我们要对一个有向赋权图(无向图每条边可以看作两条相反的有向边)的顶点S到T之间求次短路径，首先应求出S的单源最短路径。遍历有向图，标记出可以在最短路径上的边，加入集合K。然后枚举删除集合K中每条边，求从S到T的最短路径，记录每次求出的路径长度值，其最小值就是次短路径的长度。

在这里我们以为次短路径长度可以等于最短路径长度，如果想等，也可以看作是从S到T有不止一条最短路径。如果我们规定求从S到T大于最短路径长度的次短路径，则答案就是每次删边后大于原最短路径的S到T的最短路径长度的最小值。

用Dijkstra+堆求单源最短路径，则每次求最短路径时间复杂度为O(N*log(N+M) + M)，所以总的时间复杂度为O(N*M*log(N+M) + M^2)。该估计是较为悲观的，因为一般来说，在最短路径上的边的条数要远远小于M，所以实际效果要比预想的好。

十四、（图论）次小生成树

类比次短路径求法，很容易想到一个“枚举删除最小生成树上的每条边，再求最小生成树”的直观解法。如果用Prim+堆，每次最小生成树时间复杂度为O(N*log(N+M) + M)，枚举删除有O(N)条边，时间复杂度就是O(N^2*log(N+M) + N*M)，当图很稠密时，接近O(N^3)。这种方法简易直观，但我们有一个更简单，而且效率更高的O(N^2+M)的解法，下面介绍这种方法。

首先求出原图最小生成树，记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v)，加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边)，把它删掉，计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值，就是次小生成树。

具体实现时，更简单的方法是从每个节点i遍历整个最小生成树，定义F[j]为从i到j的路径上最大边的权值。遍历图求出F[j]的值，然后对于添加每条不在最小生成树中的边(i,j)，新的生成树权值之和就是MinST + w(i,j) – F[j]，记录其最小值，则为次小生成树。

该算法的时间复杂度为O(N^2 + M)。由于只用求一次最小生成树，可以用最简单的Prim，时间复杂度为O(N^2)。算法的瓶颈不在求最小生成树，而在O(N^2+M)的枚举加边修改，所以用更好的最小生成树算法是没有必要的。

十五、（策略）竞赛中的策略

首先通读所有的题目；草拟出算法，复杂度，数量，数据结构，微妙的细节，??

· 集体讨论所有可能的算法—— 然后选择最“笨”但却可行的算法。（注：请注意这

一点，对参赛选手来说获奖就是唯一目的）

· 进行计算！（空间和时间复杂度，并且加上实际期望和最坏情况下的数量） · 试图证明该算法错误——使用特殊的（退化的）测试数据。

· 将问题排序：根据你所需付出的努力，将能够最快解决的问题排在前面。（答题的次 序为：以前做过的，容易的，不熟悉的，难的）

13

14 Webb.S

编写程序解决一个问题—— 对每一道题而言，一次一道题

· 确定算法

· 构造特殊情况的测试数据 · 写出数据结构

· 编写并测试输入子程序（编写额外的子程序来显示数据输入的正确性） · 编写并测试输出子程序

· 逐步细化：通过写注释来刻划程序的逻辑轮廓 · 一个部分一个部分地填充并调试代码

· 完成代码使其正常运转，并验证代码的正确性（使用一般情况的测试数据） · 试图证明代码错误——使用特殊情况的测试数据来验证代码正确性

· 逐渐优化——但足够了即可，并且保存所有的版本（使用最坏情况的（即运行时间

长的）测试数据来计算出实际运行时间）

时间安排策略和“故障控制”方案

制定一个计划决定在各种（可预测的）故障发生时的行动；想象你可能遇到的问题并计算出 你所希望做出的反应。核心问题是：“你何时花费更多的时间在调试程序上，你何时放弃并 继续做下一题？”。考虑以下问题： · 你已经花费了多长时间来调试它？ · 你可能有什么样的BUG？ · 你的算法有错吗？

· 你的数据结构需要改变吗？

· 你是否对什么地方可能会出错有一些头绪？

· 花费较短的时间（20 分钟）在调试上比切换去做其他别的事要好；但是你或许能够 在45 分钟内解决另一个问题（ A short amount (20 mins) of debugging is better than switching to anything else; but you might be ableto solve another from scratch in 45 mins.） · 你何时返回到一个你先前放弃的问题？

· 你何时花费较多的时间优化一个程序，你何时放弃当前优化工作而切换去作其他 事？

· 从这点考虑出去（Consider from here out）——忘记先前的努力，着眼于将来： 你如何才能就你目前所有的抓住下一个小时。

在你上交你的答案之前列出一个校验表：

· 在竞赛结束前五分钟结束编写代码（Code freeze five minutes before end of

contest）。

· 将所有的声明关闭。 · 将调试输出关闭。

· 确认输入输出文件名正确。 · 确认输入输出格式正确。 · 重新编译并再测试一次。

· 将文件以正确的文件名复制到正确的位置（软盘）。

提示和技巧

· 如果可以就用暴力法（即穷举法）解决（注：居然将这条作为技巧，可见竞赛的目

的就是获奖，为此要“不择手段”。）

· KISS(=Keep It Simple, Stupid)：简单就好！（KISS: Simple is smart!） · 提示：注意限制（在问题陈述中指明）

14

15 Webb.S

· 如果可以给你带来方便的话就浪费内存（假如你能侥幸逃脱规则处罚的话） · 不要删除你额外的调试输出，将它注释起来 · 逐渐地优化，足够了即可 · 保留所有的工作版本 · 编码到调试：

o 注意留有空白（whitespace is good） o 使用有意义的变量名 o 不要重复使用变量 o 逐步细化

o 在写代码之前先写注释 · 有可能的话尽量避免使用指针

· 避免使用麻烦的动态内存：静态地分配所有的东西。

· 尽量不要使用浮点数；如果你不得不使用，在所有使用的地方设置允许的误差（绝

对不要测试两个浮点数相等） · 如何写注释：

o 不要写得太长，简洁的注解就可以了

o 解释复杂的功能：++i; /* increase the value of i by 1*/ 这样的注释 是毫无意义的。 o 解释代码中的技巧

o 将功能模块划定界限并且归档（ Delimit & document functional sections）

o 注释要好像是写给某个了解该问题但并不了解程序代码的聪明人看的 o 对任何你不得不考虑的东西加以注释

o 在任何你看到了以后会问“他到底干什么用”的地方加注释（Anything you looked at even once saying, \） o 总是注释数组的索引次序

· 记录你每一次竞赛的情况：成功之处、犯的错误，以及何处你可以做得更好；利用 这些记录来改进你的策略。

复杂度

基础和阶符号

复杂度分析的基本原理围绕着符号大“O”，例如：O(N).这意味着算法的执行速度或内存占 用将会随着问题规模的增倍而增倍。一个有着O(N 2)的算法在问题的规模增倍时其运行时间 将会减慢4 倍（或者消耗4 倍的空间）。常数时间或空间消耗的算法用O(1)表示。这个概念 同时适用于时间和空间；这里我们将集中讨论时间。 一种推算一个程序的O( ) 运行时间的方法是检查它的循环。嵌套最深的（因而也是最慢的） 循环支配着运行时间，同时它也是在讨论O( ) 符号时唯一考虑的循环。有一个单重循环和 一个单层嵌套循环（假设每个循环每次执行N 次）的程序的复杂度的阶是O(N 2)，尽管程序 中同时有一个O(N)循环。

当然，递归也像循环一样计算，并且递归程序可以有像O(b N)， O(N!)， 甚至O(N N)的阶。

经验法则

· 在分析一个算法以计算出对于一个给定的数据集它可能要运行多长时间的时候，第

一条经验法则是：现代（1999）计算机每秒可以进行10M 次操作。对于一个有五秒 钟时间限制的程序，大约可以处理50M 次操作。真正优化的好的程序或许可以处理 2 倍甚至4 倍于这个数目的操作。复杂的算法或许只能处理这个数目的一半。

15

16 Webb.S

· 640K 确实是苛刻的内存限制。幸运的是，1999-2000 赛季将是这个限制的最后一次

起作用。

· 210 约等于10 3

· 如果有k 重嵌套的循环，每重大约循环N 次，该程序的复杂度为O(N k)。

· 如果你的程序有l 层递归，每层递归有b 个递归调用，该程序复杂度为O(b l)。 · 当你在处理有关排列组合之类的算法时，记住N 个元素的排列有N!个，N 个元素的 组合或N 个元素组成的集合的幂集的有2 n 个。 · 对N 个元素排序的最少时间是O(NlogN)。

· 进行数学计算！将所有的数据加起来。（Plug in the numbers.）

解决方案的范例

产生器vs. 过滤器

产生大量可能的答案然后选择其中正确的（比如8 皇后问题的解答），这样的程序叫做过滤 器。那些只产生正确答案而不产生任何错误节点的叫做产生器。一般来说，过滤器较容易（较 快）编程实现但是运行较慢。通过数学计算来判断一个过滤器是否足够好或者是否你需要尝 试制作一个产生器。 预先计算

有时生成表格或其他数据结构以便快速查找结果是很有用的。这种方法叫做预先计算（在这 里用空间换取时间）。你可以将需要预先计算的数据和程序一起编译，在程序开始时计算； 也可以干脆记住预先计算出的结果。比如说，一个程序需要将大写字母转化为小写字母，可 以不需任何条件地利用一个表格进行快速查找来实现。竞赛题经常要用到素数——生成一长 串素数在程序中某处使用通常是很实用的。 分解（编程竞赛中最困难的事）

虽然在竞赛中经常使用的基本算法不超过20 种，但是某些需要将两种算法结合才能解决的 组合型问题却是很复杂的。尽量将问题不同部分的线索分离开来以便你可以将一个算法和一 个循环或其他算法结合起来以独立地解决问题的不同部分。注意，有时你可以对你的数据的 不同（独立）部分重复使用相同的算法以有效地改进程序的运行时间。 对称

许多问题中存在着对称（例如，无论你按哪一个方向，一对点之间的距离通常是相同的）。 对称可以是2 路的（？？原文是2-way），4 路的，8 路的或是更多的。尽量利用对称以减少

运行时间。

例如，对于4 路对称，你只需解决问题的四分之一，就可以写下4 个结果，这四个结果和你 所解决的一个结果是对称的（注意自对称的解答，他当然只应该被输出一次或两次）。 正向vs. 逆向 令人惊讶的是，许多竞赛题用逆向法解决比正面突破要好得多。以逆序处理数据或构造一种 基于某种非明显的方式或顺序检索数据的突破策略时，要特别小心。 简化

某些问题可以被改述为一个有点不同的其他问题，这样你解决了新问题，就已经有了原始问 题的答案或者容易找出原始问题的答案；当然，你只需解决两者之中较容易的那个。另外， 像归纳法一样，你可以对一个较小的问题的解答作一些小小的改变以得到原问题的完整答 案。

16

17 Webb.S 十六、（纲）NOIP常用知识点列表

那些最最基本的内容我就不赘述了。。。

感觉这些应该是NOIP难度的知识点，尽量掌握吧。。。前面的数字分别是难度系数和重要度(1---5)

1、排序：

(1,5)冒泡/选排(这个很常用，一定要保证正确性)

(2,5)快排(Pascal选手可以去FPC文件夹里找代码,C/C++选手注意sort的正确性)

(3,4)归并排序(最好要会，因为有可能有题要卡快排)

2、数据结构：

(2,2)循环队列(节省空间用) (2,4)单调队列(DP里经常用) (1,3)完全二叉树的数组存储 (2,5)并查集(一定要会路径压缩) (3,4)图的前向星存法

(4,2)Trie树，后缀数组(这些学过的就再复习一下，没学过就不用看了，估计考的概率不大)

(3,2)森林转二叉树(树状DP常用)

3、动态规划：

(1,5)基本的背包问题(一定要熟练写出方程，尤其注意边界的取值)

(3,4)多线程DP(二取方格数) (3,2)LIS的二分优化

(2,4)DP的队列优化(LCIS，单调队列很常用的) (3,4)树状DP(其实就是记忆化搜索，很好理解)

4、图论：

(1,5)最短路(dijkstra,floyd,spfa) (2,5)最小生成树(prim,kruskal) (2,5)拓扑排序

(2,3)floyd求最小环

(3,4)求(有向/无向)图的强连通分量 (1,3)判断图中是否有环 (3,2)图的关键路径

(4,1)差分约束系统(就是求最长路，用spfa)

5、其他：

(2,4)RMQ问题的ST算法(LCA问题也可以转化为RMQ问题)

(4,5)高精度的加减乘除开方(开方一般情况下直接二分比较方便)

(3,4)表达式求值(栈或并查集皆可，一般来说并查集比较容易实现)

(2,2)扩展欧几里得算法(解同余方程用) (1,5)乘法转加法神器：log

(1,4)求最大子序列和的备忘录算法

(2,3)位运算优化搜索(N皇后问题，建议去USACO做一下) (4,2)搜索剪枝(推荐做USACO的fence rail那题)

17

18 Webb.S NOIP常用基础知识点列表

I.高精度

a.加法 b.减法 c.乘法 d.高精度除单精 II.排序算法 a.选择排序 b.插入排序 c.hash排序 d.归并排序 e.堆排序 f.快排

III.字符串匹配算法 a.蛮力法 b.KMP IV.数论

a.欧几里德算法

b.扩展欧几里德算法(ax+by=c的正整数) c.素数测试 {O(sqrt(n))} d.筛法求素数

e.快速乘方(请用高精) V.树论

a.二叉搜索树 b.优先队列

c.线段树 (RMQ问题建议使用st算法) d.平衡树一种(建议学习SBT) VI.图论

a.拓扑排序

b.割顶，割边(桥) {O(n)} c.强连通分支 {O(n)}

d.有向无回路图的最长路径(罕见用上的) e.欧拉回路 f.最小生成树

1.Prime 2.Kruskal (这个个人觉得挺重要的) g.次小生成树 {简单的删除最大边是不对的} h.最短路径

1.Dijkstra

{推荐单源使用spfa，同样可以通过设上2.Bellman-ford

限发现图中是否有负权回路，而且这个思3.spfa

想在去除dp中的暂时后效性非常有用} 4.flyod

VII.计算几何学 {noip不是不考几何} a.判断两条线段是否相交 b.凸包算法 {O(n)} VIII.其他算法 a.并查集

b.RMQ问题(通解：线段树，st算法)

18

19 Webb.S 十七、（图论）Kruskal和SPFA

用Kruskal算法求最小生成树的思想如下：

设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。

Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？

我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。

SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内，求出源点到其他所有点的最短路径，可以处理负边回路（某一个顶点入队超过n次）。SPFA的实现比Dijkstra或者Bellman_Ford还要简单。

设dist代表s到i点的当前最短距离，fa代表s到i的当前最短路径中i点之前的一个点的编号。开始时dist全部为+∞，只有dist[s]=0，fa全部为0。

维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。

每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。

SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。

设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。

19

20 Webb.S 十八、（图论）匈牙利算法

所谓二分图，简单的来说就是满足可以把图中的所有点分成两堆使得任意一边的两个顶点均不在同一堆中这一条件的图；而二分图的匹配则是指原图中的边集的一个子集并且这个子集满足其中任意两条边均不共顶点；至于最（极）大匹配，顾名思义就是说边数最多的匹配。

根据这些定义，我们可以很明显的发现，这个题实在是一个典型的不能再典型的二分图的最大匹配：

人：一堆点

传送点：另一堆点 建图：

有些人能够在规定时间跑到某些传送点：点与点之间有边，且任意一边的两个顶点的不在同一堆点中。

一个传送点只能传送一个人：任意一个点只能使用一次，即一种逃跑方案对应一个匹配。 求最多有多少个人能够逃脱：求最大匹配含有多少条边。 匈牙利算法实现思想

现在有一群人要逃跑，他们按照编号大小（一定顺序即可）逐个选择目的地，但是这样就会产生一些矛盾，即有可能两个人选择了同一目的地，于是他们就可以协商一下，如果后选者能为先选者找到另一个传送点，那么先选的人就同意放弃这个点，转而走后选者帮他找的那个传送点（当然可能后来选的传送点也已经被占用，这时我们可以采用递归的方式进行判断是否能为后选的传送点的原主人再找另一个传送点），如果后选者找不到另外一个可以让先选者逃生的路线，那么对不起，先选的人不会放弃自己逃生的机会，后选者只有另寻出路了。

匈牙利算法其实是一个类似于贪心的过程，其主体思想就是若让某个人逃生可以让逃生的总人数加一的话，那么让他走，否则就把他留下。首先我们可以为依次为每个人寻找传送点（显然若某个点一条边都没有那么他肯定是跑不出去的，所以对于这样的人我们可以不做考虑），当然这样可能会出现某个人的目的地已经被前面的人占用了，考虑到如果仅仅是更换这个传送点的归属的话，逃生的总人数并未发生改变，即未产生有意义的变化，所以我们约定必须要能够为传送点原先的主人找到另一个穿送点才能把这个这个传送点让给他，即要使得逃生的总人数增加，产生有意义的变化。如此，对每个人都判断一下让他逃跑是否会产生有意义的变化即可得到最终结果。

这个题目的需要注意的几个地方

1：注意输入格式，多读，一定要多读。

2：需要开一个数组保证不会与同一个人协商两次，以免产生无限递归导致栈溢出（如果不开数组判断的话有可能产生如下问题：1要占2的传送点，2要占3的传送点，3要占2的传送点，2又要占3的传送点??）

十九、心得

* memset 因为memset是以字节为单位就是对array指向的内存的4个字节进行赋值，每个都用ASCII为1的字符去填充， 转为二进制后，

1就是00000001,占一个字节。一个INT元素是4字节，

合一起就是00000001000000010000000100000001，就等于16843009， 就完成了对一个INT元素的赋值了。 memset 127 = max (int)

20

21 Webb.S

memset 128 =-max (int) memset 0x3f= max (long long) memset-0x3f=-max (long long) memset的正规用法是只能用来初始化char类型的数组的，也就是说，它只接受0x00-0xFF的赋值 然而，在大多数情况下，需要对一个double或int的数组赋一个相对很大或很小的初值 以下的赋值方式是不正确的： memset(arr,2147483647,sizeof(arr)); 但是可以用一些技巧，来得到一个差不多的最大值，比如像： memset(arr,0x7F,sizeof(arr)); 它将arr中的值全部赋为2139062143 这是用memset对int赋值所能达到的最大值 类似的还有： memset(arr,0x80,sizeof(arr)); //set int to -2139062144 memset(arr,0x7F,sizeof(arr)); //set double to 1.38242e+306 memset(arr,0xFE,sizeof(arr)); //set double to -5.31401e+303 *** gdb

* 数组不够开可以打滚动 * 更改代码备份。

* 判断条件的顺序，在变化前判断 * I64d I大写 lld 均小写

* 在函数中递归进入的全局变量和过程变量 * 条件中\不是\* 比较中相等的额外处理

* 一个函数中的局部变量不能在另一个函数中使用 * sort只要写cmp很好用

* bool cmp(node a,node b) {return a.eb.s);} * 语法错误当对一个不清楚是可以先看后面的，可能能把前面的订正对 * cmp中要以什么序排就在这个状态return 1 * struct Movie/*可以指定类型名也可以不指定*/ { //成员都是public的 int ID; string Name; } movie; //可以在声明struct的时候声明一个struct实例，这个有啥意思呢？* 死都不打线段树 * 一题别打太长时间

* 一题时间做太长了换题目

* for 循环 改变量i时 要都改，还要注意int i 是否在循环内使用 * c++里面也有continue，用法相同 * #define （替换成） （要替换的）

*** pow速度测试——貌似挺快的，不过精度不高

21

22 Webb.S

* math库的pow不靠谱，位数大失去精度，不用

* 求一个数的质因数，可以把2~sqrt(n)的数求出来，在除过去，得到的最后一个数即为质数

* 要使用或更改读入数据时，先进行备份 * 交程序前要把原来过程的输出//掉

* set中lower_bound指>=的而upper_bound指>的，lower可能用用方便点，iterator--就是<的了

* C++ STL iterator的常用方法有： iterator++ 移到下个元素 iterator-- 移到上个元素

*iterator 访问iterator所指元素的值

< > == != iterator之间的比较，例如判断哪个元素在前

iterator1 + iterator2 iterator之间的加法运算，类似于指针加法 * 递归处理数据较复杂，可以先存到数组里。 * 改完检查遍再调试。 *** 快速幂

* 看清题目规模，尤其是10^5与5*10^4这类区别 * string数组是动态内存

* 注意用int 与long long的使用 * 测时间： 创建enter文件， 再创建.bat文件，打入 time

* max()函数在算法(algorithm)库中 * #include <>里面不能有空格 *** 找树的直径(>1的)

* 由整数获得的实数要用(float)强制类型转换

* 用float可能可以解决double带来的一些精度的问题

*** 一个数组赋值给另一个数组——memcpy 与for 语句一样快 * 注意是<还是<=

* 无论是函数还是过程，后面要加()，如swap(); * 特别考虑数据中0、1的情况 * NOIP搜索题倒着搜分数高

* for(int j = 1; j <=n; i ++) *** 位运算

* 二分注意边界

* NOIP动规都是不带优化的，便怀疑是贪心。

* while (scanf(\判断是否文件结尾 * 不用abs与fabs，还是自己写个函数吧。 * 字符串回车神马的用P吧。 * 加油！！

22

本文来源：https://www.bwwdw.com/article/44m3.html