NOI国家集训队论文分类(至2008)(摘抄自C博客)讲解

问题三——分析（4）


维护一个表Hlst，表头指针p，表尾指针q。 在递推到第i阶段，bot…top：Si中第bot到第top个元素 （即：lst[bot],lst[bot+1],…,lst[top])都与h联系。 Hlst[k].bot=Hlst[k-1].top+1。
p
H l s t
q
top bot Hlist[k ] h value

问题一——算法分析
for i:=n downto 1 do g(i,1):=f(i,n); ｛边界条件｝ for k:=2 to m do 计算边界g(n-k+1,k); j:=n-k+1; for i:=n-k downto m-k+1 do if f(I,j)<=g(j+1,k-1) then g(i,k):=g(j+1,k-1)｛性质一｝ else if f(i,i)>=g(i+1,k-1) then 【 g(i,k):=f(i,i); j:=i 】 else 【while f(i,j-1)>=g(j,k-1) do j:=j-1; {定si,k} g(i,k):=min{f(i,j),g(j,k-1)} {性质三} if g(i,k)=g(j,k-1) then j:=j-1】 end_for_k 外层每循环一次，j递减的工作量是O(n)。因此总的复杂度O(n２)。

pk q
F (i ) li min Hlst [k ].value
value值不断更新，在求F(n),F(n-1),…,F(0)
时都要察看最小的value。 堆!
问题三——算法分析

年的NOI中都出现了与概率有关 在05,06,08年的 , , 年的 中都出现了与概率有关 的试题
2 22
全文总览
样本空间 连续型随机变量 随机变量 离散型随机变量
SPOJ RNG SGU Random Shooting SRM 349 LastMarble UVA Randomness
3 22
要用到的定义
1 fi ( [x-Ri, j-Ri+1]x ) = ∫x R i R f i 1 ( t )dt [j-Ri+1,j] [j,x] i
x
P
P
f i1 (t )
f i (x)
19 22
j-Ri j-Ri+1
j j+1
t
j
j+1
x
本题总结
在解决本题的过程中,我们遇到了这样的困难: 在解决本题的过程中,我们遇到了这样的困难: N个随机变量代表着 维空间,较为抽象 个随机变量代表着N维空间 个随机变量代表着 维空间, 两个解法都从N较小的情况开始分析 较小的情况开始分析, 两个解法都从 较小的情况开始分析,发现规律
23 22
用归纳法, 用归纳法,当N=1时,V((0,+∞),x) = x显然 时 显然 符合结论. 符合结论. 设当N=2,3,…,k-1时都有结论成立,那么 时都有结论成立, 设当 时都有结论成立 N=k时,V([0,+∞), [0,+∞),…, [0,+∞),x)就是 时 就是 一个k维锥体的 维体积, 维锥体的k维体积 一个 维锥体的 维体积,椎体的底面面积 是 ( kx 1)! 同时我们知道体积就是截面面积的积分值, 同时我们知道体积就是截面面积的积分值, 而对与锥体的顶点距离为h的截面而言 的截面而言, 而对与锥体的顶点距离为 的截面而言,其 截面面积 (kx 1)! ( h ) 为,所以 所以 x x h 1 x x ( ) dh= ( 0) = V([0,+∞), [0,+∞),…, [0,+∞),x) = ∫ (k 1)! x (k 1)! k k! ■

Gn = {1 ,2 , …, n}的全部非空子集排成一个
序列 P1 , P2 , …, P2 n - 1 ,使得对任意的 i ∈{1 ,
2 , …,2 n - 2} ,总有
| Pi ∩Pi + 1 | = 1 ,且 P1 = {1} , P2 n - 1 = Gn .
当 n = 3 时 ,序列{1} ,{1 ,2} ,{2} ,{2 ,3} ,
+
(6 k 2
+4i
+ 1)
=4k
+2i
+1
为蓝色 ,取 an + 1 = 6 k + 4 i + 1 即可.
至此引理 3 证完.
综上三个引理便知结论成立.
2008 年第 7 期
第二天
四 、首先 ,当 n ≥3 时 ,对 n 用数学归纳
法证明下述命题 :
对任意的正整数 n ( n ≥3) ,可以将集合
P′2 k - 4 ∪{ k + 1} , P′2 k - 5 , …, P′3 ,
P′2 ∪{ k + 1} ,{ k + 1} , P′1 ∪{ k + 1} , P′2 ,
P′3 ∪{ k + 1 } , P′4 , …, P′2 k - 2 , ′ P2 k - 1 ∪
{ k + 1}.
q ≥2 p - 1.
三 、引理 1 若正整数集 N+ 中存在一个
无穷的等差数列 ,则结论成立.
事实上 ,设无穷序列 c1 < c2 < …< cn <
…是 一 个 N+ 中 的 红 色 的 等 差 数 列. 则 取
ai = c2 i - 1 ( i ∈N+ ) ,便得到一个满足要求的

