安徽省2009年省选题Day2.doc

1：飞行棋（Fly）在经过地“小小宇航员夏令营”的学习以及模拟飞行实验后，小可可明白宇航员并不是那么容易当的，除了需要强健的身体，丰富的经验以 及灵活的应变能力以外，缜密的思维也是不可少的，为了早日实现自己的宇航员的梦想，小可可决定在平时就开始锻炼利用棋类游戏来 锻炼自己的思维。小可可发明一种飞行棋，棋盘是一个圆周形，在圆周形上有若干个点，已知这些点与点之间的弧长，弧长均为正整数，并且依圆弧顺序排列 ，飞行棋的规则是找出这些点中有没有可以围成矩形的，在最短时间内找出所有不重复矩形的玩家胜出。输入：第一行为正整数N，表示棋盘上点的个数，接下来n行分别为这N个点所分割的各个圆弧的长度。输出：所构成的不重复的矩形。样例： 输入： 8 1 2 2 3 1 1 3 3 输出： 3 100%的数据:n=20Timelimit:1000ms2：中国象棋（Chess） 这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另 一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一 列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！ 输入：一行包含两个整数N，M，之间由一个空格隔开。 输出：总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。 样例： 输入： 1 3 输出： 7样例说明：除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。提示：100%的数据中N和M不超过100 50%的数据中N和M至少有一个数不超过8 30%的数据中N和M均不超过6Casetimelimit:1000ms3:跳棋（checker） 象棋的问题被小可可轻松解决了，下面小可可邀请你一起来研究另一个难题，这次与跳棋有关，问题是这样的：在一个1行N列（N是 奇数）的棋盘上，在K个格子是红色的，这种情况下，在开始移动之前，你可以棋盘的任何空位上放棋子。在游戏开始后，你只可以随时在一 个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子就被吃掉了 ，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。现在你和小可可要解答以下两个问题：1.移动开始前至少要放多少棋子才能完成任务？2.如果使移动开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务？这是你和小可可合作解决的最后一个问题了，共同努力吧！关于规则的补充说明：1.只能往空位上放棋子，不管是移动开始前还是在移动过程中。2.移动开始前棋盘最左端的那个原始棋子绝对不能被吃掉。输入：第一行一个正奇数N 第二行有N个整数，如果第i个整数是1，说明第i个格子是红色，否则则为白色，数字之间用一个空格隔开。输出：两个用一个空格隔开的整数，分别为对第一问和第二问的回答。样例： 输入： 5 0 0 0 1 0 输出： 1 1提示