杭电OJ第11页2045~2049算法题（C语言）

古城微笑少年丶 2023-10-06 16:01 51阅读 0赞

#### 目录 ####

*  2045.不容易系列之(3)—— LELE的RPG难题
 *  2046.骨牌铺方格
 *  2047.阿牛的EOF牛肉串
 *  2048.神、上帝以及老天爷
 *  2049.不容易系列之(4)——考新郎

## 2045.不容易系列之(3)—— LELE的RPG难题 ##

Problem Description
    人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE的粉丝,即"可乐"）,经过多方打探，某资深Cole终于知道了原因，原来，LELE最近研究起了著名的RPG难题:
    有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
    以上就是著名的RPG难题.
    如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?
    Input
    输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。
    Output
    对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。
    Sample Input
    1
    2
    Sample Output
    3
    6

分析：本题的关键在于找规律，设s\[i\]表示有i个方格时满足要求的涂法  
（1）n=1时，三种颜色均可以选择，故有**s\[1\]=3**；  
（2）n=2时，第一个方格三种颜色均可以选择，但第二个方格只能选剩余的两个，所以**s\[2\]=6**；  
（3）n=3时，第一个方格三种颜色均可以选择，但第二个方格只能选剩余的两个，然而题目说了头尾不能相同所以最后一个方格只有一种选择，所以**s\[3\]=6**；  
（4）n=4时，第一个方格三种颜色均可以选择，但第二个方格只能选剩余的两个，之后的方格就要分情况考虑。当第三个格选择的是与第一个和第二个都不相同的颜色时，那么第四个方格只能选择1种，一共有6种，当第三格选择的颜色与第一种相同时，那么第四格就只能选择2种，一共12种。所以综合上述两种情况总共有**s\[4\]=12+6=18**种；  
（5）n=5时，同理可以推出**s\[5\]=30**；  
（5）n=6时，**s\[6\]=66**；  
······  
根据上述结果可以推出满足的递推式：**s\[i\]=s\[i-1\]+2\*s\[i-2\]（i>=5）**  
原理解释：  
（1）当n=i-1时，满足要求的涂法有s\[i-1\]种，若n=i，则在原来i-1个方格的基础上，由于第i-1个方格的颜色与第一个方格的颜色不同，且也不能与第i个方格的相同，所以第i个方格只有一种颜色可以选择，此时s\[i\]=s\[i-1\]；  
（2）当n=i-2时，满足要求的涂法有s\[i-2\]种，若n=i，此时第i-1个方格只有2种颜色可以选择（与第i-2个方格的颜色不同即可），第i个方格课选择的颜色与上面一种情况同理，只有一种颜色可以选择，所以此时s\[i\]=2\*s\[i-2\]；  
而当i>=5时，第i-3个方格所选择的颜色不能够影响s\[i\]的值（这里类似于[2041超级楼梯][2041]），所以只有第i-1和第i-2个方格的颜色的选择可以影响s\[i\]的值，所以综合上述两种情况，可以得到上面的递推式。

#include <stdio.h>
    
    void RPG(){
        
    	//s[i]表示有i个方格时满足要求的涂法
    	__int64 s[51]={
        0,3,6,6,18};
    	int i,n;
    	for(i=5;i<=50;i++){
        
    		s[i]=s[i-1]+2*s[i-2];
    	}
    	while(scanf("%I64d",&n)!=EOF){
        
    		if(n<=0 || n>50){
        
    			printf("n的取值范围为(0,50]之间的整数!\n");
    			continue;
    		}
    		printf("%I64d\n",s[n]);
    	}
    }

## 2046.骨牌铺方格 ##