浅谈图论模型的建立与应用广东省中山市第一中学黄源河【关键字】图论模型、建立、转化【摘要】在近几年的信息学竞赛中，图论题目层出不穷。

图论作为一个新生的数学分支，相比其他数学分支来说，具有许多自有的特性。

利用图论解题，通常具有高效、简洁的便利。

有了这门工具，并不意味就能很好地解决问题，还在于我们能否熟练地识别与建立一系列的图论模型。

本文通过一些实例，简单地介绍一下图论建模的方法。

【正文】引言应用数学知识解题时，首先要通过对实际问题的分析，研究组建用以描述这个问题的数学模型。

使用数学的理论和方法对模型进行分析从而得到结果，再返回去解决现实的实际问题。

图论模型是一类特殊的数学模型，建立图论模型，就是要从问题的原型中，抽取对我们有用的信息和要素，把问题抽象为点、边、权的关系。

经过图论建模之后，杂乱无章的信息变得有规可寻，要素的内在联系体现在了点、边、权的关系。

有不少经典的图论模型可以直接用特定的算法解决，一些复杂的问题，只要能认清问题的本质，把握问题的关键，建立合适的图论模型，往往能转化为我们熟悉的经典问题。

本文要写的，正是我在图论建模方面的一点心得与认识。

例题分析〖例题1〗Place the Robots (ZOJ)[问题大意]有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。

机器人只能放在空地上。

在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。

问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。

[分析]在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。

因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到下面的这个图：那么，问题转化为求图的最大独立集问题。

众所周知，这是NP-完全问题。

看来，建立这样的模型，没有给问题的求解带来任何便利，我们必须建立一个行之有效的新模型。

二分法与统计问题淮阴中学李睿[关键字]线段树二叉树二分法[摘要]我们经常遇到统计的问题。

这些问题的特点是，问题表现得比较简单，一般是对一定范围内的数据进行处理，用基本的方法就可以实现，但是实际处理的规模却比较大，粗劣的算法只能导致低效。

为了解决这种困难，在统计中需要借助一些特殊的工具，如比较有效的数据结构来帮助解决。

本文主要介绍的是分治的思想结合一定的数据结构，使得统计的过程存在一定的模式，以到达提高效率的目的。

首先简要介绍线段树的基础，它是一种很适合计算几何的数据结构，同时也可以扩充到其他方面。

然后将介绍IOI2001中涉及的一种特殊的统计方法。

接着将会介绍一种与线段树有所不同的构造模式，它的形式是二叉排序树，将会发现这种方法是十分灵活的，进一步，我们将略去对它的构造，在有序表中进行虚实现。

目录一线段树1.1 线段树的构造思想1.2 线段树处理数据的基本方法1.3 应用的优势1.4 转化为对点的操作二一种解决动态统计的静态方法2.1 问题的提出2.2 数据结构的构造和设想2.3 此种数据结构的维护2.4 应用的分析三在二叉排序树上实现统计3.1 构造可用于统计的静态二叉排序树3.2 进行统计的方法分析3.3 一个较复杂的例子四虚二叉树4.1 虚二叉树实现的形态4.2 一个具体的例子4.3 最长单调序列的动态规划优化问题[正文]一 线段树在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX 轴上的线段。

由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。

一个线段是对应于一个区间的，因此线段树也可以叫做区间树。

1.1线段树的构造思想线段树处理的是一定的固定线段，或者说这些线段是可以对应于有限个固定端点的。

处理问题的时候，首先抽象出区间的端点，例如说N 个端点ti(1≤i ≤N)。

