信息学奥林匹克复赛辅导材料.doc

完整版)信息学奥林匹克复赛辅导材料
信息学奥林匹克复赛辅导一：
数学分析
在去年竞赛中，数学分析类试题频繁出现,由此可以看出数学和程序设计之间的“孪生关系”：数学中难以用笔和纸推算的问题需要借助计算机解决；而编程者要解决此类问题，需要有坚实的数学功底和灵活的应变能力，能够对运算对象进行组合分析—怎样计算具有某种特性的对象个数，怎样枚举这些对象。信息学竞赛中离散数和有限数一类试题激增，正说明了信息学与数学的依赖关系日益凸现，数学需要反映计算机的计算、检索、记忆、决策的原理和机制，信息学的发展需要现代数学的支撑。两门学科的整合是国际中学理科教育发展的一个大趋势.
§1.1 解方程
使用计算机解方程，与其说是考核选手的编程技术，不如说是考核选手的数学机巧和能力.解题的关键是通过数学分析得出计算公式和公式中变数的取值范围，在此基础上通过顺序查找或分治法枚举变数的可能值,将符合条件的变数代入表达式,即可得出问题的解。这是编程解数学题的一般思路,也是程序设计竞赛与数学竞赛的区别所在
【例题一】反正切函数的应用（全国赛）
反正切函数可展开成无穷级数，有如下公式
(其中) 公式（1）
使用反正切函数计算是一种常用的方法.例如，最简单的计算的方法：
公式（2）
然而,这种方法的效率很低,但我们可以根据角度和的正切函数公式：
公式(3）
通过简单的变换得到：
公式4)
利用这个公式,令，则，有

使用和的反正切来计算，速度就快多了.
我们将公式（4）写成如下形式

其中、和均为正整数.
我们的问题是：对于每一个给定的（)，求＋的值。我们保证对于任意的a都存在整数解。如果有多个解,要求你给出+最小的解。

