您所在位置：主题：数学推理在竞赛中的应用
奥特曼
[专家分：360] 发布于 2003-10-12 10:39:00
（2002年初中组4：过河卒）
——2002年第八届信息学分区联赛 初中组第四题
【问题描述】
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
Arena
——信息学初学者之家 2003.7.29练习赛 第三题
【问题描述】
近日，CWTV网络电视公司为了提高收视率，举办了一场CWTV拳击擂台赛。一共有n名选手参赛，分别为A1，A2……An。拳击赛的举办者对每名参赛选手的实力作了详尽的分析，发现若Ai能击败Aj，则一定有Ai>Aj。
现在举办者需要制定一个出场次序，第一个出场的作为第一任擂主，然后其他选手依次出场向擂主挑战，凡是挑战者战胜了擂主，那么这个挑战者就顶替原擂主的位置成为新的擂主。由于举办者希望比赛尽量的精彩，他希望在整个擂台赛中一共更换k次擂主。请你帮助他算出满足他的要求的出场次序的个数。
例如：出场顺序14253说明了擂主依次是1,4,5，这符合n=5和k=2。
【输入格式】
从文件c.in 共一行：n，k。n为参赛人数，k为更换擂主次数。
规模：0<n<=500，0<=k<n
【输出格式】
出场次序的个数输出到文件c.out。
【输入样例1】
2 0
【输出样例1】
1
【输入样例2】
3 1
【输出样例2】
3
【样例说明】
n=2，k=0有唯一的出场顺序21
n=3，k=1有出场顺序132；231；213
[思路]
① K次
② K-1次
f(n-1，k)*(n-1)
f(n-1,k-1)*1
f(n,k)=1 k=n-1
f(n,0)=(n-1)!
F(n,k)=0 k>=n
步步高升（Step by Step）
——华南师大附中袁豪 2001分区联赛模拟赛 提高组第二题
【问题描述】
春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位，看到一盆叫做“步步高升”的盆竹。“步步高升，步步高升……”学习就是要一步一步来，不能急，要打好基础。在稳固的基础上才谈得上步步高升！TENSHI若有所思。她看到这盆东西好意头，于是想买下。谁知一问价钱，“不贵不贵，才２ＸＸＲＭＢ。”TENSHI差点没昏倒，囊中羞涩嘛。但是TENSHI还是很想买下来，于是她就在一旁观察。观察了一段时间，她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元，那么他第i+1次报的价格为Wi－A或Wi －B。到了最后，TENSHI以Z元成交，高高兴兴的回家去了。
【任 务】
求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。
【输入格式】
从文件STEP.INP读入数据。文件第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件：
10 ≤ W1 ≤106，1 ≤ Z ≤ 106 ，Z < W1
2 ≤ A 、B ≤ 10000，A≠B
【输出格式】
直接把所求得的方法总数输出到文件STEP.OUT的第一行。文件只有一行（包括换行符）。注意：结果不超过MAXLONGINT
【样例一】
STEP.INP STEP.OUT
256 885 9 3889832
【样例二】
STEP.INP STEP.OUT
100 1013 23 0
[思路]
f (小于0)=0
f (0)=1
f (n)=f (n-A)+f (n-B)
w1-z=wi
K好数（K-Good Number）
——信息学初学者之家 2002分区联赛模拟赛＃2 普及组第三题
【问题描述】
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。给定K、L，求L位K好数的数目。
【输入格式】
从文件读入数据，第一行为K、Ｌ，其中K<=16，L<=10。
【输出格式】
将结果输出到 KGOOD.OUT
【样例】
KGOOD.DAT KGOOD.OUT
4 2 7
[思路]
1,2,3,4…… 1
0~k-1 11 13
花痴
——信息学初学者之家 2003国庆邀请赛 第二试第一题
【问题描述】
Hongyan没事就在神秘岛上闲逛，岛上各种奇花异草数不胜数，钟情于花的他很快便被苹果树下的一丛奇花迷住了（路边的野花不要采哦！），他惊奇地发现，这些花的形状都是正多边形的，而且花瓣与花瓣之间的层层嵌套看起来就像将正多边形的每一对顶点都用线段连上了心的。酷爱数学的他居然想要将花朵上的每一对平行线都数出来……就像数星星似的，数来数去都数不完。远处，Worm已经做好饭准备叫大家吃了，为了不使hongyan挨饿，请你尽快帮帮他吧！
【输入文件】
输入文件flower.in只有一个数N，4<=N<=2500
【输出文件】
输出文件flower.out只有一个数,输出正N边形所有顶点对间连线中共有多少对平行线。
【输入样例】
6
【输出样例】
12
样例说明：
比如说正6边形，顶点顺序是ABCDEF，那么对应的12对平行线是：
AB与CF、AB与DE、DE与CF、BC与AD、BC与EF、AD与EF、CD与BE、CD与AF、BE与AF、AC与DF、BD与AE、CE与BF。
[思路]
(2n-4)/2=n-2+2=n ((n-1)*n)/2=(n-1)/2
(2n)/2=n=6/2=3
(2n)/2=n
2
n * n
((n-3)*n)/2+n
取数游戏
——信息学初学者之家 2003分区联赛模拟赛＃1 普及组第一题
【问题描述】
我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。如果你能算出一共有多少种取法，那么你会被天神Lijiganjun奖励。
【输入格式】
输入文件“choice.in”中仅包含一个数n（1< n < 50）。
【输出格式】
输出文件“choice.out”中仅包含一个数———你的答案。
【样例】
CHOICE.IN CHOICE.OUT
5 13
[思路]
斐波拉契数列
1 2 3 4 5 6 7 8 ……
0 1 1 2 3 5 8 13
f(n)=f(n-2)+f(n-1)
K 上升段
——信息学初学者之家 2003分区联赛模拟赛＃1 提高组第二题
【问题描述】
对于n 的一个全排列，如果它可以划分成k 个单调递增序列，则称其为k 上升段。例如：排列1 2 4 5 6 3 9 10 7 8 是一个合法的3 上升0段，它可以划分成1 2 4 5 6;3 9 10;7 8这三个单调递增序列。对每个给定的(n,k)，请你给出n 的所有k 上升段的个数。
【输入格式】
输入仅有1 行，包含两个数n, k（1 < n < 20, 1 < k < n）。
【输出格式】
输出n 的所有k 上升段的个数。
【样例】
K.IN K.OUT
3 2 4
[思路]
y
X
取走一个数
K上升段
K-1上升段
f (n,k)=k*f (n-1,k)+(n-k+1)*f (n-1,k-1)
f (n,1)=1 f (n,0)=0 f (n,n)=1or0
——2002年第八届信息学分区联赛 初中组第四题
【问题描述】
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
Arena
——信息学初学者之家 2003.7.29练习赛 第三题
【问题描述】
近日，CWTV网络电视公司为了提高收视率，举办了一场CWTV拳击擂台赛。一共有n名选手参赛，分别为A1，A2……An。拳击赛的举办者对每名参赛选手的实力作了详尽的分析，发现若Ai能击败Aj，则一定有Ai>Aj。
现在举办者需要制定一个出场次序，第一个出场的作为第一任擂主，然后其他选手依次出场向擂主挑战，凡是挑战者战胜了擂主，那么这个挑战者就顶替原擂主的位置成为新的擂主。由于举办者希望比赛尽量的精彩，他希望在整个擂台赛中一共更换k次擂主。请你帮助他算出满足他的要求的出场次序的个数。
例如：出场顺序14253说明了擂主依次是1,4,5，这符合n=5和k=2。
【输入格式】
从文件c.in 共一行：n，k。n为参赛人数，k为更换擂主次数。
规模：0<n<=500，0<=k<n
【输出格式】
出场次序的个数输出到文件c.out。
【输入样例1】
2 0
【输出样例1】
1
【输入样例2】
3 1
【输出样例2】
3
【样例说明】
n=2，k=0有唯一的出场顺序21
n=3，k=1有出场顺序132；231；213
[思路]
① K次
② K-1次
f(n-1，k)*(n-1)
f(n-1,k-1)*1
f(n,k)=1 k=n-1
f(n,0)=(n-1)!
F(n,k)=0 k>=n
步步高升（Step by Step）
——华南师大附中袁豪 2001分区联赛模拟赛 提高组第二题
【问题描述】
春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位，看到一盆叫做“步步高升”的盆竹。“步步高升，步步高升……”学习就是要一步一步来，不能急，要打好基础。在稳固的基础上才谈得上步步高升！TENSHI若有所思。她看到这盆东西好意头，于是想买下。谁知一问价钱，“不贵不贵，才２ＸＸＲＭＢ。”TENSHI差点没昏倒，囊中羞涩嘛。但是TENSHI还是很想买下来，于是她就在一旁观察。观察了一段时间，她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元，那么他第i+1次报的价格为Wi－A或Wi －B。到了最后，TENSHI以Z元成交，高高兴兴的回家去了。
【任 务】
求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。
【输入格式】
从文件STEP.INP读入数据。文件第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件：
10 ≤ W1 ≤106，1 ≤ Z ≤ 106 ，Z < W1
2 ≤ A 、B ≤ 10000，A≠B
【输出格式】
直接把所求得的方法总数输出到文件STEP.OUT的第一行。文件只有一行（包括换行符）。注意：结果不超过MAXLONGINT
【样例一】
STEP.INP STEP.OUT
256 885 9 3889832
【样例二】
STEP.INP STEP.OUT
100 1013 23 0
[思路]
f (小于0)=0
f (0)=1
f (n)=f (n-A)+f (n-B)
w1-z=wi
K好数（K-Good Number）
——信息学初学者之家 2002分区联赛模拟赛＃2 普及组第三题
【问题描述】
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。给定K、L，求L位K好数的数目。
【输入格式】
从文件读入数据，第一行为K、Ｌ，其中K<=16，L<=10。
【输出格式】
将结果输出到 KGOOD.OUT
【样例】
KGOOD.DAT KGOOD.OUT
4 2 7
[思路]
1,2,3,4…… 1
0~k-1 11 13
花痴
——信息学初学者之家 2003国庆邀请赛 第二试第一题
【问题描述】
Hongyan没事就在神秘岛上闲逛，岛上各种奇花异草数不胜数，钟情于花的他很快便被苹果树下的一丛奇花迷住了（路边的野花不要采哦！），他惊奇地发现，这些花的形状都是正多边形的，而且花瓣与花瓣之间的层层嵌套看起来就像将正多边形的每一对顶点都用线段连上了心的。酷爱数学的他居然想要将花朵上的每一对平行线都数出来……就像数星星似的，数来数去都数不完。远处，Worm已经做好饭准备叫大家吃了，为了不使hongyan挨饿，请你尽快帮帮他吧！
【输入文件】
输入文件flower.in只有一个数N，4<=N<=2500
【输出文件】
输出文件flower.out只有一个数,输出正N边形所有顶点对间连线中共有多少对平行线。
【输入样例】
6
【输出样例】
12
样例说明：
比如说正6边形，顶点顺序是ABCDEF，那么对应的12对平行线是：
AB与CF、AB与DE、DE与CF、BC与AD、BC与EF、AD与EF、CD与BE、CD与AF、BE与AF、AC与DF、BD与AE、CE与BF。
[思路]
(2n-4)/2=n-2+2=n ((n-1)*n)/2=(n-1)/2
(2n)/2=n=6/2=3
(2n)/2=n
2
n * n
((n-3)*n)/2+n
取数游戏
——信息学初学者之家 2003分区联赛模拟赛＃1 普及组第一题
【问题描述】
我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。如果你能算出一共有多少种取法，那么你会被天神Lijiganjun奖励。
【输入格式】
输入文件“choice.in”中仅包含一个数n（1< n < 50）。
【输出格式】
输出文件“choice.out”中仅包含一个数———你的答案。
【样例】
CHOICE.IN CHOICE.OUT
5 13
[思路]
斐波拉契数列
1 2 3 4 5 6 7 8 ……
0 1 1 2 3 5 8 13
f(n)=f(n-2)+f(n-1)
K 上升段
——信息学初学者之家 2003分区联赛模拟赛＃1 提高组第二题
【问题描述】
对于n 的一个全排列，如果它可以划分成k 个单调递增序列，则称其为k 上升段。例如：排列1 2 4 5 6 3 9 10 7 8 是一个合法的3 上升0段，它可以划分成1 2 4 5 6;3 9 10;7 8这三个单调递增序列。对每个给定的(n,k)，请你给出n 的所有k 上升段的个数。
【输入格式】
输入仅有1 行，包含两个数n, k（1 < n < 20, 1 < k < n）。
【输出格式】
输出n 的所有k 上升段的个数。
【样例】
K.IN K.OUT
3 2 4
[思路]
y
X
取走一个数
K上升段
K-1上升段
f (n,k)=k*f (n-1,k)+(n-k+1)*f (n-1,k-1)
f (n,1)=1 f (n,0)=0 f (n,n)=1or0