那么对于任何一个要处理的线段（区间）[a,b]来说，总可以找到相应的i,j ，使得ti=a,tj=b,1≤i ≤j ≤N 。

线段树的应用广西柳铁一中林涛【摘要】在竞赛解题中，常遇到与区间有关的操作，比如统计若干矩形并的面积，记录一个区间的最值、总量，并在区间的插入、删除和修改中维护这些最值、总量。

线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍线段树的各种操作以及一些推广。

本文通过3个例子：《蛇》、《空心长方体》、《战场统计系统》，讲述线段树中基本的插入、删除、查找操作，和不规则的修改和删除操作，以及到二维的推广。

关键字：线段树二分子树收缩叶子释放面积树【正文】1. 线段树的定义及特征定义1：线段树一棵二叉树，记为T (a,b)，参数a,b表示该节点表示区间[a,b]。

区间的长度b-a记为L。

递归定义T[a,b]：若L>1 ：[a, (a+b) div 2]为T的左儿子[(a+b) div 2,b]为T的右儿子。

若L=1 ：T为一个叶子节点。

表示区间[1, 10]的线段树表示如下：(以下取对数后均向上取整)定理1：线段树把区间上的任意一条线段都分成不超过2log L条线段证明：(1)在区间(a，b)中，对于线段(c，d)，如果(c<=a) 或(d>=b)，那么线段在(a，b)中被分为不超过log(b-a)。

用归纳法证明，如果是单位区间，最多被分为一段，成立。

如果区间(a，b)的左儿子与右儿子成立，那么如果当c<=a时，1．若d<=(a+b)div2那么相当与其左儿子分该线段，所分该线段数树不超过log((a+b)div 2-a)，即不超过log(b-a),成立。

2．若d>(a+b) div 2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过1+log(b-(a+b) div 2),也不超过log(b-a)，成立。

对于d>=b的情况证明类似，不再赘述。

(2)在区间(a,b)中，对于任意线段也用归纳法证明。

对于单位区间，最多分为一段，成立。

2015/11/25
北京12中庄燕文
【题目类型】双线程动态规划 【建议编程时间】40分钟。这里的编程时间包括调试时间。 【空间复杂度】约27M，全局变量完全可承受。50*50*50*50*sizeof(int)=2.5*10^7. 【解题分析】 1、 读入矩阵，注意行列。 2、 采用一个四维数组记录当前两条路走到的位置(i1,j1,i2,j2)时取得的最大值，初始化为 0，表示不可能到达。(0,0,0,0)为1，最后减1输出。 3、 一个四重循环枚举两条路分别走到的位置。由于每个点均从上或左继承而来，故内部 有四个if，分别表示两个点从上上、上左、左上、左左继承来时，加上当前两个点所取得 的最大值。例如，f[i][j][k][l] = max{f[i][j][k][l], f[i-1][j][k-1][l] + a[i][j] + a[k][l]}，表示两点均从 上面位置走来。 4、 输出右下角处的最大值f[m][n][m][n]，注意换行。 【编程注意】 1、 在数组边界处特殊处理，避免数组越界。 2、 若待继承的点最大值为零，则停止判断，不能从这里走来。 3、 显然，非矩阵右下角的汇合点，两个位置不能重合（否则路径相交），若重合则最大 值为0，不可达。
2015/11/25
北京12中庄燕文
这道题的错误做法很多,错误做法却能得满分的也很多, 这里就不多说了.直接切入正题,就是即将介绍的这个基 于二分图的算法. 注意到并没有说基于二分 图匹配,因为这个算法和二分图匹配无关.这个算法只是 用到了给一个图着色成二分图. 第一步需要解决的问题是,判断是否有解. 考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同 一个栈中的充要条件是什么(注意没有必要使它们同时 存在于同一个栈中,只是压入了同一个栈).实际上,这个 条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].

[Key Words]
Network Flow, Maximum Flow, Minimum Cut, Maximum Weight Closure of a Graph, Finding
a Maximum Density Sub Graph, Minimum Weight Vertex Covering Set and Maximum Weight
第 2 页 共 45 页
[][Library]Thesis
最小割模型在信息学竞赛中的应用
Amber
3.1. 引入 Introduction...........................................................................................................16 3.2. 构造 Construction of Algorithm ....................................................................................17 3.3. 证明 Proof......................................................................................................................17 3.4. 应用 Application............................................................................................................19
knowledge of minimum cut model. The thesis sets focus on researching that is in four aspects: 1. the application based on the

