杭电OJ第11页2055~2059算法题（C语言）

太过爱你忘了你带给我的痛 2023-10-06 16:03 42阅读 0赞

#### 目录 ####

*  2055.An easy problem
 *  2056.Rectangles
 *  2057.A + B Again
 *  2058.The sum problem
 *  2059.龟兔赛跑

## 2055.An easy problem ##

Problem Description
    we define f(A) = 1, f(a) = -1, f(B) = 2, f(b) = -2, ... f(Z) = 26, f(z) =
     -26;
    Give you a letter x and a number y , you should output the result of y+f(x).
    Input
    On the first line, contains a number T.then T lines follow, each line is a 
    case.each case contains a letter and a number.
    Output
    for each case, you should the result of y+f(x) on a line.
    Sample Input
    6
    R 1
    P 2
    G 3
    r 1
    p 2
    g 3
    Sample Output
    19
    18
    10
    -17
    -14
    -4

分析：本题需要注意的字母与数的对应关系。

#include <stdio.h>
    
    void EasyProblem(){
        
    	int x,n,res;
    	char y;
    	scanf("%d",&n);
    	while(n--){
        
    		getchar();
    		scanf("%c%d",&y,&x);
    		if(y>='A' && y<='Z'){
        
    			res=y-'A'+1;
    		}else{
        
    			res='a'-y-1;
    		}
    		res+=x;
    		printf("%d\n",res);
    	}
    }

## 2056.Rectangles ##

Problem Description
    Given two rectangles and the coordinates of two points on the diagonals of 
    each rectangle,you have to calculate the area of the intersected part of 
    two rectangles. its sides are parallel to OX and OY .
    Input
    Input The first line of input is 8 positive numbers which indicate the 
    coordinates of four points that must be on each diagonal.The 8 numbers are 
    x1,y1,x2,y2,x3,y3,x4,y4.That means the two points on the first rectangle 
    are(x1,y1),(x2,y2);the other two points on the second rectangle are 
    (x3,y3),(x4,y4).
    Output
    Output For each case output the area of their intersected part in a single 
    line.accurate up to 2 decimal places.
    Sample Input
    1.00 1.00 3.00 3.00 2.00 2.00 4.00 4.00
    5.00 5.00 13.00 13.00 4.00 4.00 12.50 12.50
    Sample Output
    1.00
    56.25

分析：在计算时，要注意2个矩形不同的位置关系：相离、相交和包含。此外在计算之前将矩形的对角线坐标统一转换为左下——右上，这样便于后面的分情况计算。

#include <stdio.h>
    
    //交换两个数的值 
    void swap(double *a,double *b){
        
    	double temp;
    	temp=*a;
    	*a=*b;
    	*b=temp;
    }
    
    void Rectangles(){
        
    	double x1,y1,x2,y2,x3,y3,x4,y4;
    	double a,b,c,d;
    	while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4)!=EOF){
        
    		//将矩形的对角线坐标统一转换为左下——右上，便于后面的分情况计算
    		if(x1>x2) swap(&x1,&x2);
    		if(y1>y2) swap(&y1,&y2);
    		if(x3>x4) swap(&x3,&x4);
    		if(y3>y4) swap(&y3,&y4);
    		//相离
    		if(x3>=x2 || y3>=y2 || x4<=x1 || y4<=y1){
        
    			printf("0.00\n");
    			continue;
    		}
    		//包含或相交 
    		a=(x1<=x3)?x3:x1;
    		b=(x2<=x4)?x2:x4;
    		c=(y1<=y3)?y3:y1;
    		d=(y2<=y4)?y2:y4;
    		printf("%.2lf\n",(b-a)*(d-c));
    	}
    }

## 2057.A + B Again ##

Problem Description
    There must be many A + B problems in our HDOJ , now a new one is coming.
    Give you two hexadecimal integers , your task is to calculate the sum of 
    them,and print it in hexadecimal too.
    Easy ? AC it !
    Input
    The input contains several test cases, please process to the end of the 
    file.
    Each case consists of two hexadecimal integers A and B in a line seperated
     by a blank.
    The length of A and B is less than 15.
    Output
    For each test case,print the sum of A and B in hexadecimal in one line.
    Sample Input
    +A -A
    +1A 12
    1A -9
    -1A -12
    1A -AA
    Sample Output
    0
    2C
    11
    -2C
    -90

分析： 十六进制数在数学上有正负表示，但是在计算机中负数用补码表示，所以如果相加的结果为负数，那么在以十六进制形式输出时，需要判断正负，然后再做相应的输出。

#include <stdio.h>
    
    void AAddBAgain(){
        
    	__int64 a,b;
    	while(scanf("%I64x%I64x",&a,&b)!=EOF){
        
    		printf("%I64X\n",a+b);
    		//以16进制形式输出 
    		if(a+b<0){
        
    			printf("-%I64X\n",-(a+b));
    		}else{
        
    			printf("%I64X\n",a+b);
    		}
    	}
    }

