2016-08-30

ACM 1002-1007

1HDOJ-ACM 1002-1007解答及思路

1002

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

要求2个不超过1000位的大数（整形）相加允许进行1-20次的相加操作

C++参考AC代码

#include <stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
	int T,len1,len2,p;
	cin>>T;
	for(int q=0;q<T;q++)
	{
		char s1[1000],s2[1000];
		int num1[1000]={0},num2[1000]={0};
		cin>>s1>>s2;
		if((s1[0]=='0')&&(s2[0]=='0'))
		{
			cout<<"Case "<<q+1<<":"<<endl<<"0 + 0 = 0"<<endl;
			if(q!=T-1)
				cout<<endl;
		}
		else
		{
			len1=strlen(s1);
			len2=strlen(s2);
			for(int i=len1-1,j=0;i>=0;i--)
				num1[j++]=s1[i]-'0';
			for(int i=len2-1,j=0;i>=0;i--)
				num2[j++]=s2[i]-'0';
			for(int i=0;i<1000;i++)
			{
				num1[i]+=num2[i];
				if(num1[i]>9)
				{
					num1[i]-=10;
					num1[i+1]++;
				}
			}
			cout<<"Case "<<q+1<<":"<<endl;
			cout<<s1<<" + "<<s2<<" = ";
			for(p=999;(p>=0)&&(num1[p]==0);p--);
			for(;p>=0;p--)
				cout<<num1[p];
			cout<<endl;
			if(q!=T-1)
				cout<<endl;
		}
	}
	return 0;
}

思路

输入2个大数分别存放在s1和s2两个字符数组中，再分别定义2个足够大的整型数组num1和num2并且把所有元素初始化为0，把s1和s2中的字符转变成整数倒序存在在
num1和num2中，然后进行对应位数相加，如果大于10的话，自减10并且后一位加1，结果存放在num1中，接着用一个带分号的for循环从最后一位开始判断，如果位数
大于0并且数组对应位数的值为0的话，位置下标自减1，直到对应的数字不是0为止开始输出，把数据再正向输出出来
，就是所要的结果。

注意事项

以上方法没有考虑到0+0=0的情况，需要额外考虑，并且注意输出格式，Case的C要大写而且要注意输出时的空格，最后一行不需要换行，要用for循环判断是否为最
后一行。

1003

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

要求输入一串数字后找出其中和最大的子串并且输出最大值以及这一串的起始和终止位置

C++参考AC代码

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int T,N,a[100000],begin,end,position,sum,max;
	cin>>T;
	for(int j=0;j<T;j++)
	{
		cin>>N;
		for(int i=0;i<N;i++)
			cin>>a[i];
		begin=end=position=0;
		sum=max=a[0];
		for(int i=1;i<N;i++)
		{
			if(sum+a[i]<a[i])
			{
				sum=a[i];
				position=i;
			}
			else
				sum+=a[i];
			if(sum>max)
			{
				max=sum;
				begin=position;
				end=i;
			}
		}
		cout<<"Case "<<j+1<<":"<<endl<<max<<" "<<begin+1<<" "<<end+1<<endl;
		if(j!=T-1)
			cout<<endl;
	}
	return 0;
}

思路

从第一个数据开始循环，第一个if语句判断最大子序列的起始位置，如果前n项的和小于第n+1项的话，起始位置移到第n+1项，sum变为n+1项的数值，如果前n项和大于
等于n+1项，那么sun加上第n+1项的竖直，第二个if语言判断目前的sum是否大于最大值max，如果大于，sum的值赋给max，把起始位置赋给begin，末尾位置t赋给end，
依次循环到数据末端结束，输出结果。

注意事项

注意输出格式，如何找对起始位置于末尾位置以及判断是否为序列的最大值是关键。

1004

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

找出字符串中出现次数最多的子字符串

C++参考AC代码

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
	int N,max,flag;
	char a[1050][20];
	cin>>N;
	while(N!=0)
	{
		int sum[1050]={0};
		for(int i=0;i<N;i++)
			cin>>a[i];
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
			{
				if(strcmp(a[i],a[j])==0)
					sum[i]++;
			}
		max=sum[0];
		flag=0;
		for(int i=0;i<N-1;i++)
		{
			if(max<sum[i+1])
			{
				max=sum[i+1];
				flag=i+1;
			}
		}
		cout<<a[flag]<<endl;
		cin>>N;
	}
	return 0;
}

思路

用数组sum存贮每个字符串出现的次数，接着求出sum中最大元素的位置并输出该位置的字符串

注意事项

二维数组输入输出可以使用首地址，数组sum的初始化为0要在while循环里进行。

1005

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

类似于斐波拉契数列，已知f（1）=f（2）=1，f（n）=(A×f(A,B,n-1)+B×f(A,B,n-2))%7，求f（n）

C++参考AC代码(一)

#include<stdio.h>
#include<iostream>
using namespace std;
int f(int A,int B,int n)
{
	if((n==1)||(n==2))
		return 1;
	else
		return (A*f(A,B,n-1)+B*f(A,B,n-2))%7;
}
int main()
{
	int A,B,n;
	cin>>A>>B>>n;
	while(!((A==0)&&(B==0)&&(n==0)))
	{
		cout<<f(A,B,n%48)<<endl;
		cin>>A>>B>>n;
	}
	return 0;
}

