安徽省2009年省选题day2

《安徽省2009年省选题day2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1：飞行棋（Fly）在经过地“小小宇航员夏令营”的学习以及模拟飞行实验后，小可可明白宇航员并不是那么容易当的，除了需要强健的身体，丰富的经验以及灵活的应变能力以外，缜密的思维也是不可少的，为了早日实现自己的宇航员的梦想，小可可决定在平时就开始锻炼——利用棋类游戏来锻炼自己的思维。小可可发明一种飞行棋，棋盘是一个圆周形，在圆周形上有若干个点，已知这些点与点之间的弧长，弧长均为正整数，并且依圆弧顺序排列，飞行棋的规则是找出这些点中有没有可以围成矩形的，在最短时间内找出所有不重复矩形的玩家胜出。输入：第一行为正整数N，表示棋盘上点的个数，接下来n行分别为这N个点所分割

2、的各个圆弧的长度。输出：所构成的不重复的矩形。样例：输入：812231133输出：3100%的数据:n<=20Timelimit:1000ms2：中国象棋（Chess）这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。你也来和小可可一起锻炼一下思维吧！输入：一行包含两个整数N，M，之间由一个空格隔开。输出：总共的方案数，由于该值可能很大，只需给

3、出方案数模9999973的结果。样例：输入：13输出：7样例说明：除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。提示：100%的数据中N和M不超过10050%的数据中N和M至少有一个数不超过830%的数据中N和M均不超过6Casetimelimit:1000ms3:跳棋（checker）象棋的问题被小可可轻松解决了，下面小可可邀请你一起来研究另一个难题，这次与跳棋有关，问题是这样的：在一个1行N列（N是奇数）的棋盘上，在K个格子是红色的，这种情况下，在开始移动之前，你可以棋盘的任何空位上放棋子。在游戏开始后，你只可以随时在

4、一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子就被吃掉了，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。现在你和小可可要解答以下两个问题：1.移动开始前至少要放多少棋子才能完成任务？2.如果使移动开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务？这是你和小可可合作解决的最后一个问题了，共同努力吧！关于规则的补充说明：1.只能往空位上放棋子，不管是移动开始前还是在移动过程中。2.移动开始前棋盘最左端的那个原始棋子绝对不能被吃掉。输入：第一行一个正奇数N第二行有N个

5、整数，如果第i个整数是1，说明第i个格子是红色，否则则为白色，数字之间用一个空格隔开。输出：两个用一个空格隔开的整数，分别为对第一问和第二问的回答。样例：输入：500010输出：11提示：100%的数据中，N不超过1000.输出中数字不会超过10的15次方！30%的数据，N不超过20Timelimit:1000ms