国家集训队1999论文集 邵铮

数学模型的建立、比较和应用

苏州中学邵铮

关键字: 数学模型算法母函数

【摘要】

数学模型是解决实际问题的一种基本工具。将实际问题抽象成一个数学模型，运用数学工具进行求解，并将结果应用于具有相同特征的一类问题中，是解决问题的一种基本的途径。本文首先介绍了数学模型的一些性质，然后建立了三种不同的数学模型来求解一个问题，将三种数学模型相互比较，得出数学模型抽象性与高效性之间的关系，再将数学模型推广应用于另两个问题的求解，得出数学模型抽象性与可推广性之间的关系，最后总结全文，揭示出有关数学模型的一些普遍规律。

一、引论

实际问题往往是纷繁而复杂的，而其中的规律也是隐藏着的，要想直接用计算机来求解实际问题往往有一定的困难。计算机擅长的是解决数学问题。因此，我们有必要将实际问题抽象成数学模型，然后再用计算机来对数学模型进行求解。

与实际问题相比，数学模型有以下几个性质：

抽象性：数学模型是实际问题的一种抽象，它去除了实际问题中与问题的求解无关的部分，简明地体现了问题的本质。这一点是下面两个性质的基础。

高效性：数学模型中各个量之间的关系更为清晰，容易从中找到规律，从而提高求解的效率。由于这一点是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型效率的高低有重要的影响，这一点将在第二部分中详细阐述。

可推广性：数学模型可以推广到具有相同性质的一类问题中。换句话说，解决了一个数学模型就解决了一类实际问题。这里的“相同性质”是指相同的本质，表面看似毫不相干的问题可能有着相同的本质。由于这一点也是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型的推广范围也有重要的影响，这一点将在第三部分中详细阐述。

二、数学模型的建立和比较

由于考虑问题的角度不同，面对同一个实际问题，可能建立起各种各样的数学模型。在各种数学模型中，我们要寻找的是效率高的模型。模型的效率同模型的抽象化程度有关，下面从一个实例中来分析它们之间的具体关系。

【多边形分割问题】将一个凸n边形用n-3条互不相交的对角线分割为n-2

个三角形,求分割方案的总数.

如:n=5时,有以下几种分割方案:

这道题可用以下几种方法来求解:

<1>.搜索法:

这种方法的思路是将各种分割方案全都列举出来。

显然，一组n-3条互不相交的对角线对应于一种分割方案，因此可把问题看作是求不同的对角线组的数目。

将n边形的n个顶点按顺时针方向编号为1、2、3……n，则一条对角线可表示为一个数对(a1,a2)，a1、a2分别表示对角线两端顶点的序号，a1

对角线在对角线组中的顺序是无关紧要的，因此，一个对角线组是一个集合，它的元素是对角线。

判断两条对角线是否相交是一个必须解决的问题。设两条对角线分别为

(a1,a2)与(b1,b2)，若把表示对角线的数对看作开区间，那么两条对角线不相交的充要条件是两个区间有包含关系或他们的交集为空集。

于是，我们建立起解决本问题的第一个数学模型：

已知：n的值,

一个集合由(n-3)个不同的开区间(i,j)组成,

i∈{1..n-2}, j∈{i+2..n},(i≠1)或(j≠n)

同一个集合中任两个不同的开区间(i1,j1),(i2,j2)满足：

((i1,j1)∩(i2,j2)=空集)或((i1,j1)包含(i2,j2))或((i2,j2)包含(i1,j1)) 求：不同的集合的个数

搜索时，先考虑以顶点1为始端的对角线，可以不连任何对角线(图一中A)，也可以连(1,3)(图一中B)，或连(1,4)(图一中C)，或同时连(1,3)(1,4) (图一中D)。对于每一种情况，再考虑以顶点2为始端的对角线，依此类推。当得到n-3条互不相交的对角线时，便找到了一种方案(参见图一)。

图一在考虑以顶点i为始端的对角线时，有以下几条规则必须遵循：

1.与原有对角线相交的对角线不得选取。

2.当i>=3时，若顶点i-1为始端的对角线一条都未连，则对角线(i-2,i)必须是已经连的。

