第十二届全国青少年信息学奥林匹克联赛初赛试题讲解

2只有一堆时，无论有多少，先取者都可以一次性全部取走，所以必胜。

(1,1)时，显然先取者必败。

(1,2)时，先取者必胜，他可以在2那一堆中取1个，于是变成(1,1)，但这成为上一种情况了，于是接下来取的人必败，亦即先取者必胜。

(1,3)时，先取者必胜。他可以在3那一堆中取2个，于是变成(1,1)。

(2,2)时，先取者必败。他在任何一堆中取1个，对方随即在另一堆中取1个，即变成(1,1)；如果他取走一堆中的全部石子，对方即取走另一堆中的全部石子。

(2,3)时，先取者必胜。他可以在3那一堆中取1个，于是变成(2,2)。

(3,3)时，先取者必败。他取走任一堆中的1,2或3个，就变成了以上讨论过的情形。

(1,1,1)时，先取者必胜。他取走任一堆，就变成了(1,1)。

(1,1,2)时，先取者必胜。他取走2那一堆，就变成了(1,1)。

(1,1,3)时，先取者必胜。他取走3那一堆，就变成了(1,1)。

(1,2,2)时，先取者必胜。他取走1那一堆，就变成了(2,2)。

(1,2,3)时，先取者必败。分析如下：

他先取1那一堆，则变为(2,3)，由上面的分析，对手必胜。

他从2那一堆中取1个，就变成了(1,1,3)，对手可以将3那一堆全部取走，变成了(1,1)，于是必胜。

他将2那一堆全部取走，就变成了(1,3)，对手必胜。

他从3那一堆中取1个，就变成了(1,2,2)，对手必胜。

他从3那一堆中取2个，就变成了(1,2,1)，对手必胜。

他将3那一堆全部取走，就变成了(1,2)，对手必胜。

这些胜负有什么规律呢？我们可以将每堆的数转换成二进制，然后看每一位上所有堆里的1的个数总和：

必胜情况：(n) (1,2)(1,3)(2,3) (1,1,1)(1,1,2)(1,2,2)

必败情况： (1,1)(2,2)(3,3) (1,2,3)

化为二进制：

必胜情况：

(n)<只有1堆>：……（反正每位只要有1肯定只有1个）

(1,2)：1,10

列成竖式：

01

10

个位上只有1个1，“十位”（因为是二进制所以叫十位不妥，这里为了方便说明暂且使用，下同）上也只有1个1。

(1,3)：1,11

列成竖式：

01

11

个位上有2个1（1的1个，3的1个），十位上有1个1。

(2,3)：10,11

个位上有1个1，十位上有2个1。

(1,1,1)：1,1,1

个位上有3个1。

(1,1,2)：1,1,10

个位上有2个1，十位上有1个1。

(1,1,3)：1,1,11

个位上有3个1，十位上有1个1。

(1,2,2)：1,10,10

个位上有1个1，十位上有2个1。

必败情况：

(1,1)：1,1

个位上有2个1。

(2,2)：10,10

十位上有2个1。

(3,3)：11,11

个位上有2个1，十位上也有2个1。

(1,2,3)：1,10,11

个位上有2个1，十位上也有2个1。

下面分析一下这些情况。

先看必败情形。容易发现，所有的必败情形，都是所有的数位上都有偶数个1。

下看必胜情形。我们发现，出现了两种情况：

1只有1位上有奇数个1，如(1,3)(2,3)(1,1,1)(1,1,2)(1,2,2)。而先取者取走该位上的1，所有的位上就都变成了偶数个1，而这时后取者变成了先取者。

2有若干位上都是奇数个1，如(n)(1,2)(1,1,3)。先取者取（不一定取走哪位）后，所有的位上也都变成了偶数个1。后取者变成了先取者。

以上两种情况，都是将后取者逼至必败情况从而取胜。

由以上分析我们可以得到结论：将所有的堆的石子数化为二进制后，如果所有数位上的1的个数都是偶数，那么先取者必败；如果有些位上的1的个数是奇数，先取者能够将所有数位上的1的个数都变为偶数的话，那么先取者必胜。

好，下面来分析我们的题目。

3,5,7,19,50化为二进制是：

000011

000101

000111

010011

110010

可见，只有最高位的1是奇数个，其他位上都是偶数个。

所以只需要将最高位的1取走即可必胜。

二进制的100000就是10进制的32，所以要将50个石子的那堆取32个，取掉就变成偶数个数目。于是先取者必胜。以后无论对方怎么取，始终保证每一位上的1的个数是偶数即可（一种简单的方法是，他在一堆中取几个，你在另一堆中也取几个就可以）。

16 5个数通过7次比较排序的方法如下。

5个数之间的大小关系构成的一个树形图T。T中的一个结点代表一个数，而一条边代表它所

