蓝书刘汝佳算法竞赛入门经典勘误

大牛为你推荐十本最适合信息学竞赛的书籍展开全文1. 信息学竞赛书籍1) 《全国信息学奥林匹克联赛》系列【作者】吴文虎王建德【简介】全书对试题进行了类型归纳，并分上、下两册出版。

上册包括基础类试题、数据结构类试题、搜索类试题和动态程序设计类试题。

下册包括计算几何类试题和构造类试题。

全书对每种类型试题作了简要的介绍，所有的试题都给出了具体的算法分析和相应的源代码。

本书既适合教师辅导学生使用，也适合参加信息学奥林匹克竞赛的学生自学。

2) 《信息学奥林匹克教程》系列【作者】向期中吴耀斌曹利国朱全民【简介】该套教程根据NOIP、NOI及IOI的要求，以算法为主线，以习题分析为载体，深入浅出，既有各个算法设计基本思路的讲解及对求解问题的分析，又给出了具体的编程思路与参考程序。

其中，第三册提高篇主要针对提高竞赛水平的学生，详细阐述了基本算法设计策略、搜索及搜索优化方法、图论算法处理及其动态规划的应用等内容，为适应信息学竞赛新的发展的需要，还简单介绍了Linux 操作系统、Gcc、Free Pascal编程环境。

并附有联系测试题。

3) 《全国青少年信息学奥林匹克联赛培训教材》系列【作者】吴再陵【简介】本系列丛书是由中国计算机学会委托江苏省青少年科技中心编写的一套信息学奥林匹克辅导参考书。

本丛书注重系统性、入门性与实用性，始终围绕编程实践，以算法分析为主线，讲思想、讲方法，侧重基础联系，引导学生在参与的实践中掌握科学思维方法，提高使用计算机的能力。

本书主要围绕PASCAL语言，深入浅出地讲解程序设计，是入门者不可多得的一本好书。

本书是专门针对PASCAL语言学习的一本习题集，给出了具体的算法分析和参考程序清单。

4) 《信息学奥林匹克竞赛指导》系列【作者】吴文虎王建德【简介】该系列丛书主要讲了数论、图论、组合数学等相关知识点。

该系列丛书的特点是既有基本概念的讲解及对所解问题的分析，又有编程的思路与参考程序。

本书是参加奥林匹克竞赛学生的必读书，也可作为大学生的参考书。

数学伴你学答案数学，作为一门重要的学科，是我们日常生活中不可或缺的一部分。

无论是做生意、计算货币、解决计划或者是进行科学研究，数学都是必不可少的工具。

然而，毫不吹捧地说，数学并不是每个人都喜欢的学科。

一些学生，甚至有点害怕数学，认为它难以理解，甚至认为数学是“毒瘤”。

事实上，并非每一个人都可以像Einstein那样，将数学视为“最高坦白的哲学。

”但是，通过改变对数学的态度和方法，每个人都可以掌握数学的基础知识，并理解如何将这些理论应用于日常生活。

通过良好的数学学习方法和技巧的掌握，我们可以大大提高我们的数学理解和能力，让我们一起来探讨一下。

首先，最重要的是改变对数学的态度。

虽然很多人觉得数学很难，但事实上数学不难。

数学对于我们的生活是至关重要的。

数学是解决现实问题的重要工具，有很多真实的例子可以证明这点。

因此我们必须对数学学习充满信心，不能放弃，要对它抱乐观的态度。

其次，要学会用正确的方法来学习数学。

除了学习数学概念和理论外，我们可以结合一些实践来掌握数学技巧。

刘汝佳的“算法竞赛入门经典”或Skiena的“算法设计和分析基础原理”等教材，在学习数字理论，组合数学，图论等数学相关技巧时是非常有用的资料，它们可以帮助我们学习数学知识，同时也培养了我们的思维和解决问题的能力。

此外，我们还可以选择一些在线数学课程或视频资源，如卡内基梅隆大学的公开课、麻省理工学院的OCW 等，它们可以帮助我们更有效地学习数学知识。

最后，我们可以通过练习来提高我们的数学能力。

做数学题并不是在考试前好好准备，或者仅在学校课堂上做作业，而是一个日常学习过程。

我们可以通过刷题来提高我们的技能，并确保我们对数学知识的掌握程度。

可以使用一些教辅资料或者在线平台，如Khan Academy、真题人生、知乎问题广场等，帮助我们更好地进行练习和复习。

总的来说，数学对我们的生活至关重要，并且学习数学可以提高我们的思维解决问题的能力，从而更好地适应现代复杂的社会格局。

算法竞赛⼊门经典习题解答思考题因为浮点数+=0.1之后变成0.10000000000000001，⽽不是真正的0.1，所以造成了永远⽆法等于10.1，形成死循环。