Problem Description
    在2×n的一个长方形方格中,用一个1×2的骨牌铺满方格,输入n ,输出铺放方案的总数.
    例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：
    Input
    输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。
    Output
    对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。
    Sample Input
    1
    3
    2
    Sample Output
    1
    3
    2

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzAwNDA0NA_size_16_color_FFFFFF_t_70]  
分析：设dom\[i\]表示在2 x i的一个长方形方格铺放方案的总数，则由题可知dom\[0\]=0、dom\[1\]=1、dom\[2\]=2、dom\[3\]=3、dom\[4\]=5、…，**由此可以得出相应的递推式dom\[i\]=dom\[i-1\]+dom\[i-2\]。**  
此外值得注意的是，在测试过程过，当输入50时，最后得到的结果为一个负数，这显然是一个错误的结果，最后经过排查得知原来是**int的取值范围在32/64位系统中都是32位，其表示范围为-2147483648—+2147483647(-231—231\-1)，而当n=50时，铺放方案的总数早已超过了C语言中int能够表示的最大范围**。所以此时可以考虑使用C语言中的\_\_int64，其表示范围为-9223372036854775807—+9223372036854775808(-263—263\-1)，这样便可以得到正确的结果。

#include <stdio.h>
    
    void Dominoes(){
        
    	//dom[i]表示在2xi的一个长方形方格铺放方案的总数
    	__int64 dom[51];
    	int i,n;
    	dom[0]=0;
    	dom[1]=1;
    	dom[2]=2;
    	for(i=3;i<=50;i++){
        
    		dom[i]=dom[i-1]+dom[i-2];
    	}
    	while(scanf("%I64d",&n)!=EOF){
        
    		if(n<=0 || n>50){
        
    			printf("n的取值范围为(0,50]之间的整数!\n");
    			continue;
    		}
    		printf("%I64d\n",dom[n]);
    	}
    }

## 2047.阿牛的EOF牛肉串 ##

Problem Description
    今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做EOF的队伍，由04级的阿牛、XC
    以及05级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段
    激情燃烧的岁月，想了一想，阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只
    由"E" "O" "F"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,
    阿牛同时禁止在串中出现O相邻的情况，他认为，"OO"看起来就像发怒的眼睛，效果不好。
    你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？
    PS: 阿牛还有一个小秘密，就是准备把这个刻有 EOF的牛肉干，作为神秘礼物献给杭电五十周年校
    庆，可以想象，当校长接过这块牛肉干的时候该有多高兴！这里，请允许我代表杭电的ACMer向阿牛
    表示感谢！
    再次感谢！
    Input
    输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0<n<40)。
    Output
    对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。
    Sample Input
    1
    2
    Sample Output
    3
    8

分析：若直接将n带入计算，不易求解，所以可以考虑推导出递推式。设设满足定义i长度的字符串有num\[i\]种，并且字符串中的字符的下标为1~n，由题知num\[0\]=0、num\[1\]=3、num\[2\]=8，当长度为n(n>=3)时，推导过程如下：  
（1）若第n个字符为O，假定1~n-2满足题目的要求，那么第n-1个位置上的字符不能为O，只能为E或者F，所以总数为2 \*num(n-2)；  
（2）若第n个字符不为O，假定1~n-1题目的要求，那么第n个位置上的字符只能为E或者F，所以总数为2\*num(n-1)  
所以可得到递推式**num\[n\]=2\*(num\[n-1\]+num\[n-2\])**  
实质上本题是**错排问题**的一种变形，有关**错排问题**可以[查看百度百科][Link 1]

#include <stdio.h>
    
    void BeefKebabs(){
        
    	//num[i]表示在满足长度为i的不同字符串数
    	__int64 num[40];
    	num[0]=0;
    	num[1]=3;
    	num[2]=8;
    	int i,n;
    	for(i=3;i<40;i++){
        
    		num[i]=2*(num[i-1]+num[i-2]);
    	}
    	while(scanf("%d",&n)!=EOF){
        
    		if(n<=0 || n>=40){
        
    			printf("n的取值范围为(0,40)之间的整数!\n");
    			continue;
    		}
    		printf("%I64d\n",num[n]);
    	}
    }

## 2048.神、上帝以及老天爷 ##