输入文件(arctan.in）
输入文件中只有一个正整数,其中。

输出文件（arctan。out）
输出文件中只有一个整数，为+的值。
输入样例
1
输出样例
5
【例题二】一元三次方程求解（分区联赛）
有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a,b，c，d 均为实数），并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值≥1。
要求由小到大依次在同一行输出这三个实根（根与根之间留有空格)，并精确到小数点后2位。
提示:记方程f(x)=0，若存在2个数x1和x2,且x1〈x2，f（x1）＊f（x2)＜0，则在(x1，x2）之间一定有一个根。
【样例】
输入： 1 —5 —4 20
输出： -2.00 2.00 5.00

§1。2逻辑推理
将运算对象定义为逻辑变量，按照题意要求和对象间的关系进行布尔运算，推理问题的解.这里提醒大家的是注意理解题意。解题过程是一个不断发掘已知条件、向目标靠拢的过程因此不能视题目的文字描述为鸡肋，不屑一顾。有时候文字描述中蕴藏了丰富的信息,对解题起到了决定性的作用。只有在全面正确的理解题意的基础上，才能准确定义对象间的关系,通过布尔运算进行合乎逻辑的推理.
【例题三】聪明的学生（组队赛）
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A，B和C.有一天，教授给他们三人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们,每个人的纸条上都写了一个正整数,且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数,但却看不见自己的数。

这时，教授先对学生A发问了：“你能猜出自己的数吗?”A回答：“不能。”
教授又转身问学生B：“你能猜出自己的数吗？"B想了想，也回答：“不能。”
教授再问学生C同样的问题,C思考了片刻后，摇了摇头：“不能”。
接着，教授又重新问A同样的问题，再问B和C,……，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误的报了出来。
现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M，你能推断出另外两个学生的头上贴的是什么数吗？
提示：在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是“不能”；而且除此之外在A,B，C之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。
教授总是从学生A开始提问的.
你可以假定，这三个足够聪明的学生能够根据已知的条件在最早的轮次猜出自己的数,并且永远都不会猜错.
稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数.

输入：
输入文件为guess.in.
该文件包括若干组测试数据,其中的每一行代表一组测试数据,由两个整数N和M组成（即在教授第N次提问时,轮到回答问题的那个人猜出了贴在自己头上的数是M）。两个数之间用空格分隔开。最后,由-1 -1组成的一行标志着输入数据的结束。
0输出文件为guess。out。按照输入文件中的顺序依次给出各组数据的结果.
文件中对应每组数据的输出的第一行是一个整数p,是可能情况的总数.接下来的p行，每一行包括三个数,分别为贴在A,B,C头上的三个数。输出时，所有解按照A头上的数增序排列；在A头上的数相同的情况下，按照B头上的数增序排列。
输入输出样例：
Guess.in
5 8
3 2
2 3
-1 -1

Guess.out
3
2 8 6
5 8 3
6 8 2
1
1 1 2
1
2 3 1

§1.3初等数论
初等数论是用初等数学方法来研究整数的整除、不定方程、同余式等方面问题的数论分支。其内容包括碾转相除法、因数、倍数、公因数、公倍数、最大公因数、最小公倍数、素数、合数、等。初等数论中难以用笔和纸推算的问题可以借助计算机解决.
【例题四】最大公约数与最小公倍数问题(分区联赛）
输入二个正整数x0，y0（2≤x0<100000，2≤y0≤1000000)，求出满足下列条件的p，q的个数：
条件：1．p，q是正整数
2．要求p，q以x0为最大公约数，以y0为最小公倍数。
试求：满足条件的所有可能的两个正整数的个数。
【样例】
输入：x0=3 y0=60
输出：4
说明：(不用输出)此时的p q分别为:
3 60
15 12
12 15
60 3
所以满足条件的所有可能的两个正整数的个数共4种。
§1。4组合分析
对运算对象进行组合分析，利用计数公式计算具有某种特性的对象个数,或者枚举这些对象.对一些简单的题，可通过组合分析直接得出计数公式;对搜索类试题使用“组合分析+局部搜索"的方法，可显著提高计算效率。
【例题五】数的计数(分区联赛）
我们要求找出具有下列性质数的个数(包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：
1． 不作任何处理；
2． 在它的左边加上一个自然数，但该自然数不能超过原数的一半；
3． 加上数后，继续按此规则进行处理,直到不能再加自然数为止。
【样例】
输入：6
满足条件的数为 6（此部分不必输出）
16
26
126
36
136
输出：6
【例题六】Twofive(国际赛）
圣诞老人和它的小助手之间的秘密信息通常用一种25语言编码。这种25语言的字母标语拉丁字母表相同，唯一的例外是没有字母’Z’，换句话说，25语言的字母表包含从’A’到’Y’25个字母,顺序与拉丁字母表相同.25语言中的每个单词刚好包含25个不同的字母。一个单词可以写成一个按行排列的5 x 5的矩阵表;例如，单词ADJPTBEKQUCGLRVFINSWHMOXY被表示成：
A D J P T
B E K Q U
C G L R V
F I N S W
H M O X Y
25语言中的一个有效单词是每行每列的字母均按升序排列的5 x 5矩阵表.所以，ADJPTBEKQUCGLRVFINSWHMOXY是一个有效单词，与此相反，ADJPTBEGQUCKLRVFINSWHMOXY则不是一个有效单词（第2列违反升序排列，第3列同样不符合）。
圣诞老人有一本字典.该字典是一个按升序排列（字典序)的所有有效的25语言单词表，并且从1开始编号。例如，ABCDEFGHIJKLMNOPQRSTUVWXY是字典中编号为1的单词，而ABCDEFGHIJKLMNOPQRSUTVWXY是字典中编号为2的单词，该单词是在编号为1的单词中将U和T的位置互换而成。然而,这个字典规模非常庞大。请写一个程序确定一个任意给定单词的编号，同时也可用来查询一个给定编号所对应的单词。字典中的单词数不会超过231 。
输入
输入文件名是twofive。in。第一行是由一个字母’W'或'N'组成的串：
如果第一行的串为'W’，则第二行包含一个25语言的有效单词。如果第一行的串为'N'，则第二行包含一个25语言有效单词的编号。
输出
输出文件名是twofive。out，并且输出由一行组成：
如果输入文件的第二行包含一个25语言的有效单词，则输出文件的那一行包含该单词的编号。如果输入文件的第二行包含一个编号,则输出文件的那一行包含该编号所代表的25语言的有效单词。
输入输出示例
2
twofive。in twofive.out
W
ABCDEFGHIJKLMNOPQRSUTVWXY

towfive.in twofive。out
ABCDEFGHIJKLMNOPQRSUTVWXY
N
2

§1。5线性代数
根据题意构造方程组（1≤k≤m)，建立m*(n+1)的系数矩阵A（图1.5。1，其中常数项b为n+1列）.

图1.5.1
通过消元求系数矩阵中的一个子单位矩阵(该子矩阵除主对角线的元素为1外,其余元素为零（图1。5.2）)

图1。5。2
显然，aii=1，表明xi=bi’.只有当零行的常数项全零时，方程有解。若出现零行的常数项非零的情况，则方程无解.
选手应该掌握计算线性方程组的基本理论,能够根据题意要求列出线性方程组，能够编程求解线性方程组，并通过讨论解的情况推出答案。
【例题七】GPA排名系统（组队赛）
目前,高等院校往往采用GPA（Grade Point Average）来评价学生的学术表现。传统的排名方式是求每一个学生的平均成绩，以平均成绩作为依据进行排名.
但是这样的排名方法已经引起了教育界以及社会各界人士的争议。因为它存在着许多弊端。对于不同的课程,选课学生的平均成绩会不同程度地受到课程的难易程度和老师的严厉程度的制约。因而这样的排名系统无形中就鼓励了学生选择一些比较容易的课程，因为这样可以事半功倍地获得较高的平均分.
为了克服这些弊端,我们需要对排名系统做一定的改进。一种改进的方案是对选第i门课的每一个学生的成绩加上一个特定的修正值di，例如编号为j的学生该课的成绩Gij修改为G’ij=Gij+di.最终使得经过调整后,该课的平均分等于选该课的所有学生的所有课的平均分.对每一门课都做这样的调整，使得上述条件对所有课程都满足。这种调整方案一定程度地避免了传统排名系统的不公正。而你的任务正是根据一个大学某一个年级学生某学年的成绩，给出他们的排名.假设每一个学生都至少选一门课。
输入:
输入文件为gap。in。
输入文件第一行是两个正整数m(1≤m≤500）和n（1≤n≤100)，分别表示学生人数和课程数目。
接下来m行是一个矩阵,矩阵中第i 行的第j个元素表示第i个学生第j门课的成绩G（i,j）。输入的成绩是一个0到100之间的整数，如果该学生没有选这门课，那么G（i,j）＝-1。由于该方案的施行只是为了获得更加科学的排名，因此调整后的成绩的数值大小本身没有什么意义，因此调整后的成绩可以不是0－100之间的数.
输出:
输出文件为gpa。out。
输出采用改进方案后这些学生的排名。以学生编号的形式输出，每行是一个学生的编号。
如果在上述调整后，有若干学生平均分相等(精确到小数点后的三位），则他们的名次相同，按照任意顺序输出.
当然许多时候，上述调整无法顺利进行，即调整的目标无法达到。（因此,在实际问题中，我们往往在最小二乘意义下获得一种最接近目标的调整方案.）也有可能或者因调整不唯一而不能确定学生的名次.若以上两种情况发生，则输出“fail"。
输入输出样例:
Gpa.in
4 2
60 —1
70 -1
80 45
—1 65
Gpa.out
4
3
2
1

样例说明：
一种可行的调整方法是:
第一门课每一个学生的成绩加上10，第二门课每一个学生的成绩加上35。
调整后的情况是:
70 –1
80 –1
90 80
-1 100
调整后第一门课的平均分为：(70＋80+90)/3=80
选第一门课的所有学生的所有课的平均分为：（70+80+90+80）/4=80.
第二门课的平均分为：（80+100）/2=90
选第二门课的所有学生的所有课的平均分为：（90+80+100)/3=90
然后,计算每一个学生的平均分并且排名,即得到了输出的结果。