歧路修远，上下求索――例谈信息学竞赛分析中的“深”与“广”
肖汉骏
指导教师
陈颖
福建省福州第一中学
高三（8）班
2008年1月
摘要
本文是作者对信息学竞赛新变化的一些思考和总结。着重阐述了信息学竞赛分析中“深”与“广”的特殊意义、做到这两点的方法，以及平常的学习过程中应该注意的一些地方。
关键词：思维方法，深入分析，多角度，归纳
目录
摘要i
目录ii
第一章汪洋恣肆：“深”与“广”在信息学中的意涵1
1.1何为“深”？ (1)
1.2何为“广” (1)
第二章谋定而后动：深入分析问题本质3
2.1例一：n位数枚举1 (3)
2.2例二：推箱子2 (6)
2.3将问题纵向延伸 (9)
第三章横看成岭侧成峰：多角度思考10
3.1例三：Caves and tunnels3 (10)
3.2例四：Paper4 (11)
3.3多作横向对比 (15)
第四章磨刀不误砍柴工：对程序设计学习的几点启示16
4.1培养良好的分析习惯 (16)
4.2多思考、勤交流 (16)
4.3正确对待经典问题 (16)
4.4适当的总结归纳 (17)
1原创问题
2原创问题
3Ural1553.Novosibirsk SU Contest.Petrozavodsk training camp,September2007
42004年第二届广东省大学生程序设计竞赛
目录iii 参考文献18致谢19
第一章汪洋恣肆：“深”与“广”在信息
学中的意涵
人们往往用“深”与”广“来形容海洋，但另一方面，人类的脑海却比任何一个大洋都来得深邃、来得广阔。作为思维分析能力充分展示的舞台，“深”与“广”在信息学竞赛中又有什么特殊的含义呢？又如何在分析中做到”深“与”广“呢？本文将和大家一同探索这些问题。
1.1何为“深”？
问题分析中的“深”，有这么几层意思：
一是层次性。一个问题在分析之初往往不那么容易，有的是高维数的，有的是条件复杂的。层次方面的观察就是要抓住问题的来龙去脉，从低维的情况、条件简化的情况来考察问题，得出一些性质。再由浅入深，分析这些性质在高维情况、条件复杂的情况下产生的变化，以求突破。
二是连贯性。分析问题的过程往往是漫长而坎坷的。有时候灵光一闪，似有所得，有时候又陷入困境，卒无所获。倘若走一步看一步，想到哪里就分析到哪里，思维就容易混乱，抓不到目标。反之，若能锲而不舍，沿着确定的方向步步深入，充分利用每一步分析的结果，就容易挖掘出一些有用的东西来。
三是注意要素之间的关系。哲学告诉我们，“事物是普遍联系的”。在信息学问题中，要素之间的关系也是值得深究的对象。问题并不是要素的简单相加，要素之间的相互关系也是客观存在的，而且更为本质和深刻。要素间诸如单调性、周期性等等关系，如果能有意识地深入研究，往往可以成为解题的突破口。
1.2何为“广”
而问题分析中的“广”，内涵就更为丰富：
第一章汪洋恣肆：“深”与“广”在信息学中的意涵2
一是开阔的眼界。在考场的仓促时间内，很多问题要获得完美的解决是困难的，甚至是不可能的。这就需要我们发挥想象力，运用各种策略解决问题。可以是随机化算法，也可以是贪心算法，甚至针对数据可能的形态，分别设计算法。随着策略的不同，程序的实际效果也大相庭径。
二是广阔的思路。一个相同的问题，从不同角度看往往有不同结果。如果能把不同角度的分析结果综合起来，就能较为全面地理解问题，一些隐蔽的信息在各个方向的探测下，也就没有了藏身之处了。
三是丰富的分析手段。分析手段是思维的利器，能抓出问题的本质所在。但是，就像每种武器都有自己的长处和短处，分析手段也有各自的特点。比如，数学推演精确但抽象，图形性质直观但不易量化。若能掌握各种分析手段，就似精通了十八般兵器的武林高手，“谈笑间，问题灰飞烟灭”。
第二章谋定而后动：深入分析问题本质
下面，以两道题为例，谈谈如何在问题分析中做到“深”。
2.1例一：n位数枚举1
问题描述：
统计所有n位数中，不包含数字0且被9整除的数的个数。
数据范围：
1 n 500
初步分析：
题目叫我们统计，很容易想到枚举算法。
算法一、在n位数中找枚举所有n位数，再判断是否包含数字0和被9整除；
时间复杂度：O(10n)
利用特殊条件深化分析：
注意问题中要求统计的是“不包含数字0”且“被9整除”的数，这便是问题的特殊条件。从这两个角度，可以得出两种不同的算法：
算法二、在9的n位数倍数中找利用被9整除这一条件，我们可以直接枚举这个n位数是9的多少倍，对范围内的倍数一一检查，效率至少是原来的9倍；
时间复杂度：O(10n)
1原创问题
第二章谋定而后动：深入分析问题本质4
算法三、在不含0的n位数中找如果我们把n位数看成是0～9的一个可重复的排列，那么不包括数字0的n位数，就是1～9的一个可重复的排列，再对这些n位数进行是否被9整除的判断；
时间复杂度：O(9n)
然而这些指数级别的算法，对于n的规模来说，显然是不够的。
由浅入深，层层递进：
回顾刚才的几种想法，算法一最简单直接不过；算法二利用了倍数的性质，只是稍有改进；算法三提出了把n位数看作是可重复排列的想法，自然地去除了0的干扰。但我们发现，算法二和三都是利用某个特殊性质，还未将两个性质结合起来使用。于是在算法三的基础上，结合9的倍数的特殊性质，我们提出算法四。
算法四、利用9的倍数的特殊性质被9整除的性质决定了n位数的数字和也要被9整除，而当前n?1位定下之后，由于1～9除以9的余数各不相同，最后一位实际上可以被唯一确定。至此，问题化为1～9的长度为n?1的可重复排列数是多少，答案也是显然的：9n?1。
时间复杂度：O(log n)2
至此，问题获完整解决。
枚举对象和效率的关系：
正如刚才我们所看到的，枚举也有低效和高效之分。然而造成这种区别的原因是什么呢？
如图2.1所示，A区域表示所有的n位数，B区域表示9的n位数倍数，C 区域表示不含0的n位数，D区域则是我们要统计的数的集合。从集合的观点来看，枚举的一般算法就是找到一个包含最终目标的集合，作为我们的枚举对象，例如图示中的集合A、B、C，然后对枚举出来的元素逐一检查，排除掉多余2采用快速幂算法，并假设高精度运算为O(1)
第二章谋定而后动：深入分析问题本质5
A
D
B C
图2.1:集合的角度
的部分，从而得到最终目标。而枚举效率的高低，就和枚举对象的选择息息相关了。如果对应集合的元素个数越多，则效率越低，反之，则效率越高。
以上文提到的四种算法为例：算法一几乎就是按照题目所叙述的直接操作，对应的集合A也是最大的；算法二和算法三分别把握住了问题某个方面的性质，但并不全面，所以时间复杂度只是稍有优化，对应的集合B、C稍有缩小；算法四则把算法二和算法三结合起来，创造性地建立起原问题和另外一个易于计数的问题的一一对应关系，直接计算出集合D的大小。
如何选择合适的枚举对象：
枚举对象的重要性已经被充分证明了，但是如何选择合适的枚举对象呢？其实从图2.1中可以得到一些启示：一开始，我们明确题意后，接触的仅仅是问题最原始的形态，如图中的A部分，枚举对象是粗糙的；随着我们对问题特殊性质的注意，并加以挖掘和利用，就有可能由表及里，得到较好的枚举对象，如图中的B、C部分；而当我们注意到问题多种性质间的区别和联系，就可以综合地把握住问题本质，真正选择出合适的枚举对象。
这个过程，实际上也就是对问题的分析步步深入的过程。我们分析地越深入，越接近问题的本质，就越可能找到简单的算法解决问题。在分析中对特殊性质的注意，对多种性质间相互关系的注意，能帮助我们更准确地把握住问题的内涵和外延，甚至实现算法的突破。
第二章谋定而后动：深入分析问题本质6 2.2例二：推箱子3
问题描述：
小Z是一个聪明且贪玩的孩子。一天，正当他在网上到处寻找乐趣的时候，一个经典但困难的游戏进入了他的视野――推箱子。
推箱子游戏是在一个由墙和空地组成的地图上进行的，其目的是要将所有箱子推到指定的位置。玩家控制一个小人，每次操作使小人向上下左右四个方向之一尝试移动。如果是空地，则只改变小人的位置；如果是箱子，且箱子的相同移动方向是空地，则小人和箱子同时移动一格；其余情况移动无效。
不看不知道，一看吓一跳，这个推箱子游戏的箱子数实在太多了！小Z看得头晕脑涨，于是他下决心只玩一个箱子的游戏。追求完美的他总是想用最少的操作完成游戏，你能帮助他完成这个游戏吗？
输入数据：
第一行是n,m,k，分别表示地图的行数、列数以及在这个地图上进行的游戏次数。
接下来n行m列描述这张地图。墙用’#’表示，空地用’.’表示。
接下来k行每行6个整数，分别表示小人、箱子和目标位置的行号和列号。
输入数据保证小人不能走出地图，且小人和箱子不会重合，也不在墙上。
输出数据：
对每一次游戏都输出一行，为完成这个游戏所需要的最小操作次数。如果不能完成游戏则输出’No Answer!’。
数据规模：
3 n,m 30
1 k 1000
3原创问题
第二章谋定而后动：深入分析问题本质7初步分析：
由于要求的是操作步数最少，就涉及到地形，箱子位置等诸多因素。在找不到合适的模型的情况下，搜索无疑是一种有益的尝试。
暴力搜索：
广度优先搜索。每次向四个方向进行移动尝试。基本的剪枝是避重性剪枝，搜索的一个状态可以用小人和箱子的坐标表示。如果碰到之前搜索过的就不必搜索了。
这个搜索的时间复杂度可以用状态的数量衡量，最坏情况下，小人和箱子的坐标可以取遍所有空地，故得：
时间复杂度：O(kn2m2)
两种移动的分离：
相对于问题的规模来说，算法一的复杂度还不尽人意。例一的分析过程提示我们，如果能发现问题独有的性质的话，可能会有新的突破。
再次回顾问题4，我们发现小人的运动实际上是有一定规律的：或者是为了推动箱子，或者是进行一系列移动，为下一次推动箱子做准备。然而我们的搜索程序并不能让我们的小人时时刻刻都遵守这两条规则。更多地，当小人不推动箱子时，它只是不住地上窜下跳。若强制让小人沿着最短路向它的下个目标走去，似乎可以避免不必要的搜索。
双重搜索：
根据上述思路，我们将搜索对象从操作本身转移到箱子的移动路线上。由于箱子移动之时小人必然在箱子四面的一面，故不同的状态数目也只有O(nm)了。而小人不推动箱子的路线，则可以通过一个额外的广搜解决。一般情况下，这个额外的广搜应该很快结束，程序效率提高得也很明显。然而在极端情况5下，这个广搜还是有可能遍历整个棋盘的。
4又或者多玩几盘推箱子游戏后...:-)
5比如死胡同什么的。
第二章谋定而后动：深入分析问题本质8
另外需要注意的是，由于我们并不是严格按照操作数从少到多扩展状态，故有时候对同一个状态需要重复搜索。但由于重复搜索的条件比较苛刻，对时间复杂度的影响微乎其微。
时间复杂度：O(kn2m2)
相同的地图：
分析到这里，问题似乎难以有所突破了。但是在之前提出的算法中，我们都没有利用一个性质：回答的是k个不同的问题，但使用的是一个相同的地图。不变的地图难道就没有不变的信息么？如果能通过某种预处理，将地图的信息挖掘出来，或许就能“柳暗花明又一村”。
从搜索到最短路：
在这个想法的启发下，再仔细琢磨之前的双重搜索，不由得让我们眼前一亮：那个额外的广搜所解决的部分，不就恰恰脱离了具体问题，而只跟地图有关么？只要事前枚举箱子的位置，进行必要的搜索和储存，在后面的k个问题中，就不需要新的搜索了。
然而分析并不能就此止步。小人不推动箱子的移动可以预处理，推动箱子的移动不也可以预处理么？如果我们将算法二中的每个状态作为点，而将若干操作达到的状态转移作为边，边权赋值为操作的次数，那么原问题就可以用简单的最短路模型表示了！需要注意的仅仅是起点、终点最多可能均有四个，只要增设新的起点、终点，问题并不难解决。
时间复杂度：O(n2m2+knm)6
回顾：
应该说，以上的三种算法，都是建立在分析的不断深化上，相互之间是有深刻联系的。如果没有暴力搜索的尝试，或许我们就不会发觉小人无谓的上窜下跳，从而将小人的两种操作分离开来；如果没有双重搜索中对状态表示的改进，可能我们就难以将搜索问题图论化，以全新的算法解决原题。
6使用SPFA算法，由于是稀疏图，且有很强的层次性，实际效果极好。
第二章谋定而后动：深入分析问题本质9
所以，“深入分析问题本质”的想法，还要求我们抓住那些尚未利用的性质和条件，寻找和原有分析结果结合的可能性，抽丝剥茧，一步步把问题本质揭露出来。
2.3将问题纵向延伸
值得一提的是，解题的成功不意味着问题的结束。适当地对问题增减条件，思考新情况下问题产生的变化，则更能深刻地理解问题。
以第二道例题为例，推箱子是大家都很熟悉的问题，而这个问题的一般解法就是迭代加深搜索，而表现比较好的优化就是文中所提及的双重搜索。作者正是在思考双重搜索的时间效率时，注意到第二重搜索只跟地图有关的性质，从而对问题加以变化，使得搜索问题得以图论化处理。
而第一道题也可以纵向延伸：问题中不包含的仅仅是数字0，整除性要求也仅仅是不被9整除。如果把不包含的数字推广到0～9的任意子集，整除性也推广到除以p的余数不能是r1,r2,···,r k。问题又将有新的变化。具体问题和解题报告可以参考我的原创比赛。
第三章横看成岭侧成峰：多角度思考
接下来，再以两道题为例，谈谈如何在问题分析中做到“广”。
3.1例三：Caves and tunnels1
问题描述：
给出一棵n个结点的树以及Q个操作。每个操作或者增加某个结点的权值，或者询问两个结点路径上的最大权值。权值一开始均为0。
数据规模：
1 n,Q 100000
分析：
如果是在线性表上进行操作，那么就是经典的动态RMQ问题，用线段树可以轻松解决。然而本题的操作对象却是一棵树。线性表的操作如何推广到树呢？是仿照线性表的解决方法进行分治？还是通过化归，用线性表解决？方法似乎有很多，我们可以一个个尝试。
树的分治：
注意到我们解决线性表问题时，采用的基本思想就是分治。当问题推广到树的时候，对树进行分治似乎也是种不错的想法。
然而稍加尝试就会发现，由于树不具备线性性质，分治点和询问点的关系难以表达。故不能和线性表一样，在区间被包含时直接将区间的统计数据调出。多方努力无果后，分治的尝试宣告失败。
1Ural1553.Novosibirsk SU Contest.Petrozavodsk training camp,September2007
第三章横看成岭侧成峰：多角度思考11化归到线性表：
另外一种想法，就是将问题化归到线性表上解决。“树内任意两点只有一条路径”，这个性质也的确和线性表有关系。
最简单的想法，就是为每个询问到的路径都建立一张线性表。这当然太慢了：路径数实在太多。但是，如果把路径数缩小一些呢？
在这个想法的启发下，我们任意指定树中一点为根，就可以把连接两点的路径以它们的最近公共祖先为分界点，分为两段处理。这样，所有的路径都指向根。如果为每个结点到根的路径都建立一张线性表，诚然可以解决问题，但其时空代价却难以承受。有没有更好的方法呢？
两种想法的结合：
刚才的两种想法，虽然都没有解决问题，但其中的思路却是可以借鉴的。多角度思考并不是打一枪换一炮，有意识地寻找不同想法结合的可能，或许可以打开局面，走出困境。
注意到线性表的想法之所以遇到阻碍，乃是因为建立的表的数量实在太多。而分治不恰恰就是减少问题规模的利器么？在这个思路的启发下，我们每次为当前树中最深的叶子结点到根的路径制作线性表，其余的分叉递归处理。就是将一棵树看成是由多个链组成的。将一颗树上的问题转化到多个链上的问题。可以证明，每次询问涉及到的线性表数目最坏情况下是O (√n )的。
时间复杂度：O (Q √n )
3.2例四：Paper 2
问题描述：
小D 要读n 篇文章，每篇文章有一个阅读时间T i ，价值V i ．读一篇文章的代价为从0时刻到读完这篇文章的时间乘上它的价值，小D 希望安排一个读文章的顺序使得总的读文章的代价最小．
22004年第二届广东省大学生程序设计竞赛
第三章横看成岭侧成峰：多角度思考12
图3.1:交换顺序之后
另外，有一些文章的作者是相同的，小D希望按照这个作者写文章的先后顺序来读这些文章．
数据规模：
1 n 50000
初步分析：
这个问题要求的是一个最佳的阅读顺序，使得总代价最小。但又附加了一定限制，即同一作者所写的文章要按时间顺序阅读。
直接考虑问题本身似乎不容易找到很好的方向，所以我们不妨先尝试弱化条件，由浅入深地解决原问题。
去除限制条件：
我们尝试去除作者因素，考虑这个特殊情况下问题的解。
问题要我们求一个最优序列。显然，最优序列不是胡乱排列的，这个序列必然有某种特殊处，才使得它成为最优。而最优序列的特殊之处就在于：经过任意改变后，得到的结果都不比原序列优。
在序列中最简单的改变莫过于交换相邻元素了3。我们就照着这个思路进行深入分析：
考察相邻的两本书，设它们的阅读时间为T1,T2，价值为V1,V2。如图3.1所示，交换这两本书的阅读顺序后，第一本书的阅读完成时间推迟了T2，第二本书则提前了T1，所以，总代价的变化为T2V1?T1V2。
对于最优序列，一定有T2V1>T1V2，也即V1
T1>V2
T2
。相邻两项有这个关系，
3只改变两个元素，其余元素都不影响。
第三章横看成岭侧成峰：多角度思考13
那么，整个序列不就是按照V i
i
从大到小的顺序排列么？至此，特殊情况已被轻松解决。
最特殊的一般情况：
回到一般情况，我们该如何处理作者因素对阅读顺序的影响？仍然应用从特殊到一般的思想展开分析：
在所有一般情况中，只有一个作者的情况是最特殊的，但其顺序已被固定，没有研究的价值；接下来，就是只有两个作者的情况了。而在所有两个作者的情况中，某位作者只写了一篇文章的情况又最为特殊。我们不妨来考察一下这篇独立文章应何时阅读。
同样的，我们通过研究任意改变后的总代价的变化，考察最优阅读顺序所应具有的特殊性质。由于相同作者的文章顺序固定，不可改变，所以，改变必须包括那篇独立文章。而根据刚才的分析，最优序列中相邻的可交换元素满足关系：
V i T i >
V i+1
T i+1
也即，独立文章的比值要小于前面的，大于后面的。然而这又意味着什么呢？单纯从数学推演的角度出发，满足上式的位置可能有很多，没有好的性质能够加以利用。而二元组比值的形式，不禁促使我们联想到直线的斜率。这里，不妨把问题图形化，用广泛的分析手段尝试解决问题。
以形助数：
我们将每篇文章看作一个向量(T i,V i)，则比值V i
T i
就是这个向量的斜率。我们将这些向量首尾相接，在平面直角坐标系中表示出来。那么，独立文章的插入位置在图形中可以形象地表示为“凸点”，如图3.2：
当然，只注意问题一个方面的性质是有悖于“广”的要求的。注意那些不可插入位置，它们在图形中表示为“凹点”。容易用反证法证明，凹点是不能被新的文章插入的4。也就是说，一旦出现凹点，就可以把形成凹点的两个向量合并，去除这个凹点。
4否则与前面或者后面的向量交换，得到的解更优。
第三章横看成岭侧成峰：多角度思考14
图3.2:以形助数
而什么图形不包含凹点呢？是的，就是凸包！而凸包上边的斜率，恰恰是单调递减的！可以预感，我们离最终的答案只有一步之遥。
最终算法：
分别处理每一个作者，求出文章形成的凸包。则该作者所写的文章被凸包上的点划分为若干段，每段的斜率单调递减。而后把所有文章段按斜率降序排序，即为所求的最优序列。容易证明这个序列是合法的，因为相同作者所写的文章段本身就满足斜率降序，故排序不会破坏写作的先后顺序。
时间复杂度：O(n log n)
回顾：
回顾这道题的解决过程：
1.我们先去除了限制条件，从特殊情况着眼，得出了最优序列相邻元素之间
的关系
2.在一般情况中，我们又选取了最为特殊的两作者情况讨论。得出了插入位
置的数学性质。
3.随后又运用了数形结合的分析方法，从正反两个方面考察了凸点和凹点。
第三章横看成岭侧成峰：多角度思考15
4.最后联想到凸包，一气呵成地解决问题。
可以看到，问题解决过程中的每一步，都或多或少地和“深”和“广”有所联系。
多角度思考实际上就是力求分析的广度，但这并不是说从不同角度孤立地看问题。而是针对问题本身不同侧面的性质，综合地把握住它的内涵和外延、特殊处与一般处。利用多个性质、多个模型解题的时候，也不是简单地相加、盲目地套用，而是将它们有机地、创造性地组合起来，才能起到最好的效果。
3.3多作横向对比
而在平常的训练过程中，也不要只满足于一种解法。多吸收他人分析中的独特之处，在适当的时候尝试一下，就能起到开阔思路的作用。以前想不到的地方，在接受了新的想法之后，就可能比较轻松的考虑到。
另一方面，不同解法的相互比较也十分重要。不同解法的效果往往不尽相同，若能分析出产生差异的原因，对不同解法的认识也会更加深刻。遇到一题多解的时候，也能更加全面地考虑不同解法的特点，使得决策更为容易。
第四章磨刀不误砍柴工：对程序设计学
习的几点启示
4.1培养良好的分析习惯
在平常的解题实践中，我们往往依靠经验、不自觉地使用各种分析方法。然而效果时好时坏，难以把握。这正说明了零碎的经验，是不能代替系统的理论的。若能在分析过程中遵循一定的规则，做到有理、有序地分析，就能避免凭借经验带来的不稳定性，这也正是良好的分析习惯带来的最大好处。
4.2多思考、勤交流
正如前文所述，思考分析的深度和广度，决定了问题解决的好坏。另一方面，信息学竞赛的最终目的，也是培养选手的思维能力。所以，在平常的训练和学习过程中，对问题自觉地从多个角度作深入分析，是很有好处的。同时需要注意的是，如果只是自己单干，或者是小集团内部封闭式的交流，则不容易打开思路，吸收新鲜的想法。反之，若能广泛地了解他人对同一道问题的思路，则有助于更加灵活地分析问题。
至于交流的途径，则不必有所拘束，大可以各显神通。在信息资源丰富、联系日趋快捷的今天，我们既可以从书本和论文中汲取养分，也可以从网络上去粗取精；既可以面对面地讨论，也可以在网络上跨空间的交流。方式可以多样，但目的都是为了提高自己的思维能力。相信只要持之以恒，必然会有一定提高。
4.3正确对待经典问题
经典问题之所以“经典”，不单是因为其常见，更是因为其中蕴含着基本但重要的信息学思维方法。然而在日常的训练中，经典问题往往只被我们当
“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 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卡的发放管理，制定本办法。
左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (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
国家旅游局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日
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）。 取消旅行社经营出境旅游业务公告，项目内容应该包括旅行社名
浅谈数位类统计问题 山东省青岛第二中学刘聪 【摘要】 在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。 【关键字】 数位区间统计递推树二进制 【正文】 在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个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)级别，因此我们要从数位上下手。
国家旅游局公告2017年第21号――许可旅行社经营出境旅 游业务公告 【法规类别】旅游综合规定 【发文字号】国家旅游局公告2017年第21号 【发布部门】国家旅游局 【发布日期】2017.09.12 【实施日期】2017.09.12 【时效性】现行有效 【效力级别】部门规范性文件 国家旅游局公告 （2017年第21号） 许可旅行社经营出境旅游业务公告 按照《旅行社条例》和《中国公民出国旅游管理办法》，许可以下70家旅行社经营出境旅游业务： 旧许可证编号新许可证 编号 出资人 法 定 代 表 经营场所许可文号
人 L-FJ50023 L-FJ-CJ00127 福建中旅旅 行社有限公 司 王丽美 南平市滨江大道商联大 厦一楼（府前路1号） 旅发 ﹝2017﹞86 号 2 武夷山中旅旅行社有限 公司 L-FJ50001 L-FJ-CJ00128 福建省中国 旅行社 陈萍 福建省武夷山市度假区 武夷宫 旅发 ﹝2017﹞86 号 3 厦门友客国际旅行社有 限公司 L-FJ20202 L-FJ-CJ00129 厦门欣欣信 息有限公司 赖 润 星 厦门市海沧区海景东路 2号9C5楼 旅发 ﹝2017﹞86 号 4 厦门青普国际旅行社有 限公司 L-FJ20216 L-FJ-CJ00124 北京青普旅 游文化发展 有限公司 杨雪山 中国（福建）自由贸易 试验区厦门片区湖里大 道24号海山商务中心 1202-E 单元 旅发 ﹝2017﹞76 号 5 山西大唐航 空国际旅行 社有限公司 L-SX00983 L-SX-CJ117 唐中诗 唐中诗 晋中市太谷县西环中路 53号 旅发 ﹝2017﹞ 105号 6 温州市教育旅游有限公 司 L-ZJ00726 L-ZJ-CJ00236 董滨/叶芬 董滨 温州市鹿城区惠民路上陡门教育新村综合楼121-123号 旅发﹝2017﹞76号 7 北京奥阿希斯旅游有限 公司 L-BJ01192 L-BJ-CJ00861 姚强、魏红日、刘亚杰 姚 强 北京市朝阳区阜通东大街6号院5号楼10层1108 旅发 ﹝2017﹞82号 8 北京四海之旅国际旅行社有限责任公司 L-BJ01052 L-BJ-CJ00862 金峦、肖季 红、任亚全 肖 季 红 北京市朝阳区霞光里66 号院1号楼3层09号 旅发﹝2017﹞82 号 9 凯撒（北京）国际会议展览有限责任公司 L-BJ01717 L-BJ-CJ00863 北京凯撒国 际旅行社有 限责任公司 魏 灵 北京市朝阳区东三环中 路25号16层1616室 旅发 ﹝2017﹞82 号 10 神州假期国际旅行社（北京）有限公司 L-BJ01779 L-BJ-CJ00864 赵林、曲超 赵 林 北京市朝阳区石门村路二院（库区）24幢4层430室 旅发 ﹝2017﹞82号 11 北京鑫路国 际商务旅行社有限公司 L-BJ01433 L-BJ-CJ00865 王庆波 王 庆波 北京市东城区东兴隆街 58号6层609 旅发﹝2017﹞82 号 12 联盟平台L-L-BJ-赵洋、王怀 赵 北京市朝阳区左家庄15旅发
线段树的应用 广西柳铁一中林涛 【摘要】 在竞赛解题中，常遇到与区间有关的操作，比如统计若干矩形并的面积，记录一个区间的最值、总量，并在区间的插入、删除和修改中维护这些最值、总量。 线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍线段树的各种操作以及一些推广。 本文通过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)中，对于任意线段也用归纳法证明。 对于单位区间，最多分为一段，成立。 若(a，b)的左儿子与右儿子均成立，则对于线段(c，d) 1．若d<=(a+b)div 2 则该区间所分该线段等于其左儿子区间所分该线段，线段数小于log((a+b) div 2-a)<2log(b-a)，成立。 2．若c>(a+b) div 2 则该区间所分该线段等于其右儿子区间所分该线段，线段数小于log(b-(a+b) div 2)<2log(b-a)，成立。 3．若1、2均不成立，则此线段在左儿子区间分该线段满足d>V.Lson.b,分该线段数不超过log(b-(a+b) div 2)，而在右儿子区间分该线段满 足c<=V.Rson.a,分该线段不超过log((a+b) div 2-1)，所以在该区间 分该线段不超过2log(b-a)，成立。 这个结论为线段树能在O(log L)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据。 【例题一】蛇1 在平面上有N个点，现在要求一些线段，使其满足以下要求： a．这些线段必须闭合 b．线段的端点只能是这N个点 c．交于一点的两条线段成90度角 d．线段都必须平行于坐标轴 e．所有线段除在这N个点外不自交 f．所有线段的长度之和必须最短 如果存在这样的线段，则输出最小长度，否则输出0。 【问题分析】 从该题的要求入手，先构出符合要求的图，再解决线段长度之和最小的问题。1．题目显然要求一个以给定的N个点为顶点的N多边形。所有线段都要和坐标轴平行，所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成90度，每个顶点必须与一条平行于X轴和一条平行于Y轴的线段相连。 2．将所有点排序后发现，在同一水平线上的点中，设这些点为P1，P2，P3，P4……Pn，P1要有一条平行于X轴的线段与其相连，就必须连它右边的点——P2，而P3如果再连P2，P2就有两条平行于X轴的线段和它相连，所以P3只能连P4，P5只能连P6……，同一垂直线上的点也是如此，所以线段的构造是唯一的，那么最小长度的问题就解决了。 3．由于解是唯一的，而是否相连只要广度扩展就可以判断了，所以关键在于判断由上述方法所构出线段是否合法——满足线段不在N个点之外自交： 1Saratov State University Problem Archive, 1028, Snake. 本题考查了基本的插入、删除和查找
NOI 国家集训队论文分类（至2008） 摘抄自 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- 杨思雨：《伸展树的基本操作与应用》 图论 图论 2005- 任恺：《图论的基本思想及方法》
伸展树的基本操作与应用 安徽省芜湖一中杨思雨 目录 【关键字】 (2) 【摘要】 (2) 【引言】 (2) 【伸展树的基本操作】 (2) 伸展操作Splay(x,S) (3) 伸展树的基本操作 (4) 时间复杂度分析 (5) 【伸展树的应用】 (7) 【总结】 (8) 【参考书目】 (9) 【附录】 (9)
【关键字】 伸展树基本操作应用 【摘要】 本文主要介绍了伸展树的基本操作以及其在解题中的应用。全文可以分为以下四个部分。 第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要地位，并且指出二叉查找树在某些情况下时间复杂度较高，进而引出了在时间复杂度上更为优秀的伸展树。 第二部分介绍了伸展树的基本操作。并给出了对伸展树时间复杂度的分析和证明，指出伸展树的各种基本操作的平摊复杂度均为O(log n)，说明伸展树是一种较平衡的二叉查找树。 第三部分通过一个例子介绍了伸展树在解题中的应用，并将它与其它树状数据结构进行了对比。 第四部分指出了伸展树的优点，总结全文。 【引言】 二叉查找树（Binary Search Tree）能够支持多种动态集合操作。因此，在信息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。 作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含n 各节点的完全二叉树，这些操作的最坏情况运行时间为O(log n)。但如果树是含n个节点的线性链，则这些操作的最坏情况运行时间为O(n)。而有些二叉查找树的变形，其基本操作在最坏情况下性能依然很好，比如红黑树、A VL树等等。 本文将要介绍的伸展树（Splay Tree），也是对二叉查找树的一种改进，虽然它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。 【伸展树的基本操作】 伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)。