Problem Description
    HDU 2006'10 ACM contest的颁奖晚会隆重开始了！
    为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：
    首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
    然后，待所有字条加入完毕，每人从箱中取一个字条；
    最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”
    大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！
    我的神、上帝以及老天爷呀，怎么会这样呢？
    不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？
    不会算？难道你也想以悲剧结尾？！
    Input
    输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(1<n<=20),表示参加抽奖的人数。
    Output
    对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参照sample output。
    Sample Input
    1
    2
    Sample Output
    50.00%

分析：本题主要考察排列问题和错排序公式。首先**n个有序的元素有n!个不同的排列**，如果一个排列使得所有的元素不在原来的位置上，则称这个排列为错排。1 2的错排是唯一的，即2 1。1 2 3的错排有3 1 2，2 3 1。这二者可以看作是1 2错排，3分别与1、2换位而得的。那么**题中没有一个人中奖的概率=n个有序元素的错排总数/n!**。设draw\[i\]表示i个有序元素的错排总数，由题可知draw\[0\]=0、draw\[1\]=0、draw\[2\]=1、draw\[3\]=2。当n>=3时，**由错排公式可得draw\[n\]=(n-1)\*(draw\[n-1\]+draw\[n-2\])**。

#include <stdio.h>
    
    void LuckDraw(){
        
    	int C,n,i;
    	__int64 draw[21]={
        0,0,1,2};
    	__int64 sum;
    	for(i=4;i<=20;i++) {
        
    		draw[i]=(i-1)*(draw[i-1]+draw[i-2]);
    	}
    	scanf("%d",&C);
    	while(C--){
        
    		sum=1;
    		scanf("%d",&n);
    		for(i=1;i<=n;i++){
        
    			sum*=i;
    		}
    		printf("%.2lf%%\n",(draw[n]*1.0/sum)*100);
    	}
    }

## 2049.不容易系列之(4)——考新郎 ##

Problem Description
    国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:
    首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
    然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.
    最后,揭开盖头,如果找错了对象就要当众跪搓衣板...
    看来做新郎也不是容易的事情...
    假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
    Input
    输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。
    Output
    对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
    Sample Input
    2
    2 2
    3 2
    Sample Output
    1
    3

分析：这题从本质上来说是一道错排题，设bride\[i\]表示i个有新娘的错排总数，排错公式与上题一样。不过本题在错排的基础上，又多了一些要求，从N个新郎，挑M个错排，也就是说有 N-M 个新郎选对了新娘，由组合数公式可知一共有C(N,N-M)种情况。所以最后N个新郎中有M个新郎找错了新娘的情况一共有C(N,N-M)\*bride\[M\]种。

#include <stdio.h>
    
    //组合数公式，C(n,m)=P(n,m)/m!=n!/((n-m!)*m!) 
    __int64 Combination(int n,int m){
        
    	int i;
    	__int64 res1=1,res2=1;
    	for(i=1;i<=m;i++){
        
    		res1*=(n-i+1);
    		res2*=i;
    	}
    	return res1/res2;
    }
    
    void Groom(){
        
    	int i,n,m,C;
    	//bride[i]表示i个新娘的错排总数
    	__int64 bride[21]={
        0,0,1};
    	__int64 sum;
    	for(i=3;i<=20;i++){
        
    		bride[i]=(i-1)*(bride[i-1]+bride[i-2]);
    	}
    	scanf("%d",&C);
    	while(C--){
        
    		scanf("%d%d",&n,&m);
    		if(n<=1 || n>20 || m<=1 || m>20 || m>n){
        
    			printf("n、m的取值范围为1<m<=m<=20，且它们均为整数!\n");
    			continue;
    		}
    		sum=bride[m]*Combination(n,n-m);
    		printf("%I64d\n",sum);
    	}
    }

[杭电OJ第11页2050~2054算法题（C语言）][OJ_11_2050_2054_C]

[2041]: https://blog.csdn.net/weixin_43004044/article/details/112461614
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzAwNDA0NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210112083111745.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzAwNDA0NA==,size_16,color_FFFFFF,t_70
[Link 1]: https://baike.baidu.com/item/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98/3849290?fr=aladdin
[OJ_11_2050_2054_C]: https://blog.csdn.net/weixin_43004044/article/details/112548717