模板类的使用carrayint100carraydouble20carraycarrayint1010stl就是建立在模板函数和模板类基础之上的功能强大的库模板函数可以实现一般化的常用算法如统计排序查找等模板类可以实现支持几乎所有类型的容器用来实现常用的数据结构如链表栈队列平衡二叉树等stl头文件一览头文件内容头文件内容iterator迭代器vector向量utility辅助功能deque双头队列memory内存管理list链表algorithm算法set集合与多重集合functional函数对象map映射与多重映射numeric数值运算stackqueue队列与优先队列32迭代器迭代器的定义和种类迭代器iterator实际上是一种一般化的指针类型是对指针类型的抽象
类型 双目 双目 双目 双目 双目 双目 双目 双目 单目 双目 双目 双目 双目 双目 单目
作用 arg1 == arg2 arg1 != arg2 arg1 > arg2 arg1 < arg2 arg1 >= arg2 arg1 <= arg2 arg1 && arg2 arg1 || arg2 !arg arg1 + arg2 arg1 - arg2 arg1 * arg2 arg1 / arg2 arg1 % arg2 -arg
更多关于迭代器的信息
指针类型就是一种特殊的随机迭代器类型. 对于一般的迭代器,这些功能都是通过操 作符重载来实现的.
更多关于迭代器的信息
各种迭代器类型之间的关系:
输出迭代器 前向迭代器 输入迭代器 双向迭代器 随机迭代器
迭代器的作用
访问元素 算法与容器之间的纽带
模板类pair
template<class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() : first(T1()), second(T2()) { } pair(const T1& x, const T2& y) : first(x), second(y) { } template<class U, class V> pair(const pair<U, V>& p) : first(p.first), second(p.second) { } };

一维序列求和
设序列的元素存储在a[]中,a的下标是 1..n的正整数,需要动态地更新某个a[x] 的值,同时要求出a[x1]到a[y1]这一段所 有元素的和.
对于序列a[1..n],我们设一个数组 C[1..n],C[i]=a[i-2k+1]+…+a[i],其中k为 , i在二进制下末尾0的个数 1001010110010000 k =4 计算C[x]对应的2k LOWBIT(x) 2k =x and (x xor (x-1))
插入一个点x 插入一个点x
procedure INSERT(x) begin now ← 1 repeat SUM[now]←SUM[now]+1 if (V[now]=x) break if (V[now]>x) now←now*2 else now←now*2+1 until false End 其中SUM是记录一棵子树上结点总数 其中 是记录一棵子树上结点总数 删除 的方法是类似的
O(n2)
对P进行特殊的限制,即,在所有等价的决策j 中,P选择a[j]最大的那一个 在处理完a[1..x-1]之后,对于所有长度为M[x]-1 的下降序列,P[x]的决策只跟其中末尾最大的 一个有关. 用另外一个动态变化的数组b,当我们计算完了 a[x]之后,a[1..x]中得到的所有下降序列按照长 度分为L类,每一类中只需要一个作为代表, 这个代表在这个等价类中末尾的数最大,我们 把它记为b[j],1≤j≤L. 处理当前的一个数a[x],我们无需和前面的a[j] (1≤j≤x-1)作比较,只需要和b[j](1≤j≤L)进行 比较.
线段树线段树-一个特殊性质举例
要得到线段树上线段并集的长度,增加 一个数据域 M[v],讨论: C[v]>0,M[v] = E[v]-B[v]; C[v]=0 且v是叶子结点,M[v]=0; C[v]=0 且v是内部结点, M[v]=M[LSON[v]]+M[RSON[v]];

信息学中的守恒法【摘要】本文提出和总结了“守恒法”，以及它在信息学竞赛中的一些应用。

守恒的本质是寻找变化中的不变量。

守恒法能帮助我们跳过、避开纷繁复杂的细节，直接看透问题的本质。

【关键字】守恒法不变量【正文】一、引言现实生活和实际问题是纷繁复杂的。