关联的两个数的大小关系，T的根就是中位数。显然T中的一条边要由一次比赛来确定。在

下

面的图中，如果x大于y，则节点x在节点y的上方且x和y有一条边相连。另外，表示一般的

数，o表示下一次即将进行比较的两个数。

第1步，先任取两个数比较，结果为：

|

o o

第2步，再取另外两个数比较，结果为：

o o

| |

第3步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：

/ \

o

|

o

第4步，按照上图比较其中两个标记为o的数，比较结果有两种情况：

o o

\ / \ / \

| / \

o o

第5步，按照上图比较其中两个标记为o的数，比较结果有两种情况：

| / \

o

/ \ |

o o o

| |

第6步，按照上图比较其中两个标记为o的数，比较结果有三种情况：

| | / \

o o

| | \ /

| / \ |

o o

|

其中第一种情况已经排好序了

第7步，按照上图比较其中两个标记为o的数，比较结果只有一种情况：

|

|

|

|

所以只需要7步比较就可以把5个数排好序

10D

另外，给你一份试卷及答案。

十二届全国青少年信息学奥林匹克联赛初赛试题

（ 普及组 Pascal 语言 二小时完成 ）

● ● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、 单项选择题 （共20题，每题15分，共计30分。每题有且仅有一个正确答案）。

1 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（ ）。

A 沃尔夫奖 B 诺贝尔奖 C 菲尔兹奖 D 图灵奖

2 在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（ ）。

A gcc/g++ B Turbo Pascal

C RHIDE D free pascal

3 以下断电之后仍能保存数据的有（ ）。

A 寄存器 B ROM C RAM D 高速缓存

4．Linux是一种( )。

A 绘图软件 B 程序设计语言 C *** 作系统 D 网络浏览器

5 CPU是( )的简称。

A 硬盘 B 中央处理器 C 高级程序语言 D 核心寄存器

6 在计算机中，防火墙的作用是（ ）。

A 防止火灾蔓延 B防止网络攻击

C 防止计算机死机 D 防止使用者误删除数据

7 在下列关于计算机语言的说法中，不正确的是（ ）。

A Pascal和C都是编译执行的高级语言

B 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上

C C++是历史上的第一个支持面向对象的计算机语言

D 与汇编语言相比，高级语言程序更容易阅读

8 在下列关于计算机算法的说法中，不正确的是（ ）。

A 一个正确的算法至少要有一个输入

B 算法的改进，在很大程度上推动了计算机科学与技术的进步

C 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性

D 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法

9 在下列各种排序算法中，不是以"比较"作为主要 *** 作的算法是（ ）。

A 选择排序 B 冒泡排序 C 插入排序 D 基数排序

10．在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如10001000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（ ）。

A 没有区别 B 按行读的方式要高一些

C 按列读的方式要高一些 D 取决于数组的存储方式。

11．在Pascal语言中，表达式 (21 xor 2)的值是（ ）

A 441 B 42 C23 D24

12．在Pascal语言中，判断a不等于0且b不等于0的正确的条件表达式是（ ）

A not a=0 or not b=0 B not((a=0)and(b=0))

C not(a=0 and b=0) D (a<>0)and (b<>0)

13．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为："进，出，进，进，进，出，出，进，进，进，出,出"。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ ）。

A 1, 2, 3, 4, 5 B 1, 2, 4, 5, 7

C 1, 4, 3, 7, 6 D 1, 4, 3, 7, 2

14．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（ ）。

A 10 B 11 C 12 D 13

15 与十进制数1770 对应的八进制数是（ ）。

A 3350 B 3351 C 3352 D 3540

16．将5个数的序列排序，不论原先的顺序如何，最少都可以通过（ ）次比较，完成从小到大的排序。

A 6 B 7 C 8 D 9

17 设A=B=D=true，C=false，以下逻辑运算表达式值为真的有（ ）。

A (A∧B)∨(C∧D) B ((A∨B∨D)∧C)

C A∧(B∨C∨D) D (A∧B∧C)∨ D

18 (2010)16 + (32)8的结果是（ ）。

A (8234)10 B (202B)16

C (20056)8 D (100000000110)2

19 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。

A a, b, c, e, d B b, c, a, e, d

C a, e, c, b, d D d, c, e, b, a

20 已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ）

A 3 2 1 4 6 5 B 3 2 1 5 4 6

C 2 1 3 5 4 6 D 2 3 1 4 6 5

二．问题求解（共2题，每题5分，共计10分）

1．（寻找假币） 现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：_________________________________________________。

2．（取石子游戏） 现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：

_________________________________________________。

三．阅读程序写结果（共4题，每题8分，共计32分）

1 Program ex301;

var

u:array[03] of integer;

i,a,b,x,y:integer;

begin

y:=10;

for i:=0 to 3 do

read(u[i]);

a:=(u[0]+u[1]+u[2]+u[3]) div 7;