C++参考AC代码(二)

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int i,n,A,B;
	int f[50],num;
	while(cin>>A>>B>>n && (A || B || n))
	{
		f[1] = 1;
		f[2] = 1;
		for(i=3; i<=49; i++)
		{
			f[i] = (A * f[i-1] + B * f[i-2]) % 7;
			if(f[i] == f[i-1] && f[i] == 1)
				break;
		}
		num = i-2;
		n = n % num;
		if(n==0)
			cout<<f[num]<<endl;
		else
			cout<<f[n]<<endl;
	}
	return 0;
}

思路

　　AC代码（1）：参考斐波拉契数列，但由于直接使用递归调用会提示超出内存，所以必须找到对应的周期。(A×f(A,B,n-1)+B×f(A,B,n-2))%7=((A×f(A,B,n-1))%7+
（B×f(A,B,n-2))%7)%7，由于取除以7的余数，所以有0，1，2，3，4，5，6七种情况，一共有7×7=49种情况，由于极端状况第49个数字会回到开头的第一个数字，所
以48为一个周期，n%48即可以把n转换到第一个周期内，大大减少了运算量。
　　AC代码（2）：直接算出最小周期，如果f[i] == f[i-1] && f[i] == 1，即到了一个周期，由于多算了2步得到数字1，1才判断为一个周期，所以真实的周期是i-2，到了
周期处使用break跳出循环进一步减少了计算量，由于余数是0的情况会输出最后一项而不是第一项，所以需要额外考虑。

注意事项

不可能直接用n使用递归调用，会超出内存，如果不使用周期可能也会超时，所以这题必须算出周期或者最小周期，来减少运算量。

1006

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

在一天的24小时内，求出三个指针两两至少相差D度的概率

参考AC代码

#include<stdio.h>
double max(double a,double b,double c)
{
	return a>b?(a>c?a:c):(b>c?b:c);
}
double min(double a,double b,double c)
{
	return a<b?(a<c?a:c):(b<c?b:c);
}
int main()
{
	double d,sum;
	double Tsm=3600./59,Tsh=43200./719,Tmh=43200./11;
	double happys,happye;
	double sm=10./59,sh=120./719,mh=120./11;
	double d_sm,d_sh,d_mh,not_d_sm,not_d_sh,not_d_mh;
	while(scanf("%lf",&d)!=EOF&&(d!=-1))
	{
		sum=0;
		d_sm=sm*d; not_d_sm=Tsm-d_sm;
		d_sh=sh*d; not_d_sh=Tsh-d_sh;
		d_mh=mh*d; not_d_mh=Tmh-d_mh;
		happys=max(d_sm,d_sh,d_mh);
		happye=min(not_d_sm,not_d_sh,not_d_mh);
		while((happys<=43200)&&(happye<=43200))
		{
			happys=max(d_sm,d_sh,d_mh);
			happye=min(not_d_sm,not_d_sh,not_d_mh);
			if(happys<happye)
				sum+=happye-happys;
			if(happye==not_d_sm)
			{d_sm+=Tsm;not_d_sm+=Tsm;}
			else if(happye==not_d_sh)
			{d_sh+=Tsh;not_d_sh+=Tsh;}
			else if(happye==not_d_mh)
			{d_mh+=Tmh;not_d_mh+=Tmh;}
		}
		printf("%.3lf\n",sum/43200*100);
	}
	return 0;
}

思路

秒针的速度s=6°/s,分针是m=1/10°/s,时针是h=1/120°/s;
相对速度s_m=59/10°/s,s_h=719/120°/s,m_h=120/11°/s;
所以相差一度所需要的时间sm=10/59 s/°,sh=120/719 s/°,mh=120/11 s/°;
差360°的周期为Tsm=3600/59 s,Tsh=43200/719 s,Tmh=43200/11 s;
假设开始时从12点整开始，旋转至再均回到12点（即时针转一圈）
两两之间最后一个满足相差d°及以上的条件视为开始happy时刻
两两之间第一个不再满足相差d°及以上视为结束happy的时刻

注意事项

注意输出格式，以及两两相遇的周期，在写代码前先理清思路。

1007

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

参考AC代码