问题1两个质量相等的小球，速度分别为5m/s, 4m/s，他们相向运动，完全弹性碰撞之后速度分别变成多少？问题210g C和10g O2在密闭容器中反应一个小时。

最后的总质量是多少？问题1我们大概耳熟能详：动量守恒、动能守恒，两个方程就能解出速度。

实际上小球碰撞的过程是复杂的，究竟两对力如何互相作用、互相影响、如何做功，思考起来是非常的复杂。

如果忽略它们变化的具体过程，我们很容易发现“动量”和“动能”这两个变化中的不变量，抓住不变量，就能跳过繁琐的细节，直达目标。

问题2也是类似的题目。

C和O2的反应同样是复杂的。

在不同的局部，条件不同，可能产生CO，也可能产生CO2；CO2和C还可能重新转化为CO……事实上不可能有人列出三个化学方程去分析——在一个密闭容器中，无论怎么变，总质量必然不变——也就是质量守恒。

抓住这一点，我们在1秒钟内就能说出答案：20g。

以上两个例子生动的说明守恒的作用。

现实生活和实际问题如此纷繁复杂，条件和变化如此之多，以至于我们考虑稍不周密就可能全盘皆错；抑或限于问题本身的复杂性，根本无法分析。

但是如果能找到一两个守恒量——也就是变化中的不变量，那么问题就能大大的简化了。

忽略细节，抓住主要矛盾，这就是守恒法。

二、一个简单的例子例题1有一个数列a1, a2, a3, ……, a n。

每次可以从中任意选3个相邻的数a i-1, a i, a i+1，进行如下操作（此操作称为“对a i进行操作”）(a i-1, a i, a i+1)à(a i-1+a i, -a i, a i+a i+1)给定初始和目标序列。

问：能不能通过以上操作，将初始序列转换到目标序列。

第 1 页 共 11 页
IOI2004 国家集训队论文 许智磊
基本概念
首先明确一些必要的定义： 字符集 一个字符 集Σ是 一个建立了 全序关系的集合，也就是说 ，Σ 中 的任意两个不同的元素 α 和 β 都可以比较大小，要么 α<β，要么 β<α（也就是 α>β） 。字符集Σ中的元素称为字符。 字符串 一个字符串 S 是将 n 个字符顺次排列形成的数组，n 称为 S 的 长度，表示为 len(S)。S 的第 i 个字符表示为 S[i]。 子串 字符串 S 的子串 S[i..j]，i≤j，表示 S 串中从 i 到 j 这一段，也就 是顺次排列 S[i],S[i+1],...,S[j]形成的字符串。 后缀 后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。 字符串 S 的从 i 开头的后缀表示为 Suffix(S,i)，也就是 Suffix(S,i)=S[i..len(S)]。 关于字符串的 大小比较，是 指通常所说 的“字 典顺序 ”比较 ，也就是对 于 两个字符串 u、v，令 i 从 1 开始顺次比较 u[i]和 v[i]，如果 u[i]=v[i]则令 i 加 1， 否则若 u[i]<v[i]则认为 u<v，u[i]>v[i]则认为 u>v（也就是 v<u） ，比较结束。如 果 i>len(u) 或 者 i>len(v) 仍 比较 出 结 果 ， 那么若 len(u)<len(v) 则 认为 u<v ， 若 len(u)=len(v)则认为 u=v，若 len(u)>len(v)则 u>v。 从字符串的大小比较的定义来看，S 的两个开头位置不同的后缀 u 和 v 进行 比较的结果不可能是相等，因为 u=v 的必要条件 len(u)=len(v)在这里不可能满 足。 下面我们约定一个字符集Σ和一个字符串 S，设 len(S)=n，且 S[n]='$'，也 就是说 S 以一个特殊字符'$'结尾，并且'$'小于Σ中的任何一个字符。除了 S[n] 之外，S 中的其他字符都属于Σ。对于约定的字符串 S，从位置 i 开头的后缀直 接写成 Suffix(i)，省去参数 S。 后 缀 数 组 后 缀 数 组 SA 是 一 个 一 维 数 组 ， 它 保 存 1..n 的 某 个 排 列 SA[1],SA[2],...SA[n] ，并 且 保证 Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。 也就是 将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入 SA 中。 名次数组 名次数组 Rank=SA-1，也就是说若 SA[i]=j，则 Rank[j]=i，不难 看出 Rank[i]保存的是 Suffix(i)在所有后缀中从小到大排列的“名次” 。

