组合游戏略述
——浅谈SG游戏的若干拓展及变形
石家庄二中贾志豪
前言
组合游戏是近几年新兴起的博弈游戏，随着张一飞学长关于组合游戏的论文的面世，组合游戏问题开始在国内信息学竞赛这片沃土上生根发芽，与大家一起成长、成熟、成才。最为马上要离开高中信息学舞台的高三学生，我一直希望能为学弟学妹们留下一些我自己的心得，于是这篇论文应运而生！！！
这篇论文的一些思想是我早在一年前节开始构思的，感谢计算机学会为我提供这样一个舞台，能让我的论文为更多的人所知道；同时感谢在我写论文时无私帮助过我的所有人，谢谢你们！！！
先介绍一下论文的主要内容：第一章作为论文的理论基础，主要从欣赏的角度引入了SG函数、游戏图、NIM游戏等概念，重点谈我对组合游戏尤其是SG函数的体会、理解；第二章主要介绍了几种不同规则的组合游戏以及相应的应对策略，旨在告诉读者，游戏规则变化之后，我们应该如何去分析新的规则、解决新的模型；第三章主要介绍了几种竞赛中常见的组合模型，并将“她”们成功的转化成了NIM模型。
鉴于这篇论文的内容较多，在这里给读者提供一些阅读建议：第一章由于篇幅原因，并没有给出SG函数、NIM游戏解法的详细证明过程，对于刚刚接触组合游戏的读者，建议先阅读一些关于SG函数的资料（张一飞关于博弈游戏的论文1、王晓柯关于组合游戏的论文2就很不错），然后再从论文的第一章看起，相信你一定会很有收获；第二、三章是论文的重头戏，如题目所言，分别谈SG游戏的拓展和变形，对于钟情于组合游戏的读者，可以重点看一看第三章，相信一定不会让你失望！！！
这篇论文主要有两个特点：
基本没有例题但处处是例子。为了让读者更好的理解论文中的思想，笔者在选题目的时候刻意将题目的背景剥掉，只剩下一个“光溜溜”的数
学模型，这样读者在阅读论文时，就不必花精力去考虑背景向模型的转
化，可以全身心去理解笔者想要传达的思想。但读者不必去担心没有地
方练习，笔者将这几年的自己做过的组合游戏题收录在了论文的附录
里。
1《由感性认识到理性认识——透析一类搏弈游戏的解答过程》，张一飞，国家集训队2002论文
2《解析一类组合游戏》，.王晓珂，国家集训队2007论文
每一个模型都有详细的证明。大多数人在学习信息学时存在的问题是“知其然，不知其所以然”，因为大多数的比赛模式是只要求结果而不
要求过程。但这会使我们对一个事物“只知表皮，不知深髓”，如果将
一个我们知道的问题稍加变形的话，我们可能就不会了。这个问题在组
合游戏中体现得尤其突出。因此笔者对于文中的每一个定理都给出了证
明，希望读者对文中的思想“知其然，知其所以然”。
为了方便大家阅读，我将论文中所有的定理表述做成了“HELLO WORLD”将所有的定义表述做成了“HELLO WORLD”，希望这样的改动能引起大家的注意和兴
趣。
目录
感谢 (4)
Chapter 1 (5)
1.1本论文讨论的范围 (5)
1.2组合游戏中状态空间向图的转化 (6)
1.3简介SG函数 (6)
1.4定义NIM-模型 (7)
Chapter 2 (9)
2.1走完最后一步者输——Anti-SG游戏和SJ定理 (9)
2.2可以将一堆石子分成多堆——Multi-SG游戏 (14)
2.3每一个可以移动的棋子都要移动——Every-SG游戏 (14)
Chapter 3 (18)
3.1翻硬币游戏 (18)
3.2无向图删边游戏 (19)
3.2.1树的删边游戏 (19)
3.2.2 Christmas Game(PKU3710) (21)
3.2.3 无向图的删边游戏 (23)
参考资料 (24)
附录 (24)
关键字
SG函数NIM模型Anti游戏
Multi游戏Every游戏翻硬币游戏
删边游戏证明拓展
感谢
谨以此论文献给：
●我的初中同班同学，集训队队员，对ppt内容提出宝贵意见的李骥扬同学●我的高中同班同学，集训队队员，给论文指出多处缺点的武森同学
●我的学长，北京大学学生，认真修改过我论文ppt的周先达同学
●我的学长，复旦大学学生，认真阅读过论文修订版的杨敏达同学
●在我生病时送我去医院，认真辅导我信息学的韩日旺老师
●在我上高一时及时指出我的缺点，辛勤辅导我信息学的李晶老师
●与我交流论文内容的唐文斌、胡伟栋教练
向以上所有人表示我最诚挚的谢意！！！
谢谢所有在我信息学道路上对我有帮助的人！！！
●C hapter 1
1.1本论文讨论的范围
本论文主要讨论一类组合游戏问题的解法，这列问题具有如下特征：
●游戏有两个人参与，二者轮流做出决策。且这两个人的决策都对
自己最有利。
●当有一人无法做出决策时游戏结束，无法做出决策的人输。无论
二者如何做出决策，游戏可以在有限步内结束。
●游戏中的同一个状态不可能多次抵达。且游戏不会有平局出现。
●任意一个游戏者在某一确定状态可以作出的决策集合只与当前
的状态有关，而与游戏者无关。
这样一类游戏可以用SG函数解决，我们将其称之为SG-组合游戏。
对“最有利”的解释：本文所说的最有利，是指对于当前要做出决策的游戏者，如果他存在一种决策，使得后手进入到一个无论怎样做出
决策都一定会输的的状态，那么结局一定是当前的游戏者胜！
中国有句古话——“智者千虑，必有一失”，而组合游戏中的游戏者却可以做到“运筹帷幄，决胜千里”。不得不说，正是组合游戏中的“智
者”吸引着我们去探索、发觉组合游戏中的魅力！
1.2组合游戏中状态空间向图的转化
我们可以将组合游戏中的每一个状态抽象成图中的一个点，将每一步决策抽象成图中的一条边。我们将这个图称为该组合游戏的游戏图。
这样，对于组合游戏中的每一次对弈，我们都可以将其抽象成游戏图中的一条从某一顶点到出度为0的点的路径。
组合游戏向图的转化，并不单单只是为了寻找一种对应关系，它可
以帮助我们淡化游戏的实际背景，强化游戏的数学模型，更加突出游戏的数学本质！
1.3简介SG函数
SG函数是对游戏图中每一个节点的评估函数。它的定义如下：
f
mex
v
f=
图中有一条从u
v
u
(
|)
{
)
(的边
}
到
其中，mex（minimal excludant）是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。
k
k
mex∈
?
A
=
∧
k
|
A
m in{
}
}
{N
事实上，所有的SG-组合游戏都存在相应的游戏图，我们完全可以根据游戏图的拓扑关系来逐一算出每一个状态点的SG函数（事实上我们只需要知道该状态点的SG函数值是否为0）。这样，我们就可以知道对于某一个状态，是先手必胜局还是先手必败局。这是不是说明我们已经将SG-组合游戏完满解决了呢？
显然不是！！！
因为我们不光要考虑算法的正确性，还要考虑算法的时空开销，而上述方法显然没有考虑算法的时空开销，上述方法的瓶颈在于没有充分利用SG-组合游戏问题的特殊性质。
我们先引出游戏的和的概念。
[定义]
游戏的和：考虑任意多个同时进行的SG-组合游戏，这些SG-组合游戏的和是这样一个SG-组合游戏，在它进行的过程中，游戏者可以任意挑选其中的一个单一游戏进行决策，最终，没有办法进行决策的人输。
■
上述方法在计算K个单一SG-组合游戏的和时，所消耗的时间、空间复杂度是分别计算这K个单一SG-组合游戏所消耗的时间、空间复杂度的乘积。
但如果我们能更好的利用SG-组合游戏的性质的话，我们可以将上一段的最后一字——“积”——改成“和”。这就是我们继续研究SG-函数的意义，也是这篇论文的意义所在。
最后我们直接给出SG函数的性质：
（1）对于任意的局面，如果它的SG值为0，那么它的任何一个后继局面的SG值不为0；
（2）对于任意的局面，如果它的SG值不为0，那么它一定有一个后继局面的SG值为0。
1.4定义NIM-模型
为了不使读者对本篇论文失去兴趣，我特意将介绍取石子游戏的内容换成小字，对这部分内容已经很熟悉的读者可以直接略过。
取石子游戏即著名的nim游戏，游戏规则如下：
?桌子上有N堆石子，游戏者轮流取石子。
?每次只能从一堆中取出任意数目的石子，但不能不取。
?取走最后一个石子者胜。
这道题每一堆石子的SG函数值很显然为该堆石子的数目，根据SG函数的特点，最后所有堆石子的SG函数的和
_
_⊕
1
=
⊕
⊕
_
SG
SG
n
SG
tot
...
SG_
2
最后，先手胜当且仅当该值为0。证明从略。
取石子游戏虽然是组合游戏中一道最基础的题目，但是它却代表了一类经典的组合模型。
事实上，每一个简单SG-组合游戏都可以完全等效成一堆数目为K 的石子，其中K为该简单游戏的SG函数值。这样的等效是充要的。
[定理]
在我们每次只能进行一步操作的情况下，对于任何的游戏的和，我们若将其中的任一单一SG-组合游戏换成数目为它的SG值的一堆石子，该单一SG-组合游戏的规则变成取石子游戏的规则（可以任意取，甚至取完），则游戏的和的胜负情况不变。
这是SG函数的基本性质，证明可参阅相关资料。
定理的一个变形是：若只考虑游戏的和，我们可以将其中的任一游戏换成SG值相等的其他游戏，游戏的和的SG函数值不变。
定理告诉我们，在考虑游戏的和时，每一个单一游戏的具体细节是可以被忽略的，我们所关心的只是SG函数值。所以我们可以将组成它的所有子游戏换成相应数目的一堆石子。这样，所有的游戏的和都等价成nim游戏。
为了以后论文的方便，我们将以后的所有例题都抽象成NIM-模型。抽象成NIM-模型后，剩下的问题就是我们所熟悉的nim游戏了。
●C hapter 2
2.1走完最后一步者输——Anti-SG游戏和SJ定理
在谁走完最后一步谁输时，如何判断输赢？
刚拿到这个问题，大多数人可能会认为要颠覆传统的SG函数解法，设计新的评估函数。
我们不妨先从最本质的nim游戏寻找突破口。
[定义]（anti-nim游戏）
?桌子上有N堆石子，游戏者轮流取石子。
?每次只能从一堆中取出任意数目的石子，但不能不取。
?取走最后一个石子者败。
[结论]
先手必胜当且仅当：
（1）所有堆的石子数都为1且游戏的SG值为0；
（2）有些堆的石子数大于1且游戏的SG值不为0。
[证明]
游戏分两种情况：
●有N个堆，每个堆只有一个石子。
显然，先手必胜当且仅当N为偶数。
●其他情况。
（1）当SG不为0时
若还有至少两堆石子的数目大于1，则先手将SG值变为0即可；
若只有一堆石子数大于1，则先手总可以将状态变为有奇数个1。所
以，当SG不为0时先手必胜。
（2）当SG为0时
至少有两堆石子的数目大于1，则先手决策完之后，必定至少有一堆的石子数大于1，且SG值不为0，由上段的论证我们可以发现，此时，无论先手如何决策，都只会将游戏带入先手必胜局，所以先手必败。
■
上述关于anti-nim游戏的推导只对anti-nim这一简单游戏成立。因为我们在证明SG函数性质时，用到了这样一个性质
SG值为0的局面不一定为终止局面。
所以，上述论证能否推广到所有SG-组合游戏，我们是需要从新给出论证的。
我们现在已经充分了解到了nim游戏与SG函数之间的内在联系，所以我们很自然的会想到下述命题：
[命题]
先手必胜当且仅当：
（1）所有单一游戏的SG值小于2且游戏的SG值为0；
（2）存在单一游戏的SG值大于1且游戏的SG值不为0。
很遗憾，这是一个错命题！
我们考虑图1给出的游戏图。
图1（旁边数字为节点的SG值）
最右边的点对应的局面为先手必胜情况中的（1），但聪明的读者可以发现，该情况应对应先手必败！
那么是不是我们对于组合游戏中的ANTI情况没有任何办法呢？
不是的！
我们可以总结出SG组合游戏中哪些情况会给出反例，然后将该命题适当的做一些修改。我在这里给出适用于Anti-SG组合游戏的SJ定理（Sprague Grundy——Jia Zhihao定理）
我们先给出Anti-SG游戏的定义：
[定义]
●Anti-SG游戏规定，决策集合为空的游戏者赢。
●Anti-SG其他规则与SG游戏相同。
[定理]（SJ定理）
对于任意一个Anti-SG游戏，如果我们规定当局面中所有的单一游戏的SG值为0时，游戏结束，则先手必胜当且仅当：（1）游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1；（2）游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。
[证明]
我们只需要证明：
（1）所有的终止局面为先手必胜局。（这一点显然，证明中略去）
（2）游戏中的任何一个先手必败局一定只能够转移到先手必胜局；
（3）游戏中的任何一个先手必胜局一定能够转移到至少一个先手必败局。
情况一：局面的SG函数为0且游戏中某个单一游戏的SG函数大于1。
∵当前局面的SG函数值为0
又∵SG函数性质（1）
∴它所能转移到的任何一个局面的SG函数值不为0 ①
∵当前局面的SG函数值为0且游戏中某个单一游戏的SG函数大于1。
∴当前局面中必定至少有2个单一游戏的SG函数大于1。
又∵每次至多只能更改一个单一游戏的SG值
∴它所能转移到的任何一个局面都至少有一个单一游戏的SG值大于1。②
由①②得，情况一所能转移到的任何一个局面都为先手必胜局。
情况二：局面的SG函数不为0且游戏中没有单一游戏的SG函数大于1。
显然，当前局面一定有奇数个游戏的SG函数值为1，其余游戏的SG 函数值为0。
（1）将某个单一游戏的SG值更改为大于1的数。
∵转移前没有单一游戏的SG值大与1，转移将某个单一游戏的SG 值更改为大于1的数。
∴转移后的局面一定有且只有一个单一游戏的SG值大于1。③
∴后继局面的SG值一定不为0。④
由③④得，后继局面一定为先手必胜局。
（2）将某个单一游戏的SG值更改为0或1。
∵转移是将某个SG值为0的单一游戏改成SG值为1的单一游戏，或将某个SG值为1的单一游戏改成SG值为0的单一游戏。
∴转移后的局面一定有偶数个SG值为1的单一局面且不含有SG值大于1的局面。
∴后继局面一定为先手必胜局。
情况三：局面的SG函数不为0且游戏中某个单一游戏的SG函数大于1。
（1）局面中只有1个单一游戏的SG值大于1。
我们选择更改SG值最大的单一游戏，我们可以选择将其更改成0或1来保证转移后的局面有且只有奇数个SG值为1的单一游戏。
则通过这种方式转以后的局面为先手必败局。
（2）局面中有至少两个单一游戏的SG值大于1。
根据SG函数性质（2），总存在一种决策可以将后继局面的SG函数值变为0 ⑤
∵局面中有至少两个单一游戏的SG值大于1
又∵每次最多只能更改一个单一游戏的SG值
∴后继局面中至少有一个游戏的SG值大于1 ⑥
由⑤⑥得，后继局面为先手必败局。
情况四：局面的SG函数为0且游戏中没有单一游戏的SG函数大于1。
当局面中所有单一游戏的SG值为0时，游戏结束，先手必胜。
否则，局面有且仅有偶数个SG值为1的单一游戏，其余游戏的SG 值为0。
我们只需将其中的某一个SG值为1的单一游戏的SG值变为0，游戏中即可出现奇数个SG值为1的单一游戏，到达先手必败局。
综上，证明完毕！
■
实际上，聪明的读者可能会发现，我们在SJ定理中给出的附加条件“规定当局面中所有的单一游戏的SG值为0时，游戏结束”过于严格，完全可以替换成“当局面中所有的单一游戏的SG值为0时，存在一个单一游戏它的SG函数能通过一次操作变为1”。
笔者为什么要将限制条件设制成这样？
因为笔者发现这样可以出题，我们可以将题目模型设成这样：游戏中存在一个按钮，游戏双方都可以触动按钮，当其中一个人触动按钮时，触动按钮的人每次必须移动对方上次移动的棋子。如果触动按钮的人能保证他能够使得对方无路可走，那么他同样获胜！
2.2可以将一堆石子分成多堆——Multi-SG游戏
遇到这种情况是我们该怎么办呢？
可能聪明的读者马上就会想到，可以通过将SG函数适当变形来解决这类问题。
您的想法完全正确！！！
我们先来定义Multi-SG游戏。
[定义]
●Multi-SG游戏规定，在符合拓扑原则的前提下，一个单一游戏
的后继可以为多个单一游戏。
●Multi-SG其他规则与SG游戏相同。
我们只需证明，我们仍然可以用SG函数来定义局面。
这个证明很简单，因为局面在游戏树中满足拓扑关系，我们可以根据拓扑关系用数学归纳法来做。因为前面已经用数学归纳法证明过一个定理，因此这个定理的证明我们就留给聪明的读者了。
2.3每一个可以移动的棋子都要移动——Every-SG游戏
如果每一个可以移动的棋子都要移动，我们应该怎么办呢？
聪明的读者肯定能够想到这样一个策略：对于我们可以赢的单一游戏，我们一定要拿到这一场游戏的胜利！！
所以，我们只需要考虑如何让我们必胜的游戏尽可能长的玩下去。
但是对手却不希望他必败的单一游戏玩的太久，这就是Every-SG游戏不同于其他SG游戏的地方：一般的SG游戏只有胜与负之间的博弈，而Every-SG游戏又添加了长与短之间的博弈，这使得Every-SG游戏更有嚼头，更有味道。
我们先来定义Every-SG游戏。
[定义]
● Every-SG 游戏规定，对于还没有结束的单一游戏，游戏者必须
对该游戏进行一步决策；
● Every-SG 游戏的其他规则与普通SG 游戏相同
我们不难想到如下解法：
在通过拓扑关系计算某一个状态点的SG 函数时（事实上，我们只需要计算该状态点的SG 值是否为0），对于SG 值为0的点，我们需要知道最快几步能将游戏带入终止状态，对于SG 值不为0的点，我们需要知道最慢几步游戏会被带入终止状态，我们用step 函数来表示这个值。
()()??
?
??
∧=+=∧∧>+=的后继状态为的后继状态为为终止状态v u v SG u step u SG v u v SG u step v v step 0)(1)(min 0)(0)(1)(max 0)(
[定理]
对于Every-SG 游戏先手必胜当且仅当单一游戏中最大的step 为奇数。
我们要证明解法的正确性，需要证明三点：
● 对于所有的单一游戏，先手必胜状态的step 值为奇数，先手必胜
状态的step 值为偶数。
● 设最大的step 为max _step ，那么胜手可以保证该单一游戏最少
会在max _step 步结束。
● 设最大的step 为max _step ，那么胜手可以保证所有他必败游戏
最多在max _step 步结束。
[证明一]（用数学归纳法）
1．所有的终止状态的step 值为0，为先手必败状态。
2．假设状态树中某些状态点已经符合要求。
我们找后继状态点已经全部被证明的状态点。
如果它是先手必败状态，那么它的后继状态都为先手必胜状态，后继状态的step值全为奇数，所以该状态点的step值为偶数。
如果它是先手必胜状态，那么它的后继状态中有先手必败状态，且它所有的先手必败的后记状态的step值为偶数，所以该状态点的step值为奇数。
■
[证明二]
我们设step最大的单一游戏为A（如果有多个的话任取一个），最终的胜手为W。
W总在A游戏处在先手必胜状态时去移动A的状态，且W可以保证他最多将该游戏的step值减小1。①
对手总在A游戏处在先手必败状态时去移动A的状态，且对手最多将该游戏的step值减小1。②
由①②得，J可以保证A游戏最少会在max
step步结束。
_
■
[证明三]
我们设step最大的单一游戏为A（如果有多个的话任取一个），最终的胜手为W。我们考虑除A外的任意一个他必败的单一游戏B。
J在每一回合都可以将B的step值减少1，将B带入先手必胜状态，对手必定将B的step至少减少1，所以J可以保证B游戏最多会在错误！
未找到引用源。步结束。■
● C hapter 3
3.1翻硬币游戏
一般的翻硬币游戏的规则是这样的：
● N 枚硬币排成一排，有的正面朝上，有的反面朝上。我们从左开
始对硬币按1到N 编号。
● 游戏者根据某些约束翻硬币（如：每次只能翻一或两枚，或者每
次只能翻连续的几枚），但他所翻动的硬币中，最右边的必须是从正面翻到反面。
● 谁不能翻谁输。
有这样的结论：局面的SG 值为局面中每个正面朝上的棋子单一存在
时的SG 值的异或和。
=
⊕
⊕
图二
[证明]（数学归纳法）
我们先确定数学归纳的顺序。对于任何一个正面朝上的硬币，我们设它的分值为2K ，（它为此从左数第K 枚硬币），一个局面的分值为所有正面朝上的硬币的分值和。
则我们可以知道，对于任意一个局面，它的所有后继局面的分值小于它。
我们以局面的分值作为归纳顺序。
1.分值为0和1的局面符合要求。（对应只有一枚硬币的情况，涉及
不到组合问题）
2.假设分值小于等于K的局面符合要求。我们证明分值为(K+1)的局
面符合要求。
对于分值为(K+1)的局面，我们考虑它的某一次决策，我们可以认为最右边的改动位是去掉了一个正面朝上硬币，其他改动位是添加了一个正面朝上硬币（因为某一位有两个正面朝上的硬币和没有正面朝上的硬币是等价的——SG值等价，胜负判定等价）。这样，我们可以将决策看成去掉了某一堆石子（最右边的改动位），添加了一个它的后继石子堆（其他改动位）。这样，它的决策与NIM游戏完全等价。
之后的证明就与NIM游戏的证明十分类似，由于篇幅原因，这里从略。相信聪明的读者自己可以完成。
3.2无向图删边游戏
3.2.1树的删边游戏
规则如下：
●给出一个有N个点的树，有一个点作为树的根节点。
●游戏者轮流从树中删去边，删去一条边后，不与根节点相连的
部分将被移走。
●谁无路可走谁输。
我们有如下定理：
[定理]
叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值
加1后的异或和。
[证明]（数学归纳法）
1.一个节点和两个节点的情况显然成立。
2.我们假设小于K 个节点的任意情况均成立，下面证明（K+1）个节点的情况也成立。我们将证明分成两部分：（1）证明根节点只有一个孩子的情况符合要求；（2）证明根节点有多个孩子的情况符合要求。
先证明第一部分：
我们假设树G 的根为A ，A 只与B 相连，图中共有N+1各节点，去掉A 后以B 为根节点的图为G ’（见图三），下面证明
1)'()(+=G SG G SG
图三
若我们去掉AB 之间的边，则所有的边都被删除，
∴G 存在SG 值为0的后继局面； ①
若我们去掉G 中的除AB 外的边E ，则删除后总边数小于等于K 。
设以B 为根的G ’去掉E 以后的后继局面的SG 值为P
∵以A 为根的G 去掉E 以后图中的总边数小于等于K
又∵中间节点的SG 值为它的所有子节点的SG 值加1后的异或和
∴A 为根的G 去掉E 以后的后继局面的SG 值为P+1
∵以B 为根的G ’可以通过去边操作使得后继局面的SG 值变为0
根节点 中间节点 G’
G 图
“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 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 大树与松鼠 说明：热身活动，让学员兴奋、紧张起来，具有一定的娱乐性。 活动方法： 1、事先分组，三人一组。二人扮大树，面对对方，伸出双手搭成一个圆圈；一人扮松鼠，并站在圆圈中间；辅导员或其它没成对的学员担任临时人员。 2、辅导员喊“松鼠”，大树不动，扮演“松鼠”的人就必须离开原来的大树，重新选择其它的大树；辅导员或临时人员就临时扮演松鼠并插到大树当中，落单的人应表演节目。 3、辅导员喊“大树”，松鼠不动，扮演“大树”的人就必须离开原先的同伴重新组合成一对大树，并圈住松鼠，辅导员或临时人员就应临时扮演大树，落单的人应表演节目。 4、辅导员喊“地震”，扮演大树和松鼠的人全部打散并重新组合，扮演大树的人也可扮演松鼠，松鼠也可扮演大树，辅导员或插其它没成对的人亦插入队伍当中，落单的人表演节目。 2 Seven Up 活动程序： 1.将学员按上个单元的分组进行竞赛。 2.使用横排轮流的方式，每一位同学轮到时坐着说出自己轮到的数字，但在轮到数目字有7（7.17.27…）或是数目字为7的倍数时（7.14.21.28….），该位同学必须站起拍手，且不可说出此数目字。 3.进行比赛，直至时间到停止，并奖励优胜组别。 活动说明：暖身活动，经由此活动增进学生的注意力与记忆力，帮助主要活动的进行。 3猜猜我是谁 说明：使初步认识的队员再次彼此认识。 道具：不透明的幕布一条 规则： 1、参加的人员分成两边 2、依序说出每人的姓名或希望别人如何称呼自己 3、训练员与助理训练员手拿布幕隔开两边成员，分组蹲下 4、第一阶段两边成员各派一位代表至幕布前，隔着幕布面对面蹲下，训练员喊一，二，三，然后放下幕布，两位成员以先说出对面成员姓名或绰号者为胜，胜者可将对面成员俘虏至本组。 5、第二阶段两边成员各派一位代表至幕布前背对背蹲下，训练员喊一、二、三，然后放下幕布，两位成员靠组内成员提示（不可说出姓名、绰号），以先说出对面成员之姓名或绰号者为胜，胜者可将对面成员俘虏至本分组。 6、活动进行至其中一组人数少于三人即可停止。 注意事项： 1、选择的幕布必须不透明，以免预先看出伙伴而失去公平性及趣味性。 2、成员蹲在幕布前，避免踩在幕布上，以免操作幕布时跌到。 3、训练员应制止站立或至侧边偷窥的情况发生。 4、组员不可离训练员太近，以免操作幕布时产生撞击。 5、组员叫出名字时间差距短，训练员须注意公平性。 6、本活动不适用于不熟悉的团队。
动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[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) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。
几个经典团队游戏 （一）传瓶游戏 规则：一班分为几组，10人一组，以最短时间内从第一名到最后一名，然后再到第一名，传递3个瓶子，依次传递，若掉在地上，按10秒处理，可借助工具，每个瓶要在每个人手上传递，每组设定时间目标后分几轮操作然后得实际结果。目的：1、不要低估自己的能力，不要首先为自己的工作和学习找借口，怀疑自己的能力，要以积极的态度面对问题; 2、看似不能实现的目标，在团队智慧的合作上能非常出色的完成。 操作过程： 第一轮几组分别制定目标 然后由第一组实际操作一下，再次制定目标，重新记成绩。 第二轮上一轮完成后，让各组制定方法，要求在8秒内完成。 A2 班实际操作（一组16人） 第一轮目标：一、40秒二、 30秒三、 29秒 第一组实际操作10秒 重新制定目标：一、 10秒二、16秒三、 8秒 第二轮成绩：一、3.7秒二、5.21秒三、 4.7秒 （二）十人一组找物品 最短时间内找到以下一组物品为胜 一幅画（**老师） 一根一米长的绳子 一朵花：任何材质 一首歌：（带春字的） 一块手绢 一片完整的树叶 一段才艺节目（排除唱歌） 一根头发 一份手抄版再别康桥字迹要漂亮 一个窗花 一块铁器 目的：团队中要发现每一个人的能力 团队合作中，任务分配要合理性 团队中每一个人能力的充分发挥后，才能更好的完成任务。 意义体现：1、选干部 2、可以调动学院积极性找到潜力 3、发挥每个人的优势，特点以利于以后工作找到好的切入点 4、体现职业规划 5、认识到自己的存在价值 6、学员自我认识 班主任根据自身特点给出不同评价，不同的职业发展道路，了解能力后让学员班
主班主任去做事（如升学，辅导学员，组织活动等），要会找到具有这样能力的人（有影响力，组织能力，愿意帮助他人）并充分利用，充分发现每一个学员的潜能，为他们做出相应的职业规划。 该活动时间安排： S1 在毕业设计前做这个活动，组长在分配任务时充分考虑到组员的情况。 Y2 在项目经理的课程上应用，说明一个项目经理要了解项目小组每一个人的能力，发挥潜能，并给于他们可以提升的方向和空间。 （三）瞎子摸号 形式：14-16个人为一组比较合适 类型：问题解决方法及沟通 时间：30分钟 材料及场地：摄像机、眼罩及小贴纸和空地 适用对象：参加团队建设训练的全体人员 操作程序 1、让每位学员戴上眼罩 2、给了他们每人一个号，但这个号只有本人知道 3、让小组根据每人的号数，按从小到大的顺序排列出一条直线 4、全过程不能说话，只要有人说话或脱下眼罩，游戏结束 5、全过程录象，并在点评之前放给学员看 有关讨论： 你是用什么方法来通知小组你的位置和号数？ 沟通中都遇到了什么问题，你是怎么解决这些问题的？ 你觉得还有什么更好的方法？ 活动过程分析：通过自己创造的沟通方式，来迅速获得其他所有人的信息，你需要知道其他所有人是比你大还是比你小。，你让他人知道比你 号大还是小的方式很重要。 目的：很多时候工作必须沟通，但往往沟通会受到很大的限制，与学员的沟通占据了班主任大部分工作时间，与学员沟通存在哪些障碍？ 班主任受限沟通案例：1、学员不善言辞，无法了解他的信息想法 2、学员不愿意到中心来，只能电话中沟通 3、学员不到中心，电话联系不上。 要善于沟通，主动根据资源建立多种沟通方法。 沟通对软件工程师的影响： 1、我国人员沟通比例不足30% 2、国外成功软件工程师沟通时间占60%以上 3、性格突破自己 4、沟通人员和途径单一 5、为成长为项目经理做准备。 （四）坐腿游戏 规则：若干人围成一个紧密的圈，前面的人做到后面的人的腿上，转圈走100步。
国家旅游局公告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
史上最经典的团队小游戏集锦 双击自动滚屏 发布者：百度小崔发布时间：阅读：496次【字体：大中小】 寻猎 所需时间：由参加的人数及所列项目的多少来决定 小组人数：无限制，但要分5-7人为一组 所需物品：给每一组发一个"寻猎"项目列表 游戏概述： 此游戏就开展于一个长期训练过程的开始或训练临近结束的阶段。 目的： 1、加深团队成员间的接触 2、发现团队成员的智慧 步骤： 1、将团队成员分为5-7人。 2、告知每个参与者将一起去参加一个搜寻活动，获胜的小组将受到奖励。 3、将"寻猎"列表交给各小组，告诉他们将利用他们自己的智慧尽可能多的获得表中所列内容。 4、设置一个时间限制，如1小时。 5、当时间到时，命令每个队都集合回来，比较哪一个队的得分高 讨论题目： 1、其他小组与完成有多少差距。 2、你是怎么分析获胜队的获胜原因的。 3、在你的小组里是否有人显得比其他人更出色。 4、有人领导你的小组吗？是谁？为什么他能领导？ 瞎子穿拖鞋 概要:蒙眼前进5步或6步穿拖鞋的游戏 方法: 1、各队轮流派出1人。 2、把拖鞋放在起点前方5步的地方。 3、回到起点蒙眼旋转三次以后出发。 4、能够准确前进5步，第6步穿到拖鞋教多的一组获胜。 参考：进行中对方可以用错误的指示来扰乱。 以X传物 这里的"X" 其实等于手或颈或口或胯下或任何你可想象之部位，而"物" 则可以是气球或卡纸或香蕉或饮管或任何你可想象之东西。 而玩法则有极多，以下提供三种： 一级版：
大家排成两圈，而他们要做的就是把一个气球由队头传至队尾。 传的过程中，不可以用手，而只能以手以外的部份来传。 那队最快传完一圈为嬴。 二级版： 大家排成两圈，最好是男女相间。 他们要做的是用口来传卡纸一张。 （卡纸不宜太薄，否则不太卫生．．．而且也要确定大家玩得才好！） 最快传完一圈那组胜。 三级版： （这个更加需要肯定玩者不会介意，否则可能会玩出火，慎之，慎之！） 道具：一条用保鲜纸包好的香蕉（当然是已去皮的了） 两套几张写了身体部位名称的纸（如腋下，口，胯下，下巴，颈等）。 照相机（这么好看，不拍下怎成？） 玩法：大家排成两圈，最好是男女相间。 首先抽一张纸，例如抽到口的话，那开始的一人便要含着那香蕉，然后第二人抽，例如抽到腋下的话，那接下的一人便要用腋下来接那香蕉。 如此类推，直至传完一圈为止，快传完的一队胜。 （试想像一下，假如之前一人抽到胯下，接下来的那人抽到口，那会是．．．） 拥挤的公交车 概要：用胶带把三张报纸连成圆纸筒，比赛人员进入圆纸筒内跑到目标再折回的接力赛。方法： 1、全员分成数队。 2、根据号令几个队员跑进纸筒内（人数不限） 3、跑到目标再折回，把纸筒交给下一组。 4、如果报纸破裂，纸箱内的人要当场用胶带修理好。 5、全员最快完成的一组获胜。 团队建设、沟通游戏--瞎子列队 活动目的： 让学员体会沟通的方法有很多，当环境及条件受到限制时，你是怎样去改变自己，用什么方法来解决问题。 形式：14-16个人为一组比较合适 类型：问题解决方法及沟通 时间：30分钟 材料及场地：摄像机、眼罩及小贴纸和空地 适用对象：参加团队建设训练的全体人员 操作程序 1、让每位学员戴上眼罩 2、给了他们每人一个号，但这个号只有本人知道
国家旅游局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年 戴德承- 退一步海阔天空——“目标转化思想”的若干应用
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 -杨思雨：《伸展树的基本操作与应用》
国家旅游局关于放宽旅行社设立服务网点政策有关事项的通知 (旅发〔2015〕211号) 各省、自治区、直辖市旅游委、局，新疆生产建设兵团旅游局： 为贯彻落实《关于促进旅游业改革发展的若干意见》(国发〔2014〕31号)精神，现就放宽旅行社设立服务网点政策有关事项通知如下： 一、放宽设立服务网点区域范围 允许设立社在所在地的省(市、区)行政区划内及其分社所在地的设区的市的行政区划内设立服务网点，不受数量限制。 在设立社所在地的省(市、区)行政区划内设立服务网点的，设立社向服务网点所在地工商行政管理部门办理服务网点设立登记后，应当在3个工作日内，持设立社营业执照副本、设立社旅行社业务经营许可证副本、服务网点的营业执照、服务网点经理的履历表和身份证明向服务网点所在地与工商登记同级的旅游主管部门备案。 旅行社在其分社所在地的设区的市的行政区划内设立服务网点的，设立社向服务网点所在地工商行政管理部门办理服务网点设立登记后，应当在3个工作日内，持设立社营业执照副本、设立社旅行社业务经营许可证副本、分社的营业执照、旅行社分社备案登记证明、服务网点的营业执照、服务网点经理的履历表和身份证明向服务网点所在地与工商登记同级的旅游主管部门备案。 二、落实分社和服务网点设立政策 各地要认真学习贯彻《国务院关于促进旅游业改革发展的若干意见》(国发〔2014〕31号)，切实按照《旅行社条例》及本通知要求，依法依规做好分社和服务网点的备案工作，不得增设或变相增设旅行社设立分社、服务网点的政策障碍。
各省级旅游主管部门要积极开展针对市、县级旅游主管部门的培训指导和监督检查，发现不依法依规开展分社和服务网点备案工作的，要及时予以纠正。 三、加强对旅行社分社和服务网点的服务监管 各地要进一步引导旅行社增强风险管控意识，审慎确定分支机构设立的数量和规模;督促设立社切实加强对分社和服务网点的管理和人员培训，依法承担经营活动的责任和后果;要加强旅游质监执法人员的培训，建立健全对旅行社分社、服务网点的事中事后监管机制，改进服务监管手段，提升服务监管水平，对发现的违法违规行为，要主动协同设立社所在地旅游主管部门进行依法查处。 国家旅游局此前发布的相关规定与本通知不一致的，依照本通知执行。 国家旅游局 2015年9月22日
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- 任恺：《图论的基本思想及方法》
经典销售团队训练游戏大全 在团队制胜的今天，只有整个销售团队胜利了，企业的销售才称之为成功，很多企业为了提高销售团队的凝聚力和战斗力，为销售团队开展各种各样的训练游戏，为了能满足大家的需要，小编收集了经典销售团队训练游戏大全，以供参考。 比划猜词 游戏名称：蒙眼作画 教具：眼罩、纸、笔，所需时间10-15分 人人都认为睁着眼睛要比闭着眼画得好，因为看得见，是这样吗?在日常工作中 我们自然是睁着眼的，但为什么总有些东西我们看不到?当发生这;些问题时我们有没有想过借助他人的眼睛，试着闭上眼睛，也许当我们闭上眼睛时，我们的心敞开了。 a让每个你带上眼罩前将他们的名字写在纸的另一面，在他们完成画图后将所有的纸挂到墙上，让队员挑选出他自己画的那幅。 b教员用语言描述一样东西，让队员蒙着眼睛画下他们所听到的，然后比较他们所画的图并思考. 解手链 形式：10人一组为最佳 时间：20分钟 适合对象：全体人员 活动目的：让队员体会在解决团队问题方面都有什么步骤，聆听在沟通中的重要性以及团队的合作精神。 操作程序： 1).培训师让每组圈着站成一个向心圈 2).培训师说：先举起你的右手，握住对面那个人的手;再举起你的左手，握住另外一个人的手;现在你们面对一个错综复杂的问题，在不松开的情况下，想办法 把这张乱网解开。 3).告诉大家一定会解开，但答案会有两种，一种是一个大圈，另外一种是套着 的环。
4).如果过程中实在解不开，培训师可允许队员决定相邻两只手断开一次，但再次进行时必须马上封闭。 瞎子走路 游戏方法：两人一组(如A和B) A先闭上眼将手交给B，B可以虚构任何地形或路线，口述注意事项指引A进行。 如：向前走。。。迈台阶。。。。跨东西。。。。向左或右拐。。。 然后交换角色，B闭眼，A指引B 分析： 1.通过体验，让队员体会信任与被信任的感觉。 2.作为被牵引的一方，应全身信赖对方，大胆遵照对方的指引行事;而作为牵引者应对伙伴的安全负起全部责任，对一举一动的指令均应保证正确、清楚。另外万一指令有错，信任很难重建。 游戏名称：勇于承担责任 规则：学员相隔一臂站成几排(视人数而定)，我喊一时，向右转;喊二时，向左转;喊三时，向后转;喊四时，向前跨一步;喊五时，不动 当有人做错时，做错的人要走出队列、站到大家面前先鞠一躬，举起右手高声说：“对不起，我错了!” 做几个回合后，提问：这个游戏说明什么问题? 面对错误时，大多数情况是没人承认自己犯了错误;少数情况是有人认为自己错了，但没有勇气承认，因为很难克服心理障碍;极少数情况有人站出来承认自己错了。 在日常工作中也有很多这样的现象，在深圳有一家香港公司的办事处，有一位主管和一位职员。办事处刚成立时需要申报税项，由于当时很多这样性质的办事处都没申报，再加上这家办事处没有营业收，所以这家办事处也没申报。两年后，在税务检查中，税务局发现这家办事处没有纳过税，于是做出了罚款决定，数额有几万。这家办事处的香港老板知道这件事后，就单独问这位主管“你当时怎么想的，现在发生这要的事情?”这位主管说“当时我想到了税务申报，但职员说很多公司都不申报，我们也不用申报了，考虑到可以给公司省些钱，我也就没再考虑，并且这些事情都是由职员一手操办的。”老板又找到这位职员，问了同样的问题。这位职员说“从为公司省钱的角度，再加上我们没有营业收入和其它公司也没申报，我把这种情况同主管说了，最终申不申报还应由主管做决定，他没跟我说，我也就没报。”
置换群快速幂运算 研究与探讨 江苏省苏州中学 潘震皓 [关键词] 置换 循环 分裂 合并 [摘要] 群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。 [正文] 一、引言 置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得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、心有灵犀 游戏规则： 1、八个代表队依次上场，每队两人。一个人比划一个人猜。 2、猜词过程中，不许说出词条中包含的任何字，否则该词条作废，根据词条难度，有三次选择放弃的机会。 3、以猜中词条的多少，取前四个队获奖。 B.无实物表演说一个场景，大家可以任意发挥想象，演一个这个场景里的物品。 C。在题板上写一些数字或者颜色，然后每人唱一句带数字或颜色的歌，但是歌词里不能有题板的数字或颜色。 D。60秒不NG 准备一系列的小道具和肢体动作，可以分为3到4个环节，然后窜成一个游戏，一个接一个连上，时间规定是60秒，当然在这之间任何一个环节出错都要重来。 2、成语接龙 根据指定的字说一个成语，第一个成语的尾字为第二个成语的首字，一直接下去，哪个组用最少的词接回第一个成语的首字为胜。 3、双人顶气球接力 两人一组只能用脸部贴着气球从一头跑到另一头，中途气球掉下重来，先完成的一组取胜。 4、瞎子穿拖鞋转载于社团网ishetuan 概要:蒙眼前进5步或6步穿拖鞋的游戏方法:1、各队轮流派出1人。2、把拖鞋放在起点前方5步的地方。3、回到起点蒙眼旋转三次以后出发。4、能够准确前进5步，第6步穿到拖鞋教多的一组获胜。参考：进行中对方可以用错误的指示来扰乱。 5、官兵捉贼 用具：分别写着“官、兵、捉、贼”字样的四张小纸人数：4个人方法：将四张纸折叠起来，参加游戏的四个人分别抽出一张，抽到“捉”字的人要根据其他三个人的面部表情或其他细节来猜出谁拿的是“贼”字，猜错的要罚，有猜到“官”字的人决定如何惩罚，由抽到“兵”字的人执行。兴奋点：简单易行，不受时间地点场合的限制 6、正话反说 游戏规则： 1、每队各出一人参加游戏。 2、主持人要事先准备好一些词语。说一个词语，参与者要反着说一遍，比如“新年好”，游戏者要立刻说出“好年新”，说错或者猛住的人即被淘汰。从三个字开始说起，第二轮四个字，第三轮五个字，以此类推，估计到五个字以上的时候游戏者就所剩无几了。 3、最后胜出的四个队获奖。 7、语言游戏:数青蛙 规则：一只青蛙,一张嘴,两只眼睛,四条腿,扑通一声跳下水。 两只青蛙,两张嘴,四只眼睛,八条腿,扑通扑通跳下水。