#include<bits/stdc++.h>
using namespace std;  
const int SIZE = 100005;  
const int L = -1;  
const int R = 1;   
typedef struct{
	int index;                  
	double x,y;  
}coord;                          
coord num[SIZE], c[SIZE];        
double getDistance(coord &bi1, coord &bi2){
	return sqrt(pow(bi1.x - bi2.x, 2.0) + pow(bi1.y - bi2.y, 2.0));  
}   
bool cmpx(coord &bi1, coord &bi2){
	if(bi1.x == bi1.x) return bi1.y < bi2.y;  
	else return bi1.x < bi2.x;  
}   
bool cmpy(coord &bi1, coord &bi2){  
	if (bi1.y == bi2.y)  return bi1.x < bi2.x;  
	else  return bi1.y < bi2.y;  
}  
inline double min(double &bi1, double &bi2, double &bi3){
	double minLength;  
	minLength = bi1 > bi2 ? bi2 : bi1;  
	minLength = minLength > bi3 ? bi3 : minLength;  
	return minLength;  
}  
inline double minDist(double &bi1, double &bi2){  
	if(bi1 > bi2) return bi2;  
	return bi1;  
}  
double divide_conquer(int low, int high){
	double dis;  
	int count = high - low;  
	if(count == 0) return 0;  
	else if (count == 1) dis = getDistance(num[low], num[high]);  
	else if (count == 2){  
		double temp1, temp2, temp3;  
		temp1 = getDistance(num[low], num[low + 1]);  
		temp2 = getDistance(num[low + 1], num[high]);  
		temp3 = getDistance(num[low], num[high]);  
		dis = min(temp1, temp2, temp3);  
	}  
	else{
		double leftmin,rightmin,min;  
		int mid = (low + high) / 2;  
		int p = 0;  
		int i, j;  
		leftmin = divide_conquer(low, mid);       
		rightmin = divide_conquer(mid + 1, high); 
		dis = minDist(leftmin, rightmin);  
		for (i = low; i <= mid; i++){  
			double leftCoord = num[mid].x - dis;  
			if (num[i].x >= leftCoord){  
				c[p].index = L;            
				c[p].x = num[i].x;  
				c[p].y = num[i].y;  
				p++;  
			}  
		}  
		for ( ; i <= high; i++){
			double rightCoord = num[mid].x + dis;  
			if (num[i].x <= rightCoord){  
				c[p].index = R;             
				c[p].x = num[i].x;  
				c[p].y = num[i].y;  
				p++;  
			}  
		}  
		sort(c, c + p, cmpy);               
		for (i = 0; i < p; i++){
			for (j = 1; (j <= 7) && (i + j < p); j++){     
				if (c[i].index != c[i + j].index){  
					min = getDistance(c[i], c[i + j]);  
					if(min < dis)  
					dis = min;  
				}  
			}  
		}  
	}  
	return dis;  
}  
int main (){
	int n;  
	while (cin >> n && n != 0){  
		double result = 0;    
		for (int i = 0; i < n; i++){  
			num[i].index = 0;  
			cin >> num[i].x >> num[i].y;  
		}  
		sort (num, num + n, cmpx);  
		result = divide_conquer(0, n - 1);  
		printf("%.2lf\n", result / 2);  
	}   
	return 0;  
}

思路

　　根据水平方向的坐标把平面上的N个点分成两部分Left和Right。我们希望这两个部分点数的个数差不多。假设分别求出了Left和Right两个部分距离最近的点对的最短距离
为MinDist（Left）和MinDist（Right），还有一种情况我们没有考虑，那就是点对中一个点来自Left部分，另一个点来自Right部分。最直接的想法，那就是穷举Left和
Right两个部分之间的点对，这样的点对很多，最多可能有N×N/4对。显然，穷举所有Left和Right之间的点对是不好的做法。是否可以只考虑有可能成为最近点对的候选点对
呢？由于我们已经知道Left和Right两个部分中的最近点对距离分别为MinDist（Left）和MinDist（Right），如果Left和Right之间的点对距离超过MDist=MinValue
（MinDist（Left），MinDist（Right）），我们则对它们并不感兴趣，因为这些点对不可能是最近点对。

　　如图2-10所示，通过直接x=M将所有的点分成xM两部分，在分别求出两部分的最近点对之后，只需要考虑点对CD。因为其他点对AD，BD，CE，CF，CG等都不可能成
为最近点对。也就是说，只要考虑从x=M-Mdist到x=M+MDist之间这个带状区域内的最小点对，然后再跟MDist比较就可以了。在计算带状区域的最小点对时，可以按Y坐
标，对带状区域内的顶点进行排序。如果一个点对的距离小于MDist，那么它们一定在一个MDist×（2×Mdist）的区域内（如图2-11所示)

　　而在左右两个Mdist*Mdist正方形区域内。最多都只能含有4个点。如果超过4个点，则这个正方形区域内至少存在一个点对的距离小于Mdist，这根xM两个部分的最近
点对距离分别是MinDist（Left）和MinDist（Right）矛盾。

　　因此，一个MDist×（2×Mdist）的区域内最多有8个点（如图2-12所示）。对于任意一个带状区域内的顶点，只要考虑它与按Y坐标排序且紧接着的7个点之间的距离就可
以了。

注意事项

sort函数的第三个参数需要自己另写cmpx和cmpy函数。以上代码在杭电上只能在C++环境中通过编译，在G++环境中编译会超时。此题在杭电上AC的代码中部分都没有考
虑全面，该方法考虑了全部情况。

本文标题:ACM 1002-1007

文章作者:Hippopmonkey

发布时间:2016-08-30, 19:22:19

最后更新:2018-04-10, 23:31:11

原始链接:http://xuboming8.github.io/2016/08/30/ACM-1002-1007/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。