浅谈基于分层思想的网络流算法上海市延安中学王欣上[关键字]层次图网络流基本算法应用MPLA Dinic MPM[摘要]本文详细地介绍了基于层次图概念的三种算法，并通过例题来说明Dinic算法在信息学竞赛中的优越性。

一、引言 (3)二、预备概念 (3)2.1剩余图的概念 (3)2.2顶点的层次 (4)2.3层次图的概念 (4)2.4阻塞流的概念 (5)三、最短路径增值算法(MPLA)的步骤及复杂度分析 (5)3.1算法步骤 (5)3.2定理的证明 (6)3.3复杂度分析 (8)四、Dinic算法的步骤以及复杂度分析 (9)4.1算法步骤 (9)4.2复杂度分析 (13)五、Dinic算法在信息学竞赛中的应用 (15)例题1 最大获利(profit) (15)例题2 矩阵游戏 (18)六、MPM的算法步骤以及复杂度分析 (19)6.1算法步骤 (19)6.2复杂度分析 (20)七、总结 (21)一、 引言图论这门古老而又年轻的学科①在信息学竞赛中占据了相当大的比重。

其中，网络流算法经常在题目中出现。

网络流涵盖的知识非常丰富，从基本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。

随着信息学竞赛的不断发展，其题目的难度以及考察范围都不断增大。

现在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并不足以解决问题。

本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的3个网络流算法，并通过列举和比较说明了其在解题中的应用，而对一些基础的知识，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料中找到。