b:=u[0] div ((u[1]-u[2]) div u[3]);

x:=(u[0]+a+2)-u[(u[3]+3) mod 4];

if (x>10) then

y:=y+(b100-u[3]) div (u[u[0] mod 3]5)

else

y:=y+20+(b100-u[3]) div (u[u[0] mod 3]5);

writeln (x,',',y);

end {注：本例中，给定的输入数据可以避免分母为0或下标越界。 }

输入：9 3 9 4

输出：_______________

2Program ex302;

const

m:array[04] of integer=(2,3,5,7,13);

var

i,j:integer;

t: longint;

begin

for i:=0 to 4 do

begin

t:=1;

for j:=1 to m[i]-1 do

t:=t2;

t:=(t2-1)t;

write (t,' ');

end;

writeln;

end

输出:____________________

3Program ex303;

Const

NN=7;

Type

Arr1=array[030] of char;

var

s:arr1;

k,p:integer;

Function fun(s:arr1; a:char;n:integer):integer;

var

j:integer;

begin

j:=n;

while (a<s[j])and(j>0) do dec(j);

fun:=j;

end;

begin

for k:=1 to NN do

s[k]:=chr(ord('A')+2k+1);

k:=fun(s,'M',NN);

writeln(k);

end

输出：_____________

4program ex304;

var

x,x2:longint;

procedure digit(n,m:longint);

var n2:integer;

begin

if(m>0) then

begin

n2:=n mod 10;

write(n2:2);

if(m>1) then digit(n div 10,m div 10);

n2:=n mod 10;

write(n2:2);

end;

end;

begin

writeln('Input a number:');

readln(x);

x2:=1;

while(x2<x) do x2:=x210;

x2:=x2 div 10;

digit(x,x2);

writeln; 5

end

输入：9734526

输出：______________________________

四．完善程序 (前4空，每空25分，后6空，每空3分，共28分)

1．（全排列）下面程序的功能是利用递归方法生成从1到n(n<10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）：

123 132 213 231 321

312

程序：

Program ex401;

Var

i,n,k:integer;

a:array[110] of integer;

count:longint; {变量count记录不同排列的个数，这里用于控制换行}

Procedure perm(k:integer);

var j,p,t:integer;

begin

if ① then

begin

inc(count);

for p:=1 to k do

write(a[p]:1);

write(' ');

if ( ② ) then writeln;

exit;

end;

for j:=k to n do

begin

t:=a[k]; a[k]:=a[j]; a[j]:=t;

③ ;

t:=a[k]; ④ ;

end

end;

begin

writeln('Entry n:');

read(n);

count:=0;

for i:=1 to n do a[i]:=i;

⑤ ;

end

2 由键盘输入一个奇数 P (P<100,000,000)，其个位数字不是5，求一个整数 S，使 P×S = 11111 ( 在给定的条件下，解 S 必存在)。要求在屏幕上依次输出以下结果:

（1）S 的全部数字。除最后一行外，每行输出 50 位数字。 （2） 乘积的数字位数。

例1：输入p=13，由于138547=111111，则应输出（1）8547，（2）6

例2：输入p=147，则输出结果应为（1）755857898715041572184429327286470143613

（2）42，即等式的右端有42个1。

程序：

program ex402;

var

p,a,b,c,t,n:longint;

begin

while (true) do

begin

writeln ('Input p, the last digit is 1 or 3 or 7 or 9:');

readln(p);

if (p mod 2<>0)and(p mod 5<>0) then

⑥ ; {如果输入的数符合要求，结束循环 }

end;

a:=0; n:=0;

while (a<p) do

begin

a:=a10+1; inc(n);

end;

t:=0;

repeat

b:=a div p;

write(b:1);

inc(t);

if ( ⑦ ) then writeln;

c:= ⑧ ; a:= ⑨ inc(n);

until c<=0;

dec(n);

writeln; writeln('n=', ⑩ );

end

子集那个主要是自己划分，比较费时间，如果不会加我QQ21014873，我教你。

蓝桥杯题目分组不同，因此题目的难易程度不同。本科B组题一般针对非985，211学校的学生参加，因此题目相对比较简单。但是含金量较低。本科A组及研究生组一般针对985，211学校其中的一些学校学生参加，竞争相对激烈，所以题目相对较难。蓝桥杯分为以下几种:

1、C程序设计:包括本科A组，本科B组，高职高专组；

2、Java软件开发:也分为本科A组，本科B组，高职高专组；

3、嵌入式设计与开发:包括大学组，研究生组；

4、单片机设计与开发:大学组；

5、电子设计与开发:大学组。

以上就是关于第十二届全国青少年信息学奥林匹克联赛初赛试题讲解全部的内容，包括:第十二届全国青少年信息学奥林匹克联赛初赛试题讲解、蓝桥杯青少年stema理论题为什么难、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！