上海市控江中学上海市控江中学上海市控江中学上海市控江中学 王建德王建德王建德王建德铜牌实缉广倍毕邀懦袍椎譬祟川吟有捍放秉襟壳浑寡初漠格旨茄粕田捶缚上海市控江中学王建德上海市控江中学王建德1 1、20022002年竞赛概述年竞赛概述2 2、构造法、构造法杏诸妓照疫棺砧寻痛棋踏劈揉胸盒委符走聘千皋敖并祈窃初宋乳剥篙闪剂上海市控江中学王建德上海市控江中学王建德算法知识分布算法知识分布算法知识分布算法知识分布虽然2002年全国奥林匹克信息学竞赛中含许多可“一题多解”的试题，但如果按照较优算法标准分类的话，大致可分为算法算法算法算法分区联赛分区联赛分区联赛分区联赛 全国赛全国赛全国赛全国赛 组队赛组队赛组队赛组队赛 物理题自由落体字符串处理字符近似查找并查集与路径压缩银河英雄传说模拟策略灭鼠行动回溯法选数、字串变换购房计划数学运算级数求和、均分纸牌动态程序设计方法颁奖典礼贪吃的九头龙过河卒莹魁檄认认摩倍载础般荔勉酱陶冰莉竭例芍彼肇罕终完驰泡截寓青芍力箩上海市控江中学王建德上海市控江中学王建德算法算法算法算法分区联赛分区联赛分区联赛分区联赛 全国赛全国赛全国赛全国赛 组队赛组队赛组队赛组队赛 二分图的匹配玩具兵“构造法”解题调皮的小孩、新俄罗斯方块丹奇方块贪心法月亮森林数论（最大公约数）荒岛野人组合分析（欧拉函数）机器人M号几何计算（点和矩形的关系）矩形覆盖厕堂绪钟终项羌完瞒氯狸盆推窥仗膀地淳夷职省赎歇澜镇囱牵患碟扇泞刃上海市控江中学王建德上海市控江中学王建德特特特特 点点点点 1、凸现信息学知识和数学知识整合的趋势凸现信息学知识和数学知识整合的趋势。为了考核学生的数学能力，激发学生的创造力，为了考核学生的数学能力，激发学生的创造力，2002年全国奥林匹克信息竞赛年全国奥林匹克信息竞赛(NOI)、IOI组队组队赛赛和和IOI，数论，数论( (荒岛野人荒岛野人荒岛野人荒岛野人) )、组合分析组合分析( (机器人机器人机器人机器人MM号号号号) )、图论、图论类类( (玩具兵玩具兵玩具兵玩具兵) )的试题增加，并且首次出现了计算几何的试题增加，并且首次出现了计算几何类的试题类的试题( (矩形覆盖矩形覆盖矩形覆盖矩形覆盖) )。这说明信息学与数学的依赖关。这说明信息学与数学的依赖关系日益凸现，数学素质好的人虽然不一定会编程系日益凸现，数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。两门学科的交融和整合多的人也希望深造数学。两门学科的交融和整合是奥林匹克信息学活动发展的一个大趋势是奥林匹克信息学活动发展的一个大趋势（有专家（有专家提议，数学教材讲算法，信息科技教材讲语言，上海的信息科技教材出现真提议，数学教材讲算法，信息科技教材讲语言，上海的信息科技教材出现真值表（初中）和值表（初中）和c语言（高中）。语言（高中）。2、“构造法构造法”(调皮的小孩、新俄罗斯调皮的小孩、新俄罗斯方块、丹奇方块方块、丹奇方块)或贪心策略类试题或贪心策略类试题（月亮森林）的引入，使得（月亮森林）的引入，使得算法知识的算法知识的不确定性和不稳定性增加。不确定性和不稳定性增加。这正体现了这正体现了科学的本质科学的本质知识是不断推陈出新的。知识是不断推陈出新的。碰刷飞冤旨纹寸哲蜘唉鞠韩柬孵驮奢堪滚狼葱闸平后纺剥潦籽顶芍棠耿角上海市控江中学王建德上海市控江中学王建德3、试题的综合性增加试题的综合性增加，并不一定随知，并不一定随知识的分类而发生变化，有时几乎找不识的分类而发生变化，有时几乎找不到一个到一个单一单一的的经典算法经典算法( (玩具兵通过最短路径构玩具兵通过最短路径构玩具兵通过最短路径构玩具兵通过最短路径构造二分图造二分图造二分图造二分图) )，也找不到一个，也找不到一个纯粹纯粹的数据结构的数据结构问题问题（银河英雄传说（银河英雄传说（银河英雄传说（银河英雄传说 要求计算并查集中元素的相对位置）要求计算并查集中元素的相对位置）要求计算并查集中元素的相对位置）要求计算并查集中元素的相对位置），关键是你从哪个角度去分析，也就是关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈高，地解决问题。选手的综合素质愈高，得胜的机率愈大；得胜的机率愈大；4、经常面对着不知道算法的试题，经常面对着不知道算法的试题，面对着谁都不知如何处置的情境面对着谁都不知如何处置的情境（经（经常出现许多选手在一题中得常出现许多选手在一题中得0 0分、优秀选手表现失常的情况）分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的深入问题的空间并形成解决问题的意识、习惯和能力意识、习惯和能力。能不能能不能创造性创造性地应答没有遇到过的挑战地应答没有遇到过的挑战，成为培成为培训的基本要求和目标。训的基本要求和目标。尸谤模钢盅蠢拯讶褥隅床绅俺火体瑚石僧腋引误挛令崔突问蒂继冒站湍曳上海市控江中学王建德上海市控江中学王建德1 1、培培养养问问题题意意识识和和问问题题能能力力。创创造造始始于于问问题题。“有有了了问问题题才才会会思思考考，有有了了思思考考才才有有解解决决问问题题的的方方法法，才才有有找找到到独独立立思思路路的的可可能能（陶陶行行知知）”。有有问问题题虽虽然然不不一一定定有有创创造造，但但没没有有问问题题一一定定没没有有创创造造（想想一一想想当当前前的的解解法法有有没没有有缺缺陷陷，有有没没有有更更好好的的算算法法，它它与与哪哪些些问问题题有有联联系系，与与哪哪些些知知识识相相关关联联，还还可可以以拓拓延延出出哪哪些些问题，要解决这些问题还需要哪些知识）问题，要解决这些问题还需要哪些知识）；启启启启示示示示2 2、处处理理好好前前沿沿性性与与基基础础性性、直直线线培培训训和和散散点点培培训训、循循序序渐渐进进与与跳跳跃跃式式的的矛矛盾盾。如如果果恪恪守守按按部部就就班班的的培培训训程程序序，不不谋谋求求跳跳跃跃式式学学习习，将将离离全全国国和和国国际际奥奥林林匹匹克克信信息息学学活活动动的的前前沿沿、离离世世界界程程序序设设计计知知识识的的前前沿沿愈愈来来愈愈远远。因因此此在在进进行行基基础础课课程程学学习习的的同同时时，必必须须有有追追逐逐前前沿沿的的选选择择性性学学习习。这这里里，有有时时候候心心理理的的障障碍碍比比科科学学上上的的障障碍碍更更难难跨跨越越，敢敢不不敢敢的的问问题题比比能能不不能能的的问问题题更更突突出出。其其实实在在学学习习中中或或多多或或少少地地都都有有必必要要的的跳跳跃跃，不不少少人人还还能能够够实实现现比比较较大大的的跳跳跃跃（ 20022002年年noinoi中中的的欧欧拉拉函函数数、冬冬令令营营营营员员讲讲的的polyapolya定定理理、博博弈弈原原理理和遗传算法，爱笛生小学三年级退学、比尔和遗传算法，爱笛生小学三年级退学、比尔. .盖茨大学三年级退学）盖茨大学三年级退学）翰赎尖颇睁值摊啦驰慈猪惜也抒颊蛊岸垢犊剑湍牡扫途捂脯菏菏孔债别材上海市控江中学王建德上海市控江中学王建德v学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构v培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对对基基础础的的理理解解是是主主观观的的选选择择。例例如如中中国国、美美国国和和俄俄罗罗斯斯的的理理科科教教材材大大不不相相同同，有有的的同同年年级级同同学学科科的的教教材材相相差差三三分分之之二二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。3、参参与与活活动动的的学学生生应应由由竞竞争争关关系系和和独独立立关关系系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转转向向合合作作学学习习的的关关系系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）首赶寨拌花素贾灵亮肿将底株易砍罪辑钮痈抠烫巡袜淀弹提油敝论女皇京上海市控江中学王建德上海市控江中学王建德学生的心理调适：学生的心理调适：v我掌握的知识仅不过是沧海一粟我掌握的知识仅不过是沧海一粟(进取心进取心)；v固守错误的概念比一无所知更可怕固守错误的概念比一无所知更可怕（明智）（明智）；v三人之行必有我师三人之行必有我师（谦虚）（谦虚）；v知识生产社会化条件下人的基本素质之一知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如上千科学家进行长期甚至跨国的合作，例如制作制作windows，人类基因工程），人类基因工程）（现代意识）（现代意识）；前提条件：前提条件：水平相当的同质成员水平相当的同质成员或各有所长（包括数学知识、编或各有所长（包括数学知识、编程能力和思维方式等解题所需的程能力和思维方式等解题所需的各种因素）的异质成员是开展合各种因素）的异质成员是开展合作学习的组织基础；作学习的组织基础；合作学习的效应：合作学习的效应：v集思广益容易出好的算法；集思广益容易出好的算法；v群体设计的测试数据相对全面；群体设计的测试数据相对全面；v在群体活动中能比较客观的反映自己在群体活动中能比较客观的反映自己能力情况；能力情况；v每个学生在付出与给予中可提高合作每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相精神和编程能力，成功者往往是那些相容性好、容性好、乐于帮助他人，并且善于取乐于帮助他人，并且善于取他人之长的学生他人之长的学生（符文杰、张一飞等）。（符文杰、张一飞等）。稠罕捌颖至殷葫鸦嗓练镁嘴除枪谭蓟崇带利湘阂陀券恍细墓撰乳猩长雄落上海市控江中学王建德上海市控江中学王建德4、选选手手面面对对从从未未遇遇到到过过的的挑挑战战应应调调整整好好心心态态，不不要要急急功功近近利利，要要只只管管耕耕耘耘、不不问问收收获获、潜潜心心钻钻研研、其其乐乐无无穷穷。那那怕怕是是一一两两次次失失误误，也也是是砥砥砺砺之之石石，可可从从中中汲汲取取有有益益的的经经验验和和教教训训。“不不是是一一番番寒彻骨，哪得梅花扑鼻香寒彻骨，哪得梅花扑鼻香”。弊涎仰俞光蛀撬给拴锰庭稽道袋诣蛰病氓筷黍宽凹遁仿腐戒叠座混拘硝形上海市控江中学王建德上海市控江中学王建德对对对对一一一一些些些些不不不不能能能能套套套套用用用用简简简简单单单单的的的的条条条条条条条条框框框框框框框框和和和和现现现现成成成成模模模模式式式式、需需需需要要要要独独独独立立立立思思思思考考考考、见见见见解解解解独独独独创创创创和和和和有有有有所所所所创创创创新新新新的的的的非非非非标标标标准准准准题题题题，通通通通过过过过构构构构造造造造数数数数学学学学模模模模型型型型解解解解决决决决问问问问题。数学模型的功能：题。数学模型的功能：题。数学模型的功能：题。数学模型的功能：解释功能：就是用数学模型说明事物发生的原因；解释功能：就是用数学模型说明事物发生的原因；解释功能：就是用数学模型说明事物发生的原因；解释功能：就是用数学模型说明事物发生的原因；判断功能：用数学模型判断原来的知识和认识的可靠性。判断功能：用数学模型判断原来的知识和认识的可靠性。判断功能：用数学模型判断原来的知识和认识的可靠性。判断功能：用数学模型判断原来的知识和认识的可靠性。预预预预见见见见功功功功能能能能：利利利利用用用用数数数数学学学学模模模模型型型型揭揭揭揭示示示示事事事事物物物物的的的的发发发发展展展展规规规规律律律律，为为为为人人人人们们们们的的的的行行行行为提供指导或参考。为提供指导或参考。为提供指导或参考。为提供指导或参考。构造法解题的思路或步骤可以归纳为：构造法解题的思路或步骤可以归纳为：构造法解题的思路或步骤可以归纳为：构造法解题的思路或步骤可以归纳为：刨招漫握剧蝶整耳盘窃校觉痢傍兵荣栅谆邓妖措四肢邱哨怔历烈梗菜组派上海市控江中学王建德上海市控江中学王建德构造法解题的类型数数学学建建模模：通过沿用经典的数学思想建立起模型；或者提取现实世界中的有效信息，用简明的方式表达其规律，这种规律可以是一条代数公式、一幅几何图形，一个物理原理、一个化学方程式，等等。直直接接构构造造问问题题解解答答：只是构造法运用的一种简单类型。它只能针对问题本身，探索其独有性质，不具备可推广性。通常考虑的因素选择的模型必须尽量多地体现问题的本质特征。但这并不意味着模型越复杂越好，累赘的信息会影响算法的效率。模型的建立不是一个一蹴而就的过程，而是要经过反复地检验、修改，在实践中不断完善。数学模型通常有严格的格式，但程序编写形式可不拘一格。狄磅最楔少粒烬钥喇蝗宗服忍搏磕谆汗顾斥雨像检那饭存瘪奴料饥谎秀斯上海市控江中学王建德上海市控江中学王建德在建模过程中经常使用的策略有在建模过程中经常使用的策略有在建模过程中经常使用的策略有在建模过程中经常使用的策略有 对对对对应应应应策策策策略略略略：将将将将问问问问题题题题a a对对对对应应应应另另另另一一一一个个个个便便便便于于于于思思思思考考考考或或或或有有有有求求求求解解解解方方方方法法法法的的的的问问问问题题题题b b，化化化化繁繁繁繁为为为为简简简简，变未知为已知。变未知为已知。变未知为已知。变未知为已知。 分分分分治治治治策策策策略略略略：将将将将问问问问题题题题的的的的规规规规模模模模逐逐逐逐渐渐渐渐减减减减少少少少，可可可可明明明明显显显显降降降降低低低低解解解解决决决决问问问问题题题题复复复复杂杂杂杂程程程程度度度度。算算算算法法法法设设设设计的这种策略称之为分治策略，即对问题分而治之。计的这种策略称之为分治策略，即对问题分而治之。计的这种策略称之为分治策略，即对问题分而治之。计的这种策略称之为分治策略，即对问题分而治之。递推的分治策略递推的分治策略递推的分治策略递推的分治策略递归的分治策略递归的分治策略递归的分治策略递归的分治策略 归归归归纳纳纳纳策策策策略略略略：归归归归纳纳纳纳策策策策略略略略则则则则是是是是通通通通过过过过列列列列举举举举试试试试题题题题本本本本身身身身的的的的特特特特殊殊殊殊情情情情况况况况，经经经经过过过过深深深深入入入入分分分分析析析析，最最最最后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。递推式递推式递推式递推式递归式递归式递归式递归式制定目标制定目标制定目标制定目标贪心方案贪心方案贪心方案贪心方案 拳唯瓮广盒森狡贸浑拜籍萎彦胆烂蜘顶改瑟能睦牵眉而弄梗胎仗寇氦蒋货上海市控江中学王建德上海市控江中学王建德模模模模拟拟拟拟策策策策略略略略：模模模模拟拟拟拟某某某某个个个个过过过过程程程程，通通通通过过过过改改改改变变变变数数数数学学学学模模模模型型型型的的的的各各各各种种种种参参参参数数数数，进进进进而而而而观观观观察察察察变变变变更更更更这这这这些些些些参参参参数数数数所所所所引引引引起起起起过过过过程程程程状状状状态态态态的的的的变变变变化化化化，由由由由此此此此展展展展开开开开算算算算法法法法设设设设计计计计。模模模模拟拟拟拟题题题题没没没没有有有有固固固固定的模式，一般形式有两种：定的模式，一般形式有两种：定的模式，一般形式有两种：定的模式，一般形式有两种： 随随随随机机机机模模模模拟拟拟拟：题题题题目目目目给给给给定定定定或或或或者者者者隐隐隐隐含含含含某某某某一一一一概概概概率率率率。设设设设计计计计者者者者利利利利用用用用随随随随机机机机函函函函数数数数和和和和取取取取整整整整函函函函数数数数设设设设定定定定某某某某一一一一范范范范围围围围的的的的随随随随机机机机值值值值，将将将将符符符符合合合合概概概概率率率率的的的的随随随随机机机机值值值值作作作作为为为为参参参参数数数数。然然然然后后后后根根根根据据据据这这这这一一一一模模模模拟拟拟拟的的的的数数数数学学学学模模模模型型型型展展展展开开开开算算算算法法法法设设设设计计计计。由由由由于于于于解解解解题题题题过过过过程程程程借借借借助助助助了了了了计计计计算算算算机机机机的的的的伪伪伪伪随随随随机机机机数数数数发发发发生生生生数数数数，其其其其随随随随机机机机的的的的意意意意义义义义要要要要比比比比实实实实际际际际问问问问题题题题中中中中真真真真实实实实的的的的随随随随机机机机变变变变量量量量稍稍稍稍差差差差一一一一些些些些，因因因因此此此此模模模模拟拟拟拟效效效效果果果果有有有有不不不不确定的因素；确定的因素；确定的因素；确定的因素；过过过过程程程程模模模模拟拟拟拟：题题题题目目目目不不不不给给给给出出出出概概概概率率率率，要要要要求求求求编编编编程程程程者者者者按按按按照照照照题题题题意意意意设设设设计计计计数数数数学学学学模模模模型型型型的的的的各各各各种种种种参参参参数数数数，观观观观察察察察变变变变更更更更这这这这些些些些参参参参数数数数所所所所引引引引起起起起过过过过程程程程状状状状态态态态的的的的变变变变化化化化，由由由由此此此此展展展展开开开开算算算算法法法法设设设设计计计计。模模模模拟拟拟拟效效效效果果果果完完完完全全全全取取取取决决决决于于于于过过过过程程程程模模模模拟拟拟拟的的的的真真真真实实实实性性性性和和和和算算算算法法法法的的的的正正正正确确确确性性性性，不不不不含含含含任任任任何何何何不不不不确确确确定定定定因因因因素素素素。由由由由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。模拟的解题方法一般有三种类型模拟的解题方法一般有三种类型模拟的解题方法一般有三种类型模拟的解题方法一般有三种类型 直叙式模拟直叙式模拟直叙式模拟直叙式模拟 筛选法模拟筛选法模拟筛选法模拟筛选法模拟 构造法模拟构造法模拟构造法模拟构造法模拟庞只藩票幻谍佩视瞥啪爹楷存啊彝宦扁铭剪褪纽屠扎暂奏茂叁钨娥端吃柬上海市控江中学王建德上海市控江中学王建德构造的一般思想方法构造的一般思想方法1 1、统计分析法、统计分析法2 2、机理分析法、机理分析法把天竞榆帧赶宣措簇殿枫勘积蛙海虐神馁乌酉铂肩泊浮谎苟席谆涤拿母均上海市控江中学王建德上海市控江中学王建德1 1、统计分析法、统计分析法：我们在一时得不到事物的特征机理的情况下，通过某种方法测试得到一些数据（即问题的部分解），再利用数理统计知识对数据进行处理，从而得到最终的数学模型抽震广高漏围弗腐新杯赚庭蒸贤突峻枉弓哀篮捻艘糕揩伞涉牟喧滨粤藻毡上海市控江中学王建德上海市控江中学王建德极值问题极值问题m，n为整数，且满足下列两个条件：m，n1，2，3，k(1k109)；(n2-mn-m2)2=1。由键盘输入k，求一组满足上述两个条件的m，n并且使m2+n2的值最大。K2348163264N2338132155M122581334烷蓟楔佃骤刹恋蟹尼唁哨谜醇传鼎娟已纤开荚殷翔栖撵侧逊拥怒昏费驻弱上海市控江中学王建德上海市控江中学王建德如果我们的猜想正确，那么当(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)一定是方程的另一组解。varm，n，next，k:longint；beginwrite(k=)；readln(k)；读入读入n和和m的上限的上限kif(k1000000000)thenhalt；如果如果k不在要求范围内，就终止不在要求范围内，就终止m1；n1；nextm+n；确定斐波拉契数列的头三项确定斐波拉契数列的头三项whilenextythenbegincifxythenbegincyy；y yx x；x xcc；endend； 按照递增顺序排列按照递增顺序排列x x和和y y if x=y div 1.618 if x=y div 1.618 若若x x和和y y接近接近黄金分割数，则失败；否则胜利黄金分割数，则失败；否则胜利 then writeln(0) then writeln(0) else writeln(1) else writeln(1)；弥锣椒盯蚌卞煞操福焊茄依拣脾藤皿跺娄颧褪汉考汕桔层获胎札态鞠水计上海市控江中学王建德上海市控江中学王建德根根据据客客观观事事物物的的特特性性，分分析析其其内内部部的的机机理理，弄弄清清关关系系，在在适适当当抽抽象象的的条条件件下下，得得到到可可以以描描述述事物属性的数学工具。事物属性的数学工具。我我们们在在联联赛赛中中可可以以用用这这种种方方法法建建立立数数学学模模型型，然后根据所对应的算法求出解。如下然后根据所对应的算法求出解。如下图图所示：所示：腊契牺桩柬准醋条螟筑驾东形鞠谭潍筑油咽薛童契操椰撂卒肪抽咨臣晌璃上海市控江中学王建德上海市控江中学王建德 国际象棋（国际象棋（国际象棋（国际象棋（knightknightknightknight） 国国国国际际际际象象象象棋棋棋棋是是是是我我我我们们们们休休休休息息息息娱娱娱娱乐乐乐乐时时时时所所所所常常常常玩玩玩玩的的的的游游游游戏戏戏戏。在在在在各各各各个个个个棋棋棋棋子子子子中中中中，马马马马的的的的行行行行进进进进方方方方式式式式最最最最为为为为特特特特殊殊殊殊，也也也也为为为为人人人人们们们们所所所所津津津津津津津津乐乐乐乐道道道道。我我我我们们们们都都都都知知知知道道道道：马马马马走走走走的的的的是是是是“日日日日”字字字字，也也也也就就就就是是是是说说说说每每每每次次次次都都都都是是是是向向向向水水水水平平平平或或或或竖竖竖竖直直直直方方方方向向向向移移移移动动动动1 1 1 1格格格格，而而而而向向向向另另另另一一一一个个个个方方方方向向向向移移移移动动动动2 2 2 2格格格格，所所所所以以以以也也也也可可可可称称称称作作作作是是是是1*21*21*21*2的马（走法如下图所示）。在图中我们看到一个马由的马（走法如下图所示）。在图中我们看到一个马由的马（走法如下图所示）。在图中我们看到一个马由的马（走法如下图所示）。在图中我们看到一个马由8 8 8 8种跳的方向。种跳的方向。种跳的方向。种跳的方向。小小小小明明明明是是是是一一一一个个个个数数数数学学学学爱爱爱爱好好好好者者者者，他他他他将将将将马马马马的的的的走走走走法法法法重重重重新新新新定定定定义义义义了了了了一一一一下下下下，重重重重新新新新定定定定义义义义后后后后的的的的广广广广义义义义马马马马成成成成为为为为n*mn*mn*mn*m的的的的马马马马。为为为为了了了了研研研研究究究究广广广广义义义义马马马马，小小小小明明明明让让让让马马马马从从从从（0 0 0 0，0 0 0 0）出出出出发发发发，随随随随意意意意的的的的在在在在一一一一张张张张足足足足够够够够大大大大的的的的棋棋棋棋盘盘盘盘上上上上跳跳跳跳。他他他他发发发发现现现现，有有有有时时时时候候候候广广广广义义义义马马马马总总总总是是是是无无无无法法法法跳跳跳跳入入入入某某某某些些些些格格格格子子子子中中中中，比比比比如如如如从从从从2*22*22*22*2的的的的马马马马永永永永远远远远不不不不可可可可能能能能跳跳跳跳到到到到（1 1 1 1，1 1 1 1），这这这这令令令令他他他他非非非非常常常常感感感感兴兴兴兴趣趣趣趣。他他他他希希希希望望望望知知知知道道道道对对对对于于于于给给给给定定定定的的的的n n n n，m m m m，n*mn*mn*mn*m的的的的广广广广义义义义马马马马是是是是否否否否能能能能够够够够跳跳跳跳到到到到所所所所有有有有的的的的格格格格子子子子。由由由由于于于于n n n n，m m m m可可可可以以以以非非非非常常常常大大大大，这这这这令令令令小小小小明明明明花花花花了了了了许许许许多多多多功功功功夫夫夫夫在在在在尝尝尝尝试试试试上上上上，但但但但仍仍仍仍不不不不能能能能得得得得出出出出肯肯肯肯定定定定的的的的结结结结论论论论。于于于于是是是是他他他他就就就就来来来来找找找找你你你你这这这这个个个个计计计计算算算算机专家了帮忙。机专家了帮忙。机专家了帮忙。机专家了帮忙。【输入】【输入】【输入】【输入】在输入文件在输入文件在输入文件在输入文件knIGHT.InknIGHT.InknIGHT.InknIGHT.In中包含了多组测试数据，每个测试数据占一行。中包含了多组测试数据，每个测试数据占一行。中包含了多组测试数据，每个测试数据占一行。中包含了多组测试数据，每个测试数据占一行。每每每每组组组组测测测测试试试试数数数数据据据据由由由由2 2 2 2个个个个数数数数n n n n，m m m m（1n1n1n1n，m10m10m10m108 8 8 8）组组组组成成成成，表表表表示示示示广广广广义义义义马马马马的的的的类类类类型型型型。文文文文件件件件最最最最后后后后一行由一行由一行由一行由2 2 2 2个个个个0 0 0 0表示文件结束。表示文件结束。表示文件结束。表示文件结束。【输出】【输出】【输出】【输出】将将将将答答答答案案案案输输输输出出出出到到到到文文文文件件件件knIGHT.OUTknIGHT.OUTknIGHT.OUTknIGHT.OUT中中中中，每每每每组组组组测测测测试试试试数数数数据据据据占占占占一一一一行行行行。如如如如果果果果马马马马能能能能跳跳跳跳到到到到指指指指定定定定的的的的位位位位置输出置输出置输出置输出YESYESYESYES，否则输出，否则输出，否则输出，否则输出ImPOSSIbLEImPOSSIbLEImPOSSIbLEImPOSSIbLE。搀浆硕拨出函彻渤确哺哈蛰荧媚秸婪滔驯虹链岿撕冰随栗似啦笑帚缸袜桃上海市控江中学王建德上海市控江中学王建德 当n为奇数时，将棋盘染色成黑白相间。自（0，0）出发的马始终在白格子上跳跃，黑色的格子是马永远到不了的。当n为偶数时，我们有这样的移动方案（如上图（b）所示），使得马从（0，0）开始经过一系列的跳步后，到（1，0）的位置，也就是说可是让马到达相邻的格子，所以马可以遍历整个棋盘。从最简单的从最简单的从最简单的从最简单的1*n1*n1*n1*n的广义马开始分析的广义马开始分析的广义马开始分析的广义马开始分析茫霖荔振序医嫁躯伶炙遥幸孰冈硼落汞息茅揭疹窃揭徒垂盯谈侍各咱势见上海市控江中学王建德上海市控江中学王建德将将将将n*mn*mn*mn*m的广义马对应的广义马对应的广义马对应的广义马对应1*n1*n1*n1*n的广义马的广义马的广义马的广义马 第第第第1 1 1 1种种种种情情情情况况况况：若若若若n n n n，m m m m有有有有最最最最大大大大公公公公约约约约数数数数p p p p（p1p1p1p1），则则则则马马马马只只只只能能能能跳跳跳跳到到到到形形形形似似似似（p*sp*sp*sp*s，p*tp*tp*tp*t）的的的的格子上，其他的格子都到达到不了。格子上，其他的格子都到达到不了。格子上，其他的格子都到达到不了。格子上，其他的格子都到达到不了。 第第第第2 2 2 2种种种种情情情情况况况况：若若若若n+mn+mn+mn+m是是是是偶偶偶偶数数数数，类类类类似似似似于于于于1*n1*n1*n1*n马马马马的的的的情情情情况况况况，马马马马只只只只能能能能在在在在同同同同色色色色的的的的格格格格子子子子内内内内跳跳跳跳动动动动，不能遍历棋盘。不能遍历棋盘。不能遍历棋盘。不能遍历棋盘。 第第第第3 3 3 3种种种种情情情情况况况况：若若若若n+mn+mn+mn+m为为为为奇奇奇奇数数数数且且且且n n n n，m m m m互互互互质质质质。不不不不妨妨妨妨设设设设n n n n为为为为奇奇奇奇数数数数，那那那那么么么么m m m m为为为为偶偶偶偶数数数数。因因因因为为为为1*n1*n1*n1*n马马马马的的的的问问问问题题题题已已已已经经经经被被被被彻彻彻彻底底底底解解解解决决决决，所所所所以以以以很很很很自自自自然然然然的的的的想想想想将将将将n*mn*mn*mn*m经经经经过过过过一一一一系系系系列列列列变变变变换换换换转转转转化化化化成成成成1*n1*n1*n1*n马马马马的的的的问问问问题题题题。我们可以看到马的跳法本质上是我们可以看到马的跳法本质上是我们可以看到马的跳法本质上是我们可以看到马的跳法本质上是4 4 4 4种（另种（另种（另种（另4 4 4 4种可以看成是以下种可以看成是以下种可以看成是以下种可以看成是以下4 4 4 4种跳法反跳一步）：种跳法反跳一步）：种跳法反跳一步）：种跳法反跳一步）： （m m m m，n n n n） （m m m m，-n-n-n-n） （n n n n，m m m m） （n n n n，-m-m-m-m）马经过跳马经过跳马经过跳马经过跳p p p p次次次次、q q q q次次次次、r r r r次次次次、s s s s次次次次后后后后水平方向的位移为（水平方向的位移为（水平方向的位移为（水平方向的位移为（p+qp+qp+qp+q）*m+*m+*m+*m+（r+sr+sr+sr+s）*n *n *n *n 竖直方向的位移为（竖直方向的位移为（竖直方向的位移为（竖直方向的位移为（p-qp-qp-qp-q）*n+*n+*n+*n+（r-sr-sr-sr-s）*m*m*m*m为了利用为了利用为了利用为了利用1*n1*n1*n1*n马的结论，解不定方程（马的结论，解不定方程（马的结论，解不定方程（马的结论，解不定方程（p+qp+qp+qp+q）*m+*m+*m+*m+（r+sr+sr+sr+s）*n=1*n=1*n=1*n=1。nnnn，m m m m互质。互质。互质。互质。该方程一定有解（该方程一定有解（该方程一定有解（该方程一定有解（p p p p0 0 0 0，q q q q0 0 0 0，r r r r0 0 0 0，s s s s0 0 0 0）。）。）。）。又又又又mmmm是偶数是偶数是偶数是偶数n n n n是奇数。是奇数。是奇数。是奇数。（p p p p0 0 0 0+q+q+q+q0 0 0 0）是偶数，（）是偶数，（）是偶数，（）是偶数，（r r r r0 0 0 0+s+s+s+s0 0 0 0）是奇数。）是奇数。）是奇数。）是奇数。（p p p p0 0 0 0+q+q+q+q0 0 0 0）与（）与（）与（）与（p p p p0 0 0 0-q-q-q-q0 0 0 0）同奇偶，而（）同奇偶，而（）同奇偶，而（）同奇偶，而（r r r r0 0 0 0+s+s+s+s0 0 0 0）与（）与（）与（）与（r r r r0 0 0 0-s-s-s-s0 0 0 0）同奇偶。）同奇偶。）同奇偶。）同奇偶。（p p p p0 0 0 0-q-q-q-q0 0 0 0）是偶数，）是偶数，）是偶数，）是偶数，(r(r(r(r0 0 0 0-s-s-s-s0 0 0 0) ) ) )是奇数。是奇数。是奇数。是奇数。（p p p p0 0 0 0-q-q-q-q0 0 0 0）*n+*n+*n+*n+（r r r r0 0 0 0-s-s-s-s0 0 0 0）*m*m*m*m是偶数。是偶数。是偶数。是偶数。也也也也就就就就是是是是马马马马通通通通过过过过一一一一系系系系列列列列的的的的跳跳跳跳动动动动所所所所得得得得到到到到的的的的效效效效果果果果相相相相当当当当于于于于1*len1*len1*len1*len的的的的马马马马跳跳跳跳一一一一步步步步的的的的效效效效果果果果（len=len=len=len=（p p p p0 0 0 0-q-q-q-q0 0 0 0）*n+*n+*n+*n+（r r r r0 0 0 0-s-s-s-s0 0 0 0）*m*m*m*m）。根根根根据据据据前前前前面面面面的的的的结结结结论论论论，1*len1*len1*len1*len的的的的马马马马可可可可以以以以遍遍遍遍历历历历整整整整个个个个棋棋棋棋盘盘盘盘，所所所所以以以以当当当当n+mn+mn+mn+m为为为为奇奇奇奇数数数数且且且且n n n n，m m m m互质时，互质时，互质时，互质时，n*mn*mn*mn*m的马可以遍历整个棋盘。算法的时间复杂度为的马可以遍历整个棋盘。算法的时间复杂度为的马可以遍历整个棋盘。算法的时间复杂度为的马可以遍历整个棋盘。算法的时间复杂度为W(1)W(1)W(1)W(1)，空间需求为，空间需求为，空间需求为，空间需求为W(1)W(1)W(1)W(1)。 拉脖易吕朗磨梁樊摈梁耸褒镁凶垛艺能党轮烈项裙挖兵涕擎榨狐胆苏昔躲上海市控江中学王建德上海市控江中学王建德varn，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 beginreadln(n，m)； 读广义马的类型if(n+m)mod2=0 若n+m偶数，则无解then writeln(ImPOSSIbLE) else begin if nm，若不满足，则交换n，m tempn；nm； mtemp； end；thenif gcd(n，m)=1若n，m互质，则输出成功信息；否则输出失败信息 then writeln(YES) else writeln(ImPOSSIbLE)；end；elseend.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 X数列的和（数列的和（Sum of X-SequenceSum of X-Sequence）蹲幅彩校钞迹迂欲贬莫求姻几笼杨伍能引覆角追萧琳畦诽崭舷被袒伸钻泛上海市控江中学王建德上海市控江中学王建德长长度度为为n n的的X X数数列列共共有有2 2n-1n-1个个，要要全全部部枚枚举举一一遍遍是是不不现现实实的的。所所以以，一一定定有有更更好好的的方方法法。这这就就需需要要我我们们对对题题目目作作进进一一步步的的研研究究。只只要要做做适适当当的的变变换换，其其中中的的奥奥秘秘就就会会浮浮出出水水面。面。 我们假设存在这样的一个数列我们假设存在这样的一个数列aai i 满足题目要求，讨论满足题目要求，讨论S S应满足的条件。应满足的条件。令令 b bi i=a=ai+1i+1-a-ai i， 则则 由由 题题 目目 知知 ， b bi i=1=1或或 -1-1。 且且 a a1 1=0=0， a a2 2=b=b1 1， a a3 3=b=b1 1+b+b2 2， ，a an n=b=b1 1+b+b2 2+b+bn-1n-1。所所以以S=aS=a1 1+a+a2 2+a+an n=0+b=0+b1 1+(b+(b1 1+b+b2 2)+(b)+(b1 1+b+b2 2+b+bn-1n-1)=(n-)=(n-1)b1)b1 1+(n-2)b+(n-2)b2 2+2*b+2*bn-2n-2+b+bn-1n-1 （1 1）易知易知|S|S| (n-1)+(n-2)+1=(n-1)*n/2(n-1)+(n-2)+1=(n-1)*n/2。1+2+(n-1)=(n-1)*n/2 1+2+(n-1)=(n-1)*n/2 （2 2）由由(2)(2)式式-(1)-(1)式式得得：(n-1)*n/2-S=(n-1)*(1- (n-1)*n/2-S=(n-1)*(1- b b1 1)+(n-2)*(1- )+(n-2)*(1- b b2 2)+2*(1- )+2*(1- b bn-n-2 2)+(1- b)+(1- bn-1n-1) )因因为为1-b1-bk k=0=0或或2 2，所所以以上上式式右右端端为为偶偶数数。要要使使等等式式成成立立，则则其其左左端端也也为为偶偶数数，即即S S与与(n-1)*n/2(n-1)*n/2同奇偶。同奇偶。再再把把等等式式两两边边同同除除以以2 2，令令c ci i=(1-b=(1-bi i)/2)/2（易易知知c ci i=0=0或或1 1），得得(n-1)*n/2-S/2=(n-1) (n-1)*n/2-S/2=(n-1) c c1 1+(n-2) c+(n-2) c2 2+ 2*c+ 2*cn-2n-2+ c+ cn-1n-1令令T=(n-1)*n/2-S/2T=(n-1)*n/2-S/2所所以以原原问问题题转转化化为为一一个个简简单单的的数数学学问问题题：T能能否否表表示示成成1，2，（n-1）中中若干个不重复的数之和。若干个不重复的数之和。驹母条惋粳蠢除骆酸厦已注茸圾乓腊惨孽本苯太余锯峰絮唇憋狂蒲僧软活上海市控江中学王建德上海市控江中学王建德这这个个问问题题不不难难解解决决。当当0 0 T T (n-1)*n/2(n-1)*n/2时时，T T能能够够表表示示成成1 1，2 2，（n-1n-1）中中若若干干个个不不重重复复的数之和。问题转化的必要性是显然的。接着用数学归纳法来证明它的充分性。证：的数之和。问题转化的必要性是显然的。接着用数学归纳法来证明它的充分性。证：(1)(1)当当n=1n=1时，时，0 0 T T 0 0，0=00=0。当当n=2n=2时，时，0 0 T T 1 1，0=00=0，1=11=1。当当n=3n=3时，时，0 0 T T 3 3，0=00=0，1=11=1，2=22=2，3=1+23=1+2。均成立。均成立。(2)(2)当当n=kn=k（k k 3 3）时，归纳假设成立。则当）时，归纳假设成立。则当n=k+1n=k+1时：时：若若0 0 TkTt) 判断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) endthenelse inc(a)；c=0，即aj=aj-1+1 writeln(a) 输出数列中的一项 end；forend；elseend.main虚照蕉描或箩仑残力树蒂繁拭敲竿啊濒颓肃蛰湖叙蜂捣镑颈抨却情狱涩旗上海市控江中学王建德上海市控江中学王建德密码锁（密码锁（密码锁（密码锁（locklock）凭凭借借你你多多年年的的开开锁锁经经验验，你你马马上上断断定定眼眼前前这这扇扇门门用用的的是是密密码码锁锁。只只见见锁锁身身上上有有n n行行数数字字，在在每每行行数数字字末末尾尾都都有有好好几几个个数数字字拨拨盘盘。看看着着这这一一行行行行多多少少不不一一的的数数字字，和和数数字字末末尾尾留留下下的的空空格格，你你忽忽然然想想起起了了小小时时候候经经常常玩玩的的一一个个游游戏戏：找找规规律律。这这个个游游戏戏就是给你一个数列的前几项，让你填出后一项，例如：就是给你一个数列的前几项，让你填出后一项，例如：2 4 6 (8)2 4 6 (8)1 4 9 (16)1 4 9 (16)在在玩玩游游戏戏的的过过程程中中，你你发发现现了了一一个个窍窍门门，对对于于所所有有这这类类问问题题，都都可可以以用用这这种种方方法法解解决决：对对于于一一个个已已知知前前m m项项的的数数列列a a1 1，a a2 2，a a3 3aam m，一一定定可可以以找找到到唯唯一一一一个个不不超超过过m-m-1 1次次的的多多项项式式f(x)f(x)，使使得得f(1)=af(1)=a1 1，f(2)=af(2)=a2 2f(m)=af(m)=am m，那那么么f(m+1)f(m+1)就就是是要要找找的的下下一项。一项。现在你决定用这种方法试着打开眼前这把密码锁。现在你决定用这种方法试着打开眼前这把密码锁。【输入】【输入】第一行是一个整数第一行是一个整数n n，代表门上共有，代表门上共有n n行数字，行数字，n100n100。以下以下n n行，每行对应门上的一行数字，每行的数字不超过行，每行对应门上的一行数字，每行的数字不超过10001000个。个。输入的数字之间用空格隔开，每行末尾没有多余的空格。输入的数字之间用空格隔开，每行末尾没有多余的空格。输入的数字都是绝对值小于输入的数字都是绝对值小于10108 8的整数。的整数。【输出】【输出】输输出出应应该该包包括括n n行行，为为根根据据输输入入数数据据的的规规律律推推出出的的下下一一个个数数字字，顺顺序序与与输输入入数数据据相对应。保证结果的绝对值都小于相对应。保证结果的绝对值都小于10108 8。阉手逸谚耽石狭佐噶炯达梅貉仰销爱窿揍沧柯迟毖赐婪晰渭喂獭秩剂绪妆上海市控江中学王建德上海市控江中学王建德这道题最直接的方法就是构造出数列的通项公式：对于一个已知m项的数列，构造出的通项公式共有m项，当im时，f(i)总是有且仅有一项不为零，而且等于ai。例如数列前3项为1，3，5，通项公式为：这种方法的缺点是运算过程中数的规模比较大，如果用高精度计算，时空效率可能无法接受。如果不用高精度，恐怕得不到准确解。慰幼直砌磊橱炳行剁武蓝猫跋沃腊参紫蓬呜浚鞘挥驭旨最渐椽骋秧铺俐酶上海市控江中学王建德上海市控江中学王建德方法二方法二方法二方法二定定定定理理理理：如如如如果果果果一一一一个个个个数数数数列列列列的的的的通通通通项项项项公公公公式式式式是是是是关关关关于于于于自自自自然然然然数数数数n n n n的的的的r r r r次次次次多项式，那么这个数列是多项式，那么这个数列是多项式，那么这个数列是多项式，那么这个数列是r r r r阶等差数列。阶等差数列。阶等差数列。阶等差数列。这个定理的证明很简单，只要反复进行g(n)=f(n)-f(n-1)的运算，求数列的差数列，就会发现通项公式的次数每迭带一次都会降低一次，最终原数列的r阶差数列就是一个常数列。也就是说原数列是一个r阶等差数列。在这道题里，已知这个数列的通项公式有m-1项，那么这个数列就是一个m-1阶的等差数列。于是就可以借助等差数列求出数列的第m+1项，例如数列1，4，9：方方法法二二十十分分简简洁洁，要要计计算算的的数数据据不不是是很很大大，而而且且计计算算量量较较小小。算算法法的的时时间间复复杂杂度度为为W(n*mW(n*m2 2/2)/2)。由由于于计计算算过过程程中中有有许许多多数数据不需要保存，所以空据不需要保存，所以空间间需求是需求是W(1)W(1)。 陇淫乱毕梯围枯川捂借辖客掖露逞诸文孩胶砰苗女亏晕郎顷在栋势补岔坎上海市控江中学王建德上海市控江中学王建德var num：array1.2000of 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；forend.main束肌精涡氛唬戏锄稽羞圆援斧绝芳锑玖绿弱唇拴橇江咳棘吱揍何鞍瞎雾减上海市控江中学王建德上海市控江中学王建德空中都市空中都市在在一一个个未未来来的的空空中中都都市市中中，有有很很多多个个小小岛岛（城城区区）。现现在在要要求求在在这这些些岛岛之之间间架架一一些些桥桥梁梁（桥桥是是架架在在两两个个岛岛之之间间的的）。要要求求，首首先先，如如果果A A与与B B之之间间有有桥桥，B B与与C C之之间间有有桥桥，则则A A与与C C之之间间就就不不能能再再架架桥桥了了。即即，对对于于城城市市中中的的任任意意三三个个岛岛，不不能能在在其其中中两两两两都都架架上上桥桥。在在这这样样的的前前提提下下，要要求求架架的的桥桥的的数数量量最最多多（不不考考虑虑具具体体的的空空间间结构问题）。结构问题）。输输 入入 文文 件件 只只 包包 含含 一一 行行 ， 其其 中中 包包 含含 非非 负负 整整 数数n n（0=n=10000=n=1000），是城市中小岛的数目。），是城市中小岛的数目。输出文件也只包含一行，是最大能够架的桥的数目。输出文件也只包含一行，是最大能够架的桥的数目。输入示例：输入示例：6 6输出示例：输出示例：9 9奄适污脚已纂亲些贴颧捷塑昌了瘩篷厢腻满赦献肝蜕邮解蓬父瞥栅倦遏湖上海市控江中学王建德上海市控江中学王建德1 1、递推法、递推法、递推法、递推法如果设对于如果设对于n n个小岛，可以架的桥数为的话，则应满足如下的关系：个小岛，可以架的桥数为的话，则应满足如下的关系：其其中中，符符号号表表示示向向下下取取整整。首首先先，这这个个式式子子的的正正确确性性还还是是比比较较容容易易证证明明的（考虑使用抽屉原理）。的（考虑使用抽屉原理）。2 2、构造法、构造法、构造法、构造法按按照照题题意意，如如果果小小岛岛A A与与小小岛岛B B之之间间、小小岛岛B B与与小小岛岛C C之之间间和和小小岛岛A A与与小小岛岛C C之之间间都都有有桥桥的的话话，则则说说明明A A、B B、C C三三个个小小岛岛之之间间存存在在传传递递性性。试试题题要求构造一个含要求构造一个含n n个顶点且满足下述条件的图个顶点且满足下述条件的图任三个顶点间任三个顶点间不含传递性不含传递性图中所含边数最多。图中所含边数最多。我们通过下述方法将空中都市问题对应一个简单问题：我们通过下述方法将空中都市问题对应一个简单问题：把把n n个个小小岛岛分分为为尽尽量量平平均均的的两两部部分分，第第一一组组为为n/2n/2（或或(n-1)/2(n-1)/2）个个顶顶点点, ,第第二二组组为为n/2n/2（或或(n+1)/2(n+1)/2）个个顶顶点点。然然后后第第一一组组的的每每一一个个顶顶点点分分别别向向第第二组的所有顶点引出边。二组的所有顶点引出边。汁馋波砷击荤脸虞尝慈煎室唇猩邱碰嫉内魁竟查呕诸捂典睡像烁乱祥怀肥上海市控江中学王建德上海市控江中学王建德由此得出桥的数目是下面，我们来证明这个构造方法的正确性。由于两组的任一对顶点之间都有边相连，因此如果再架桥的话，只能在同组的一对顶点之间进行。如果在某一组的顶点i和顶点j间架桥，则由于顶点i和顶点j与另一组的任一个顶点k相连，使得顶点i、顶点j和顶点k之间存在传递关系，这是不允许的。由此可见，按照上述方法得出的图所含边数最多。下面给出解法：Readln(n)；kord(odd(n)；n为偶数时，k=0；n为奇数时，k=1ifk=1输出桥数的最大值thenwriteln(n-1)*(n+1)/4)elsewriteln(n*n/4)；fori1 to (n-k)div 2 do 枚举第一组的每一个小岛 forj(n-k)div 2+1 to n do 枚举第二组的每一个小岛 writeln(,i,j,)； 输出棵麓思韩娠驹纺萍脓或赌词藕雕焚醉签淤菊拆伦您沫暴中勾跃孩埂是登榨上海市控江中学王建德上海市控江中学王建德舞会舞会某某学学校校要要召召开开一一个个舞舞会会。现现在在已已知知在在学学校校的的所所有有n n名名学学生生中中，有有些些学学生生曾曾经经互互相相跳跳过过舞舞。（跳跳过过舞舞的的两两个个学学生生一一定定是是一一个个男男生生和和一一个个女女生生）。现现在在要要求求被被邀邀请请的的学学生生中中的的任任何何一一对对男男生生女女生生互互相相都都不不能能跳跳过过舞舞，求求这这个个舞舞会会最最多能够邀请多少学生参加。多能够邀请多少学生参加。输输入入文文件件的的第第一一行行是是n n和和mm。其其中中n n是是可可选选的的学学生生的的总总数数，mm是是已已知知的的跳跳过过舞舞的的学学生生的的对对数数（n=1000,m=2000n=1000,m=2000）。然然后后有有mm行行，分分别别包包含含两两个个非非负负整整数，表示这两个编号的学生曾经跳过舞。（学生的编号是从数，表示这两个编号的学生曾经跳过舞。（学生的编号是从0 0号到号到n-1n-1号。）号。）输出文件只要求输出一行，其中包含一个数字，即能够邀请的最大的学生数。输出文件只要求输出一行，其中包含一个数字，即能够邀请的最大的学生数。输入示例：输入示例：8686020223233535141416163131输出示例：输出示例：5 5盐知名渣笆镭冶涨弗俞娟只恤久虞胎商尝儿取歉吠葬掸埠藩母帅培回日趁上海市控江中学王建德上海市控江中学王建德算法分析算法分析1 1、二分图、二分图、二分图、二分图男女生各分两个顶点集，若跳过舞，则连边。男女生各分两个顶点集，若跳过舞，则连边。2 2、最小覆盖集、最小覆盖集、最小覆盖集、最小覆盖集覆覆覆覆盖盖盖盖集集集集KK的的的的定定定定义义义义：覆覆盖盖集集K K为为一一个个顶顶点点子子集集，且且G G的的每每一一条条边边至至少少有有一一个个顶顶点点属属于于k k。含含顶顶点点数数最少的覆盖集即为最小覆盖集。最少的覆盖集即为最小覆盖集。去掉最小覆盖集的顶点，所有的舞对拆散。因此去掉最小覆盖集的顶点，所有的舞对拆散。因此n-n-最小覆盖集的顶点数最小覆盖集的顶点数= =能够邀请的最大的学能够邀请的最大的学生数。生数。 吐掌厨够留传俏凯突价沦牌希孟剩浚额驮顽赚宾售嫡忙集铱雇原性去骆惹上海市控江中学王建德上海市控江中学王建德KnightsKnights一一张张大大小小为为n*nn*n的的国国际际象象棋棋棋棋盘盘，上上面面有有一一些些格格子子被被拿拿走走了了。你你的的任任务务是是确确定定在在这这个个棋棋盘盘上上放放置置尽尽可可能能多多的的马马并并使使他他们们不不互互相相攻攻击击。棋棋盘盘的的大大小小n n不不超超过过200200。算法分析算法分析算法分析算法分析下下面面，从从构构造造图图的的角角度度分分析析本本题题的的模模型型。将将棋棋盘盘的的每每一一个个格格子子作作为为一一个个顶顶点点，两两点点间间直直接接可可达达（互互可可攻攻击击）的的关关系系作作为为边边。则则题题目目所所要要求求的的就就是是在在这这样样一一张张图图中中的的最最大大独独立立子子集集。由由于于对对于于任任意意一一张张图图，其其最最大大独独立立子子集集和和最最小小覆覆盖盖集集互互为为补补集集，所所以以本本题题也也是是一一个个求求最最小小覆覆盖盖集集的的图图论论问问题题。众众所所周周知知，一一般般图图的的最最小小覆覆盖盖图图是是一一个个NPCNPC问问题题。那那么么本本题题能能否否逃逃脱脱厄厄运呢？这只有从本题的特殊性来分析运呢？这只有从本题的特殊性来分析。莽骤皖魁槐窃睁旱湃沸锭厢再统爹私桓掸儒纪悟抱勇扶慌膜努股还旬闯蚜上海市控江中学王建德上海市控江中学王建德常识告诉我们，在一张国际象棋的棋盘上，白格和黑格是相交错的，一匹马只能从一个白格跳到一个黑格，或是从一个黑格跳到一个白格。由于这种特殊性，马的攻击范围的不规则，在这时却给我们的解题带来了方便。因为一个位置上的马只能攻击和其所在位置颜色不同的格子，这是一个必要条件。换句话说，同一颜色的任意两个格子间不存在边。所以，棋盘可以按照颜色分成两个部分，在同一部分的任意两点都是不能互相攻击的。也就是说定义在攻击关系上的棋盘是一个二分图。同时，由于二分图的独特性质，它的最小覆盖数=最大匹配数。没横喜软翠谓便兄理早凛伟扳狭颖驹搬期逞椽厢灶绝控鹿突哗择莫狮拦曾上海市控江中学王建德上海市控江中学王建德4色排列色排列问题描述红、黄、蓝、绿4种颜色围成长度为N(N=30)的一圈（位置编号为1、2、N），不能有一种颜色是连续3个，共有多少种方案？样例输入：5输出：780匠宦党悯隧昼跳楔疾榆俩瑚武楚绚搜锡冒嗓潞巷俏窗地回蔚炕霉章乔聪厕上海市控江中学王建德上海市控江中学王建德最少步数最少步数问题描述在各种棋中，一种棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将更加增加趣味性，因此，他规定马既能按“日”飞，也能各象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就和他玩一种新游戏，在围棋盘上（19*19）任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A，B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。样例输入：12161810输出：89刺皱萝粱哇屹年汹切烁和迪玫够楼痘哮具非颠断描栗伟汽奄响哭轿狗喇厌上海市控江中学王建德上海市控江中学王建德平分面积平分面积 问题描述问题描述 按顺时针依次给出一个凸按顺时针依次给出一个凸N N边形的边形的N(=10)N(=10)个点的个点的坐标，要求从第一点坐标出发划一条线，恰好把此坐标，要求从第一点坐标出发划一条线，恰好把此N N边形划分成面积相等的两块（相差边形划分成面积相等的两块（相差0.010.01），求此），求此直线与多边形的另一个交点坐标（精确到小数点后直线与多边形的另一个交点坐标（精确到小数点后2 2位）。位）。 样例样例 输入：注释输入：注释3 3N N的值的值010010第第1 1点坐标点坐标x,yx,y3.503.50第第2 2点坐标点坐标-3.50-3.50第第3 3点坐标点坐标输出：输出：0.00.00.000.00轮兄拉辣兢抽茁藏搂臀刚谬陪姐鄂孩熟捡巢腿呸硅腾竖擂瘟懒迈愁便袖拔上海市控江中学王建德上海市控江中学王建德