## 2058.The sum problem ##

Problem Description
    Given a sequence 1,2,3,......N, your job is to calculate all the possible
     sub-sequences that the sum of the sub-sequence is M.
    Input
    Input contains multiple test cases. each case contains two integers N, M( 
    1 <= N, M <= 1000000000).input ends with N = M = 0.
    Output
    For each test case, print all the possible sub-sequence that its sum is 
    M.The format is show in the sample below.print a blank line after each 
    test case.
    Sample Input
    20 10
    50 30
    0 0
    Sample Output
    [1,4]
    [10,10]
    
    [4,8]
    [6,9]
    [9,11]
    [30,30]

分析：  
**思路1：** 采用两层for循环，求出不同长度的子序列之和，输出其和等于m的子序列。该方法简单粗暴，是一个穷举遍历的过程，但是题目中的m的取值可以达到109，如果在输入时，m就取109并且n也足够大，在测试时可以发现每计算出一个结果需要等待几秒钟，这说明该方法的时间复杂度较高。  
**思路2：**  
（1）求出和为m的子序列的最大长度，显而易见，当子序列的首项为1时，其长度最大，设其为length（当然有可能和为m且首项为1的子序列并不存在）。假设1+2+3+…+k=m，由等差数列求和公式可知(1+k)\*k/2=m，所以k<(2m)1/2，即最大长度不会超过(2m)1/2。  
（2）使用for循环，从最大长度开始依次查找和为m的子序列。**与思路1不同的是，在查找过程中不用求出每一个可能的子序列的和，而是通过等差数列求和公式直接反解出和为m的子序列的首项和尾项，这样节省了运算时间**。例如设某一子序列的首项为a，尾项为a+i-1，长度为i，由等差数列求和公式可知其和为sum=(2a+i-1)i/2，如果sum正好等于m，并且尾项a+i-1<=n，那么一定有a=(2m/i-i+1)/2，a+i-1=(2m/i-i+1)/2+i-1<=n，这样就得到了该子序列。经过测试发现，当m=109时，其运算速度较思路1有了很大的提升。

#include <stdio.h>
    #include <math.h>
    
    //思路1
    void SumProblem1(){
        
    	__int64 n,m,i,j,sum;
    	while(scanf("%I64d %I64d",&n,&m)!=EOF){
        
    		if(n==0 && m==0){
        
    			break;
    		}
    		if(n<1 || n>1000000000 || m<1 || m>1000000000){
        
    			printf("n和m的取值范围为[1,1000000000]之间的整数！\n");
    			continue;
    		}
    		for(i=1;i<=n;i++){
        
    			sum=0;
    			for(j=i;j<=n;j++){
        
    				sum+=j;
    				if(sum==m){
        
    					printf("[%I64d,%I64d]\n",i,j);
    				}
    				if(sum>m){
        
    					break;
    				}
    			}
    		}
    		printf("\n");
    	}
    }
    
    //思路2
    void SumProblem2(){
        
    	__int64 n,m,i,j,sum,length;
    	while(scanf("%I64d %I64d",&n,&m)!=EOF){
        
    		if(n==0 && m==0){
        
    			break;
    		}
    		if(n<1 || n>1000000000 || m<1 || m>1000000000){
        
    			printf("n和m的取值范围为[1,1000000000]之间的整数！\n");
    			continue;
    		}
    		//子序列从1开始时的长度最大 
    		length=(__int64)sqrt((double)m*2);
    		for(i=length;i>=1;i--){
        
    			if((2*m)%i==0){
        
    				if((2*m/i-i+1)%2==0 && (2*m/i-i+1)/2+i-1<=n){
        
    					//利用等差数列求和公式求解第一项和最后一项 
    					printf("[%I64d,%I64d]\n",(2*m/i-i+1)/2,(2*m/i-i+1)/2+i-1);
    				}		
    			}
    		}
    		printf("\n");
    	}
    }

## 2059.龟兔赛跑 ##

