问题简述 给出一个整数n，请按从小到大的顺序，输出分母不大于n的所有最简真分数。比如n=4时，输出序列为：1/4 1/3 1/2 2/3 3/4 分析 设farey(a,b,c,d)表示按大小输出开区间(a/b,c/d)中的分母不大于n的最简真分数的算法。那么我们只要执行farey(0,1,1,1)就可输出想要的结果。 由于 a/b < (a+c)/(b+d) < c/d，所以我们的farey(a,b,c,d)要先输出(a/b,(a+c)/(b+d))中的数，这等价于执行farey(a,b,a+c,b+d)，然后输出(a+c)/(b+d)，最后再输出((a+c)/(c+d),c/d)中的数，这等价于执行farey(a+c,b+d,c,d)。 于是我们的farey写成代码便为

问题简述 给出n和k，求n个结点的高度为k的正则二叉树有多少种。 分析 设dp[i,j]表示用i个点组成深度最多为j的二叉树的方法数，则： dp[i,j]=∑(dp[k,j-1]×dp[i-1-k,j-1])(k∈{1..i-2}) 边界条件：dp[1,i]=1 我们要求的是深度恰好为K的方法数S，易知S=dp[n,k]-dp[n,k-1]。 代码 /* ID: aikilis1 LANG: C TASK: nocows */ #include <stdio.h> int main(void) { int n,k,i,j,p; unsigned f[200][100]={0}; freopen("nocows.in","r",stdin); freopen("nocows.out","w",stdout); scanf("%d%d",&n,&k); for (i=1;i<=

问题简述 有N(10<=N<=100)盏灯，他们分别从1到N被标上号码。这些灯都连接到四个按钮： 按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。 按钮2：当按下此按钮，将改变所有奇数号的灯。 按钮3：当按下此按钮，将改变所有偶数号的灯。 按钮4：当按下此按钮，将改变所有序号是3*K+1(K>=0)的灯。例如：1,4,7... 一个计数器C记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器C为0。 你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有

问题简述 给定的一个1,2,3组成的数字序列，求排成升序所需的最少交换次数。 分析 本来位置正确的数我们不必去动它,因为如果我们某次交换了它,我们最后还得把它交换回来. 另一方面,只需两次交换我们就能让任意三个数按任意的顺序排列,而一次交换最多可以把两个元素放到正确的位置上(这两个元素正好在对方的位置上).所以我们首先便将可以对换到正确位置的数先对换了,这样保证我们的每次交换都实现了最大的价值. 如果还剩有不能对换的数,那么它们一定既有1,也有2,还有3,因为假设1,2,3其中某个缺失了,那么剩下两个就可以对换,这与我们已经对

问题简述 既是一个质数又是一个回文数(从左到右和从右到左是看一样的)的数被称为回文质数，比如151就是一个回文质数。 写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数; 分析 直接从a到b进行搜索肯定行不通，完全是在虐待电脑而且效率过低，必然超时。 我们可以按数的位数生成回文数再判断其是不是质数。 要生成k位的回文数，（这里我们假定k为奇数，为偶数时稍作变换即可，但是后面可以看到完全没有讨论偶数的必要）， 我们可以枚举所有的(k+1)/2位的数，再把它以中间那位数为中心对折，就生成

问题简述 有S个牛棚，有的有牛，有的没有，用不多于M个木板覆盖牛棚，使得所有有牛的牛棚都被覆盖。每块木板的长度都是任意的，求所需木板的最小总长度。 分析 如果只有一块木板，那么显然最省的办法是从第一个有牛的牛棚开始，一直覆盖到最后一个有牛的牛棚，设从第一个有牛牛棚到最后一个有牛牛棚的距离是L,那么只用一块木板的时候，最短长度就是L。 如果增加到2块木板呢？可以看到，我们只需要在一块木上截下一段，就可以变为2块木板。截哪一段呢？显然是将覆盖最长空白的那一块截下来，这样浪费的木料最少。这里空白指的是一段连续

问题简述 有一条由N颗珠子组成的项链，每颗珠子都是红色（r），蓝色（b），或者白色（w）之一。 你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大多数的数目的子。 Example 举例来说，在图片 A 中的项链，可以收集到8个珠子,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链。 在一些项链中，包括白色的珠子如图片 B 所示。 当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可