杭电OJ第11页2060~2064算法题（C语言）

以你之姓@ 2023-10-06 16:03 17阅读 0赞

#### 目录 ####

*  2060.Snooker
 *  2061.Treasure the new start, freshmen!
 *  2062.Subset sequence
 *  2063.过山车
 *  2064.汉诺塔III

## 2060.Snooker ##

Problem Description
    background:
    Philip likes to play the QQ game of Snooker when he wants a relax, though
     he was just a little vegetable-bird. Maybe you hadn't played that game 
     yet, no matter, I'll introduce the rule for you first.
    There are 21 object balls on board, including 15 red balls and 6 color 
    balls: yellow, green, brown, blue, pink, black.
    The player should use a white main ball to make the object balls roll into 
    the hole, the sum of the ball's fixed value he made in the hole is the 
    player's score. The player should firstly made a red ball into the hole, 
    after that he gains red-ball's value(1 points), then he gets the chance to 
    make a color ball, then alternately. The color ball should be took out 
    until all the red-ball are in the hole. In other word, if there are only 
    color balls left on board, the player should hit the object balls in this
     order: yellow(2 point), green(3 point), brown(4 point), blue(5 point), 
     pink(6 point), black(7 point), after the ball being hit into the hole, 
     they are not get out of the hole, after no ball left on board, the game 
     ends, the player who has
    the higher score wins the game. PS: red object balls never get out of the 
    hole.
    I just illustrate the rules that maybe used, if you want to contact more 
    details, visit http://sports.tom.com/snooker/ after
    the contest.
    
    for example, if there are 12 red balls on board(if there are still red 
    ball left on board, it can be sure that all the color
    balls must be on board either). So suppose Philp can continuesly hit the 
    ball into the hole, he can get the maximun score is
    12 * 1 (12 red-ball in one shoot) + 7 * 12(after hit a red ball, a black 
    ball which was the most valuable ball should be the target) + 2 + 3 + 4 + 
    5 + 6 + 7(when no red ball left, make all the color ball in hole).
    Now, your task is to judge whether Philip should make the decision to give
     up when telling you the condition on board(How many object balls still 
    left not in the hole and the other player's score). If Philp still gets 
    the chance to win, just print "Yes", otherwise print "No". (PS: if the max 
    score he could get on board add his current score is equal to the 
    opponent's current score, still output "Yes")
    Input
    The first line contains a numble N indicating the total conditions. Then 
    followed by N lines, each line is made of three integers:
    Ball_Left P_Score O_Score represeting the ball number left on board, 
    Philp's current score, and the opponent's current score.
    All the input value are in 32 bit integer value range.
    Output
    You should caculate the max score left Philp can gain, and judge whether 
    he has the possiblity to win.
    Sample Input
    2
    12 1 1
    1 30 39
    Sample Output
    Yes
    No

分析：通过分析题意可知，要根据球台上剩余的球数来计算Philp目前能够得到的最大分数：  
（1）Ball\_Left>6，球台上还有红球，为了获得最多的分数，每一次打进红球后都选择打黑球；  
（2）Ball\_Left<=6，球台上只剩下彩色球，按照规则直接计算即可。

#include <stdio.h>
    
    void Snooker(){
        
    	/*
    		Ball_Left:球台上剩余的球数 
    		P_Score:Philp当前得分 
    		O_Score:对手的得分 
    	*/
    	int Ball_Left,P_Score,O_Score;
    	int n,sum,i; 
    	int s[6]={
        7,6,5,4,3,2};
    	//n个案例 
    	while(n--){
        
    		scanf("%d%d%d",&Ball_Left,&P_Score,&O_Score);
    		if(Ball_Left>6){
        
    			//球台上还有红球，为了获得最多的分数，每一次打进红球后都选择打黑球
    			sum=(Ball_Left-6)*8+2+3+4+5+6+7;
    		}else{
        
    			//剩余的球均为彩色球
    			sum=0;
    			for(i=0;i<Ball_Left;i++){
        
    				sum+=s[i];
    			}
    		}
    		if(sum+P_Score>=O_Score){
        
    			printf("Yes\n");
    		}else{
        
    			printf("No\n");
    		}
    	}
    }

## 2061.Treasure the new start, freshmen! ##

Problem Description
    background:
    A new semester comes , and the HDU also meets its 50th birthday. No matter 
    what's your major, the only thing I want to tell you is:"Treasure the 
    college life and seize the time." Most people thought that the college 
    life should be colorful, less presure.But in actual, the college life is 
    also busy and rough. If you want to master the knowledge learned from the 
    book, a great deal of leisure time should be spend on individual study and 
    practise, especially on the latter one. I think the every one of you 
    should take the learning attitude just as you have in senior school.
    "No pain, No Gain", HDU also has scholarship, who can win it? That's 
    mainly rely on the GPA(grade-point average) of the student had got. Now, I 
    gonna tell you the rule, and your task is to program to caculate the GPA.
    If there are K(K > 0) courses, the i-th course has the credit Ci, your 
    score Si, then the result GPA is
    GPA = (C1 * S1 + C2 * S2 +……+Ci * Si……) / (C1 + C2 + ……+ Ci……) (1 <= i <=
     K, Ci != 0)
    If there is a 0 <= Si < 60, The GPA is always not existed.
    
    Input
    The first number N indicate that there are N test cases(N <= 50). In each 
    case, there is a number K (the total courses number), then K lines 
    followed, each line would obey the format: Course-Name (Length <= 30) ,
     Credits(<= 10), Score(<= 100).
    Notice: There is no blank in the Course Name. All the Inputs are legal
    Output
    Output the GPA of each case as discribed above, if the GPA is not existed, 
    ouput:"Sorry!", else just output the GPA value which is rounded to the 2 
    digits after the decimal point. There is a blank line between two test 
    cases.
    Sample Input
    2
    3
    Algorithm 3 97
    DataStruct 3 90
    softwareProject 4 85
    2
    Database 4 59
    English 4 81
    Sample Output
    90.10
    Sorry!

分析：本题的实质是计算加权平均成绩，按照公式直接计算即可。

#include <stdio.h>
    
    void WeightedAverageScore(){
        
    	int n,k,flag;
    	//credit:每门课程的学分
    	double creditSum,scoreSum,score,credit;
    	char courseName[60];
    	scanf("%d",&n);
    	if(n<0 || n>50){
        
    		printf("n的取值范围为[0,50]之间的整数！\n");
    		return;
    	}
    	//n个测试用例 
    	while(n--){
        
    		//k门课程 
    		scanf("%d",&k);
    		scoreSum=creditSum=0;
    		while(k--){
        
    			scanf("%s",courseName);
    			scanf("%lf%lf",&credit,&score);
    			if(score<60){
        
    				flag=1;
    			}		
    			scoreSum+=credit*score;
    			creditSum+=credit;
    		}
    		if(flag){
        
    			printf("Sorry!\n");
    		}else{
        
    			printf("%.2lf\n",scoreSum/creditSum);
    		}
    	}
    }

## 2062.Subset sequence ##

Problem Description
    Consider the aggregate An= {
         1, 2, …, n }. For example, A1={
        1}, A3=
    {
        1,2,3}. A subset sequence is defined as a array of a non-empty subset. 
    Sort all the subset sequece of An in lexicography order. Your task is to 
    find the m-th one.
     
    Input
    The input contains several test cases. Each test case consists of two 
    numbers n and m ( 0< n<= 20, 0< m<= the total number of the subset 
    sequence of An ).
     
    Output
    For each test case, you should output the m-th subset sequence of An in 
    one line.
     
    Sample Input
    1 1
    2 1
    2 2
    2 3
    2 4
    3 10
     
    Sample Output
    1
    1
    1 2
    2
    2 1
    2 3 1

分析：  
（1）设f\[n\]表示元素总数为n时，子集的总个数。显然，f\[0\]=0、f\[1\]=1、f\[2\]=4、f\[3\]=15、f\[4\]=64…，经过观察和推理可以知道**f\[n\]=n\*\{f\[n-1\]+1\}**。推导过程如下：所有的子集可以按字典顺序排序并按照首数字分成n组，而每组里除了只有一个元素的第一项，剩下的子集就是不同的n-1个元素的子集合了，所以有f\[n\]=n\*\{f\[n-1\]+1\}。  
（2）设将所有的子集可以按字典顺序排序并按照首数字分成n组后，每组的子集个数为num\[n\]=f\[n\]/n，联立可以得到f\[n\]=n\*\{f\[n-1\]+1\}，可得**num\[n\]= (n-1) \* num\[n-1\]+1**。

#include <stdio.h>
    
    void SubsetSequence(){
        
    	//n:元素总个数  t:对所有子集分组后所求子集所在的组数 
    	int i,n,t;
        __int64 m;
        //num[i]:表示n=i时将所有子集分组后平均每组的个数
        __int64 num[21]={
        0};
        //FirstEle[i]:将所有子集按字典顺序排序并按照首数字分组后第i组的初始首元素
        int FirstEle[21];
        for (i=1;i<21;i++)
            num[i]=num[i-1]*(i-1)+1;
        while (scanf("%d%I64d",&n,&m)!=EOF){
        
            for(i=0;i<21;i++){
        
            	FirstEle[i]=i;
            }
            while (n>0 && m>0){
        
            	//计算所求子集位于分组后的组数 
                t=m/num[n]+(m%num[n]>0?1:0);
                if(t>0){
        
                    printf("%d",FirstEle[t]);
                    //输出该组首项后，利用自增来进行覆盖，起到删除该元素的作用 
                    for(i=t;i<=n;i++){
        
                    	FirstEle[i]++;
                    }
                    //m变为表示在剩余子集的位置 
                    m-=((t-1)*num[n]+1);
                    putchar(m==0?'\n':' ');
                }
                //元素个数减一
                n--;
            }
        }	
    }

## 2063.过山车 ##

Problem Description
    RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排
    只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但
    是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意
    和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问
    题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的
    Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
     
    Input
    输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。
    0<K<=1000
    1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一
    个0结束输入。
     
    Output
    对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
     
    Sample Input
    6 3 3
    1 1
    1 2
    1 3
    2 1
    2 3
    3 1
    0
     
    Sample Output
    3

分析：本题主要是对匈牙利算法的应用。可查看[这篇文章][Link 1]。

#include <stdio.h>
    #include <string.h>
    
    //k:可能匹配数
    //m:女生数
    //n:男生数
    int k,m,n;
    //map[i][j]==1:男生i和女生j之间有意愿组成搭档
    //boy[i]==j:男生i与女生j已经组成搭档
    //girl[i]==j:女生i与男生j已经组成搭档
    //partner[i]==1:标记递归过程中暂时被拆散的女生i,使得此轮递归被拆散的男生不能
    //再选择这个女生而是选择其他有组成搭档意愿并且没有被标记的女生 
    int map[1001][1001],boy[501],girl[501],partner[501];
    
    int find(int x){
        
    	int i;
    	//遍历每个女生
    	for(i=1;i<=n;i++){
        
    		//一对男女生之间有意愿组成搭档，并且该女生目前还未被标记过 
    		if(map[x][i] && partner[i]==0){
        
    			//暂时标记该女生 
    			partner[i]=1;
    			//girl[i]==-1:女生i目前没有和其他男生组成搭档
    			//find(girl[i])==1:已经与女生i组成搭档的男生girl[i]可以与其他的
    			//女生组成搭档(即男生girl[i]将女生i"让给"男生x) 
    			if(girl[i]==-1 || find(girl[i])){
        
    				boy[x]=i;
    				girl[i]=x;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    
    void RollerCoaster(){
        
    	//cnt:记录最大匹配数
    	int i,j,cnt;
    	while(scanf("%d%d%d",&k,&m,&n)==3 && k){
        
    		cnt=0;
    		memset(boy,-1,sizeof(boy));//cx数组记录与x匹配的y点
    		memset(girl,-1,sizeof(girl));
    		memset(map,0,sizeof(map));
    		
    		//保存输入的组合关系 
    		for(i=1;i<=k;i++){
        
    			int a,b;
    			scanf("%d%d",&a,&b);
    			map[a][b]=1;
    		}
    		
    		//遍历每个男生 
    		for(i=1;i<=m;i++){
        
    			//男生i没有搭档 
    			if(boy[i]==-1){
        
    				memset(girl,0,sizeof(girl));
    				cnt+=find(i);//来找每一条增广路，可使得匹配加1；
    			}
    		}
    		printf("%d\n",cnt);
    	}
    }

## 2064.汉诺塔III ##

Problem Description
    约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、
    由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次
    只能移动一个盘，且不允许大盘放在小盘的上面。
    现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或
    从中间移出)，也不允许大盘放到小盘的上面。
    Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请
    你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？
     
    Input
    包含多组数据，每次输入一个N值(1<=N=35)。
     
    Output
    对于每组数据，输出移动最小的次数。
     
    Sample Input
    1
    3
    12
     
    Sample Output
    2
    26
    531440

分析：设hanoi\[i\]表示i个圆盘从最左边移到最右边至少需要的次数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzAwNDA0NA_size_16_color_FFFFFF_t_70]  
将n个圆盘从最左边移到最右边分为两步：  
（1）先将最下面的圆盘移动到最右边  
（2）然后再将剩余的n-1个圆盘移动到最右边  
其中将n-1个圆盘移动从最左边移动到最右边（或者从最左边移动到最右边）的最少次数为hanoi\[n-1\]，由上图可知，该操作一共进行了3次，而将最下面的圆盘从最左边移动到最右边一共移动了2次，所以可以得到递推式：  
**hanoi\[n\]=3\*hanoi\[n-1\]+2**，然后在依此为依据编写代码即可。

#include <stdio.h>
    
    void Hanoi3(){
        
    	//hanoi[i]表示i个圆盘从最左边移到最右边至少需要的次数 
    	__int64 hanoi[36]={
        0,2};
    	int i,n;
    	for(i=2;i<=35;i++){
        
    		hanoi[i]=3*hanoi[i-1]+2;	
    	}
    	while(scanf("%d",&n)!=EOF){
        
    		if(n<=0 || n>35){
        
    			printf("圆盘个数的取值范围为[1,35]之间的整数！\n");
    			continue;
    		}
    		printf("%I64d\n",hanoi[n]);
    	}
    }

[杭电OJ第11页2065~2069算法题（C语言）][OJ_11_2065_2069_C]

[Link 1]: https://blog.csdn.net/dark_scope/article/details/8880547
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzAwNDA0NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210115102113348.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzAwNDA0NA==,size_16,color_FFFFFF,t_70
[OJ_11_2065_2069_C]: https://blog.csdn.net/weixin_43004044/article/details/112691613