倒三⾓形第⼀种解法：逆序倒三⾓形第⼆种解法顺序；程序3-1 逆序输出蛇形填数#include <iostream>#include <cstdio>int const maxn = 101;int n,a[maxn][maxn];using namespace std;int main(){cin>>n;int x = 0,y = n-1,tot;tot = a[x][y] = 1;while(tot < n*n){while(x+1<n && !a[x+1][y]) a[++x][y] = ++tot;while(y-1>=0 && !a[x][y-1]) a[x][--y] = ++tot;while(x-1>=0 && !a[x-1][y]) a[--x][y] = ++tot;while(y+1<n && !a[x][y+1]) a[x][++y] = ++tot;}for(int i = 0;i<n;i++){for(int j = 0;j<n;j++)printf("%4d",a[i][j]);cout<<endl;}return 0;}错误之处：1、没有写终⽌打破循环的条件tot < n*n;2、条件⾥⾯没有写下⼀个位置的条件即使+1或-1，判断为空⾥⾯⽤了⾃增，⽽应该要⽤下⼀个位置+1或-1.3、赋值语句⾥⾯应该要⽤⾃增或⾃减。

运⾏效果如下所⽰：TeX 中的引号例题 3-3 回⽂词（Palindrome, Uva401）Uva1586 分⼦量。

#《算法竞赛入门经典》勘误关于勘误¶下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。

有发现新错误的欢迎大家在留言中指出，谢谢！一些一般性的问题¶运算符<?、>?已经被废弃，请用min、max代替（代码仓库中的代码已更新，g++ 4.6.2下编译通过）重大错误¶p24. 最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。

