浅析竞赛中一类数学期望问题的解决方法
福建省福州第八中学汤可因
摘要
期望在我们生活中有着十分广泛的应用，而对于我们信息学奥赛也出现了不少求解期望值的问题。本文对于竞赛中涉及求离散型随机变量的数学期望的题目所使用的常用方法归纳成为两大类，并进行了总结与分析。
关键字
期望递推动态规划方程组
目录
引言 (3)
预备知识 (3)
一、期望的数学定义 (3)
二、期望的线性性质 (3)
三、全概率公式 (4)
四、条件期望与全期望公式 (4)
一、利用递推或动态规划解决 (4)
例题一：聪聪与可可 (5)
分析 (5)
小结 (6)
例题二：Highlander (6)
分析 (6)
小结 (8)
例题三：RedIsGood (8)
分析 (8)
小结 (9)
二、建立线性方程组解决 (10)
引入 (10)
分析 (10)
需要注意的地方 (12)
例题四：First Knight (12)
分析 (12)
例题五：Mario (15)
分析 (15)
总结 (16)
参考文献 (17)
引言
数学期望亦称为期望，期望值等，在概率论和统计学中，一个离散型随机变量的期望值是试验中每次可能结果的概率乘以其结果的总和。
而期望在我们生活中有着十分广泛的应用。例如要设计一个彩票或赌博游戏，目标为赢利，那么计算能得到的钱以及需要付出的钱的期望，它们的差则需要大于0。又例如对于是否进行一项投资的决策，可以通过分析总结得出可能的结果并估算出其概率，得到一个期望值而决定是否进行。期望也许与每一个结果都不相等，但是却是我们评估一个事情好坏的一种直观的表达。
正因为期望在生活中有如此之多的应用，对于我们信息学奥赛也出现了不少求解期望值的问题。而其中大多数又均为求离散型随机变量的数学期望。本文对于这类题目所会涉及到的常用方法进行了归纳，总结与分析。
预备知识
一、期望的数学定义
如果X 是一个离散的随机变量，输出值为 x 1, x 2, ...， 和输出值相应的概率为p 1, p 2, ... （概率和为1）, 那么期望值 ∑=i
i i x p X E )(。
例如投掷一枚骰子，X 表示掷出的点数，P (X =1)，P (X =2)，…，P (X =6)均为61，那么5.36
654321616615614613612611)(=+++++=?+?+?+?+?+?=X E 。
二、期望的线性性质
对于任意随机变量X 和Y 以及常量a 和b ，有
E (aX + bY ) = aE (X ) + bE (Y )
当两个随机变量X 和Y 独立且各自都有一个已定义的期望时，有
E (XY ) = E (X )E (Y )
三、全概率公式
假设{ B n | n = 1, 2, 3, ... } 是一个概率空间的有限或者可数无限的分割，且每个集合B n 是一个可测集合，则对任意事件A 有全概率公式：
∑=n
n n B P B A P A P )()|()(
其中P (A | B )是B 发生后A 的条件概率
四、条件期望与全期望公式
)21()( ，，，，====j i y Y x X P p j i ij
当X =x i 时，随机变量Y 的条件数学期望以E (Y | X =x i )表示。
全期望公式：
)
()|()())|((Y E p y p p y p p p y p x X Y E x X P X Y E E i k
ik k i k
i ik k i i k
i ik
k i i i i =======
∑∑∑∑∑∑∑
所以∑====i i i x X Y E x X P X Y E E Y E )|()())|(()(
例如，一项工作由甲一个人完成，平均需要4小时，而乙有0.4的概率来帮忙，两个人完成平均只需要3小时。若用X 表示完成这项工作的人数，而Y 表示完成的这项工作的期望时间（单位小时），由于这项工作要么由一个人完成，要么由两个人完成，那么这项工作完成的期望时间E (Y ) = P (X = 1)E (Y | X = 1) + P (X = 2)E (Y | X = 2) = (1－0.4)×4－0.4×3 = 3.6。
一、利用递推或动态规划解决
递推作为一种基础的算法，相信所有人都不会陌生。而对于一部分期望问题而言，递推则为一种快速有效的方法。我们不需要将所有可能的情况都枚举出来，而是根据已经求出的期望推出其它状态的期望，亦或根据一些特点和结果相同的情况，求出其概率。
例题一：聪聪与可可1
在一个魔法森林里，住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。
整个森林可以认为是一个无向图，图中有N个美丽的景点，景点从1至N 编号。在景点之间有一些路连接。
可可正在景点M (M ≤N)处。以后的每个时间单位，可可都会选择去相邻的景点（可能有多个）中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。
聪聪是很聪明的，所以，当她在景点C时，她会选一个更靠近可可的景点，如果这样的景点有多个，她会选一个标号最小的景点。如果走完第一步以后仍然没吃到可可，她还可以在本段时间内再向可可走近一步。
在每个时间单位，假设聪聪先走，可可后走。在某一时刻，若聪聪和可可位于同一个景点，则可可就被吃掉了。
问平均情况下，聪聪几步就可能吃到可可。
分析：
根据题目要求聪聪会向可可不断靠近，且边无权，所以先进行N次广度优先搜索，预处理出p[i, j]表示顶点i到顶点j的最短路上与顶点i相邻且编号最小的顶点编号。即聪聪在景点i，可可在景点j时，聪聪第1步会走到的景点编号。
设f [i, j]来表示聪聪在顶点i，可可在顶点j时聪聪抓住可可的平均步数。令w[i, j]表示与顶点i相邻的j个点编号，而用t[i]表示顶点i的度。
可以确定聪聪下一步所在的顶点即p [p [i , j ], j ]，可可下一步在顶点w [i , j ]，概率为1
][1+i t ，下一步这个情况下的期望f [p [p [i , j ], j ], w [i , j ]]已经计算出，那么就是比f [p [p [i , j ], j ], w [i , j ]]多出一步。可可在原地停留的情况则类似。
所以可以得到：
11][]],],,[[[]],[],],,[[[],[]
[1+++=∑=i t j j j i p p f k j w j j i p p f j i f i t k
当然，f [i , i ] = 0，因为聪聪和可可已经在同一个点。若p [p [i , j ], j ] = j 或p [i , j ] = j 则说明在这一步聪聪即可吃掉可可，那么f [i , j ]=1。
用记忆化搜索即可解决。
小结：
对于一些题目，可以期望间的递推关系，而其也可以认为是对应了全概率公式和期望的性质的应用。这是比较常见的也是最直观的一种状态设计方法和解法。对于第二部分所要提到的利用方程组解，也是针对“循环”的情况而基于这样的一种解法得来。
例题二：Highlander 2
随机给出1，2，…，n 个数字的一个错位排列i 1i 2…i n （也就是等概率选择n 个数字所有错位排列中的一个），对应了一张有向图G = (V , E )，其中V ={1, 2, …, n }，E ={(1, i 1), (2, i 2), …, (n , i n )}。问在最长环上的顶点数的期望值。
2 ≤ n ≤ 100。
分析：
根据题目描述，则最后得到的有向图所有顶点出度入度均为1，所以有向图
必然由若干个不相交的环组成。而且由于是错位排列，所以没有自环。那么，我们通过不断确定排列中若干个数字，使其在同一个环内。为了避免重复，环的长度为从小到大确定。如果排列中剩下m 个数字没有确定，并要使其中k 个数字
属于同一个长度为k 的环，那么有k
A k m 种方案。如果有i 个环长度相同，则还需要除以i 的全排列也就是i i A 。
那么用f [i , j , k ]表示了错位排列中i 个数字已经确定，最长环为j ，且有k 个
长度为j 的环的方案数。例如当n = 4时，f [2, 2, 1]有2
24A = 6种方案：21**，3*1*，4*1*，*32*，*4*2，**43，f [4, 2, 2]可以由f [2, 2, 1]得来，由于有2个重复的环则还需要除以全排列所以32
2]1,2,2[]2,2,4[22=?=A f f ，而对应了2143，3412，4321这3种错位排列方案。
状态转移方程就可以得出：
∑∑??????=+-=+-+-=?????????????=-≤≤-??????<<-≤≤--=>==j i k j i j l j j i n j j
i n i n k j i f j i g k i j j A l j i g j i k i j k j A k j j i f k i j i i A k j i f 1
)1,min(2]
,,[],[)(0
)122(*],[)122(*]1,,[)11(],,[其他情况，，，， 答案即为∑∑∑∑≤=≤=≤=≤=n j j n k k n j j n
k k k j n f k j n f k j 2121]
,,[]
,,[**
虽然说f [i , j , k ]可能很大，但是由于只是用于计算概率，用实数类型记录依然可以满足题目要求
注：
1、答案中分母的∑∑≤=≤=n j j n
k k k j n f 21],,[即为n 个数字错位排列的排列总数。若用d [n ]
表示n 个数字的错排方案数，那么有递推式d [n ] = (n - 1) (d [n - 1] + d [n – 2])，其中 d [1] = 0，d [2] = 1。
2、可以用二维的状态得到一个更好的复杂度，但是上述给出的是最直观的一种方法。
小结：
对于一些问题比较难找到期望的递推关系，但是枚举对于多数题目依旧不现实的情况下。这时可以利用期望的定义即∑=i
i i x p X E )(。一般来说，对于这类
问题，我们可以根据实际情况以概率或方案数（除以总方案数依旧等于概率）作为状态，而下标直接或间接对应了这个概率下的变量值。而问题就变成比较一般的统计方案或者利用全概率公式计算概率的递推问题。
例题三：RedIsGood 3
桌面上有R 张红牌和B 张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
分析：
用f [i , j ]表示剩下i 张红牌和j 张黑牌获得钱的期望。决策只有2种，即翻牌与不翻牌。不翻牌期望为0。翻到红、黑牌的概率分别为j i i +、j
i j +，而分别会
得到、损失1美元，所以期望为j
i j j i f j i i j i f +--+++-*)1]1,[(*)1],1[(。 那么可以比较容易地得出下面的转移方程：
???
????==>+-==+--+++-=000,01],1[0,0}*)1]1,[(*)1],1[(,0max{],[i j i j i f j i j i j j i f j i i j i f j i f
那么f [R , B ]则为所求。
小结：
对于一些求期望并且带有决策的题需要用动态规划来解决，这类题由于要满足最优子结构，一般用期望来表示状态，而期望正表现了这个状态的优或劣。例如上题，若继续翻牌的期望小于0则说明翻牌平均情况下会损失更多钱，那么还不如就此收手。
二、建立线性方程组解决
引入
给出一个有向图G = (V , E )，点带权，顶点i 的权值为W i 。对于每条边E v u ∈),(有一个属性P u , v ，且P u , v 为正数，其中P u , v 表示从顶点u 经过边(u , v )到顶点v 的概率。若某点i 发出边概率和为P i ，即∑∈=
E j i j i i p S ),(,，那么在顶点i 时有1－P i 的
概率停止行动。定义路径path =
v i W ，即这条路径上所有点权之和。问从一个顶点s 开始，在每次按照指定的概率走的前提下，在某一顶点停止行动时所走的路径权的期望值。
例如右图，s = 1 ，W 1 = W 2 = W 3 = 1，W 4 = 0。
可以看到从起点到停止行动有两条路径，这两条路径
权分别为3和2，而走这两条路径的概率均为0.5。所以能
得到期望值为3×0.5+2×0.5 = 2.5。
若调整一条边的方向并修改相关概率，由于图中出现了
环，这样路径就会有无数条。所以我们必须找到一种有效
的方法处理一般的情况。
分析：
设F i ,j 为从顶点i 出发，经过j 步的权和的期望，那么可以得到：
i i W F =0,，当0>j 时，可以分成停止行动和走到某一个相邻点这两类情况。若存在一条边(i , k )，走这条边的概率k i P ,，那么从顶点i 出发经过顶点k 的期望值即为顶点k 出发j －1步的期望1,-j k F 加上顶点i 的权值W i 。当然，在点i 时还有)1(),(,∑∈-
E k i k i P 的概率停止行动，而停止行动依然要计算顶点i 的权值W i ，所以
有：
∑∑∑∈-∈∈-+=-++=
E k i i j k k i i E k i k i E k i i j k k i j i W
F P W P W F P F ),(1,,),(,),(1,,,)1()(
若F i ,j 当∞→j 时收敛，设收敛于F i ，那么答案即为F s ，可以通过迭代法求出满足精度要求的解。但是显然当精度要求较高或增长速度较慢，程序运行时间就将会很长，并且当极限不存在时也难以判断。
所以可以抛弃步数的思想，设F i 为从顶点i 出发的权和期望，对于每个F i 类似地建立这样一个等式∑∈+=
E j i i j j i i W
F P F ),(,，那么F s 则为所需要的答案。当图
不存在环的情况下，那么我们就可以利用拓扑序进行递推以求得一个更好的复杂度。但是对于一般情况，显然按照这个式子递推就不完全可行了。这时利用所有的等式建立线性方程组求解则是成为了一个有效的方法。一般情况下，接下来即为利用高斯消元求解这个线性方程组。这样既得到了一个稳定的复杂度，根据方程组是否有唯一解的情况也能判断极限是否存在。
同一般线性方程组一样，这个方程依然面对着无解或无数组解的问题。而方程组没有唯一解并不代表所有未知数没有唯一解，例如下面这个方程组：
???+==11b b a
由于a 与b 无关所以b 无解不影响a 有唯一解。
由于每个顶点对应了方程组中的一个变量，那么方程组中只需要保留与顶点s 有关，即s 到达的顶点即可。实际操作中也可以对高斯消元的过程作一些相关调整。
而若需要求的未知数仍没有唯一解，一般情况下可以认为期望不存在。但是遇到具体问题时，需要根据题目的条件具体分析（例如下文会提到的例题Mario ）。
这可以作为绝大多数以期望作为状态的期望问题的模型，而对于无环的情况递推可以得到一个不错的时间复杂度，而对于一般情况高斯消元则成为通常解决这类期望问题的一把利器。
需要注意的地方：
● 若权在边上而不在点上的话，即边(u , v )的权值为W u ,v ，那么同理方程即为
∑∈+=
E j i j i j j i i W
F P F ),(,,)(。
● 可以调整消元顺序让所要求的E s 放在最后，这样就可以不用回代，让实现更
简洁，并在一些问题上能节省常数时间。
例题四：First Knight 4
一个矩形区域被分成m *n 个单元编号为 (1, 1)至 (m , n )，左上为 (1, 1)，右
下为(m , n )。给出)(,k j i P ，其中1 ≤ i ≤ m ，1 ≤ j ≤ n ，1 ≤ k ≤ 4，表示了 (i , j )到 (i +1,
j )，(i , j +1)，(i -1, j )，(i , j -1)的概率。一个骑士在 (1, 1)，按照给定概率走，每步都于之前无关，问到达 (m , n )的期望步数。
题目保证对于i ≠m 或j ≠n ，有14
1)(,=∑=k k j i P ，且)1(,j i P 和)2(,j i P
中至少一个不为0。且保证走出矩形的概率与)(,k n m P 均为0，答案不超过1000000。
1 ≤ m, n ≤ 40。
分析：
初看这道题可以发现这题直接对应了上面给出的模型，而且题目条件)1(,j i P 和
)2(,j i P 中至少一个不为0，即所有点到达结束点(m , n )的概率均为1，说明这个方程组不存在特殊情况，可以很容易地列出方程：
11,)4(,,1)3(,1,)2(,,1)1(,,++++=--++j i j i j i j i j i j i j i j i j i E P E P E P E P E ，
其中1 ≤ i ≤ m ，1 ≤ j ≤ n 。 但是由于未知数个数为mn ，那么时间复杂度则达到O (m 3n 3)，再加上数据组数非常多，虽然时限为30s ，直接套用高斯消元对于数据范围m , n ≤ 40显然还是无法接受的。但是否说明这种方法不能用于此题呢？答案是否定的。
一、直观的优化。
1、 避免与0相乘。观察增广矩阵的特点，由于j i E ,最多与4项有关，所以增广矩阵中会有很多的0。对于两行消元时若某行的主元素所在列的元素为0，那么显然这两行就不需要进行消元操作。而由于乘法的常数较大，所以消元时判断乘数都不为0时才进行乘法运算。
2、 调整消元顺序。让1,1E 最后进行消元，这样可以不用回代。让满足(i + j ) mod 2 = 1（类似国际象棋棋盘其中的一色）的j i E ,先进行消元。由于这些先进行消元的项互不相关，即消掉一项后另外几项的方程不会改变，所以每个方程最多与4个方程进行消元。实践证明，这么调整顺序会节省大约一半的时间。
进行以上两点优化之后即可通过此题，但是提交5后运行时间为22s ，不是很理想。
二、进一步思考。
虽然用上述优化本题在时限内得到解决，但是时空复杂度依然不很理想，为什么一个看似6时间复杂度依然为O (n 3m 3)的算法依旧可以快速运行出极限数据的结果？有没有更好的方法？
观察方程：
11,)4(,,1)3(,1,)2(,,1)1(,,++++=--++j i j i j i j i j i j i j i j i j i E P E P E P E P E
对于i = 1，由于走出矩形的概率为0，有0)3(,=j i P ，
11,1)4(,11,1)2(,,2)1(,1,1+++=-+j j j j i j j j E P E P E P E
对于所有的j E ,1，将j E ,2看作常数项进行消元，对那么可以用只含有n E E E ,22,21,2，，， 的代数式来表示j E ,1，即：
j n n j c E a E a E a E ,1,22,221,21,1++++= ，其中a i ，c 分别表示消元后方程的系
5
提交地址：http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4297
数和常数。
将j E ,1代入方程11,2)4(,2,1)3(,21,2)2(,2,3)1(,2,2++++=-+j j j j j j j j j E P E P E P E P E 后，对于所有j E ,2便可以用n E E E ,22,21,2，，， 和j E ,3表达出，同样将j E ,3当作常数项进行消元。
同理，不断将j i E ,以k i E ,1+，k = 1, 2, …, m 表示的代数式代入，直到i = m ，
j m E ,只与k m E ,有关，解出后回代即可求解。
由于每次只对n 个方程进行消元，要处理的项不超过2n +1个，这样时间复杂度可以达到O (n 3m )，但是实现起来可以略显麻烦。所以我们就可以思考如何直接应用到高斯消元的过程之中。
同样为了避免回代，可以以逆序也就是1,11-,1,11,1-1,1-,1-1,1-,,E E E E E E E E E n n m n m n m m n m n m ，，，，，，，，，，， -这样一个顺序消元。
若当前消去的元为y x E ,。而到y x E ,时为第((m －x ＋1)×n －y ＋1)步，按照高斯消元的过程，需要接下来的(m ×n －((m －x ＋1)×n －y ＋1))也就是((x －1)×n ＋y －1)个方程进行操作。或者说与开始的mn 个方程相比，减少的方程数和消去的未知量数相等。对于所有满足i < x －1或i = x －1且j < y 的方程
11,)4(,,1)3(,1,)2(,,1)1(,,++++=--++j i j i j i j i j i j i j i j i j i E P E P E P E P E 是不包含y x E ,及之前消去的未知量的，所以它们并未改变，即不属于减少的方程，且与本次消元也无关。满足以上条件的方程即增广矩阵中不需要有变化的行有((x －2)×m ＋y －1)个。所以相减后可以发现，每次消元时，实际需要进行消元的有关的方程不超过n 个。而可以看出，由于y x E ,之前项的系数已被消去，而对于这其中n 个方程中位于消元顺序最后的且系数大于0的未知量为y x E ,2-，所以这n 个方程中系数大于0的项不超过2n 个。
这样一来，每次消元只需要与其后至多n 行中的2n ＋1列进行处理进行即可。时间复杂度为O (n 3m )，若对于第i 行的某个格子列出的方程只储存第i -1行至第
i+1行的格子对应的未知量系数及常数，空间复杂度可以达到O(n2m)。这样本题得到一个不错的解决。
例题五：Mario7
Mario生活在一个N×M的迷宫里，格子的属性分别为金币，怪兽，管道，墙和空地。每当Mario走到金币的格子上时，它都能拿到所给出的金币数（但金币不消失）。当Mario进入怪兽所在格子时，他将损失一条命。当Mario进入管道的入口时，他会立即传送到管道的出口，出口唯一，但是对应出口的入口可能有很多。墙是不可进入的。管道的出口和空地一样，进入时不会有任何事情发生。
Mario从一个给定的起点（起点在空地上）开始，他有3条命，他每次等概率向相邻4格能走的格子走，在命为0或者他不能再获得更多金币时游戏结束。问他能得到的金币的期望值，若期望值为无穷大则输出-1。
1 ≤ N,M ≤ 15。
分析：
首先对于这种3条命的游戏一般做法即对图进行分层，对应了剩余命分别为3，2，1条。除了障碍和管道入口每个格子都对应了图中每层各一个点。对于1条命图中的怪兽对应的顶点为结束顶点，k (k > 1)条命对应的点分别对应k– 1条命对应层能到达的顶点连边。其他格子与其能到达的格子同层连边，对于有金币的格子对应的点权为金币数，其他格子对应的点权为0。
但是这个游戏还有另外一种结束条件，即不能获得更多金币，那么对于所有格子进行广度优先搜索，若其不能到达一格金币数大于0的格子那么这个格子满足这个条件。即满足条件的格子都作为结束结点。搜索时不必判断命的情况，因为若不能在命数限制下到达那么在分层图中也是不连通的。对于这类格子在图中
的结点也没有发出的边。不过实际编写程序时的时候可以不将这些顶点放入图内，在方程中按照0处理。
这样处理之后一样地列出方程求解。而当然，实际操作时不必构图，而可以直接在地图上建立方程组。
若不能求出起点的期望（即没有唯一解的情况下），那么此时由于图中不存在拿不到金币的点，且所有点权非负，所以可以判断出期望就为如题目描述中所说的无穷大。
还有需要注意的一点，这题就存在起点不能到达的点，可以利用判断某个格子是否能走到能拿到钱的格子的广度优先搜索过程处理出能到达的点，这样既不会增加编程复杂度又能节省常数时间。
总结
本文对竞赛中出现利用递推也包括动态规划解决的几道问题说起，对每题的特点总结出一类问题的状态设计方法和一般的解法。之后又对无法用递推有效解决的一个图模型，由于迭代的效率低，且无法得到精确解，提出了建立线性方程组并利用高斯消元解决的方法。而题目不会是一成不变的，所以随后通过两道例题讲解了实际应用到具体题目时的优化及处理。
当然，不能说本文覆盖了解决信息学竞赛所有期望值求解问题的有效方法。然而把握期望的概念，灵活设计方法，注意观察题目的特点，从而发现本质，这才是最为关键的。
参考文献：
[1] https://www.doczj.com/doc/d59920499.html,/ Wikipedia
[2] 2004年国家集训队研究报告《有关概率和期望问题的研究》鬲融
“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 1 引论 人们在借助计算机解决一个实际问题时，无非就是详细地告诉计算机应该怎么做，使它能通过人们给定的输入得到人们想要的输出。由于一般的计算机只能处理数字信号，所以只有把实际问题转化为数学问题，计算机才能帮助我们。这一步就是建立数学模型。 数学模型的建立在通过计算机解决问题的过程中非常重要。它把计算机无法理解的问题加以转化，使一切事物量化，最终变为只含数学过程的问题。它是人脑与计算机沟通的桥梁。不仅如此，数学模型的好坏直接影响着人与计算机之间的信息交流，影响着计算机对问题的“理解”。好的数学模型能够抓住问题的本质，表述简捷明了，易于人们找到有效的解决方法，并通过编制程序的方式将解决方法告诉计算机；相反，对于同一个问题，如果数学模型不能抓住问题本质，人们就可能无法解决问题，或者找不到有效的方法，更不用提告诉计算机如何做了。 由于建立数学模型是为了解决问题，所以人们在做这项工作时往往希望把问题归结为已经很好解决的经典问题或若干这样问题的有机结合。这样，只要应用前人的研究成果就可以了。比如，排序、求图的单源最短路、网络流等等都是经典问题，前人不仅给出一般解法，而且对各种特殊情况和变形作了深入的研究。但事情并不总像人们希望的那样，有的问题即使可以归结为已有问题，在其中加入一些干扰因素后，原有性质就会发生改变，原来建立起的数学模型难以再用严谨的数学语言表达。这样问题中的部分图论问题可以用本文提出的“分层图思想”解决。 该思想注重对原问题性质的挖掘，通过对原问题数学模型的扩展，将干扰因素融入新的数学模型之中，恢复了模型的严谨性，进而与已解决问题产生联系，得到有效算法。
国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营许可证》换发及变更的通知 【法规类别】旅游综合规定 【发文字号】旅管理函[2008]16号 【发布部门】国家旅游局 【发布日期】2008.02.02 【实施日期】2008.02.02 【时效性】现行有效 【效力级别】部门规范性文件 国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营许可证》换发及变 更的通知 （旅管理函〔2008〕16号） 各省、自治区、直辖市旅游局（委）： 为了进一步规范《国际旅行社业务经营许可证》的换发和变更，现根据《旅行社管理条例》及实施细则，就有关事项通知如下： 一、《国际旅行社业务经营许可证》有效期为三年，国际旅行社应当在《国际旅行社业务经营许可证》到期之日前的三个月内，持许可证到原颁证机关（国家旅游局）换发。 二、《国际旅行社业务经营许可证》在有效期内需要变更许可证载明事项内容的，应当在完成工商部门的变更登记之日起的相关规定期限内，持相关材料和许可证到原颁证机
关申请换发。 三、《国际旅行社业务经营许可证》损坏的，应当在相关规定期限内将损坏《国际旅行社业务经营许可证》正、副本上交颁证机关申请换发。 四、《国际旅行社业务经营许可证》遗失的，应当在遗失之日起的相关规定期限内在当地公开发行的报纸上刊登启事，并提供报纸原件向颁证机关申请换发。 五、《国际旅行社业务经营许可证》涉及变更事项的，各省（自治区、直辖市）旅游局须认真审验相关材料，并在《国际旅行社变更事项备案登记表》内签章。 附件：1、《国际旅行社业务经营许可证》变更事项所需提供材料的具体规定 2、国际旅行社变更事项备案登记表 国家旅游局质量规范与管理司 2008年2月2日附件1： 《国际旅行社业务经营许可证》变更事项 所需提供材料的具体规定
摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Pólya原理及其应用》 2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 - 周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Pólya计数法的应用》 数位问题 2009 - 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004 - 薛矛：《解决动态统计问题的两把利刃》 2007 - 余江伟：《如何解决动态统计问题》 博弈 2002 - 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》2007 - 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》 母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007 - 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005 - 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003 - 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题 2003 - 张宁：《猜数问题的研究:<聪明的学生>一题的推广》
2006 - 龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 - 何林：《数据关系的简化》 2006 - 朱晨光：《基本数据结构在信息学竞赛中的应用》 2007 - 何森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001 - 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 - 黄刚：《数据结构的联合》 块状链表 2005 - 蒋炎岩：《数据结构的联合——块状链表》 2008 - 苏煜《对块状链表的一点研究》 动态树 2006 - 陈首元：《维护森林连通性——动态树》 2007 - 袁昕颢：《动态树及其应用》 左偏树 2005 - 黄源河：《左偏树的特点及其应用》 跳表 2005 - 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009 - 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree》 线段树 2004 - 林涛：《线段树的应用》 单调队列 2006 - 汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 - 杨思雨：《伸展树的基本操作与应用》
动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。
国家旅游局关于印发《导游IC卡发放管理办法(试行)》的通 知 【法规类别】旅游服务机构导游人员管理 【发文字号】旅办发[2010]198号 【修改依据】国家旅游局办公室关于修订《导游IC卡发放管理办法(试行)》等事项的通知 【发布部门】国家旅游局 【发布日期】2010.12.28 【实施日期】2010.12.28 【时效性】已被修改 【效力级别】部门规范性文件 国家旅游局关于印发《导游IC卡发放管理办法（试行）》的通知 （旅办发（2010）198号） 各省、自治区、直辖市旅游局（委）： 为规范和加强导游IC卡发放管理工作，健全导游IC卡使用管理制度，现将《导游IC卡发放管理办法（试行）》，印发给你们，并就有关事项通知如下： 一、自2011年1月1日起，由各省、自治区、直辖市和新疆生产建设兵团旅游局（委）（以下简称“省级旅游局”）负责本地区（系统）导游IC卡的制作、颁发和监督检查工作；原有A版制版系统城市不再发放和制作导游IC卡，继续承担IC卡年审职责，系统
保留年审功能；原有B版系统的城市职责和系统功能不变。 二、请各省级旅游局通知并督促使用A版系统城市旅游局立即停止制作发放IC卡，协调配合系统开发维护单位完成对系统软硬件的调整和剩余导游IC卡的清理回收工作，于2010年12月31日前将清理情况书面报告我局。 三、自本通知发出之日起，我局只向各省级旅游局发放导游IC卡，请各省级旅游局在开展导游IC卡系统调整和IC卡清理回收工作的同时，研究制订相关管理办法，与清理工作一并报我局备案。 四、换卡、补卡收取成本费的标准为30元/张（含卡、卡套和加工制作、邮寄等全部费用），汇付账户和具体方式另行通知。 五、我局将对各省导游IC卡发放管理工作进行不定期抽查和调研工作。 《导游IC卡发放管理办法（试行）》和此通知执行中有重要情况和意见，请及时报告我局。 特此通知。 联系人：卓超美 联系电话：（010）65201338 国家旅游局办公室 二Ｏ一Ｏ年十二月二十八日 导游IC卡发放管理办法（试行） 第一条依据《导游人员管理条例》，为规范导游IC卡的发放管理，制定本办法。
2018年全国高中数学联合竞赛一试试题（A 卷） 一、填空题：本大题共 8小题，每小题 8分，共64分． 1.设集合{1,2,3,,99}A = ，{2}B x x A =∈，{2}B x x A =∈，则B C 的元素个数 . 解析：因为{1,2,3,,99}A = ，所以{2,4,6,,198}B = ,{1,2,3,,49}C = ,于是 {2,4,6,,48}B C = ，共24个元素. 2.设点P 到平面α Q 在平面α上，使得直线PQ 与α所成角不小于30 且不大于60 ，则这样的点Q 所构成的区域的面积为 . 解析：过点P 作平面α的垂线，这垂足为O ，则点Q 的轨迹是以O 为圆心，分别以1ON =和3OM =为半径的扇环,于是点Q 所构成的区域的面积为21S S S =-= 9 8πππ-=. 3. 将1,2,3,4,5,6随机排成一行，记为,,,,,a b c d e f ，则abc def +是偶数的概率为 . 解析：（直接法）将1,2,3,4,5,6随机排成一行，共有6 6720A =种不同的排法，要使 abc def +为偶数，abc 为与def 同为偶数或abc 与且def 同为奇数. （1）若,,a b c 中一个偶数两个奇数且,,d e f 中一个奇数两个偶数. 共324种情形； （2）若,,a b c 中一个奇数两个偶数且,,d e f 中一个偶数两个奇数. 共324种情形； 共有648种情形.综上所述，abc def +是偶数的概率为 6489 72010 =. （间接法）“abc def +是偶数”的对立事件为“abc def +是偶数”， abc def +是偶数分成两种情况：“abc 是偶数且def 是奇数”或“abc 是奇数且def 是偶数”，每 P O M N α
左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (5) 3.1 左偏树的合并 (5) 3.2 插入新节点 (7) 3.3 删除最小节点 (8) 3.4 左偏树的构建 (8) 3.5 删除任意已知节点 (9) 3.6 小结 (12) 四、左偏树的应用 (13) 4.1 例——数字序列（Baltic 2004） (13) 五、左偏树与各种可并堆的比较 (15) 5.1 左偏树的变种——斜堆 (15) 5.2 左偏树与二叉堆的比较 (16) 5.3 左偏树与其他可并堆的比较 (16) 六、总结 (18)
【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。
国家旅游局公告2006年第1号——欠缴质保金的旅行社名单 【法规类别】旅游服务机构导游人员管理 【发文字号】国家旅游局公告2006年第1号 【发布部门】国家旅游局 【发布日期】2006.01.04 【实施日期】2006.01.04 【时效性】现行有效 【效力级别】XE0303 国家旅游局公告 （2006年第1号） 根据我局《关于进一步做好旅行社质量保证金回收工作的通知》（[2005]105号）的要求，各地旅行社补缴质量保证金的工作基本结束。目前，全国仍有74家旅行社未能按时补齐质保金，其中组团社有16家，国际社有58家。现将74家旅行社的名单公示如下。请上述旅行社在2006年2月28日前补齐质保金，逾期将按有关规定给予降类或注销处理。 特此公告。 附：欠缴质保金的旅行社名单 国家旅游局
二00六年一月四日 附： 一、组团社名称及许可证编号（16家） 1 珠海经济特区环球国际旅行社L-GD-GJ00024 2 台山中国旅行社L-GD-GJ00139 3 湛江市旅游总公司L-GD-GJ00017 4 黑龙江省中国青年旅行社L-HLJ-GJ00009 5 伊春中国国际旅行社L-HLJ-GJ00011 6 海南港澳国际旅行社有限公司L-HAN-GJ00006 7 包头中国国际旅行社L-NMG-GJ00008 8 喀什国际旅行社有限责任公司L-XJ-GJ00006 9 开封中国国际旅行社L-HEN-GJ00006 10 广西玉林国际旅行社有限公司L-GX-GJ00024 11 北海中国国际旅行社有限公司L-GX-GJ00005 12 青海省中国青年旅行社有限责任公司L-QH-GJ00003 13 甘肃海外旅游总公司L-GS-GJ0
2009年全国高中数学联赛试题及答案
全国高中数学联赛 全国高中数学联赛一试命题范围不超出教育部《全日制普通高级中学数学教学大纲》中所规定的教学要求和内容，但在方法的要求上有所提高。主要考查学生对基础知识和基本技能的掌握情况，以及综合和灵活运用的能力。 全国高中数学联赛加试命题范围与国际数学奥林匹克接轨，在知识方面有所扩展，适当增加一些竞赛教学大纲的内容。全卷包括4道大题，其中一道平面几何题. 一 试 一、填空（每小题7分，共56分） 1． 若函数( )f x = ()()()n n f x f f f f x ??=??????，则() ()991f = ． 2． 已知直线:90L x y +-=和圆22:228810M x y x y +---=，点A 在直线L 上，B ，C 为圆M 上两点，在ABC ?中，45BAC ∠=?，AB 过圆心M ，则点A 横 坐标范围为 ． 3． 在坐标平面上有两个区域M 和N ，M 为02y y x y x ?? ??-? ≥≤≤，N 是随t 变化的区 域，它由不等式1t x t +≤≤所确定，t 的取值范围是01t ≤≤，则M 和N 的公共面积是函数()f t = ． 4． 使不等式 1111 200712 213 a n n n +++ <-+++对一切正整数n 都成立的最小正整数a 的值为 ． 5． 椭圆22 221x y a b +=()0a b >>上任意两点P ，Q ，若OP OQ ⊥，则乘积 OP OQ ?的最小值为 ． 6． 若方程()lg 2lg 1kx x =+仅有一个实根，那么k 的取值范围是 ． 7． 一个由若干行数字组成的数表，从第二行起每一行中的数字均等于其肩 上的两个数之和，最后一行仅有一个数，第一行是前100个正整数按从小到大排成的行，则最后一行的数是 （可以用指数表示） 8． 某车站每天800~900∶∶，900~1000∶∶都恰有一辆客车到站，但到站的时
国家旅游局32号令：《旅游投诉处理办法》自2010年7月1日起施行2010-5-19 15:12:43国家旅游局政策法规司字号：[大中小]选择背景色： 国家旅游局令 第32号 《旅游投诉处理办法》已经2010年1月4日国家旅游局第1次局长办公会议审议通过。现予公布，自2010年7月1日起施行。 国家旅游局局长：邵琪伟 二○一○年五月五日 旅游投诉处理办法 第一章总则 第一条为了维护旅游者和旅游经营者的合法权益，依法公正处理旅游投诉，依据《中华人民共和国消费者权益保护法》、《旅行社条例》、《导游人员管理条例》和《中国公民出国旅游管理办法》等法律、法规，制定本办法。 第二条本办法所称旅游投诉，是指旅游者认为旅游经营者损害其合法权益，请求旅游行政管理部门、旅游质量监督管理机构或者旅游执法机构（以下统称“旅游投诉处理机构”），对双方发生的民事争议进行处理的行为。 第三条旅游投诉处理机构应当在其职责范围内处理旅游投诉。 地方各级旅游行政主管部门应当在本级人民政府的领导下，建立、健全相关行政管理部门共同处理旅游投诉的工作机制。 第四条旅游投诉处理机构在处理旅游投诉中，发现被投诉人或者其从业人员有违法或犯罪行为的，应当按照法律、法规和规章的规定，作出行政处罚、向有关行政管理部门提出行政处罚建议或者移送司法机关。 第二章管辖 第五条旅游投诉由旅游合同签订地或者被投诉人所在地县级以上地方旅游投诉处理机构管辖。 需要立即制止、纠正被投诉人的损害行为的，应当由损害行为发生地旅游投诉处理机构管辖。 第六条上级旅游投诉处理机构有权处理下级旅游投诉处理机构管辖的投诉案件。 第七条发生管辖争议的，旅游投诉处理机构可以协商确定，或者报请共同的上级旅游投诉处理机构指定管辖。 第三章受理
1999年 陈宏- 数据结构的选择与算法效率——从IOI98试题PICTURE谈起 来煜坤- 把握本质，灵活运用——动态规划的深入探讨 齐鑫- 搜索方法中的剪枝优化 邵铮- 数学模型的建立、比较和应用 石润婷- 隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性睢》?- 准确性、全面性、美观性——测试数据设计中的三要素 周咏基- 论随机化算法的原理与设计 2000年 陈彧- 信息学竞赛中的思维方法 方奇- 动态规划 高寒蕊- 递推关系的建立及在信息学竞赛中的应用 郭一- 数学模型及其在信息学竞赛中的应用 江鹏- 探索构造法解题模式 李刚- 动态规划的深入讨论 龙翀- 解决空间规模问题的几种常用的存储结构 骆骥- 数学模型的建立和选择 施遥- 人工智能在围棋程序中的应用 肖洲- 数据结构的在程序设计中的应用 谢婧- 规模化问题的解题策略 徐串- 论程序的调试技巧 徐静- 图论模型的建立与转化 杨江明- 论数学策略在信息学问题中的应用 杨培- 非最优化算法初探 张辰- 动态规划的特点及其应用 张力- 类比思想在解题中的应用 张一飞- 冗繁削尽留清瘦——浅谈信息的充分利用 2001年 高寒蕊- 从圆桌问题谈数据结构的综合运用 符文杰- Pólya原理及其应用 高岳- 中等硬度解题报告 江鹏- 从一道题目的解法试谈网络流的构造与算法 刘汝佳- 搬运工问题的启示 李益明- 计算几何的相关问题 李源- 树的枚举 骆骥- 由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性毛子青- 动态规划算法的优化技巧 俞玮- 基本动态规划问题的扩展 张一飞- 求N!的高精度算法 2002年 戴德承- 退一步海阔天空——“目标转化思想”的若干应用
国家旅游局关于放宽旅行社设立服务网点政策有关事项的通知 (旅发〔2015〕211号) 各省、自治区、直辖市旅游委、局，新疆生产建设兵团旅游局： 为贯彻落实《关于促进旅游业改革发展的若干意见》(国发〔2014〕31号)精神，现就放宽旅行社设立服务网点政策有关事项通知如下： 一、放宽设立服务网点区域范围 允许设立社在所在地的省(市、区)行政区划内及其分社所在地的设区的市的行政区划内设立服务网点，不受数量限制。 在设立社所在地的省(市、区)行政区划内设立服务网点的，设立社向服务网点所在地工商行政管理部门办理服务网点设立登记后，应当在3个工作日内，持设立社营业执照副本、设立社旅行社业务经营许可证副本、服务网点的营业执照、服务网点经理的履历表和身份证明向服务网点所在地与工商登记同级的旅游主管部门备案。 旅行社在其分社所在地的设区的市的行政区划内设立服务网点的，设立社向服务网点所在地工商行政管理部门办理服务网点设立登记后，应当在3个工作日内，持设立社营业执照副本、设立社旅行社业务经营许可证副本、分社的营业执照、旅行社分社备案登记证明、服务网点的营业执照、服务网点经理的履历表和身份证明向服务网点所在地与工商登记同级的旅游主管部门备案。 二、落实分社和服务网点设立政策 各地要认真学习贯彻《国务院关于促进旅游业改革发展的若干意见》(国发〔2014〕31号)，切实按照《旅行社条例》及本通知要求，依法依规做好分社和服务网点的备案工作，不得增设或变相增设旅行社设立分社、服务网点的政策障碍。
各省级旅游主管部门要积极开展针对市、县级旅游主管部门的培训指导和监督检查，发现不依法依规开展分社和服务网点备案工作的，要及时予以纠正。 三、加强对旅行社分社和服务网点的服务监管 各地要进一步引导旅行社增强风险管控意识，审慎确定分支机构设立的数量和规模;督促设立社切实加强对分社和服务网点的管理和人员培训，依法承担经营活动的责任和后果;要加强旅游质监执法人员的培训，建立健全对旅行社分社、服务网点的事中事后监管机制，改进服务监管手段，提升服务监管水平，对发现的违法违规行为，要主动协同设立社所在地旅游主管部门进行依法查处。 国家旅游局此前发布的相关规定与本通知不一致的，依照本通知执行。 国家旅游局 2015年9月22日
2020年全国高中数学联赛试题及详细解析 说明： 1． 评阅试卷时，请依据本评分标准。选择题只设6分和0分两档，填空题只设9分和0分两档；其 他各题的评阅，请严格按照本评分标准规定的评分档次给分，不要再增加其它中间档次。 2． 如果考生的解题方法和本解答不同，只要思路合理、步骤正确，在评卷时可参考本评分标准适当 划分档次评分，5分为一个档次，不要再增加其他中间档次。 一、选择题（本题满分36分，每小题6分） 本题共有6小题，每小题均给出A ，B ，C ，D 四个结论，其中有且仅有一个是正确的。请将正确答案的代表字母填在题后的括号内。每小题选对得6分；不选、选错或选出的代表字母超过一个（不论是否写在括号内），一律得0分。 1．使关于x 的不等式36x x k -+-≥有解的实数k 的最大值是（ ） A ．63- B ．3 C ．63+ D ．6 2．空间四点A 、B 、C 、D 满足,9||,11||,7||,3||====DA CD BC AB 则BD AC ?的取值（ ） A ．只有一个 B ．有二个 C ．有四个 D ．有无穷多个 6.记集合},4,3,2,1,|7777{ },6,5,4,3,2,1,0{4 4 33221=∈+++==i T a a a a a M T i 将M 中的元素按从大到小的
顺序排列，则第2020个数是（ ） A ． 43273767575+++ B ．43272767575+++ C ．43274707171+++ D ．4327 3707171+++ 二、填空题（本题满分54分，每小题9分） 本题共有6小题，要求直接将答案写在横线上。 7.将关于x 的多项式2019 3 2 1)(x x x x x x f +-+-+-=Λ表为关于y 的多项式=)(y g ,202019192210y a y a y a y a a +++++Λ其中.4-=x y 则=+++2010a a a Λ . 8.已知)(x f 是定义在),0(+∞上的减函数，若)143()12(2 2 +-<++a a f a a f 成立，则a 的取值范围是 。 12.如果自然数a 的各位数字之和等于7，那么称a 为“吉祥数”.将所有“吉祥数”从小到大排成一列 ,,,,321Λa a a 若,2005=n a 则=n a 5 . 三、解答题（本题满分60分，每小题20分） 13.数列}{n a 满足：.,2 36 457,12 10N n a a a a n n n ∈-+= =+ 证明：（1）对任意n a N n ,∈为正整数；(2)对任意1,1-∈+n n a a N n 为完全平方数。 14.将编号为1,2，…，9的九个小球随机放置在圆周的九个等分点上，每个等分点上各有一个小球. 设圆周上所有相邻两球号码之差的绝对值之和为要S.求使S 达到最小值的放法的概率.（注：如果某种放法，经旋转或镜面反射后可与另一种放法重合，则认为是相同的放法） 15.过抛物线2 x y =上的一点A （1,1）作抛物线的切线，分别交x 轴于D ，交y 轴于B.点C 在抛物线
NOI国家集训队论文分类（至2008） 摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Polya原理及其应用》 2003 -许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 -周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Polya计数法的应用》 数位问题 2009 -高逸涵《数位计数问题解法研究》 2009 -刘聪《浅谈数位类统计问题》 动态统计 2004 -薛矛：《解决动态统计问题的两把利刃》 2007 -余江伟：《如何解决动态统计问题》 博弈 2002 -张一飞：《由感性认识到理性认识一一透析一类搏弈游戏的解答过程》2007 -王晓珂：《解析一类组合游戏》 2009 -曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 -方展鹏《浅谈如何解决不平等博弈问题》 2009 -贾志豪《组合游戏略述一一浅谈SG游戏的若干拓展及变形》母函数 2009 -毛杰明《母函数的性质及应用》 拟阵 2007 -刘雨辰：《对拟阵的初步研究》 线性规划 2007 -李宇骞：《浅谈信息学竞赛中的线性规划一一简洁高效的单纯形法实现与应用》 置换群 2005 -潘震皓：《置换群快速幕运算研究与探讨》 问答交互 2003 -高正宇：《答案只有一个一一浅谈问答式交互问题》 猜数问题 2003 -张宁：《猜数问题的研究：< 聪明的学生> 一题的推广》
2006 -龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 -何林：《数据关系的简化》 2006 -朱辰光:《基本数据结构在信息学竞赛中的应 用》 2007 -何森：《浅谈数据的合理组织》 2008 -曹钦翔《数据结构的提炼与压缩》 结构联合 2001 -高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 -黄刚：《数据结构的联合》 块状链表 2005 -蒋炎岩：《数据结构的联合——块状链表》 2008 -苏煜《对块状链表的一点研究》 动态树 2006 -陈首元：《维护森林连通性——动态树》 2007 -袁昕颢：《动态树及其应用》 左偏树 2005 -黄源河：《左偏树的特点及其应用》 跳表 2005 -魏冉：《让算法的效率跳起来”——浅谈跳跃表”的相关操作及其应用》2009 -李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Bala nee Tree 》 线段树 2004 -林涛：《线段树的应用》 单调队列 2006 -汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 -杨思雨：《伸展树的基本操作与应用》
置换群快速幂运算 研究与探讨 江苏省苏州中学 潘震皓 [关键词] 置换 循环 分裂 合并 [摘要] 群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。 [正文] 一、引言 置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得O(k*乘法)或是O(logk*乘法)的算法；而对于分数幂运算，则找不到较好的方法实现。 二、置换群的整幂运算 2.1 整幂运算的一个转化 在置换群中有一个定理：设e T k =， （T 为一置换，e 为单位置换（映射函数为x x f =)(的置换）），那么k 的最小正整数解是T 的拆分的所有循环长度的最小公倍数。 或者有个更一般的结论：设e T k =， （T 为一循环，e 为单位置换），那么k 的最小正整数解为T 的长度。 我们知道，单位置换就是若干个只含单个元素的循环．．．．．．．．．的并。也就是说，长度为l 的循环，l 次的幂，把所有元素都完全分裂了。这是为什么呢？ 我们来做一个试验：(下面的置换均以循环的连接表示) 设n=6，那么3 26 )(T T =。任取一T=(1 3 5 2 4 6)，来做一遍乘法： ()() 36 2 45 1 34 126565432134 1 2 6 51265431265436543211265436543211265436543212 =???? ??=???? ?????? ??=???? ?????? ??=T 分裂成了2份！而且这2份恰好是T 的奇数项和偶数项！（注意可以写成(1 5 4)(3 2 6)）
旅行社公告暂行规定 第一条为规范有关旅行社的公告发布行为，加强对企业经营和旅游行政管理的指导服务，根据《旅行社条例》和《旅行社条例实施细则》，制订本暂行规定。 第二条旅行社公告事项如下： （一）旅行社业务经营许可证的颁发、变更、注销、吊销； （二）许可或暂停、停止旅行社经营出境、边境旅游业务； （三）旅行社经营或暂停、停止经营赴台旅游业务； （四）旅行社分社、服务网点设立与撤销备案； （五）旅行社委托代理招徕旅游者业务备案； （六）旅行社的违法经营行为； （七）旅行社的诚信记录； （八）旅游者对旅行社投诉信息； （九）旅行社质量保证金交存、增存、补存、降低交存比例和被执行赔偿等情况； （十）旅行社统计调查情况； （十一）全国和地区旅行社经营发展情况； （十二）旅游行政管理部门认为需要公开发布的其他有关旅行社的事项和情况信息。 第三条旅行社业务经营许可证颁发、变更公告，由颁发旅行社业务经营许可证和办理旅行社业务经营许可证变更事项的旅游行政管理部门发布。 旅行社业务经营许可证颁发公告，项目内容应该包括旅行社名称、
许可证编号、出资人、法定代表人、经营场所、许可经营业务、许可文号（附件1）。 旅行社业务经营许可证变更公告，项目内容应该包括旅行社许可证编号和变更前与变更后的名称、出资人、法定代表人、经营场所（附件2）。 第四条旅行社业务经营许可证注销、吊销公告，由办理注销旅行社业务经营许可证备案手续和作出吊销旅行社业务经营许可证决定的旅游行政管理部门发布。 旅行社业务经营许可证注销公告，项目内容应该包括旅行社名称、许可证编号、经营场所（附件3）。 旅行社业务经营许可证吊销公告，项目内容应该包括旅行社名称、许可证编号、主要负责人(附件4)。 第五条暂停旅行社业务公告，由作出暂停决定的旅游行政管理部门发布。 暂停旅行社业务公告，项目内容应该包括旅行社名称、许可证编号、经营场所、暂停时间期限(附件5)。 第六条许可或暂停、取消旅行社经营出境旅游业务公告，由国家旅游局或其委托出境旅游业务许可的省、自治区、直辖市旅游行政管理部门发布。 许可旅行社经营出境旅游业务公告，项目内容应该包括旅行社名称、原许可证编号、新许可证编号、出资人、法定代表人、经营场所、许可文号（附件6）。 暂停旅行社经营出境旅游业务公告，项目内容应该包括旅行社名称、许可证编号、经营场所、暂停时间期限（附件7）。 取消旅行社经营出境旅游业务公告，项目内容应该包括旅行社名
2000年全国高中数学联合竞赛试卷 （10月15日上午8:00?9:40） 一、选择题（本题满分36分，每小题6分） 1．设全集是实数，若A={x|≤0}，B={x|10=10x}，则A∩?R B是() (A){2}(B){?1}(C){x|x≤2}(D)? 2．设sin?＞0，cos?＜0，且sin＞cos，则的取值范围是() (A)(2k?+，2k?+)，k?Z(B)(+，+)，k?Z (C)(2k?+，2k?+?)，k?Z(D)(2k?+，2k?+)∪(2k?+，2k?+?)，k?Z 3．已知点A为双曲线x2?y2=1的左顶点，点B和点C在双曲线的右分支上，△ABC是等边三角形，则△ABC的面积是() (A)(B)(C)3(D)6 4．给定正数p，q，a，b，c，其中p?q，若p，a，q是等比数列，p，b，c，q是等差数列，则一元二次方程bx2?2ax+c=0() (A)无实根(B)有两个相等实根(C)有两个同号相异实根(D)有两个异号实根 5．平面上整点（纵、横坐标都是整数的点）到直线y=x+的距离中的最小值是() (A)(B)(C)(D) 6．设ω=cos+i sin，则以?，?3，?7，?9为根的方程是() (A)x4+x3+x2+x+1=0(B)x4?x3+x2?x+1=0 (C)x4?x3?x2+x+1=0(D)x4+x3+x2?x?1=0 二．填空题（本题满分54分，每小题9分） 1．arcsin(sin2000?)=__________． 2．设a n是(3?)n的展开式中x项的系数(n=2，3，4，…)，则(++…+))=________. 3．等比数列a+log23，a+log43，a+log83的公比是____________. 4．在椭圆+=1(a＞b＞0)中，记左焦点为F，右顶点为A，短轴上方的端点为B.若该椭圆的离心率是，则∠ABF=_________. 5．一个球与正四面体的六条棱都相切，若正四面体的棱长为a，则这个球的体积是________. 6．如果：(1)a，b，c，d都属于{1，2，3，4}； (2)a?b，b?c，c?d，d?a； (3)a是a，b，c，d中的最小值， 那么，可以组成的不同的四位数的个数是_________ 三、解答题(本题满分60分，每小题20分) 1．设S n=1+2+3+…+n，n?N*，求f(n)=的最大值．
全国高中数学联赛试题 及解答 集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN]
2000年全国高中数学联合竞赛试卷 （10月15日上午8:009:40） 一、选择题（本题满分36分，每小题6分） 1．设全集是实数，若A={x|≤0}，B={x|10=10x}，则A∩R B是() (A){2}(B){1}(C){x|x≤2}(D) 2．设sin＞0，cos＜0，且sin＞cos，则的取值范围是() (A)(2k+，2k+)，k Z(B)(+，+)，k Z (C)(2k+，2k+)，k Z(D)(2k+，2k+)∪(2k+，2k+)，k Z 3．已知点A为双曲线x2y2=1的左顶点，点B和点C在双曲线的右分支上，△ABC是等边三角形，则△ABC的面积是() (A)(B)(C)3(D)6 4．给定正数p，q，a，b，c，其中pq，若p，a，q是等比数列，p，b，c，q是等差数列，则一元二次方程bx22ax+c=0() (A)无实根(B)有两个相等实根(C)有两个同号相异实根(D)有两个异号实根 5．平面上整点（纵、横坐标都是整数的点）到直线y=x+的距离中的最小值是() (A)(B)(C)(D) 6．设ω=cos+i sin，则以，3，7，9为根的方程是() (A)x4+x3+x2+x+1=0(B)x4x3+x2x+1=0 (C)x4x3x2+x+1=0(D)x4+x3+x2x1=0 二．填空题（本题满分54分，每小题9分） 1．arcsin(sin2000)=__________． 2．设a n是(3)n的展开式中x项的系数(n=2，3，4，…)，则(++… +))=________. 3．等比数列a+log23，a+log43，a+log83的公比是____________. 4．在椭圆+=1(a＞b＞0)中，记左焦点为F，右顶点为A，短轴上方的端点为B.若该椭圆的离心率是，则∠ABF=_________. 5．一个球与正四面体的六条棱都相切，若正四面体的棱长为a，则这个球的体积是________. 6．如果：(1)a，b，c，d都属于{1，2，3，4}； (2)ab，bc，cd，da； (3)a是a，b，c，d中的最小值， 那么，可以组成的不同的四位数的个数是_________ 三、解答题(本题满分60分，每小题20分) 1．设S n=1+2+3+…+n，n N*，求f(n)=的最大值．
浅谈数位类统计问题 山东省青岛第二中学刘聪 【摘要】 在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。 【关键字】 数位区间统计递推树二进制 【正文】 在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。 【例题1】Amount of degrees (ural 1057) 题目大意： 求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意： 17 = 24+20， 18 = 24+21， 20 = 24+22。 输入：第一行包含两个整数X和Y。接下来两行包含整数K和B。 输出：只包含一个整数，表示满足条件的数的个数。 数据规模：1 ≤ X ≤ Y ≤ 231?1，1 ≤ K ≤ 20，2 ≤ B ≤ 10。 分析： 所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。 很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。