Problem Description
    据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后，心中郁闷，发誓要报
    仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定
    的速度(VR m/s)一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。
    最近正值HDU举办50周年校庆，社会各大名流齐聚下沙，兔子也趁此机会向乌龟发起挑战。虽然乌龟
    深知获胜希望不大，不过迫于舆论压力，只能接受挑战。
    比赛是设在一条笔直的道路上，长度为L米，规则很简单，谁先到达终点谁就算获胜。
    无奈乌龟自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有
    了不少积蓄。为了能够再赢兔子，乌龟不惜花下血本买了最先进的武器——“"小飞鸽"牌电动车。这辆
    车在有电的情况下能够以VT1 m/s的速度“飞驰”，可惜电池容量有限，每次充满电最多只能行驶C米
    的距离，以后就只能用脚来蹬了，乌龟用脚蹬时的速度为VT2 m/s。更过分的是，乌龟竟然在跑道上
    修建了很多很多（N个)的供电站，供自己给电动车充电。其中，每次充电需要花费T秒钟的时间。当
    然，乌龟经过一个充电站的时候可以选择去或不去充电。
    比赛马上开始了，兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序，判
    断乌龟用最佳的方案进军时，能不能赢了一直以恒定速度奔跑的兔子。
    Input
    本题目包含多组测试，请处理到文件结束。每个测试包括四行：
    第一行是一个整数L代表跑道的总长度
    第二行包含三个整数N，C，T，分别表示充电站的个数，电动车冲满电以后能行驶的距离以及每次充
    电所需要的时间
    第三行也是三个整数VR，VT1，VT2，分别表示兔子跑步的速度，乌龟开电动车的速度，乌龟脚蹬电
    动车的速度
    第四行包含了N(N<=100)个整数p1,p2...pn,分别表示各个充电站离跑道起点的距离，其中0<p1<p2<...<pn<L
    其中每个数都在32位整型范围之内。
    Output
    当乌龟有可能赢的时候输出一行 “What a pity rabbit!"。否则输出一行"Good job,rabbit!";
    题目数据保证不会出现乌龟和兔子同时到达的情况。
    Sample Input
    100
    3 20 5
    5 8 2
    10 40 60
    100
    3 60 5
    5 8 2
    10 40 60
    Sample Output
    Good job,rabbit!
    What a pity rabbit!

分析：本题属于一道动态规划(Dynamic Program)题。为了方便求解，可以先将起点和终点划分到N个充电站中，这样一共有N+2点。由动态规划算法的特点可知，经分解得到的子问题往往是不独立的，如果能够保存已解决的子问题的答案，在需要时再找出以求得的答案，可以避免大量的重复计算。所以可以用**dp\[i\]来表示乌龟从起点到第i个充电站的最小时间**，那么在求dp\[i\]的时候，dp\[0\]~dp\[i-1\]已经求出，让j从0遍历到i-1，算出乌龟从第j个充电站充完电一直到第i个充电站所用的时间(中途没有充过电)t(j,i)。那么**状态转移方程为dp\[i\]=min(dp\[j\]+t(j, i),dp\[i\])** , 最后以此为依据再编写代码即可。

#include <stdio.h>
    
    void Race(){
        
    	/*
    		L:赛道长度  
    		N:供电站个数 
    		C:电动车冲满电以后能行驶的距离  
    		T:电动车每次充电所需要的时间
    		VR:兔子跑步的速度
    		VT1:乌龟开电动车的速度
    		VT2:乌龟脚蹬电动车的速度
    	*/
    	int L,C,T,N,VR,VT1,VT2,i,j;
    	//dis[i]表示第i个充电站离跑道起点的距离 
    	int dis[102];
    	//dp[i]表示乌龟从起点到第i个充电站的最小时间
    	double dp[102];
    	//假设INF为本程序中的无穷大
    	const double INF=0xFFFFFFFF;
    	int length;
    	double time;
    	while(scanf("%d",&L)!=EOF) {
        
    		scanf("%d%d%d",&N,&C,&T);
    		scanf("%d%d%d",&VR,&VT1,&VT2);
    		if(N<=0 || N>100){
        
    			printf("充电站的个数的取值范围为[1,100]之间的整数！\n");
    			continue;
    		}
    		//输入各个充电站离道起点的距离
    		for(i=1;i<=N;i++){
        
    			scanf("%d",&dis[i]);
    		}
    		//将终点设为第N+1个充电站
    		dis[N+1]=L;
    		//将起点设为第0个充电站
    		dis[0]=0;
    		//起点到起点最小耗费时间为0
    		dp[0] =0;
    		for(i=1;i<=N+1;i++){
        
    			//由于目前到第i个充电站的最小耗费时间未知，所以暂时设置为无穷大 
    			dp[i]=INF;
    			for(j=0;j<i;j++){
        
    				//从第j个加电站到第i个加电站的距离
    				length=dis[i]-dis[j];
    				//如果该距离大于电动车冲满电后能行驶的最大距离
    				if(length>C){
        
    					//把电动车行驶的时间加上乌龟用脚踏的时间
    					time=C*1.0/VT1+(length-C)*1.0/VT2;
    				}else{
        
    					//直接加上这段距离除于电动车的速度所得的时间
    					time=length*1.0/VT1;
    				}
    				time+=dp[j];
    				if(j>0){
        
    					//j>0表示乌龟不是从起点出发，走完上述的路程后，电动车需要充电 
    					time+=T;
    				}
    				//修改乌龟到第i个充电站的最短时间
    				dp[i]=(dp[i]<time)?dp[i]:time;
    			}
    		}
    		//将兔子到达终点的时间与乌龟到达终点的时间进行比较 
    		if((L*1.0/VR)>dp[N+1]){
        
    			printf("What a pity rabbit!\n");
    		}else{
        
    			printf("Good job,rabbit!\n");
    		}
    	}
    }

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

[OJ_11_2060_2064_C]: https://blog.csdn.net/weixin_43004044/article/details/112646904