当前位置：文档之家 › noip算法总结

noip算法总结

  • 格式：doc
  • 大小：39.34 KB
  • 文档页数：11

.

. 算法总结

一、 动态规划和递推

dp一般的解题步骤：

分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化

由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧

Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解

关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。

二、 图论及网络流

最小生成树：克鲁斯卡尔算法和普利姆算法，

——重要性质1：最小生成树上任意两点的路径的最大边最小

——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题 生成树计数）

最短路：spfa算法、堆+迪杰斯特拉算法

Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环

——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数>n-1则存在负权环

堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能做，复杂度是O((n+m)logn)的

拓扑排序：可以将有向图转化为一个线性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环

——一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列

——再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可

强连通分量、缩点：tarjan算法

核心是每个点记一个时间戳ti[i], 另外low[i]表示i点能延伸出的搜索树中节点的ti[i]的最小值，还要维护个栈记当前路径上的点，low[i]初始化为ti[i]，如果搜完i了，ti[i]=low[i]则当前栈顶到i的所有点会在一个强连同分量内。

关键代码： procedure dfs(i:longint); .

. var j,k:longint; begin inc(time);ti[i]:=time;v[i]:=true;low[i]:=time; inc(ed);q[ed]:=i;j:=h[i]; while j<>0 do begin k:=point[j]; if ti[k]=0 then begin dfs(k);if low[k]

欧拉路：

含义：不重复地经过每条边的一条路径，如果起点和终点相同则叫“欧拉回路”，起点和终点不同叫“欧拉路径”

存在欧拉路径的条件：至多两个点的度为基数（回路则要求全都为偶数）

实现：（非常简单）

一顿乱dfs就可以了，每次退栈的再将这条边加入答案序列 procedure dfs(i:longint);

var j,k:longint;

begin

j:=h[i];

while j<>0 do begin

k:=point[j];

if w[(j+1)>>1]>0 then begin

dec(w[(j+1)>>1]); dfs(k);

inc(ans[0]); ans[ans[0]]:=dir[j];

end;

j:=next[j];

end;

end;

上面的代码中正边和反边的编号是相邻的，关注inc(ans[0])的位置，是在递归调用的后面

哈密尔顿回路

含义：经过所有点的一个回路

这是个NPC问题，只有近似算法（暴搜就不提了）

比较好用的是模拟退火，以环上相邻两点有边相连的个数作为估价值，随机化调整

二分图匹配：

最大匹配：匈牙利算法，理论O(nm)，实际复杂度好很多

最佳匹配：KM算法，理论O(n^2m)，实际复杂度同匈牙利一样相当不错

——重要性质：最小可行定标和 = 最优匹配

KM算法中构造了一个非常不错的不等式lx[i] + ly[j] >= w[i,j]，有的题目可以利.

. 用这个不等式套KM求出最小可行定标和，如20101112 ti糟糕的传染

网络流

非常神奇的一个东西，数学味有余而图论味不足，通常用来解决限制条件太强，以至于无论如何都表示不了状态的题，很多经典例题见《网络流24题》

通常使用的最大流算法是dinic，代码要背熟，一般能10分钟之内敲出来

最大流最小割定理

经典模型：最小割模型，最大权闭合图，平面图网络流转最小割

——参考神文胡伯涛论文

费用流

相当于网络流的一个强化，能多处理一维信息。具体来讲就是给边多加一个“费用”，每次增广的费用就是这条增广路的费用之和*流量。

费用流有最小费用最大流和最大费用最大流，用spfa每次找条最短（长）路增广即可

最小费用最大流还可以用zkw算法加速，差不多比裸spfa+增广快10倍的样子（在二分图网络流上尤为明显），我和盾盾研究了一种更nb的费用流，我命名为“距离标号连续增广路费用流算法”，能够秒杀几千个点的稠密随机图，二分图就更不在话下了，速度几乎达到了dinic的三分之一的样子，而且实现非常简单！

经典例题参考《网络流24题》

三、 贪心

贪心的关键是找结论，同时给出证明，然后就可以利用这个结论来做题了

当然，考场上对你猜出的结论给出证明通常是很难的，所以用贪心法解题需要丰富的经验，正确的“题感”，胆大心细才能搞出来

由于经常要取最优值，所以常常与堆、平衡树等数据结构结合起来

贪心+其他算法：

由于贪心往往能大幅化简状态，利用问题的某些“单调性”，加上贪心的思想，往往能是问题大幅简化，从而结合其他算法解决问题

经典例题：田忌赛马，利用贪心来确定状态

四、 分治

分而治之的思想在信息学竞赛中是非常重要的，下面主要介绍一下分治的经典应用

二分查找

思想很简单，功能很强大，边界要注意，负数要特判（NOI2010 PIANO）

在非负数范围内的二分一般写法

如果是l := mid - 1或+ 1则mid := (l + r) div 2

而如果是r := mid - 1 或 +1则 mid := (l + r + 1) div 2

快速幂

