上海市控江中学王建德.PPT

上海市控江中学 王建德,浙江集训队辅导讲义,1、2002年竞赛概述,2、构造法,算法知识分布,虽然2002年全国奥林匹克信息学竞赛中含许多可“一题多解” 的试题，但如果按照较优算法标准分类的话，大致可分为,特 点,1、凸现信息学知识和数学知识整合的趋势。为了考核学生的数学能力，激发学生的创造力，2002年全国奥林匹克信息竞赛(NOI)、IOI组队赛和IOI，数论(荒岛野人)、组合分析(机器人M号)、图论类(玩具兵)的试题增加，并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与数学的依赖关系日益凸现，数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。两门学科的交融和整合是奥林匹克信息学活动发展的一个大趋势（有专家提议，数学教材讲算法，信息科技教材讲语言，上海的信息科技教材出现真值表（初中）和c语言（高中）。,2、“构造法”(调皮的小孩、新俄罗斯方块、丹奇方块 )或贪心策略类试题（月亮森林）的引入，使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质知识是不断推陈出新的。,3、试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法(玩具兵通过最短路径构造二分图)，也找不到一个纯粹的数据结构问题（银河英雄传说 要求计算并查集中元素的相对位置），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；,4、经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经常出现许多选手在一题中得0分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战，成为培训的基本要求和目标。,1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（陶行知）”。有问题虽然不一定有创造，但没有问题一定没有创造（想一想当前的解法有没有缺陷，有没有更好的算法，它与哪些问题有联系，与哪些知识相关联，还可以拓延出哪些问题，要解决这些问题还需要哪些知识）；,启 示,2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（ 2002年noi中的欧拉函数、冬令营营员讲的polya定理、博弈原理和遗传算法，爱笛生小学三年级退学、比尔.盖茨大学三年级退学）,学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构 培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同，有的同年级同学科的教材相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。,3、参与活动的学生应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）,学生的心理调适： 我掌握的知识仅不过是沧海一粟(进取心)； 固守错误的概念比一无所知更可怕（明智）； 三人之行必有我师（谦虚）； 知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如制作windows，人类基因工程）（现代意识）；,前提条件：水平相当的同质成员或各有所长（包括数学知识、编程能力和思维方式等解题所需的各种因素）的异质成员是开展合作学习的组织基础；,合作学习的效应： 集思广益容易出好的算法； 群体设计的测试数据相对全面； 在群体活动中能比较客观的反映自己能力情况； 每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相容性好、 乐于帮助他人，并且善于取他人之长的学生（符文杰、张一飞等）。,4、选手面对从未遇到过的挑战应调整好心态，不要急功近利，要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两次失误，也是砥砺之石，可从中汲取有益的经验和教训。“不是一番寒彻骨，哪得梅花扑鼻香”。,对一些不能套用简单的条条框框和现成模式、需要独立思考、见解独创和有所创新的非标准题，通过构造数学模型解决问题。数学模型的功能： 解释功能：就是用数学模型说明事物发生的原因； 判断功能：用数学模型判断原来的知识和认识的可靠性。 预见功能：利用数学模型揭示事物的发展规律，为人们的行为提供指导或参考。 构造法解题的思路或步骤可以归纳为：,构造法解题的类型 数学建模：通过沿用经典的数学思想建立起模型；或者提取现实世界中的有效信息，用简明的方式表达其规律，这种规律可以是一条代数公式、一幅几何图形，一个物理原理、一个化学方程式，等等。 直接构造问题解答：只是构造法运用的一种简单类型。它只能针对问题本身，探索其独有性质，不具备可推广性。 通常考虑的因素 选择的模型必须尽量多地体现问题的本质特征。但这并不意味着模型越复杂越好，累赘的信息会影响算法的效率。 模型的建立不是一个一蹴而就的过程，而是要经过反复地检验、修改，在实践中不断完善。 数学模型通常有严格的格式，但程序编写形式可不拘一格。,在建模过程中经常使用的策略有 对应策略：将问题a对应另一个便于思考或有求解方法的问题b，化繁为简，变未知为已知。 分治策略：将问题的规模逐渐减少，可明显降低解决问题复杂程度。算法设计的这种策略称之为分治策略，即对问题分而治之。 递推的分治策略 递归的分治策略 归纳策略：归纳策略则是通过列举试题本身的特殊情况，经过深入分析，最后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。 递推式 递归式 制定目标 贪心方案,模拟策略：模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟题没有固定的模式，一般形式有两种： 随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素； 过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。 模拟的解题方法一般有三种类型 直叙式模拟 筛选法模拟 构造法模拟,构造的一般思想方法,1、统计分析法,2、机理分析法,1、统计分析法： 我们在一时得不到事物的特征机理的情况下，通过某种方法测试得到一些数据（即问题的部分解），再利用数理统计知识对数据进行处理，从而得到最终的数学模型,极值问题 m，n 为整数，且满足下列两个条件： m，n 1， 2， 3， ，k (1k109)； (n2-mn-m2)2=1。 由键盘输入k，求一组满足上述两个条件的m，n 并且使m2+n2的值最大。,如果我们的猜想正确，那么当(n，m)是方程(n2-mn-m2)2=1的一组解时，根据斐波拉契数列关系，(n+m，n)也一定是方程的一组解。 若(n+m)2-(m+n)n-n2)2=1成立，则 =(n2+(m+n)n-(n+m)2)2=1=(n2+mn+n2-n2-2mn-m2)2=1=(n2-mn-m2)2=1成立 以上各步可逆，所以当(n，m)是方程(n2-mn-m2)2=1的一组解时，(n+m，n)一定是方程的另一组解。,var m，n，next，k :longint； begin write('k= ')； readln(k)； 读入n和m的上限k if (k1000000000) then halt； 如果k不在要求范围内，就终止 m1； n1； nextm+n； 确定斐波拉契数列的头三项 while next=k do 顺推，求出m，n的最大值 begin mn； nnext；nextm+n； end；while writeln('m= '，m)； writeln('n= '，n)； 输出可使m2+n2的值最大的m和n end.main,取石子问题 有两堆石子，数量可能不同。有两个人轮流取。每次有两种不同的取法。一是在任意一堆中取走任意多的石子。二是在两堆中同时取走相同数量的石子。最后把石子全部取完的是胜者。现在给出初始的两堆石子的数目，现在如果轮到你来取，又假设双方都采取最好的策略，问最后你是胜者还是败者。 输入文件只有一行，其中包含两个非负整数a和b，表示两堆石子的数目。（a,b1,000,000,000）。 输出文件也只有一行，包含一个数字。如果最后你是胜者，则输出1。反之，则输出0。 输入示例：6 10 输出示例：0,1、分析失败的情况 测试结果有两种可能 失败的情况：(1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20) (14,23) (16,26) (17,28)(19,31) (21,34)。 胜利的情况:（1，1）（1，3）（1，4）。 胜利的情况比失败的情况多得多。 在上述两种情况中，我们选择相对容易得出的失败情况展开分析，寻找规律； 从1开始的每一个数字，在这些数字对中都会出现一次且仅会出现一次； 数对的差成等差数列1，2，3，4； 有些数对的数字排列来自斐波那契数列 有些数对虽然不是标准斐波那契数列中的数字，但还是符合斐波那契数列的规则； 如果数对(a,b)出现在其中，则(a+b,a+2b)也必然出现在数对中（相反的结论是不对的）； 数对中两个数之比都非常接近于=0.618，即著名的黄金分割数。,2 、判别a、b的输赢 由于从1开始的每一个自然数，按照斐波那契数列的规则不重复地出现在失败的数对中，因此，可以得出如下结论： 在失败的数对中如果一个数为x，则取（x*0.618）的小数部分k。 若数对按照递增顺序排列成（a，b），且满足a=，则确定（a,b）失败。由此得出算法： readln(x,y)； if xy then begin cy；yx；xc；end； 按照递增顺序排列x和y if x=y div 1.618 若x和y接近黄金分割数，则失败；否则胜利 then writeln(0) else writeln(1)；,根据客观事物的特性，分析其内部的机理，弄清关系，在适当抽象的条件下，得到可以描述事物属性的数学工具。 我们在联赛中可以用这种方法建立数学模型，然后根据所对应的算法求出解。如下图所示：,国际象棋（knight） 国际象棋是我们休息娱乐时所常玩的游戏。在各个棋子中，马的行进方式最为特殊，也为人们所津津乐道。我们都知道：马走的是“日”字，也就是说每次都是向水平或竖直方向移动1格，而向另一个方向移动2格，所以也可称作是1*2的马（走法如下图所示）。在图中我们看到一个马由8种跳的方向。 小明是一个数学爱好者，他将马的走法重新定义了一下，重新定义后的广义马成为n*m的马。为了研究广义马，小明让马从（0，0）出发，随意的在一张足够大的棋盘上跳。他发现，有时候广义马总是无法跳入某些格子中，比如从2*2的马永远不可能跳到（1，1），这令他非常感兴趣。他希望知道对于给定的n，m，n*m的广义马是否能够跳到所有的格子。由于n，m可以非常大，这令小明花了许多功夫在尝试上，但仍不能得出肯定的结论。于是他就来找你这个计算机专家了帮忙。 【输入】 在输入文件knIGHT.In中包含了多组测试数据，每个测试数据占一行。 每组测试数据由2个数n，m（1n，m108）组成，表示广义马的类型。文件最后一行由2个0表示文件结束。 【输出】 将答案输出到文件knIGHT.OUT中，每组测试数据占一行。如果马能跳到指定的位置输出YES，否则输出ImPOSSIbLE。,当n为奇数时，将棋盘染色成黑白相间。自（0，0）出发的马始终在白格子上跳跃，黑色的格子是马永远到不了的。,当n为偶数时，我们有这样的移动方案（如上图（b）所示），使得马从（0，0）开始经过一系列的跳步后，到（1，0）的位置，也就是说可是让马到达相邻的格子，所以马可以遍历整个棋盘。,从最简单的1*n的广义马开始分析,将n*m的广义马对应1*n的广义马 第1种情况：若n，m有最大公约数p（p1），则马只能跳到形似（p*s，p*t）的格子上，其他的格子都到达到不了。 第2种情况：若n+m是偶数，类似于1*n马的情况，马只能在同色的格子内跳动，不能遍历棋盘。 第3种情况：若n+m为奇数且n，m互质。不妨设n为奇数，那么m为偶数。因为1*n马的问题已经被彻底解决，所以很自然的想将n*m经过一系列变换转化成1*n马的问题。我们可以看到马的跳法本质上是4种（另4种可以看成是以下4种跳法反跳一步）： （m，n） （m，-n） （n，m） （n，-m） 马经过跳p次、q次、r次、s次后 水平方向的位移为（p+q）*m+（r+s）*n 竖直方向的位移为（p-q）*n+（r-s）*m 为了利用1*n马的结论，解不定方程（p+q）*m+（r+s）*n=1。 n，m互质。该方程一定有解（p0，q0，r0，s0）。 又m是偶数n是奇数。（p0+q0）是偶数，（r0+s0）是奇数。 （p0+q0）与（p0-q0）同奇偶，而（r0+s0）与（r0-s0）同奇偶。 （p0-q0）是偶数，(r0-s0)是奇数。 （p0-q0）*n+（r0-s0）*m是偶数。 也就是马通过一系列的跳动所得到的效果相当于1*len的马跳一步的效果（len=（p0-q0）*n+（r0-s0）*m）。根据前面的结论，1*len的马可以遍历整个棋盘，所以当n+m为奇数且n，m互质时，n*m的马可以遍历整个棋盘。算法的时间复杂度为W(1)，空间需求为W(1)。,var n，m，temp：longint； n，m为广义马的类型 function gcd(a，b：longint)：longint；计算n和m的最大公约数 begin if b=0 then gcda else gcdgcd(b，a mod b)； end； gcd begin readln(n，m)； 读广义马的类型 if(n+m)mod2=0 若n+m偶数，则无解 then writeln('ImPOSSIbLE') else begin,if nm，若不满足，则交换n，m tempn；nm； mtemp； end；then if gcd(n，m)=1若n，m互质，则输出成功信息；否则输出失败信息 then writeln('YES') else writeln('ImPOSSIbLE')； end；else end.main,Dr. Steven最近在研究一种叫作X数列的整数数列。X数列有两个独特的性质：它的首项是0，任意相邻两项的差是1或者-1。 Dr. Steven正在研究X数列的长度与它的各项之和之间的关系。你是他的一名学生，也参加了这个课题。为了研究的方便，他希望你能够编一个程序：从输入文件中读入X数列的长度、X数列中所有项的和，找一个满足要求的X数列，并把结果写到输出文件中。 输入： 输入文件Sum.in的第一行是一个整数n(1n10 000)，表示X数列中的项数。第二行是一个整数S（|S| 50 000 000），表示X数列中所有项的和。 输出： 把找到的满足要求的X数列输出到文件Sum.out中，每一项占一行，第k项输出在第k行，共n行。如果不存在这样的X数列，则输出“nO”。,X数列的和（Sum of X-Sequence）,长度为n的X数列共有2n-1个，要全部枚举一遍是不现实的。所以，一定有更好的方法。这就需要我们对题目作进一步的研究。只要做适当的变换，其中的奥秘就会浮出水面。 我们假设存在这样的一个数列ai满足题目要求，讨论S应满足的条件。 令bi=ai+1-ai，则由题目知，bi=1或-1。且a1=0，a2=b1，a3=b1+b2，an=b1+b2+bn-1。所以S=a1+a2+an=0+b1+(b1+b2)+(b1+b2+bn-1)=(n-1)b1+(n-2)b2+2*bn-2+bn-1 （1） 易知|S|(n-1)+(n-2)+1=(n-1)*n/2。1+2+(n-1)=(n-1)*n/2 （2） 由(2)式-(1)式得：(n-1)*n/2-S=(n-1)*(1- b1)+(n-2)*(1- b2)+2*(1- bn-2)+(1- bn-1) 因为1-bk=0或2，所以上式右端为偶数。要使等式成立，则其左端也为偶数，即S与(n-1)*n/2同奇偶。 再把等式两边同除以2，令ci=(1-bi)/2（易知ci=0或1），得(n-1)*n/2-S/2=(n-1) c1+(n-2) c2+ 2*cn-2+ cn-1 令T=(n-1)*n/2-S/2 所以原问题转化为一个简单的数学问题：T能否表示成1，2，（n-1）中若干个不重复的数之和。,这个问题不难解决。当0T(n-1)*n/2时，T能够表示成1，2，（n-1）中若干个不重复的数之和。问题转化的必要性是显然的。接着用数学归纳法来证明它的充分性。证： (1)当n=1时，0T0，0=0。 当n=2时，0T1，0=0，1=1。 当n=3时，0T3，0=0，1=1，2=2，3=1+2。 均成立。 (2)当n=k（k3）时，归纳假设成立。则当n=k+1时： 若0Tk，则易知k(k-1)*k/2。由归纳假设T可以表示成1，2，(k-1)中若干个不重复的数之和。此时c1= 0。 若kTk*(k+1)/2，则先取出一个k，易知k*(k+1)/2 - k=(k-1)*k/2。归纳假设T-k可以表示成1，2，(k-1)中若干个不重复的数之和。此时c1= 1。 由此可证，对于满足0Tk*(k+1)/2的T，一定能够表示成1，2，k中若干个不重复的数之和。即n=k+1时，归纳假设亦成立。证毕。 由上面的分析证明过程可以得出，T的取值范围是0， (n-1)*n/2，且T为整数。S的取值范围是-(n-1)*n/2， (n-1)*n/2，且S为整数，S与(n-1)*n/2同奇偶。有了这个基础，我们便可以将原问题对应一个简单问题： 首先判断S是否在-(n-1)*n/2， (n-1)*n/2的范围内，且S是否与(n-1)*n/2同奇偶。如果这两个条件不成立，则所求的数列不存在。如果满足这两个条件，则令T=(n-1)*n/2-S/2，然后就按照上文中证明里的方法求ci，而ai=ai-1+bi-1= ai-1+1-2*ci-1，所以ai 的值也就迎刃而解了,var a，i，n，s，t：longint；n为数列的项数；s为各项的和；a为数列中的一项 begin readln(n)；输入x数列的项数和所有项的和 readln(s)； tn*(n-1) div 2； if odd(s-t) or(abs(s)t) 判断S是否在-(n-1)*n/2， (n-1)*n/2的范围内，且S是否与(n-1)*n/2同奇偶 then writeln('nO') else begin t(t-s)div2；令T=(n-1)*n/2-S/2 a0；首项为0 writeln(a)；,for in-1 downto 1 do begin 逐项计算 if t=i c=1，即aj=aj-1-1 then begin dec(t，i)；dec(a) endthen else inc(a)；c=0，即aj=aj-1+1 writeln(a) 输出数列中的一项 end；for end；else end.main,密码锁（lock） 凭借你多年的开锁经验，你马上断定眼前这扇门用的是密码锁。只见锁身上有n行数字，在每行数字末尾都有好几个数字拨盘。看着这一行行多少不一的数字，和数字末尾留下的空格，你忽然想起了小时候经常玩的一个游戏：找规律。这个游戏就是给你一个数列的前几项，让你填出后一项，例如： 2 4 6 (8) 1 4 9 (16) 在玩游戏的过程中，你发现了一个窍门，对于所有这类问题，都可以用这种方法解决：对于一个已知前m项的数列a1，a2，a3am，一定可以找到唯一一个不超过m-1次的多项式f(x)，使得f(1)=a1，f(2)=a2f(m)=am，那么f(m+1)就是要找的下一项。 现在你决定用这种方法试着打开眼前这把密码锁。 【输入】 第一行是一个整数n，代表门上共有n行数字，n100。 以下n行，每行对应门上的一行数字，每行的数字不超过1000个。 输入的数字之间用空格隔开，每行末尾没有多余的空格。 输入的数字都是绝对值小于108的整数。 【输出】 输出应该包括n行，为根据输入数据的规律推出的下一个数字，顺序与输入数据相对应。保证结果的绝对值都小于108。,这道题最直接的方法就是构造出数列的通项公式： 对于一个已知m项的数列，构造出的通项公式共有m项，当im时，f(i)总是有且仅有一项不为零，而且等于ai。例如数列前3项为1，3，5，通项公式为： 这种方法的缺点是运算过程中数的规模比较大，如果用高精度计算，时空效率可能无法接受。如果不用高精度，恐怕得不到准确解。,方法二 定理：如果一个数列的通项公式是关于自然数n的r次多项式，那么这个数列是r阶等差数列。 这个定理的证明很简单，只要反复进行g(n)=f(n)-f(n-1)的运算，求数列的差数列，就会发现通项公式的次数每迭带一次都会降低一次，最终原数列的r阶差数列就是一个常数列。也就是说原数列是一个r阶等差数列。 在这道题里，已知这个数列的通项公式有m-1项，那么这个数列就是一个m-1阶的等差数列。于是就可以借助等差数列求出数列的第m+1项，例如数列1，4，9： 方法二十分简洁，要计算的数据不是很大，而且计算量较小。算法的时间复杂度为W(n*m2/2)。由于计算过程中有许多数据不需要保存，所以空间需求是W(1)。,var num：array12000of longint； 数列 n，m：integer； 行数和当前行的数字个数 i，j，k：integer； begin readln(n)； 读入行数 for i1 to n do begin 依次读入每一行的数字信息 m0； while not eoln do begin inc(m)； read(numm)； end；while readln； for jm downto 2 do 计算m-1阶等差数列的等差值 for k1 to j-1 do numk numk+1-numk； for j2 to m do 计算和输出第i行的最后一项 num1 num1+numj； writeln(num1)； end；for end.main,空中都市 在一个未来的空中都市中，有很多个小岛（城区）。现在要求在这些岛之间架一些桥梁（桥是架在两个岛之间的）。要求，首先，如果A与B之间有桥，B与C之间有桥，则A与C之间就不能再架桥了。即，对于城市中的任意三个岛，不能在其中两两都架上桥。在这样的前提下，要求架的桥的数量最多（不考虑具体的空间结构问题）。 输入文件只包含一行，其中包含非负整数n（0=n=1000），是城市中小岛的数目。 输出文件也只包含一行，是最大能够架的桥的数目。 输入示例： 6 输出示例： 9,1、递推法 如果设对于n个小岛，可以架的桥数为的话，则应满足如下的关系： 其中，符号表示向下取整。首先，这个式子的正确性还是比较容易证明的（考虑使用抽屉原理）。 2、构造法 按照题意，如果小岛A与小岛B之间、小岛B与小岛C之间和小岛A与小岛C之间都有桥的话，则说明A、B、C三个小岛之间存在传递性。试题要求构造一个含n个顶点且满足下述条件的图 任三个顶点间不含传递性 图中所含边数最多。 我们通过下述方法将空中都市问题对应一个简单问题： 把n个小岛分为尽量平均的两部分，第一组为n/2（或(n-1)/2）个顶点,第二组为n/2（或(n+1)/2）个顶点。然后第一组的每一个顶点分别向第二组的所有顶点引出边。,由此得出桥的数目是 下面，我们来证明这个构造方法的正确性。 由于两组的任一对顶点之间都有边相连，因此如果再架桥的话，只能在同组的一对顶点之间进行。如果在某一组的顶点i和顶点j间架桥，则由于顶点i和顶点j与另一组的任一个顶点k相连，使得顶点i、顶点j和顶点k之间存在传递关系，这是不允许的。由此可见，按照上述方法得出的图所含边数最多。下面给出解法： Readln(n)； kord(odd(n)； n为偶数时，k=0；n为奇数时，k=1 if k=1 输出桥数的最大值 then writeln(n-1)*(n+1)/4) else writeln(n*n/4)； for i1 to (n-k)div 2 do 枚举第一组的每一个小岛 for j(n-k)div 2+1 to n do 枚举第二组的每一个小岛 writeln(,i,j,)； 输出 ,舞会 某学校要召开一个舞会。现在已知在学校的所有n名学生中，有些学生曾经互相跳过舞。（跳过舞的两个学生一定是一个男生和一个女生）。现在要求被邀请的学生中的任何一对男生女生互相都不能跳过舞，求这个舞会最多能够邀请多少学生参加。 输入文件的第一行是n和m。其中n是可选的学生的总数，m是已知的跳过舞的学生的对数（n=1000,m=2000）。然后有m行，分别包含两个非负整数，表示这两个编号的学生曾经跳过舞。（学生的编号是从0号到n-1号。） 输出文件只要求输出一行，其中包含一个数字，即能够邀请的最大的学生数。 输入示例： 8 6 0 2 2 3 3 5 1 4 1 6 3 1 输出示例： 5,算法分析 1、二分图 男女生各分两个顶点集，若跳过舞，则连边。 2、最小覆盖集 覆盖集K的定义：覆盖集K为一个顶点子集，且G的每一条边至少有一个顶点属于k。含顶点数最少的覆盖集即为最小覆盖集。 去掉最小覆盖集的顶点，所有的舞对拆散。因此n-最小覆盖集的顶点数=能够邀请的最大的学生数。,Knights 一张大小为n*n的国际象棋棋盘，上面有一些格子被拿走了。你的任务是确定在这个棋盘上放置尽可能多的马并使他们不互相攻击。棋盘的大小n不超过200。 算法分析 下面，从构造图的角度分析本题的模型。将棋盘的每一个格子作为一个顶点，两点间直接可达（互可攻击）的关系作为边。则题目所要求的就是在这样一张图中的最大独立子集。由于对于任意一张图，其最大独立子集和最小覆盖集互为补集，所以本题也是一个求最小覆盖集的图论问题。众所周知，一般图的最小覆盖图是一个NPC问题。那么本题能否逃脱厄运呢？这只有从本题的特殊性来分析。,常识告诉我们，在一张国际象棋的棋盘上，白格和黑格是相交错的，一匹马只能从一个白格跳到一个黑格，或是从一个黑格跳到一个白格。由于这种特殊性，马的攻击范围的不规则，在这时却给我们的解题带来了方便。因为一个位置上的马只能攻击和其所在位置颜色不同的格子，这是一个必要条件。换句话说，同一颜色的任意两个格子间不存在边。所以，棋盘可以按照颜色分成两个部分，在同一部分的任意两点都是不能互相攻击的。也就是说定义在攻击关系上的棋盘是一个二分图。同时，由于二分图的独特性质，它的最小覆盖数=最大匹配数。,4色排列 问题描述 红、黄、蓝、绿4种颜色围成长度为N(N=30)的一圈（位置编号为1、2、N），不能有一种颜色是连续3个，共有多少种方案？ 样例 输入：5 输出：780,最少步数 问题描述 在各种棋中，一种棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将更加增加趣味性，因此，他规定马既能按“日”飞，也能各象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就和他玩一种新游戏，在围棋盘上（19*19）任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A，B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。 样例 输入： 12 16 18 10 输出： 8 9,平分面积 问题描述 按顺时针依次给出一个凸N边形的N(=10)个点的坐标，要求从第一点坐标出发划一条线，恰好把此N边形划分成面积相等的两块（相差0.01），求此直线与多边形的另一个交点坐标（精确到小数点后2位）。 样例 输入： 注释 3 N的值 0 10 第1点坐标x,y 3.5 0 第2点坐标 -3.5 0 第3点坐标 输出： 0.0 0.00,