(感谢imxivid）p43. 最后，判断s[i..j]是否为回文串的方法也不难写出：int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++)(感谢imxivid）p45. 第七行和第九行i-j+1应为i+j+1。

修改后：1. {2. for (j = 0; i - j >= 0 && i + j < m; j++)3. {4. if (s[i - j] != s[i + j]) break;5. if (j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];}6. }7. for (j = 0;i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if (s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. } 13. }p53. 例题4-1. 组合数. 输入非负整数n和m，这里的n和m写反了。

应是“输入非负整数m和n”。

关于贪⼼算法的经典问题（算法效率or动态规划）如题，贪⼼算法⾪属于提⾼算法效率的⽅法，也常与动态规划的思路相挂钩或⼀同出现。

下⾯介绍⼏个经典贪⼼问题。

（参考⾃刘汝佳著《算法竞赛⼊门经典》）。

P.S.下⽂皆是我⼀个字⼀个字敲出来的，绝对“童叟⽆欺”，哈哈。

(。

⌒∇⌒) 耗费了我的很多时间，所以——希望对⼤家有帮助啊~ (=^‸^=)⼀、背包相关问题1.最优装载问题：给出N个物体，有⼀定重量。

请选择尽量多的物体，使总重量不超过C。

解法：只关⼼数量多，便把重量从⼩到⼤排序，依次选，直到装不下。

2.部分背包问题：给出N个物体，有⼀定重量和价值。

请选择⼀些物体的⼀部分使在总重量不超过C的条件下总价值最⼤。

解法：关⼼总价值⼤，物体可取部分，便优先取单位重量价值较⼤的物体。

3.乘船问题：有N个⼈，有⼀定重量。

每艘船的最⼤载重量均为C，且最多载2⼈。

请⽤最少的船装载所有⼈。

解法：关⼼数量少，要尽量使每艘船的实际载重量尽量接近于最⼤载重量。

便把重量从⼩到⼤排序，每艘船依次先载⼀个⼈，再载重量最接近船的剩余可载重量的⼈。

这样可以使眼前的消费（剩余载重量）最少。

实现：⽤2个变量 l , r 分别从两头往中间移动，l 和 r 可共乘⼀艘船，或 r ⾃⼰乘⼀艘船。

⼆、区间相关问题1.选择不相交区间：数轴上有N个开区间(Li,Ri)，请选择尽量多个区间，并保证这些区间两两没有公共点。

解法：先把这些区间按找 Ri 从⼩到⼤的顺序排序，再对按序排列的每2个区间A,B分情况讨论：(1)A被B包含，选A最优；(2)A右边的⼀部分与B左边的⼀部分相交，选A最优，因为选A⽐B减少了与后⾯区间相交的可能性；(3)A、B不相交，便2个都选。

总的来说就是排序后，从左到右选第⼀个没有与前⾯已选的区间相交的区间。

O(n)。

拓展：那么如果可以⼀共覆盖两次，那该怎么选？ ——也就是。

2.区间选点问题：数轴上有N个闭区间[Li,Ri]，请选择尽量少的点，使得每个区间内都⾄少有⼀个点。

10250-The Other Two TreesYou have a quadrilateral shaped land whose opposite fences are of equal length.You have four neighbors whose lands are exactly adjacent to your four fences,that means you have a common fence with all of them.For example if you have a fence of length d in one side,this fence of length d is also the fence of the adjacent neighbor on that side.The adjacent neighbors have no fence in common among themselves and their lands also don’t intersect.The main difference between their land and your land is that their lands are all square shaped.All your neighbors have a tree at the center of their lands.Given the Cartesian coordinates of trees of two opposite neighbors,you will have to find the Cartesian coordinates of the other two trees.InputThe input file contains several lines of input.Each line contains four floating point or integer numbers x1,y1,x2,y2, where(x1,y1),(x2,y2)are the coordinates of the trees of two opposite neighbors.Input is terminated by end of file. OutputFor each line of input produce one line of output which contains the line“Impossible.”without the quotes,if you cannot determine the coordinates of the other two trees.Otherwise,print four floating point numbers separated by a single space with ten digits after the decimal point ax1,ay1,ax2,ay2,where(ax1,ay1)and(ax2,ay2)are the coordinates of the other two trees.The output will be checked with special judge program,so don’t worry about the ordering of the points or small precision errors.The sample output will make it clear.Sample Input100-100100-100100-100Sample Output0.000000000010.00000000000.0000000000-10.00000000000.000000000010.0000000000-0.0000000000-10.00000000000.0000000000-10.00000000000.000000000010.0000000000579–ClockHandsThe medieval interest in mechanical contrivances is well illustrated by the development of the mechanical clock,the oldest of which is driven by weights and controlled by a verge,an oscillating arm engaging with a gear wheel.It dates back to1386.Clocks driven by springs had appeared by the mid-15th century,making it possible to con-struct more compact mechanisms and preparing the way for the portable clock.English spring-driven pendulum clocks were first commonly kept on a small wall bracket and later on a shelf.Many bracket clocks contained a drawer to hold the winding key.The earliest bracket clocks,made for a period after1660, were of architectural design,with pillars at the sides and a pediment on top.In17th-and18th-century France,the table clock became an object of monumental design,the best examples of which are minor works of sculpture.The longcase clocks(also called grandfather clocks)are tall pendulum clock enclosed in a wooden case that stands upon the floor and is typically from6to7.5feet(1.8to2.3m)in ter,the name``grandfather clock''became popular after the popular song"My Grandfather's Clock,"written in1876by Henry Clay Work.One of the first atomic clocks was an ammonia-controlled clock.It was built in1949at the National Bureau of Standards, Washington,D.C.;in this clock the frequency did not vary by more than one part in108Nuclear clocks are built using two clocks.The aggregate of atoms that emit the gamma radiation of precise frequency may be called the emitter clock;the group of atoms that absorb this radiation is the absorber clock.One pair of these nuclear clocks can detect energy changes of one part in1014,being about1,000times more sensitive than the best atomic clock.The cesium clock is the most accurate type of clock yet developed.This device makes use of transitions between the spin states of the cesium nucleus and produces a frequency which is so regular that it has been adopted for establishing the time standard.The history of clocks is fascinating,but unrelated to this problem.In this problem,you are asked to find the anglebetween the minute hand and the hour hand on a regular analog clock.Assume that the second hand,if there were one, would be pointing straight up at the12.Give all angles as the smallest positive angles.For example9:00is90degrees; not-90or270degrees.InputThe input is a list of times in the form H:M,each on their own line,with and.The input is terminated with the time 0:00.Note that H may be represented with1or2digits(for1-9or10-12,respectively);M is always represented with2 digits(The input times are what you typically see on a digital clock).OutputThe output displays the smallest positive angle in degrees between the hands for each time.The answer should between 0degrees and180degrees for all input times.Display each angle on a line by itself in the same order as the input.The output should be rounded to the nearest1/1000,i.e.,three places after the decimal point should be printed.Sample Input12:009:008:100:00Sample Output0.00090.000175.000375-Inscribed Circles and Isosceles TrianglesGiven two real numbersBthe width of the base of an isosceles triangle in inchesHthe altitude of the same isosceles triangle in inchesCompute to six significant decimal placesCthe sum of the circumferences of a series of inscribed circles stacked one on top of another from the base to the peak; such that the lowest inscribed circle is tangent to the base and the two sides and the next higher inscribed circle is tangent to the lowest inscribed circle and the two sides,etc.In order to keep the time required to compute the result within reasonable bounds,you may limit the radius of the smallest inscribed circle in the stack to a single precision floating point value of0.000001.For those whose geometry and trigonometry are a bit rusty,the center of an inscribed circle is at the point of intersection of the three angular bisectors.InputThe input begins with a single positive integer on a line by itself indicating the number of the cases following,each of them as described below.This line is followed by a blank line,and there is also a blank line between two consecutive inputs.The input will be a single line of text containing two positive single precision real numbers(B H)separated by spaces. OutputFor each test case,the output must follow the description below.The outputs of two consecutive cases will be separated by a blank line.The output should be a single real number with twelve significant digits,six of which follow the decimal point.The decimal point must be printed in column7.Sample Input10.2634510.263451Sample Output0.82764810387–BilliardIn a billiard table with horizontal side a inches and vertical side b inches,a ball is launched from the middle of the table. After s>0seconds the ball returns to the point from which it was launched,after having made m bounces off the vertical sides and n bounces off the horizontal sides of the table.Find the launching angle A(measured from the horizontal), which will be between0and90degrees inclusive,and the initial velocity of the ball.Assume that the collisions with a side are elastic(no energy loss),and thus the velocity component of the ball parallel to each side remains unchanged.Also,assume the ball has a radius of zero.Remember that,unlike pool tables,billiard tables have no pockets.InputInput consists of a sequence of lines,each containing five nonnegative integers separated by whitespace.The five numbers are:a,b,s,m,and n,respectively.All numbers are positive integers not greater than10000.Input is terminated by a line containing five zeroes.OutputFor each input line except the last,output a line containing two real numbers(accurate to two decimal places)separated by a single space.The first number is the measure of the angle A in degrees and the second is the velocity of the ball measured in inches per second,according to the description above.Sample Input10010011120010053420113248190015600000Sample Output45.00141.4233.69144.223.097967.8110112-Myacm TrianglesSource file:triangle.{c,cpp,java,pas}Input file:triangle.inOutput file:triangle.outThere has been considerable archeological work on the ancient Myacm culture.Many artifacts have been found in what have been called power fields:a fairly small area,less than100meters square where there are from four to fifteen tall monuments with crystals on top.Such an area is mapped out above.Most of the artifacts discovered have come from inside a triangular area between just three of the monuments,now called the power triangle.After considerable analysis archeologists agree how this triangle is selected from all the triangles with three monuments as vertices:it is the triangle with the largest possible area that does not contain any other monuments inside the triangle or on an edge of the triangle.Each field contains only one such triangle.Archeological teams are continuing to find more power fields.They would like to automate the task of locating the power triangles in power fields.Write a program that takes the positions of the monuments in any number of power fields as input and determines the power triangle for each power field.A useful formula:the area of a triangle with vertices(x1,y1),(x2,y2),and(x3,y3)is the absolute value of0.5×[(y3-y1)(x2-x1)-(y2-y1)(x3-x1)].For each power field there are several lines of data.The first line is the number of monuments:at least4,and at most15. For each monument there is a data line that starts with a one character label for the monument and is followed by the coordinates of the monument,which are nonnegative integers less than100.The first label is A,and the next is B,and so on.There is at least one such power field described.The end of input is indicated by a0for the number of monuments.The first sample data below corresponds to the diagram in the problem.For each power field there is one line of output.It contains the three labels of the vertices of the power triangle,listed in increasing alphabetical order,with no spaces.Example input: 6A10B40C03D13E44F064A00B10C990D9999Example output: BEFBCD。

算法竞赛-入门经典-作者刘汝佳.doc第1部分语言篇第1章程序设计入门学习目标☑熟悉C语言程序的编译和运行☑学会编程计算并输出常见的算术表达式的结果☑掌握整数和浮点数的含义和输出方法☑掌握数学函数的使用方法☑初步了解变量的含义☑掌握整数和浮点数变量的声明方法☑掌握整数和浮点数变量的读入方法☑掌握变量交换的三变量法☑理解算法竞赛中的程序三步曲：输入、计算、输出☑记住算法竞赛的目标及其对程序的要求计算机速度快，很适合做计算和逻辑判断工作。

本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。

注意这里的“依次”二字——步骤之间是有先后顺序的。

这部分的重点在于计算。

接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。

本章内容不复杂，但是不容忽视。

注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。

千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。

（为帮助没有分值的朋友能下载，特此修改文档，以免上传不了）1.1 算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。

程序1-1 计算并输出1+2的值#include<stdio.h>int main(){printf("%d\n", 1+2);return 0;}算法竞赛入门经典这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。

如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。

即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。

下面让我们做4个实验：实验1：修改程序1-1，输出3-4的结果实验2：修改程序1-1，输出5×6的结果实验3：修改程序1-1，输出8÷4的结果实验4：修改程序1-1，输出8÷5的结果直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。

数学基础(版本2009)刘汝佳例1. 同构计数•一个竞赛图是这样的有向图–任两个不同的点u、v之间有且只有一条边–不存在自环•用P表示对竞赛图顶点的一个置换。

当任两个不同顶点u、v间直接相连的边的方向与顶点P(u)、P(v)间的一样时，称该图在置换P下同构•对给定的置换P，我们想知道对多少种竞赛图在置换P下同构分析•先把置换它分解成为循环, 首先证明长度为L的偶循环将导致无解–对于点i1, 记P(i k)=i k+1, 假设i1和i L/2+1的边方向为i1->i L/2+1, 那么有i2->i L/2+2, i3->i L/2+3, …, i L/2+1->i1, 和假设矛盾!•假设确定其中k条独立边后其他边也会确定, 则答案为2k•考虑两类边: 循环内边和循环间边.分析•循环内顶点的关系–定了i 1和i j 之间的关系, i k 与i (k+j-2) mod n+1之间的关系也被确定下来了, 因此只需要确定i 1和i 2, i 3, …, i (L-1)/2+1这(L-1)/2对顶点的关系•不同循环间顶点的关系–设循环为(i 1,i 2,…,i L1)和(j 1,j 2,…,j L2), 通过类似分析得只需要确定gcd(L1, L2)对关系即可分析•最后答案为2k1+k2•其中k1=sum{(L-1)/2}, k2=sum{gcd(L1, L2)}•可以用二分法加速求幂例2. 图形变换•平面上有n个点需要依次进行m个变换处理•规则有4种, 分别把(x0,y)变为–平移M(x, y): (x0+x, y0+y)–缩放Z(L): (Lx0, Ly0)–翻转F(0): (x0, -y0); F(1): (-x0, y0)–旋转R(a): a为正时逆时针, 离原点距离不变, 旋转a度•给n(<=106)个点和m(<=106)条指令•求所有指令完成后每个点的坐标分析•如果直接模拟, 每次需要O(n)的时间, 一共O(nm), 无法承受•把点(x0, y)写成列向量[x, y]T, 则后3种变换可以都可以写成矩阵–缩放P’= Z * P, Z = [L 0; 0 L]–翻转P’= F * P, F = [1 0; 0 -1]或[-1 0; 0 1]–旋转P’= R * P, R = [cosa–sina; sina cosa]•可是无法实现平移, 怎么办呢?分析•修改表达方式, 令P = [x 0, y 0, 1]T , 则四种变换的矩阵M, Z, F, R 分别为100001,00001001x L M y Z L ⎡⎤⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦100100010010001001F −⎡⎤⎡⎤⎢⎥⎢⎥=−⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦或cos sin 0,sin cos 0001a a R a a −⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦分析•只需要先计算所有变换矩阵的乘积A, 然后对于每个点, P’= A * P•注意: 矩阵乘法不满足交换律, 因此需要按照输入顺序进行乘法•每次矩阵乘法需要33=27次乘法, 则计算A一共需要27m次乘法, 对所有点变换需要27n 次乘法, 一共27(n+m)次例3. 染色方案•N*M(N<=10100, M<=5)的格子纸，每个格子被填上黑色或者白色。

10167 - Birthday CakeBackgroundLucy and Lily are twins. Today is their birthday. Mother buys a birthday cake for them.Now we put the cake onto a Descartes coordinate. Its center is at (0,0), and the cake's length of radius is 100.There are 2N (N is a integer, 1<=N<=50) cherries on the cake. Mother wants to cut the cake into two halves with a knife (of course a beeline). The twins would like to be treated fairly, that means, the shape of the two halves must be the same (that means the beeline must go through the center of the cake) , and each half must have N cherrie(s). Can you help her?Note: the coordinate of a cherry (x , y) are two integers. You must give the line as form two integers A,B(stands for Ax+By=0), each number in the range [-500,500]. Cherries are not allowed lying on the beeline. For each dataset there is at least one solution.InputThe input file contains several scenarios. Each of them consists of 2 parts: The first part consists of a line with a number N, the second part consists of 2N lines, each line has two number, meaning (x,y) .There is only one space between two border numbers. The input file is ended with N=0.OutputFor each scenario, print a line containing two numbers A and B. There should be a space between them. If there are many solutions, you can only print one of them.Sample Input2-20 20-30 20-10 -5010 -5Sample Output0 111205 - The broken pedometerThe ProblemA marathon runner uses a pedometer with which he is having problems. In the pedometer the symbols are represented by seven segments (or LEDs):But the pedometer does not work properly (possibly the sweat affected the batteries) and only some of the LEDs are active. The runner wants to know if all the possible symbols:can be correctly identified. For example, when the active LEDs are:numbers 2 and 3 are seen as:so they cannot be distinguished. But when the active LEDs are:the numbers are seen as:and all of them have a different representation.Because the runner teaches algorithms at University, and he has some hours to think while he is running, he has thought up a programming problem which generalizes the problem of his sweat pedometer. The problem consists of obtaining the minimum number of active LEDs necessary to identify each one of the symbols, given a number P of LEDs, and N symbols to be represented with these LEDs (along with the codification of each symbol).For example, in the previous sample P = 7 and N = 10. Supposing the LEDs are numbered as:The codification of the symbols is: "0" = 1 1 1 0 1 1 1; "1" = 0 0 1 0 0 1 0; "2" = 1 0 1 1 1 0 1; "3" = 1 0 1 1 0 1 1; "4" = 0 1 1 1 0 1 0; "5" = 1 1 0 1 0 1 1; "6" = 1 1 0 1 1 1 1; "7" = 1 0 1 0 0 1 1; "8" = 1 1 1 1 1 1 1; "9" = 1 1 1 1 0 1 1. In this case, LEDs 5 and 6 can be suppressed without losing information, so the solution is 5.The InputThe input file consists of a first line with the number of problems to solve. Each problem consists of a first line with the number of LEDs (P), a second line with the number of symbols (N), and N lines each one with the codification of a symbol. For each symbol, the codification is a succession of 0s and 1s, with a space between them. A 1 means the corresponding LED is part of the codification of the symbol. The maximum value of P is 15 and the maximum value of N is 100. All the symbols have different codifications.The OutputThe output will consist of a line for each problem, with the minimum number of active LEDs necessary to identify all the given symbols.Sample Input27101 1 1 0 1 1 10 0 1 0 0 1 01 0 1 1 1 0 11 0 1 1 0 1 10 1 1 1 0 1 01 1 0 1 0 1 11 1 0 1 1 1 11 0 1 0 0 1 01 1 1 1 1 1 11 1 1 1 0 1 16100 1 1 1 0 01 0 0 0 0 01 0 1 0 0 01 1 0 0 0 01 1 0 1 0 01 0 0 1 0 01 1 1 0 0 01 1 1 1 0 01 0 1 1 0 00 1 1 0 0 0Sample Output54131 - The Psychic Poker PlayerIn 5-card draw poker, a player is dealt a hand of five cards (which may be looked at). The player may then discard between zero and five of his or her cards and have them replaced by the same number of cards from the top of the deck (which is face down). The object is to maximize the value of the final hand. The different values of hands in poker are given at the end of this problem.Normally the player cannot see the cards in the deck and so must use probability to decide which cards to discard. In this problem, we imagine that the poker player is psychic and knows which cards are on top of the deck. Write a program which advises the player which cards to discard so as to maximize the value of the resulting hand.Input and OutputInput will consist of a series of lines, each containing the initial five cards in the hand then the first five cards on top of the deck. Each card is represented as a two-character code. The first character is the face-value (A=Ace, 2-9, T=10, J=Jack, Q=Queen, K=King) and the second character is the suit (C=Clubs, D=Diamonds, H=Hearts, S=Spades). Cards will be separated by single spaces. Each input line will be from a single valid deck, that is there will be no duplicate cards in each hand and deck.Each line of input should produce one line of output, consisting of the initial hand, the top five cards on the deck, and the best value of hand that is possible. Input is terminated by end of file.Use the sample input and output as a guide. Note that the order of the cards in the player's hand is irrelevant, but the order of the cards in the deck is important because the discarded cards must be replaced from the top of the deck. Also note that examples of all types of hands appear in the sample output, with the hands shown in decreasing order of value. Sample InputTH JH QC QD QS QH KH AH 2S 6S2H 2S 3H 3S 3C 2D 3D 6C 9C TH2H 2S 3H 3S 3C 2D 9C 3D 6C TH2H AD 5H AC 7H AH 6H 9H 4H 3CAC 2D 9C 3S KD 5S 4D KS AS 4CKS AH 2H 3C 4H KC 2C TC 2D ASAH 2C 9S AD 3C QH KS JS JD KD6C 9C 8C 2D 7C 2H TC 4C 9S AH3D 5S 2H QD TD 6S KH 9H AD QHSample OutputHand: TH JH QC QD QS Deck: QH KH AH 2S 6S Best hand: straight-flushHand: 2H 2S 3H 3S 3C Deck: 2D 3D 6C 9C TH Best hand: four-of-a-kindHand: 2H 2S 3H 3S 3C Deck: 2D 9C 3D 6C TH Best hand: full-houseHand: 2H AD 5H AC 7H Deck: AH 6H 9H 4H 3C Best hand: flushHand: AC 2D 9C 3S KD Deck: 5S 4D KS AS 4C Best hand: straightHand: KS AH 2H 3C 4H Deck: KC 2C TC 2D AS Best hand: three-of-a-kindHand: AH 2C 9S AD 3C Deck: QH KS JS JD KD Best hand: two-pairsHand: 6C 9C 8C 2D 7C Deck: 2H TC 4C 9S AH Best hand: one-pairHand: 3D 5S 2H QD TD Deck: 6S KH 9H AD QH Best hand: highest-card146 - ID CodesIt is 2084 and the year of Big Brother has finally arrived, albeit a century late. In order to exercise greater control over its citizens and thereby to counter a chronic breakdown in law and order, the Government decides on a radical measure--all citizens are to have a tiny microcomputer surgically implanted in their left wrists. This computer will contains all sorts of personal information as well as a transmitter which will allow people's movements to be logged and monitored by a central computer. (A desirable side effect of this process is that it will shorten the dole queue for plastic surgeons.)An essential component of each computer will be a unique identification code, consisting of up to 50 characters drawn from the 26 lower case letters. The set of characters for any given code is chosen somewhat haphazardly. The complicated way in which the code is imprinted into the chip makes it much easier for the manufacturer to produce codes which are rearrangements of other codes than to produce new codes with a different selection of letters. Thus, once a set of letters has been chosen all possible codes derivable from it are used before changing the set.For example, suppose it is decided that a code will contain exactly 3 occurrences of `a', 2 of `b' and 1 of `c', then three of the allowable 60 codes under these conditions are:abaabcabaacbababacThese three codes are listed from top to bottom in alphabetic order. Among all codes generated with this set of characters, these codes appear consecutively in this order.Write a program to assist in the issuing of these identification codes. Your program will accept a sequence of no more than 50 lower case letters (which may contain repeated characters) and print the successor code if one exists or the message `No Successor' if the given code is the last in the sequence for that set of characters.Input and OutputInput will consist of a series of lines each containing a string representing a code. The entire file will be terminated by a line consisting of a single #.Output will consist of one line for each code read containing the successor code or the words `No Successor'.Sample inputabaacbcbbaa#Sample outputababacNo Successor10098 - Generating FastGenerating permutation has always been an important problem in computer science. In this problem you will have to generate the permutation of a given string in ascending order. Remember that your algorithm must be efficient.InputThe first line of the input contains an integer n, which indicates how many strings to follow. The next n lines contain n strings. Strings will only contain alpha numerals and never contain any space. The maximum length of the string is 10.OutputFor each input string print all the permutations possible in ascending order. Not that the strings should be treated, as case sensitive strings and no permutation should be repeated. A blank line should follow each output set.Sample Input3ababcbcaSample Outputabbaabcacbbacbcacabcbaabcacbbacbcacabcba729 - The Hamming Distance ProblemThe Hamming distance between two strings of bits (binary integers) is the number of corresponding bit positions that differ. This can be found by using XOR on corresponding bits or equivalently, by adding corresponding bits (base 2) without a carry. For example, in the two bit strings that follow:A 0 1 0 0 1 0 1 0 0 0B 1 1 0 1 0 1 0 1 0 0A XORB = 1 0 0 1 1 1 1 1 0 0The Hamming distance (H) between these 10-bit strings is 6, the number of 1's in the XOR string.InputInput consists of several datasets. The first line of the input contains the number of datasets, and it's followed by a blank line. Each dataset contains N, the length of the bit strings and H, the Hamming distance, on the same line. There is a blank line between test cases.OutputFor each dataset print a list of all possible bit strings of length N that are Hamming distance H from the bit string containing all 0's (origin). That is, all bit strings of length N with exactly H 1's printed in ascending lexicographical order.The number of such bit strings is equal to the combinatorial symbol C(N,H). This is the number of possible combinations of N-H zeros and H ones. It is equal toThis number can be very large. The program should work for .Print a blank line between datasets.Sample Input14 2Sample Output001101010110100110101100592 - Island of LogicThe Island of Logic has three kinds of inhabitants: divine beings that always tell the truth, evil beings that always lie, and human beings that are truthful during the day and lie at night. Every inhabitant recognizes the type of every other inhabitant.A social scientist wants to visit the island. Because he is not able to distinguish the three kinds of beings only from their looks, he asks you to provide a communication analyzer that deduces facts from conversations among inhabitants. The interesting facts are whether it is day or night and what kind of beings the speakers are.InputThe input file contains several descriptions of conversations. Each description starts with an integer n, the number of statements in the conversation. The following n lines each contain one statement by an inhabitant. Every statement line begins with the speaker's name, one of the capital letters A, B, C, D, E, followed by a colon `:'. Next is one of the following kinds of statements:∙I am [not] ( divine | human | evil | lying ).∙X is [not] ( divine | human | evil | lying ).∙It is ( day | night ).Square brackets [] mean that the word in the brackets may or may not appear, round brackets () mean that exactly one of the alternatives separated by | must appear. X stands for some name from A, B, C, D, E. There will be no two consecutive spaces in any statement line, and at most 50 statements in a conversation.The input is terminated by a test case starting with n = 0.OutputFor each conversation, first output the number of the conversation in the format shown in the sample output. Then print ``This is impossible.'', if the conversation cannot happen according to the rules or ``No facts are deducible.'', if no facts can be deduced. Otherwise print all the facts that can be deduced. Deduced facts should be printed using the following formats:∙X is ( divine | human | evil ).∙It is ( day | night ).X is to be replaced by a capital letter speaker name. Facts about inhabitants must be given first (in alphabetical order), then it may be stated whether it is day or night.The output for each conversation must be followed by a single blank line.Sample Input1A: I am divine.1A: I am lying.1A: I am evil.3A: B is human.B: A is evil.A: B is evil.Sample OutputConversation #1No facts are deducible.Conversation #2This is impossible.Conversation #3A is human.It is night.Conversation #4A is evil.B is divine.Reasoning made easyTo make things clearer, we will show the reasoning behind the third input example, where A says ``I am evil.''. What can be deduced from this? Obviously A cannot be divine, since she would be lying, similarly A cannot be evil, since she would tell the truth. Therefore, A must be human, moreover, since she is lying, it must be night. So the correct output is as shown.In the fourth input example, it is obvious that A is lying since her two statements are contradictory. So, B can be neither human nor evil, and consequently must be divine. B always tells the truth, thus A must be evil. Voil‘a!110 - Meta-Loopless SortsBackgroundSorting holds an important place in computer science. Analyzing and implementing various sorting algorithms forms an important part of the education of most computer scientists, and sorting accounts for a significant percentage of the world's computational resources. Sorting algorithms range from the bewilderingly popular Bubble sort, to Quicksort, to parallel sorting algorithms and sorting networks. In this problem you will be writing a program that creates a sorting program (a meta-sorter).The ProblemThe problem is to create several programs whose output is a standard Pascal program that sorts n numbers where n is the only input to the program you will write. The Pascal programs generated by your program must have the following properties:∙They must begin with program sort(input,output);∙They must declare storage for exactly n integer variables. The names of the variables must come from thefirst n letters of the alphabet (a,b,c,d,e,f).∙ A single readln statement must read in values for all the integer variables.∙Other than writeln statements, the only statements in the program are if then elsestatements. The boolean conditional for each if statement must consist of one strict inequality (either < or >) of two integer variables.Exactly n! writelnstatements must appear in the program.∙Exactly three semi-colons must appear in the programs1.after the program header: program sort(input,output);2.after the variable declaration: ...: integer;3.after the readln statement: readln(...);∙No redundant comparisons of integer variables should be made. For example, during program execution, once it is determined that a < b, variables a and b should not be compared again.∙Every writeln statement must appear on a line by itself.∙The programs must compile. Executing the program with input consisting of any arrangement of any n distinct integer values should result in the input values being printed in sorted order.For those unfamiliar with Pascal syntax, the example at the end of this problem completely defines the small subset of Pascal needed.The InputThe input consist on a number in the first line indicating the number M of programs to make, followed by a blank line.Then there are M test cases, each one consisting on a single integer n on a line by itself with 1 n 8. There will be a blank line between test cases.The OutputThe output is M compilable standard Pascal programs meeting the criteria specified above. Print a blank line between two consecutive programs.Sample Input13Sample Outputprogram sort(input,output);vara,b,c : integer;beginreadln(a,b,c);if a < b thenif b < c thenwriteln(a,b,c)else if a < c thenwriteln(a,c,b)elsewriteln(c,a,b)elseif a < c thenwriteln(b,a,c)else if b < c thenwriteln(b,c,a)elsewriteln(c,b,a)end.。

1.double 类型的输出格式为“%lf”.2.double pi=4.0*atan(1.0);这样比较精确。

3.printf("d",m);可以在输出前补充上0，但是换做其他的字符就不可以了。

4.绝对值的输出用%d,如：printf("%d",abs(-10));不可以用%f.第二章循环结构程序设计(2011-07-21 21:40:01)[编辑][删除]分类：算法竞赛入门经典标签：杂谈1. 调试程序的新方法：IDE,gdb .(还没有学会)2.判断是否是整数 floor(m+0.5)==m.1.AABB问题：法一：列举，然后判断是否是完全平方数，m=1100*a+11*b; m==floor(m+0.5) 法二：枚举所有的数，然后分离位数，分别判断是否相等。

2.阶乘之和问题：输出结果的后六位printf("%d",s%100000)3.使用计时器，可以测试程序的效率#include<time.h>printf("%.2lf",(double)clock()/CLOCKS_PER_SEC);注意的是，将其放入程序时，测试时会把键盘输入的时间一块算上，而如果不计可以使用命令行测试。

4.文件操作：（1）输入输出重定向：#define LOCALint main(){#ifdef LOCALfreopen("data.in","r",stdin);freopen("data.out","w",stdout);#endif.........}(2)文件的保存和读取：int main(){FILE *fin,*fout;fin=fopen("data.in","rb");fout=fopen("data.out","wb");.....fscanf(fin,"%d",&a);fprintf(fout,"%d\n",a);fclose(fin);fclose(fout);}第三章：数组和字符串(2011-07-22 20:27:54)[编辑][删除]标签：分类：算法竞赛入门经典杂谈1.当数组需要开的很大的时候，数组a[1000]的定义放到main函数外，否则会异常退出。