a^b = (a^(b div 2))^2 + ord(odd(b))*a

取模也适用 .

. ——扩展：求(1 + a + a^2 + a^3 + … + a^n) mod p的值

O(logn)算法：分治

1 + a + a^2 + a^3 + … + a^n

= (1 + a + a^2 + a^3 + … + a^(n div 2))*a^(n div 2) + ord(odd(n))*a^n

两个快速幂可以合到一起写

快速排序，归并排序

任何一本算法书上都会讲的，这里就略过了，值得一提的是快排记得加上随机化

k := a[random(r - l + 1) + l]

二分答案（0-1分数规划）

当答案满足在解集空间中连续分布时可以使用二分答案，将最优性问题转化为判定性问题，通常标志：最大值最小等

差分约束系统中有时也需要二分答案以解决最优性问题，顺便能多得到一个信息

二分答案还有一个优势，那就是已经知道了答案，那就可能可以将一些直接做必须在线的操作转化为离线操作（也就是说，我可以排序然后判定），诸如要求你判定“第一句出现矛盾的话”之类的题目（poj 3657）

0-1分数规划也是经典的利用二分答案来做的一类问题

通常是要求你最小化 f(x)/g(x)

令ans = f(x)/g(x)

则f(x) - g(x)*ans = 0

重构权，将f(i) - g(i)*ans作为新权值，用相应算法求出一个“最小值”，判断是否>=0，接着二分即可

详细说明及数学证明见集训队07胡伯涛论文

树的分治

一般用来解决树上的路径或统计类问题，每次只考虑跟树根有关的信息，然后递归分治处理

树的分治通常有基于点或基于边的分治，基于点的难合，基于边的复杂度太高

这里只介绍基于点的分治

步骤：

处理跟当前树根有关的信息

重新计算子树大小

在子树中选择重心为根，递归到相应子树处理

因为每次选了重心，所以递归总共logn层，每层O(n)的复杂度，总复杂度就是O(nlogn)

更详细严谨的介绍见漆子超论文

二分搜索

直接搜的复杂度是指数级的的话，一般是40左右的数据量，hash一半，搜一半，搜后面的时候利用之前的hash信息合并出原问题的解

而直接搜的复杂度达到阶乘级的话n一般就不超过20了，做法一般差不多

经典例题：POI02szy，NOI2001方程的解数

五、 搜索

合集下载

noip复习资料

noip复习资料

NOIP2002

复习资料

作者：徐沛来

2002．11．23

NOIP2002复习资料 作者 徐沛来

第一章 Pascal函数与技巧

一、常用函数与过程：

* abs(x):y

取x的绝对值，x与y可为整型或实型。

* append(f:text)

用赋给f的文件名打开存在的外部文件。如果不存在给定的文件，产生错误。如果

f已经存在，就先关闭再重新打开它。当前文件指针指向文件尾。

* frac(x):y

取x的小数部分，x与y均为实型。

* int(x):y

取x的整数部分，x与y均为实型，常写成trunc(int(x)).

* random(x):y

在0-x之间的整数中随机找一个整数，x与y均为整型。

* sin(x):y; cos(x):y; arctan(x):y; exp(x):y; ln(x):y

均与数学运算一致,三角函数返回的均为弧度,转换成角度即乘以Pi除以180.

* copy(str,n1,n2):substr

从字符串str中取从第n1个字符开始长度为n2个字符的子串substr.n1和n2是整型

表达式，如果n1大于s的长度，则返回空字符串。如果指定的n2大于第n1个字符后剩下

的字符数，则返回剩下的字符串。

* pos(substr,str):num

查找substr是否为str的子串，若是则返回substr在str中的起始位置，若否则返回

0.

* val(str,int,code)

将字串str转为数值型数据存入int, 如果字符串无效，其中非法字符的下标放在Code

中；否则，code为零。

* str(num,str)

将num表达式转成字符串str。

* delete( str,n1,n2)

从原字符串str中删去一个从n1开始长度为n2的子串，如果Index比s长，不删除

任何字符。如果指定的Count大于从第1ndex大到结尾的字符数，删除剩余部分。

NOIP信息学竞赛初赛-图论算法基础-专题十一-1

NOIP信息学竞赛初赛-图论算法基础-专题十一-1

NOIP信息学竞赛初赛专项练习题

1 / 5 专题十一：图论算法基础 对于图论算法，NOIP初赛不要求会实现算法，但手工操作还是要会的，复赛是要求会代码实现的。 什么是图 一个图是一个序偶 ,记为 G = 。 V 为顶点集, E 为 V 中结点之间的边的集合。 自环：一条边的两个端点是相同的。 重边：两个端点之间有两条以上的边，称他们是重边。 简单图：没有自环和重边的图。 无向边：边是双向的。 有向边：单向边，有箭头。 无向图：只有无向边的图。 有向图：只有有向边的图。 混合图：既有无向边又有有向边。 顶点的度：无向图中，一个顶点相连的边数称为该顶点的度；有向图中，从一个顶点出发的边数称为该顶点得出度；到达该顶点的边数称为它的入度。