3.对角线的末端顶点序号必须大于i。否则，顶点i将成为对角线的末端，另一个顶点j(j

按照以上三条规则，即可得到如图一的搜索树(图中打√的叶结点为不同的分割方案)。

搜索法的数学模型较为复杂，用它可以求出具体方案，但它的抽象化程度不高，导致了求解时的低效率。为了使用上面的规则2来提高效率，求解过程还是从多边形及其对角线本身来考虑的，数学模型的作用仅体现在判断对角线是否相交上。用该方法编制的程序在n稍大时速度就很慢。(n=12时已需运行时间16.2秒(486DX2/80)，测试结果见附表一。)

<2>.递推法:

上一种方法的数学模型中有很多与问题的要求无关的内容(如对角线的表示、对角线组的表示、每种具体方案)。在递推法建立的数学模型中，我们只考虑凸n边形的分割方案总数。

设k边形的分割方案总数为A k，于是得到A数列：A3,A4,A5...

考虑n边形的分割方案总数A n。任取n边形的一条边，不妨取边(n-1,n), 若

在某一种分割方案中，边(n-1,n)属于三角形(i,n-1,n),那么就将分割方案归入

第i 类，如图二所示。

图二

设第i 类方案总数为B i ，则

A B n i i n ==-∑12

①

计算B i 可用如下方法：

对于第i 类的方案，原n 边形已被分割为一个i+1边形与一个(n-i)边形，下面的工作分为两步，第一步是将i+1边形分割为三角形，有A i+1种方案，第二步是将(n-i)边形分割为三角形，有A n-i 种方案。为了表达的方便，令A 2=1，于是有

B A A i i n i =+-1* ②

将②代入①得：

A A A A A n i n i i n i n i i n ==+-=-+-=-∑∑(*)(*)11

212

1

③

于是，问题的数学模型即为：

已知：n 的值及数列A 2,A 3,A 4……, 该数列满足： A 2=1

A (A *A )j i j 1i i 2j 1

=+-=-∑, j>2

求：A n

利用这个模型，我们即可很方便地依次求出A 3,A 4...A n 。

递推法的数学模型比搜索法的简明，抽象化程度更高，效率也高得多。用递推法编制的程序已能应付中等数据，在n<100时不超过一秒。但当n 很大时仍然很慢，n=250时需18.7秒(486DX2/80)，测试结果见附表一。

<3>.母函数法：

上一种方法的数学模型中已去除了很多与问题的要求无关的内容，但同时，问题只要求An,而上述方法却将A 3～An 都求出了。能否不求A 3～An -1而直接由n 求出An 呢？下面用母函数这种数学模型来解决这个问题。

将A 2,A 3,A 4……作为幂级数的系数，令

Y x A x A x A x i i i ()***......==++=+∞

∑2

2233 ④

如果能解出Y(x),那么也就求出了An. 为了求Y(x),我们来看一下Y(x)^2的值:

Y x A A x j i j i j i i 2

2

2

4

()[(*)*]=-=-=+∞∑∑

而(*)A A A j i j j i i -=--∑=2

2

1,因此有:

Y x A x A x 23445()**......=++ ⑤ ⑤-④*x 得:

Y x x Y x A x 2230()*()*-+= 将A 21=代入，解出Y x ()：

Y x x x x x x

()*

=±-=±-23421142

14122423-=---x x x x ......各项系数均为负数，而A i >0,故：

Y x x x

()*

=--1142

⑥ , 其中14410-=??????-=+∞∑x k x k k *(),11212121

2121k k k ?????

?=---+*()*()*...*()!

于是，Y x x k x k k

()*

()=-????

?

?-=+∞

∑1421

20 =-+??????-+??????-++??????-+=--??????--??????----??????--x x k x k x x x k x k k k

*

(()()...()...)

()()...() (1114442)

412422412

112

1122212311

2 所以，A k k k =-

--???

???-()412

112 =--+----1212121223122112

()()...()()!

*()*k k k k =------113521122

*()*()*...*()

()!

*()*k k k k =---1352512

2***...*()()!

*k k k =

----135252462412***...*()****...*()()!()!

k k k k =

---()!()!()!2412k k k =---11

242k C k k * 于是得出了由n 直接求出A n 的数学模型：

已知：n的值，

A

C

n1

n

2n4

n2

=

-

-

-

⑦

求：A n

求解时用公式⑦可直接计算A n。

在三个数学模型中，这一个表达最为简洁，抽象化程度最高。用它来求解的效率也最高。n=1000时不超过1秒,n=5000时也仅需14.7秒(486DX2/80)，测试结果见附表一与附表二。

搜索法作为一种最基本的方法，建立在一个较为复杂的数学模型之上，它的特点是可以求出每一种分割方法，但用这种方法来求方案总数显然针对性不强，因此效率很低。递推法是建立在数列这个数学模型之上的，由于去除了很多不必要的因素，效率大为提高，对于n<=300时有较好的效果。利用母函数这种数学模型求解，是对递推法的一种数学优化，得出了更为简洁的结论，当n>300时充分显示出其优势。

从以上的分析中可以得出这样的结论：数学模型的抽象化程度越高，它的效率越高。这个结论很容易理解，因为抽象化程度越高，数学模型中与问题无关的成分就越少，于是效率也就越高。相反的，若抽象化程度不够高，则数学模型中含有较多的与问题无关的成分，那么，效率也就要低一些。

三、数学模型的推广和应用

数学模型具有可推广性。

数学模型是建立在问题本质的基础上的，而不是建立在问题的表面现象上的。因此，虽然两个问题表面毫无关系，只要它们有相同的本质，就可以用相同的数学模型求解。然而，要看到两个问题有相同的本质并不是一件容易的事。这需要我们抛开问题的表面现象，仔细地比较分析，在问题之间建立对应关系。

数学模型的可推广性与数学模型的抽象化程度有着密切的关系。为解决同一个问题而建立起的不同的数学模型可能具有不同的可推广性。

下面将由母函数建立起的数学模型应用于另一些问题的求解。

【树的计数问题】求具有n个结点的二叉树的数目。

设具有k个结点的的二叉树的数目为Dk，则

*当k=0时，是一棵空树，只有一种。

*当k>0时，二叉树可分为根结点、具有i个结点的左子树与具有k-1-i个结点的右子树。于是具有k个结点的二叉树的数目等于具有i个结点的二叉树的数目与具有k-1-i个结点的二叉树的数目的乘积。

将以上的分析写成公式，就是：

D D D D o k i k i i k ==--=-∑1

101

(*)

比较上文中A 数列与这里的D 数列可知D A n n =+2 ,于是将上文中的数学模型(⑦式)稍加变换，即得：

D C n n n

n =+21 ⑧

至此，我们已将这个问题用上面的数学模型解决了。这个问题与[多边形分割问题]具有相同的本质，即它们计数的规律是一致的，因此，它们可用相同的数学模型求解。

为了将这种数学模型进一步推广，我们再将上一个问题分析一下：将每棵二叉树的n 个结点一一编号，使每棵二叉树的前序序列都是1,2,3…,n 。由于前序序列与中序序列可唯一确定一棵二叉树，所以每棵二叉树的中序序列与其它的二叉树都是不同的。(一旦相同，那么这两棵二叉树就是同一棵二叉树了。)

另外，对于一棵前序序列确定的二叉树，它的中序序列可以由前序序列进栈与出栈生成。于是该数学模型又可直接用于下面问题的求解。

【火车进出栈问题】一列火车n 节车厢，依次编号为1,2,3,…,n 。每节车厢有两种运动方式，进栈与出栈，问n 节车厢出栈的可能排列方式有多少种。

将这个问题与上一个问题比较一下：列车原始的排列状态(1,2,3,…,n)正是二叉树的前序序列；列车车厢的进栈与出栈对应于二叉树结点的进栈与出栈；列车出栈后的排列状态正是二叉树的中序序列。

将两道题对应起来看，不难发现，列车出栈后的可能排列方式的数目就是二叉树的中序序列的数目，也就是二叉树的数目。

设n 节车厢的排列方式有En 种，则

E C n n n n =+2

1

⑨

于是，我们又用相同的数学模型解决了这个问题。

将数学模型推广到[树的计数问题]时，我们只是比较了相似的递推公式，可以说是一种简单的推广。而推广到[火车进出栈问题]时，则是从[树的计数问题]出发，将两个问题对应起来看，进行了很多逻辑分析，相比之下要复杂一些。事实上，很多数学模型的推广应用都需要进行仔细的分析。

从一个问题[多边形分割问题]出发建立起的数学模型X C n n n

n =+21

，公式中已完

全略去了分割的具体内容，只留下了问题的本质：计数。由于公式表达了计数方

法的实质内涵（X

=;X X X

k i k i

i

k

=

--

=

-

∑(*)1

1

）,于是就给了它进一步广泛应用于

一类问题求解（外延）的可能。

再考虑一下[多边形分割问题]中搜索法的数学模型。在这两个问题中，搜索法的数学模型显然是不适用的。它包含着多边形的每一种具体的分割方案，没有很好的体现问题计数的本质，因此影响了这种数学模型的可推广性。在这两个问题中，没有相应的概念对应于多边形的分割方案，于是，搜索法的数学模型便对这两个问题无能为力了。而数列与母函数两种方法的数学模型仍能应用于这两个问题。这正是由于后两种方法的数学模型更加抽象，所以更有利于它们的推广。

四、总结

以上三个实例充分说明了数学模型的高效性、可推广性以及它们与抽象性之间的关系。

数学模型具有高效性。从实际问题中建立起来的数学模型可以去除无关的内容，关系清晰，有利于效率的提高。

数学模型具有可推广性。从实际问题中建立求解的数学模型，一个数学模型建立后，往往能将其应用于一类实际问题中。乍一看[分割多边形]与[火车进出栈]没有什么联系，但通过对模型的理解可以发现两个问题有着密切的内在联系：它们是可以用相同的数学模型来求解的。

数学模型的高效性与其抽象性是紧密联系的。数学模型越是抽象，它的效率也就越高。数学模型的可推广性与其抽象性也是紧密联系的。数学模型越是抽象，它也就越容易被广泛应用。

【附件】

【程序】

1.多边形分割问题搜索法(sousuo.pas)

{$A+,B-,D-,E-,F-,G+,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}

{$M 16384,0,655360}

Program SouSuo;

Const

Max=30;

Type

TPara=record l,r:integer;end; {区间类型}

Var

method:Longint; {方案总数}

Para:array[1..Max]of TPara; {区间组}

n:integer;

time:Longint;

Function M(a,b:integer):integer;{高精度整数类型}

begin if a

Procedure Make; {搜索多边形的所有分割方案}

Var i,j:integer;

sp,lp1,lp2:integer;

Function Connect:boolean; {判断新加入区间组的区间是否与原有的区间有冲突}

var i,j,k:integer;b1,b2:boolean;

begin

j:=para[sp].l;k:=para[sp].r;

Connect:=true;

for i:=1 to sp-1 do

begin

if (j=para[i].l)or(j=para[i].r) then continue;

if (k=para[i].l)or(k=para[i].r) then continue;

if ((j>para[i].l)and(j

((k>para[i].l)and(k

then exit;

end;

Connect:=false;

end;

Function PreFalse:boolean; {检验是否有其它的冲突}

var i:integer;j,k:integer;

begin

prefalse:=false;j:=para[sp].l;

if j<=2 then exit;

for i:=1 to sp do

if (para[i].l=j-1)or(para[i].r=j-1) then exit;

k:=j;j:=k-2;

for i:=1 to sp do

if (para[i].l=j)and(para[i].r=k) then exit;

PreFalse:=true;

end;

Function Pop:boolean;forward;

Function Push:boolean; {入栈}

begin

inc(sp);

Para[sp].l:=lp1;Para[sp].r:=lp2;

Push:=((lp1=1)and(lp2=n))or(lp1>n)or(lp2>n)or connect; if prefalse then

begin Push:=true;pop;exit;end;

inc(lp2);

if lp2>n then

begin inc(lp1);lp2:=lp1+2;end;

end;

Function Pop:boolean; {出栈}

begin

if sp=0 then

begin dec(sp);pop:=false;exit;end;

lp1:=Para[sp].l;lp2:=para[sp].r;dec(sp);

inc(lp2);

if lp2>n then

begin inc(lp1);lp2:=lp1+2;end;

Pop:=(lp1>n)or(lp2>n);

end;

begin

sp:=0; {栈顶指针置0}

lp1:=1;lp2:=3;

method:=0;

while (sp>=0) do

begin

if Push then while pop do;

if sp=n-3 then {获得了一种方案}

begin

method:=method+1;

while pop do;

end;

end;

writeln('Total: ',method);

end;

var i:integer;s:string;

BEGIN

write('Input N: ');

readln(n);{输入多边形边数}

time:=MemL[$40:$6c];

if n<3 then writeln('Total: 0')

else if n=3 then writeln('Total: 1')

else MAKE; {搜索多边形的所有分割方案}

writeln('Time: ',(Meml[$40:$6c]-time)/18.2:5:1);

{输出所用的时间}

END.

2.多边形分割问题递推法(ditui.pas)

{$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-} {$M 16384,0,655360}

Program DiTui;

Const

Len=100;Max=300;

Type

Th=array[-1..Len+1]of integer;{高精度整数类型}

Var

method:array[1..Max]of Th; {i边形分割方案总数为method[i]} n:integer; {要求的多边形的边数}

time:Longint;

Function M(a,b:integer):integer; {取最大值}

begin if a

Procedure Add(var a:Th;b:Th); {a:=a+b;a,b为高精度整数类型} var i,j:integer;

begin

j:=0;

a[-1]:=m(a[-1],b[-1]);

for i:=0 to a[-1] do

begin inc(j,a[i]+b[i]);

a[i]:=j mod 10000; {每位integer存4位十进制数}

j:=j div 10000;

end;

if j<>0 then

begin inc(a[-1]);a[a[-1]]:=j;end;

end;

Procedure Mul(a,b:Th;var c:Th); {c:=a*b;a,b,c为高精度整数类型} var i,j:integer;k:Longint;

begin

fillchar(c,sizeof(Th),0);

for i:=0 to a[-1] do

begin

k:=0;

for j:=0 to b[-1] do

if i+j<=Len then

begin

inc(k,longint(a[i])*b[j]+c[i+j]);

c[i+j]:=k mod 10000;

k:=k div 10000;

end;

inc(c[i+b[-1]+1],k);

end;

c[-1]:=a[-1]+b[-1];

if c[c[-1]+1]<>0 then inc(c[-1]);

end;

Procedure OutHigh(a:Th); {输出高精度整数} var s:string[4];i,j:integer;

begin

write('Total: ');

j:=a[-1];write(a[j]);

for i:=j-1 downto 0 do

begin

str(a[i],s);while s[0]<#4 do s:='0'+s;

write(s);

end;

writeln;

end;

Procedure Make; {递推计算多边形分割总数} var i,j:integer;a:Th;

begin

fillchar(method,sizeof(method),0);

method[2,0]:=1;

method[3,0]:=1;

fillchar(a,sizeof(a),0);

for i:=4 to N do

for j:=1 to i-2 do

begin

mul(method[j+1],method[i-j],a);

Add(method[i],a);

end;

OutHigh(method[n]);

end;

var i:integer;s:string;

BEGIN

write('Input N: ');

readln(n); {输入多边形边数}

time:=MemL[$40:$6c];

if n<3 then writeln('Total: 0')

else MAKE;{递推计算多边形分割总数}

writeln('Time: ',(Meml[$40:$6c]-time)/18.2:5:1);

{输出所用的时间}

END.

3.多边形分割问题母函数法见muhanshu.Pas

{$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}

{$M 16384,0,655360}

Program MuHanShu;

Const

Len=1400;Max=6000;

Type

Th=array[0..Len+1]of integer;{高精度整数类型1,按位存储} Ty=array[0..Max]of integer;{高精度整数类型2,按因数存储} Var

fi,fo:text;fin,fon:string;

n:integer;

time:Longint;

Procedure Mul(var a:Th;b:integer); {a:=a*b;a为高精度整数类型1} Var i:integer;k:Longint;

begin

k:=0;

for i:=1 to a[0] do

begin

k:=k+a[i]*longint(b);

a[i]:=k mod 10000;

k:=k div 10000;

end;

if k<>0 then

begin inc(a[0]);a[a[0]]:=k;end;

end;

Function MaxPublic(a,b:integer):integer; {a,b的最大公因数}

var i:integer;

begin

repeat

a:=a mod b;

if a=0 then break;

b:=b mod a;

until b=0;

MaxPublic:=a+b;

end;

Procedure Divide(var k:Ty;h:integer);{k:=k div h;k为高精度整数类型2}

Var i,j:integer;

begin

for i:=1 to k[0] do

if k[i] mod h =0 then

begin k[i]:=k[i] div h;

if k[i]=1 then begin k[i]:=k[k[0]];dec(k[0]);end;

exit;

end;

for i:=k[0] downto 1 do

if MaxPublic(k[i],h)>1 then

begin

j:=MaxPublic(k[i],h);

h:=h div j;k[i]:=k[i] div j;

if k[i]=1 then begin k[i]:=k[k[0]];dec(k[0]);end;

if h=1 then exit;

end;

end;

Procedure translate(k:Ty;var a:Th);{a:=k;a为高精度整数类型1,k为高精度整数类型2}

Var i:integer;

begin

a[1]:=1;a[0]:=1;

for i:=1 to k[0] do mul(a,k[i]);

end;

Procedure Make;{按公式计算多边形分割总数}

Var i,j:integer;k:Ty;a:Th;s:string[4];

begin

k[0]:=n-2;

for i:=1 to n-2 do k[i]:=(2*n-3-i);

for i:=n-2 downto 2 do divide(k,i);

divide(k,n-1);

translate(k,a);

write('Total: ');

j:=a[0];write(a[j]);

for i:=j-1 downto 1 do

begin

str(a[i],s);while s[0]<#4 do s:='0'+s;

write(s);

end;

writeln;

end;

var i:integer;s:string;

BEGIN

write('Input N(<=',Max,'): ');

readln(n); {输入多边形边数}

time:=MemL[$40:$6c];

if n<3 then writeln('Total: 0')

else MAKE; {按公式计算多边形分割总数}

writeln('Time: ',(Meml[$40:$6c]-time)/18.2:5:1);

{输出所用的时间}

END.

4.树的计数问题、火车进出栈问题(tuiguang.pas)

{$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-} {$M 16384,0,655360}

Program TuiGuang;

Const

Len=1400;Max=5002;

Type

Th=array[0..Len+1]of integer;{高精度整数类型1,按位存储} Ty=array[0..Max]of integer;{高精度整数类型2,按因数存储} Var

fi,fo:text;fin,fon:string;

n:integer;

time:Longint;

Procedure Mul(var a:Th;b:integer); {a:=a*b;a为高精度整数类型1}

Var i:integer;k:Longint;

begin

k:=0;

for i:=1 to a[0] do

begin

k:=k+a[i]*longint(b);

a[i]:=k mod 10000;

k:=k div 10000;

end;

if k<>0 then

begin inc(a[0]);a[a[0]]:=k;end;

end;

Function MaxPublic(a,b:integer):integer; {a,b的最大公因数}

var i:integer;

begin

repeat

a:=a mod b;

if a=0 then break;

b:=b mod a;

until b=0;

MaxPublic:=a+b;

end;

Procedure Divide(var k:Ty;h:integer);{k:=k div h;k为高精度整数类型2} Var i,j:integer;

begin

for i:=1 to k[0] do

if k[i] mod h =0 then

begin k[i]:=k[i] div h;

if k[i]=1 then begin k[i]:=k[k[0]];dec(k[0]);end;

exit;

end;

for i:=k[0] downto 1 do

if MaxPublic(k[i],h)>1 then

begin

j:=MaxPublic(k[i],h);

h:=h div j;k[i]:=k[i] div j;

if k[i]=1 then begin k[i]:=k[k[0]];dec(k[0]);end;

if h=1 then exit;

end;

end;

Procedure translate(k:Ty;var a:Th);{a:=k;a为高精度整数类型1,k为高精度整数类型2}

Var i:integer;

begin

a[1]:=1;a[0]:=1;

for i:=1 to k[0] do mul(a,k[i]);

end;

Procedure Make;{按公式计算}

Var i,j:integer;k:Ty;a:Th;s:string[4];

begin

k[0]:=n-2;

for i:=1 to n-2 do k[i]:=(2*n-3-i);

for i:=n-2 downto 2 do divide(k,i);

divide(k,n-1);

translate(k,a);

write('Total: ');

j:=a[0];write(a[j]);

for i:=j-1 downto 1 do

begin

str(a[i],s);while s[0]<#4 do s:='0'+s;

write(s);

end;

writeln;

end;

var i:integer;s:string;

BEGIN

write('Input N(<=',Max-2,'): ');

readln(n); {输入N}

inc(n,2);

time:=MemL[$40:$6c];

MAKE; {按公式计算}

writeln('Time: ',(Meml[$40:$6c]-time)/18.2:5:1);

{输出所用的时间}

END.

【参考书目】

《信息学奥林匹克》1998.1-2 中国计算机学会普及工作委员会、TSINGHUA UNIVERSITY ACM STUDENT CHAPTER 主办，第87页、第93-94页；

《数据结构》（第二版），严蔚敏、吴伟民编著，清华大学出版社1992年6月，第150-154页；

《中学生数学建模读本》，孔凡海编著，江苏教育出版社1998年1月。

国家集训队2004论文集 肖天

“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 1 引论 人们在借助计算机解决一个实际问题时，无非就是详细地告诉计算机应该怎么做，使它能通过人们给定的输入得到人们想要的输出。由于一般的计算机只能处理数字信号，所以只有把实际问题转化为数学问题，计算机才能帮助我们。这一步就是建立数学模型。 数学模型的建立在通过计算机解决问题的过程中非常重要。它把计算机无法理解的问题加以转化，使一切事物量化，最终变为只含数学过程的问题。它是人脑与计算机沟通的桥梁。不仅如此，数学模型的好坏直接影响着人与计算机之间的信息交流，影响着计算机对问题的“理解”。好的数学模型能够抓住问题的本质，表述简捷明了，易于人们找到有效的解决方法，并通过编制程序的方式将解决方法告诉计算机；相反，对于同一个问题，如果数学模型不能抓住问题本质，人们就可能无法解决问题，或者找不到有效的方法，更不用提告诉计算机如何做了。 由于建立数学模型是为了解决问题，所以人们在做这项工作时往往希望把问题归结为已经很好解决的经典问题或若干这样问题的有机结合。这样，只要应用前人的研究成果就可以了。比如，排序、求图的单源最短路、网络流等等都是经典问题，前人不仅给出一般解法，而且对各种特殊情况和变形作了深入的研究。但事情并不总像人们希望的那样，有的问题即使可以归结为已有问题，在其中加入一些干扰因素后，原有性质就会发生改变，原来建立起的数学模型难以再用严谨的数学语言表达。这样问题中的部分图论问题可以用本文提出的“分层图思想”解决。 该思想注重对原问题性质的挖掘，通过对原问题数学模型的扩展，将干扰因素融入新的数学模型之中，恢复了模型的严谨性，进而与已解决问题产生联系，得到有效算法。

国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营

国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营许可证》换发及变更的通知 【法规类别】旅游综合规定 【发文字号】旅管理函[2008]16号 【发布部门】国家旅游局 【发布日期】2008.02.02 【实施日期】2008.02.02 【时效性】现行有效 【效力级别】部门规范性文件 国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营许可证》换发及变 更的通知 （旅管理函〔2008〕16号） 各省、自治区、直辖市旅游局（委）： 为了进一步规范《国际旅行社业务经营许可证》的换发和变更，现根据《旅行社管理条例》及实施细则，就有关事项通知如下： 一、《国际旅行社业务经营许可证》有效期为三年，国际旅行社应当在《国际旅行社业务经营许可证》到期之日前的三个月内，持许可证到原颁证机关（国家旅游局）换发。 二、《国际旅行社业务经营许可证》在有效期内需要变更许可证载明事项内容的，应当在完成工商部门的变更登记之日起的相关规定期限内，持相关材料和许可证到原颁证机

关申请换发。 三、《国际旅行社业务经营许可证》损坏的，应当在相关规定期限内将损坏《国际旅行社业务经营许可证》正、副本上交颁证机关申请换发。 四、《国际旅行社业务经营许可证》遗失的，应当在遗失之日起的相关规定期限内在当地公开发行的报纸上刊登启事，并提供报纸原件向颁证机关申请换发。 五、《国际旅行社业务经营许可证》涉及变更事项的，各省（自治区、直辖市）旅游局须认真审验相关材料，并在《国际旅行社变更事项备案登记表》内签章。 附件：1、《国际旅行社业务经营许可证》变更事项所需提供材料的具体规定 2、国际旅行社变更事项备案登记表 国家旅游局质量规范与管理司 2008年2月2日附件1： 《国际旅行社业务经营许可证》变更事项 所需提供材料的具体规定

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

摘抄自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 - 杨思雨：《伸展树的基本操作与应用》

2018全国初中数学竞赛试题及参考答案

中国教育学会中学数学教学专业委员会 “《数学周报》杯”2018年全国初中数学竞赛试题 答题时注意： 1．用圆珠笔或钢笔作答； 2．解答书写时不要超过装订线； 3．草稿纸不上交. 一、选择题<共5小题，每小题7分，共35分. 每道小题均给出了代号为A ，B ，C ，D 的四个选项，其中有且只有一个选项是正确的. 请将正确选项的代号填入题后的括号里，不填、多填或错填都得0分） 1．设1a ，则代数式32312612a a a +--的值为( >. .，0y >，且满足3y y x xy x x y ==，，则x y +的值为( >. .

国家集训队2001论文集 毛子青

动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。

国家旅游局关于印发《导游IC卡发放管理办法(试行)》的通知

国家旅游局关于印发《导游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卡的发放管理，制定本办法。

国家集训队2005论文集 黄源河

左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (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) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。

2018年全国初中数学联合竞赛

2018年全国初中数学联合竞赛 笫一试 一、选择题(42分) 1.已知a=2-1,b=22-6,c=6-2,那么a 、b 、c 的大小关系是( ) (A)a0.(B)M=0.(C)M<0.(D)不能确定M 为正、为负或为0. 4.Rt ΔABC 的面积为120,且∠BAC=900,AD 是斜边上的中线, 过点D 作DE ⊥AB 于点E,连CE,交AD 于点F,则ΔAFE 的面积等于( ) (A)18.(B)20.(C)22.(D)24. 5.如图2,⊙O 1与⊙O 2外切于点A,两圆的一条外公切线与 ⊙O 1相切于点B.若AB 与两圆的另一条外公切线平行, 则⊙O 1与⊙O 2的半径之比为( ) (A)2∶5.(B)1∶2.(C)1∶3.(D)2∶3. 6.如果对于不小于8的自然数n,当3n+1是一个完全平方数时,n+1都能表示成k 个完全平方数的和,那么k 的最小值为( ) (A)1.(B)2.(C)3.(D)4. 二.填空题(28分) 1.已知a<0,ab<0,化简:3231 +----a b b a =_________________. 2.如图3,7根圆形筷子的横截面圆半径为r, 则捆扎这7根筷子一周的绳子的长度为________. 3.甲,乙两人到特价商店购买商品,已知两人购买商品的件数相同, 且每件商品的单价只有8元和9元两种.若两人购买商品一共花费 了172元,则其中单价为9元的商品有_______件. 4.设N=23x++92y 为完全平方数,且N 不超过2392,则满足上述条件的一切正整数对(x,y)共有_____对. 笫二试(A) 一.(20分)已知a,b,c 三数满足方程组: ，试求方程bx 2+cx-a=0的根.

国家旅游局公告2006年第1号——欠缴质保金的旅行社名单

国家旅游局公告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号令

国家旅游局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日

最新全国初中数学竞赛试题及答案

全国初中数学竞赛试题及参考答案 一．选择题（5×7'=35'） 1.对正整数n ，记n ！=1×2×...×n,则1!+2!+3!+...+10!的末位数是( )． A ．0 B ．1 C ．3 D ．5 【分析】5≥n 时，n ！的个位数均为0，只考虑前4个数的个位数之和即可，1+2+6+4=13，故式子的个位数是3. 本题选C ． 2.已知关于x 的不等式组??????? <-+->-+x t x x x 2 353 52恰好有5个整数解，则t 的取值范围是( )． 2116.-<<-t A 2116.-<≤-t B 2116.-≤<-t C 2 116.-≤≤-t D 【分析】20232 35352<<-????????<-+->-+x t x t x x x ，则5个整数解是15,16,17,18,19=x ． 注意到15=x 时，只有4个整数解．所以 2116152314-≤<-?<-≤t t ，本题选C 3.已知关于x 的方程x x x a x x x x 22222--=-+-恰好有一个实根，则实数a 的值有( )个． A ．1 B ．2 C ．3 D ．4 【分析】422222222+-=?--=-+-x x a x x x a x x x x ，下面先考虑增根： ⅰ）令0=x ，则4=a ，当4=a 时，0,1,022212===-x x x x （舍）； ⅱ）令2=x ，则8=a ，当8=a 时，2,1,0422212=-==--x x x x （舍）； 再考虑等根： ⅲ）对04222=-+-a x x ，270)4(84= →=--=?a a ，当21,272,1==x a . 故27, 8,4=a ，2 1,1,1-=x 共3个.本题选C ．

NOI国家集训队论文分类(至2008)(摘抄自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 -杨思雨：《伸展树的基本操作与应用》

国家集训队2005论文集 潘震皓

置换群快速幂运算 研究与探讨 江苏省苏州中学 潘震皓 [关键词] 置换 循环 分裂 合并 [摘要] 群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。 [正文] 一、引言 置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得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)）

2018年全国初中数学竞赛(初一组)初赛试题参考答案

第1页（共1页）一、1.A 2.C 3.B 4.D 5.B 6.D 二、7.-18.30°9.3或-110.221 三、11.（1）19×11=12×?è??19-111；………………………………………………………………………………5分（2）1()2n -1()2n +1；12×?è?? 12n -1-12n +1；…………………………………………………………………………………………………………10分 （3）a 1+a 2+a 3+…+a 100=12×?è??1-13+12×?è??13-15+12×?è??15-17+12×?è??17-19+?+12×?è?? 1199-1201=12×?è?? 1-13+13-15+15-17+17-19+?+1199-1201……………………………………………15分=12×?è??1-1201=12×200201=100201.…………………………………………………………………………………………………20分四、12.（1）130°.…………………………………………………………………………………………………5分 （2）∠APC =∠α+∠β. 理由：过点P 作PE ∥AB ，交AC 于点E .……………………………………………………………10分因为AB ∥CD ， 所以AB ∥PE ∥CD . 所以∠α=∠APE ， ∠β=∠CPE .所以∠APC =∠APE +∠CPE =∠α+∠β.…………………………………………………………15分 （3）当点P 在BD 延长线上时， ∠APC =∠α-∠β；……………………………………………………20分当点P 在DB 延长线上时， ∠APC =∠β-∠α.……………………………………………………25分五、13.（1）根据题意，得t =?è??120-12050×550+5×2+12050≈6.3()h .答：三人都到达B 地所需时间约为6.3h.………………………………………………………………5分 （2）有，设甲从A 地出发将乙载到点D 行驶x 千米，放下乙后骑摩托车返回，此时丙已经从A 地出发步行至点E ，继续前行后与甲在点F 处相遇，甲骑摩托车带丙径直驶向B,恰好与乙同时到达. …………………………………………………………………………………………………………10分 根据题意，得2?x -x 50?550+5+120-x 50=120-x 5.…………………………………………………………15分解得x ≈101.5.…………………………………………………………………………………………20分则所用总时间为t =101.550+120-101.55≈5.7()h .答：有，方案如下:甲从A 地出发载乙，同时丙步行前往B 地，甲载乙行驶101.5千米后放下乙，乙步行前往B 地，并甲骑摩托车返回，与一直步行的丙相遇.随后甲骑摩托车载丙径直驶向B 地，恰好与步行的乙同时到达，所需时间为5.7h.………………………………………………………………………25分

2018年全国初中数学竞赛试题及解答

2018年全国初中数学竞赛试题及解答 一、选择题（只有一个结论正确） 1、设a,b,c 的平均数为M ，a,b 的平均数为N ，N ，c 的平均数为P ，若a>b>c ，则M 与P 的大小关系是（ ） （A ）M ＝P ；（B ）M ＞P ；（C ）M ＜P ；（D ）不确定。 2、某人骑车沿直线旅行，先前进了a 千米，休息了一段时间，又原路返回b 千米（ba 1,b>b 1, c>c 1,，则S 与S 1的大小关系一定是（ ）。 （A ）S ＞S 1；（B ）S ＜S 1；（C ）S ＝S 1；（D ）不确定。 二、填空题 7、已知: a 23 331a a a ++＝________。 8、如图，在梯形ABCD 中，AB∥DC，AB ＝8，BC ＝ ∠BCD＝45°，∠BAD＝120°，则梯形ABCD 的面积等于________。 9、已知关于的方程 (a-1)x 2 +2x-a-1=0的根都是整数，那么符合条件的整数有_______个。 10、如图，工地上竖立着两根电线杆AB 、CD ，它们相距15米，分别自两杆上高出地面4米、6米的A 、C 处，向两侧地面上的E 、D ；B 、F 点处，用钢丝绳拉紧，以固定电线杆。那么钢丝绳AD 与BC 的交点P 离地面的高度为________米。

国家旅游局《旅行社公告暂行规定》文档

旅行社公告暂行规定 第一条为规范有关旅行社的公告发布行为，加强对企业经营和旅游行政管理的指导服务，根据《旅行社条例》和《旅行社条例实施细则》，制订本暂行规定。 第二条旅行社公告事项如下： （一）旅行社业务经营许可证的颁发、变更、注销、吊销； （二）许可或暂停、停止旅行社经营出境、边境旅游业务； （三）旅行社经营或暂停、停止经营赴台旅游业务； （四）旅行社分社、服务网点设立与撤销备案； （五）旅行社委托代理招徕旅游者业务备案； （六）旅行社的违法经营行为； （七）旅行社的诚信记录； （八）旅游者对旅行社投诉信息； （九）旅行社质量保证金交存、增存、补存、降低交存比例和被执行赔偿等情况； （十）旅行社统计调查情况； （十一）全国和地区旅行社经营发展情况； （十二）旅游行政管理部门认为需要公开发布的其他有关旅行社的事项和情况信息。 第三条旅行社业务经营许可证颁发、变更公告，由颁发旅行社业务经营许可证和办理旅行社业务经营许可证变更事项的旅游行政管理部门发布。 旅行社业务经营许可证颁发公告，项目内容应该包括旅行社名称、

许可证编号、出资人、法定代表人、经营场所、许可经营业务、许可文号（附件1）。 旅行社业务经营许可证变更公告，项目内容应该包括旅行社许可证编号和变更前与变更后的名称、出资人、法定代表人、经营场所（附件2）。 第四条旅行社业务经营许可证注销、吊销公告，由办理注销旅行社业务经营许可证备案手续和作出吊销旅行社业务经营许可证决定的旅游行政管理部门发布。 旅行社业务经营许可证注销公告，项目内容应该包括旅行社名称、许可证编号、经营场所（附件3）。 旅行社业务经营许可证吊销公告，项目内容应该包括旅行社名称、许可证编号、主要负责人(附件4)。 第五条暂停旅行社业务公告，由作出暂停决定的旅游行政管理部门发布。 暂停旅行社业务公告，项目内容应该包括旅行社名称、许可证编号、经营场所、暂停时间期限(附件5)。 第六条许可或暂停、取消旅行社经营出境旅游业务公告，由国家旅游局或其委托出境旅游业务许可的省、自治区、直辖市旅游行政管理部门发布。 许可旅行社经营出境旅游业务公告，项目内容应该包括旅行社名称、原许可证编号、新许可证编号、出资人、法定代表人、经营场所、许可文号（附件6）。 暂停旅行社经营出境旅游业务公告，项目内容应该包括旅行社名称、许可证编号、经营场所、暂停时间期限（附件7）。 取消旅行社经营出境旅游业务公告，项目内容应该包括旅行社名

历年全国初中数学联赛试题总汇47321

1991年全国初中数学联合竞赛决赛试题 第一试 一、选择题 本题共有8个小题，每小题都给出了（A ）、（B ）（C ）、（D ）四个答案结论，其中只有一个是正确的．请把正确结论的代表字母写在题后的圆括号内． １． 设等式y a a x a y a a x a ---=-+-)()(在实数范围内成立，其中a ，x ，y 是 两两不同的实数，则2 22 23y xy x y xy x +--+的值是 （A ）3 ； （B ）31； （C ）2； （D ）3 5 ． 答（ ） ２． 如图，AB ‖EF ‖CD ，已知AB =20，CD =80，BC =100，那么EF 的值是 （A ） 10； （B ）12； （C ） 16； （D ）18． 答（ ） ３． 方程012=--x x 的解是 （A ） 25 1±； （B ）251±-； （C ） 2 5 1±或251±-； （D ）251±-±． 答（ ） ４． 已知：)19911991(2 11 1 n n x --=（n 是自然数）．那么n x x )1(2+-，的值是 （Ａ）11991-； （Ｂ）11991--； （Ｃ）1991)1(n -； （Ｄ）11991)1(--n ． 答（ ） ５． 若M n 1210099321=?????Λ，其中Ｍ为自然数，n 为使得等式成立的最大的自 然数，则Ｍ （Ａ）能被２整除，但不能被３整除； （Ｂ）能被３整除，但不能被２整除； （Ｃ）能被４整除，但不能被３整除； （Ｄ）不能被３整除，也不能被２整除．

答（ ） ６． 若a ，c ，d 是整数，b 是正整数，且满足c b a =+，d c b =+，a d c =+，那么 d c b a +++的最大值是 （Ａ）1-；（Ｂ）5-；（Ｃ）0；（Ｄ）１． 答（ ） ７． 如图，正方形OPQR 内接于ΔABC ．已知ΔAOR 、ΔBOP 和ΔCRQ 的面积分别是11=S ， 32=S 和13=S ，那么，正方形OPQR 的边长是 （Ａ）2；（Ｂ）3；（Ｃ）2 ；（Ｄ）3． 答（ ） ８． 在锐角ΔABC 中，1=AC ，c AB =，ο60=∠A ，ΔABC 的外接圆半径R ≤1，则 （Ａ）21< c < 2 ； （Ｂ）0< c ≤2 1 ； 答（ ） （C ）c > 2； （D ）c = 2． 答（ ） 二、填空题 １．Ｅ是平行四边形ABCD 中BC 边的中点，AE 交对角线BD 于G ，如果ΔBEG 的面积是１，则平行四边形ABCD 的面积是 ． ２．已知关于x 的一元二次方程02=++c bx ax 没有实数解．甲由于看错了二次项系数，误求得两根为２和４；乙由于看错了某一项系数的符号，误求得两根为－１和４，那么，=+a c b 32 ． 3．设m ，n ，p ，q 为非负数，且对一切x >０，q p n m x x x x )1(1)1(+=-+恒成立，则 =++q p n m 22)2( ． ４．四边形ABCD 中，∠ ABC ο135=，∠BCD ο120=，AB 6=，BC 35-=， CD = 6，则AD = ． 11=S 3S =1 32=S ο 120ο 135