一、棋盘类题目1.马拦过河卒中学高级本（紫皮）P2、《奥赛精解练习题》P266页棋盘上A（0,0）点有一个过河卒，需要走到目标B（n，m）点。卒街的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在点及所有跳跃一步可达点称为马的控制点。因此称之为“马拦过河卒”。输入：一行四个数据，表示B点和C点马的坐标，n、m均为不超过15的整数。输出：一个数据，表示所有的路径数。【分析】遍历每个点的路径，A点所在行及列上点的路径均为1，马的9个控制点的路径均为0，其余每个点的路径为a[x,y]:=a[x,y-1]+a[x-1,y]。2.设有一个n*m方格的棋盘（1≤m,n≤100）。求出该棋盘中包含多少个正方形、多少个长方形（不包括正方形）。(Noip97-1)例如：当n=2，m=3时，正方形的个数有8个；即边长为1的正方形有6个；边长为2的正方形有2个。长方形的个数有10个；即2*1的长方形有4个；1*2的长方形有3个；3*1的长方形有2个；3*2的长方形有1个。程序要求：输入：n和m输出：正方形的个数与长方形的个数如上例：输入：23输出：8，10【分析】二、贪心算法中学高级本（紫皮）P221.排队接水有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。输入：输入文件共2行，第一行为n；第二行为每个人的接水等待时间输出：文件为2行，第一行为排队顺序，第二行为平均等待时间。2.智力大冲浪智力大冲浪节目，奖励每个参赛者m元，首先比赛时间为n个时段(n<=500),它又给出了很多小游戏，每个小游戏都必须在规定期限Ti前完成（1=<Ti<=n)。如果一个游戏没能在规定的期限前完成，则要从奖励费m元中扣去一部分钱Wi，Wi为自然数，不同的游戏扣去的钱是不一样的，当然，每个游戏本身都很简单，保证每个人都能在一个时段完成，而且都必须从整数段开始，主持人只是想考考参赛者如何安排组织自己做游戏的顺序，作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱，注意，比赛绝不让参赛者赔钱。[问题输入]输入文件in.txt，共4行。第1行为m，表示一开始奖励给每位参赛者的钱；第2行为n，表示有n个小游戏；第3行有n个数，分别表示游戏1到n的规定完成期限；第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。[问题输出]输出文件out.txt，仅1行。表示小伟能赢取最多的钱。[输入样例]100007424314670605040302010[输出样例]99503.火柴棒题目：阿姆斯特朗数如果一个n位正整数等于其各位数字的n次方之和,则称该数为阿姆斯特朗数。例如1^3+5^3+3^3=153当n＝3时，又称水仙花数，特指一种三位数，其各个数之立方和等于该数。水仙花数共有4个，分别为：153、370、371、407。题目：史密斯数。输出4—9999中的所有史密斯数。史密斯数是可以分解的整数，且所有数位上的数字和等于其全部素数因子的数字总和。例如：9975=3×5×5×7×199+9+7+5=303+5+5+7+1+9=30贪心策略1.删数问题（最大整数）《奥赛精解练习题》P266页/《奥赛经典金钥匙》P58页文件输入一个高精度的正整数n（<=240位），去掉其中任意s个数字后剩下的数字按左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。分析：按高位到低位搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。如何寻找递减区间首字符，需要注意可能会出现串首有若干个0的情况。输入n,sWhiles>0doBeginI:=1;While(i<length(n))and(n[i]<n[i+1])doi:=i+1;Delete(n,I,1);S:=s-1;End;While(lentgh(n)>1)and(n[1]=’0’)dodelete(n,1,1)输出n;2.合并果子《奥赛经典金钥匙》P58页在一个果园里，所有果子已经打下来，分成不同数目的堆，多多决定把所有果子合并为一堆。每一次可以合并两堆，消耗体力等于两堆果子重量之和。经过n-1次合并后，就剩下一堆，还要再搬回家，所以要尽量的节省体力，设计出合并的方案，使消耗体力最少，并输出最小的体力耗费值。例如:有3种果子，数目依次为1，2，9。可以先1、2堆合并，新堆数目为3，耗费体力3，再将新堆与3堆合并，新堆数目为12，耗费体力为12，总共耗费体力=3+12=15。输入：两行，第一行整数n...