图论基本定理：著名的握手定理。无向图中结点度数的总和等于边数的两倍。有向图中结点入度的和等于出度的和等于边数。 通路：给定图G中结点和边交替出现的一个序列：v0 e1 v1 e2 v2 … ek vk，若每条边ei的两端点是vi-1 和vi ，那么称该序列是从v0到vk的一条通路。 基本通路(路径)：没有重复出现的结点的通路。 图的连通性：若一张无向图的任意两个结点之间都存在通路，那么称该图是连通的。 连通分量：图中连通的顶点与边的集合。 权和网：在图的边给出相关的数，成为权。权可以表示一个顶点到另一个顶点的距离，耗费等。带权图一般成为网。 NOIP信息学竞赛初赛专项练习题

2

/

5

最短路径：对于一张不带权的无向图来说，从s到t的最短路径就是所有从s到t的通路中长度最短的那一条(可能不唯一)，通路上的边数称为路径的长度。 完全图：任何两个顶点之间都有边（弧）相连称为完全图。 稀疏图、稠密图：边（弧）很少的图称为稀疏图，反之为稠密图。

图的存储：邻接矩阵 在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）∈E(G)或〈i,j〉∈E(G),则矩阵中第i行 第j列元素值为1，否则为0 。 例如, 下面为两个无向图和有向图对应的邻接矩阵。

NOIP2009普及组复赛解题报告

NOIP2009普及组复赛解题报告

NOIP2009普及组复赛解题报告

NFLS QMD

第一题 多项式输出

1、摘要

时间复杂度:O(n)

空间复杂度:O(n)

2、题目大意

输入一个n次多项式各项的系数，按要求输出多项式

3、算法分析

先将不为0的系数和对应的次数存入a数组和b数组，然后依次输出。要注意以下几点：

①系数绝对值为1的情况

②指数为1或0的情况

③首项加号不必输出

4、参考程序

program poly;

var

n,i,g,xx:integer;

a,b:array[0..200]of integer;

function x(n:integer):string; //处理项的x^n部分

var

st1:string;

begin

if n=0 then x:='';

if n=1 then x:='x';

if n>1 then begin

str(n,st1);

x:='x^'+st1;

end;

end;

procedure flag(t:integer); //处理每项的符号

begin

if t>0 then write('+')

else write('-');

end;

begin

assign(input,'poly.in');reset(input);

assign(output,'poly.out');rewrite(output);

readln(n);

g:=0;

for i:=n downto 0 do //保存系数非零的项

begin

read(xx);

if xx<>0 then

begin

g:=g+1;

a[g]:=xx;

b[g]:=i;

end;

end;

for i:=1 to g do

begin

if i=1 then //处理首项的情况

2023noip题目

2023noip题目

2023NOIP考题解析

题目一：数据结构与算法

本题主要考察的是对数据结构和算法的理解与运用。给定一组数字序列，请设计一个算法，找出该序列中第k小的数字。

输入

输入包括两行。第一行为一个整数n，表示数字序列的长度。第二行为n个以空格分隔的整数，表示数字序列。

输出

输出一个整数，表示数字序列中第k小的数字。

样例输入

8

9 2 4 7 1 5 3 8

样例输出

3

题解思路

为了找出第k小的数字，我们可以使用堆排序的算法。首先，将输入的数字序列构建成一个小顶堆。然后，依次将堆顶元素取出，并将其与堆尾元素进行交换，再对堆进行调整，直到取出k个数字为止。

具体实现步骤如下：

1. 将输入序列构建成一个小顶堆。可以使用数组或者二叉堆来实现堆结构。

2. 依次取出堆顶元素，并将其与堆尾元素进行交换。

3. 对堆进行调整，以满足堆的性质。

4. 重复步骤2和3，直到取出k个数字为止。

5. 返回堆尾元素，即为第k小的数字。

时间复杂度分析

构建小顶堆的时间复杂度为O(nlogn)，其中n为数字序列的长度。每次调整堆的时间复杂度为O(logn)。因此，该算法的时间复杂度为O(n+klogn)。 题目二：动态规划

本题主要考察的是动态规划的思想和应用。给定一个包含n个正整数的序列，要求选取一个长度至少为2的子序列，使得该子序列中元素之和最大。

输入

输入包括两行。第一行为一个整数n，表示序列的长度。第二行为n个以空格分隔的正整数，表示序列。

输出

输出一个整数，表示选取的子序列中元素之和的最大值。

样例输入

6

-2 1 -3 4 -1 2 1 -5 4

样例输出

6

题解思路

该题可以使用动态规划的思想来解决。定义一个数组dp，dp[i]表示以第i个元素结尾的子序列中元素之和的最大值。则 dp[i] = max(dp[i-1]+nums[i], nums[i])。

具体实现步骤如下：

1. 初始化一个长度为n的数组dp，初始值均为0。