二、预备概念②2.1剩余图的概念给定一个流量网络),(111V E G =、源点s 、汇点t 、容量函数c ，以及其上的流量函数f 。

我们这样定义对应的剩余图),(222V E G =：剩余图中的点集与流量网络中的点集相同，即12V V =。

IOI2018中国国家集训队集中培训第一试时间：2017年12月4日08:10∼13:10题目名称简单数据结构福若格斯避难所题目类型传统型传统型传统型目录dsa frogs hafen可执行文件名dsa frogs hafen输入文件名dsa.in frogs.in hafen.in输出文件名dsa.out frogs.out hafen.out每个测试点时限 3.0秒 2.0秒 1.0秒内存限制1024MB512MB512MB测试点数目20203每个测试点分值5533提交源程序文件名对于C++语言dsa.cpp frogs.cpp hafen.cpp对于C语言dsa.c frogs.c hafen.c对于Pascal语言dsa.pas frogs.pas hafen.pas 编译选项对于C++语言-O2-lm-O2-lm-O2-lm对于C语言-O2-lm-O2-lm-O2-lm对于Pascal语言-O2-O2-O2简单数据结构（dsa）【题目背景】参加完IOI2018之后就是姚班面试。

而你，由于讨厌物理、并且想成为乔布斯一样的创业家，被成功踢回贵系。

转眼，时间的指针被指向2019，大二，12月初，考试周。

你早听学长说，数据结构期中考很难，对竞赛生不友好，集训队选手做不完卷子。

你冷笑。

哼，堂堂国际金，这点难度的考试算什么。

两小时，你看完习题解析前五章所有内容，并且倒背如流；一小时，你看了500页的讲义，并且记忆犹新；十分钟，你骑车到考场，自信的你只带了一把水笔，虽然考试让带资料；现在，摊开传说中神级卷子，你定神一看——【题目描述】给出一个长度为N的序列A1,A2,···,A N，如果A中的一个子序列B1,B2,···,B M，满足条件：•1≤M≤N •∀1≤i<M，B iBi+1那么称B为A的上升倍数子序列。

现在有一个长度为N的序列A被初始化为A1,A2,···,A N，以及Q次对序列A的操作。

动态规划的特点及其应用安徽张辰【关键词】动态规划阶段【摘要】动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。

文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。

第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。

第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一些更深层次的特点。

文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。

这对我们的解题实践有一定的指导意义。

【正文】动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。

最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。

因此，如何更深入地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。

要掌握动态规划的应用技巧，就要了解它的各方面的特点。

首要的，是要深入洞悉动态规划的本质。

§1动态规划的本质动态规划是在本世纪50年代初，为了解决一类多阶段决策问题而诞生的。

那么，什么样的问题被称作多阶段决策问题呢？§1.1多阶段决策问题说到多阶段决策问题，人们很容易举出下面这个例子。

[例1]多段图中的最短路径问题：在下图中找出从A1到D1的最短路径。

仔细观察这个图不难发现，它有一个特点。

我们将图中的点分为四类（图中的A、B、C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。

这样，图中的边就被分成了三类（A→B、B→C、C→D）。

我们需要从每一类中选出一条边来，组成从A1到D1的一条路径，并且这条路径是所有这样的路径中的最短者。

从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。

更精确的定义如下：多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列[1]。

例题 Geometrical dreams(Ural1046)
虽然这样的方法显然在任何方面都要比 前面提到的普通做法要复杂 对于解决这道题目没有太大的意义 但是,它提供给我们一种崭新的思路 但是,它提供给我们一种崭新的思路— —
随机化
随机化算法对于这样的题目没有优势,但 随机化算法对于这样的题目没有优势, 随机化算法对于这样的题目没有优势 它在很多问题上都能得到运用,下面, 它在很多问题上都能得到运用,下面,我 们一起来进一步领略随机化算法的魅力吧
广东省韶关市第一中学 刘家骅
引言
信息学竞赛的题目日新月异 新型算法层出不穷
随机化算法作为一种新兴算法
犹如新生的太阳在信息学竞赛的 广阔天空上焕发光芒
简单问题的另类算法
例题 Geometrical dreams(Ural1046)
有一个多边形 1A2…AN ,在每条边 有一个多边形A AiAi+1上向多边形外做一个等腰三角形 AiMiAi+1使得角 iMiAi+1=αi 使得角A 由αi组成的集合满足其任何非空子集的角 度和不是360 360度的倍数 度和不是360度的倍数 给出 给出N(3≤N≤50) ,所有 i的坐标和 i, 所有M 的坐标和α ≤ ≤ 写一个程序, 写一个程序,输出多边行的顶点的坐标
但是,为了减轻每个顶点的负担,题目设定了 但是,为了减轻每个顶点的负担, 每个顶点的最大连接边数ki 每个顶点的最大连接边数ki 还是用图1的例子,若我们为1至5每个点分别 还是用图1的例子,若我们为1 加上了k 2的限制 的限制, 加上了ki = 1, 1, 4, 2, 2的限制,则上述方案就不 能满足要求了.此时的最优方案如图2 能满足要求了.此时的最优方案如图2所示

1
IOI2009 中国国家集训队论文
长沙市雅礼中学 漆子超
【目录】
【序言】........................................................................................................................ 3 【正文】........................................................................................................................ 4 一.树的分治算法.................................................................................................... 4 基于点的分治：.............................................................................................. 4 基于边的分治：.............................................................................................. 4 效率分析：...................................................................................................... 5 【例 1】树中点对统计................................................................................... 8 算法分析................................................................................................... 8 【例 2】Free Tour 2 ...................................................................................... 10 算法分析................................................................................................. 10 【本节小结】................................................................................................ 13 二．树的路径剖分算法：................................................................................... 14 【例 3】Query On a Tree.............................................................................. 14 算法分析................................................................................................. 14 引入路径剖分......................................................................................... 14 轻重边路径剖分..................................................................................... 15 【例 4】黑白树 ........................................................................................... 17 算法分析................................................................................................. 17 【小结】........................................................................................................ 18 路径剖分与树的分治的联系：.................................................................... 19 【例 5】Query On a Tree Ⅳ ........................................................................ 20 算法分析................................................................................................. 20 【本节小结】................................................................................................ 23 三．树的分治的进一步探讨：........................................................................... 24 如何改进基于边的分治的时间复杂度........................................................ 24 使用基于边的分治解决【例 2】................................................................. 26 使用基于边的分治解决【例 5】................................................................. 27 四．全文总结....................................................................................................... 28 【参考文献】.............................................................................................................. 29 【感谢】...................................................................................................................... 29 【附录】...................................................................................................................... 29