致我们的程序路

          算法这条路,真的很漫长,让我们大家都受益匪浅。我们计算机专业虽然不是每个方向都需求算法,但是思想肯定应用到各个领域的每个角落。近期忙着各种事情,学习各种新东西,我想人的一生中就是这样不断学习,接触新东西的过程吧。。。 在此我对广大给我留言的朋友说声抱歉,因为没能及时回复大家的问题。 我想以后我会改的了, 要拿出一些时间出来跟大家分享知识, 向大家学习。 最近在学 UNIX 网络编程, 所以我在这里重新还开个模块,记录UNIX网络编程的点点滴滴,当然算法我还是不会放弃的,要不断温故 学习,总结。 2013年, 你准备好了吗?  如果有比较好的算法,请联系我,我帮大家总结 刊登出来放在上面供广大同学学习。

HDU (1895 Sum Zero 比较技巧型的模拟+hash)

题目大意:给你5组数,让你求A[0][i]+A[1][j]+A[2][k]+A[3][l]+A[4][m]=0的组数

题目分析:如果直接暴力枚举的话,唉,肯定超时,5重循环想都不用想了,我们看看这题的思路吧,我也是参考大牛的思路的,这里的优化很高效,大家注意分析哦{^_^};首先我们把5行中的4行 两两进行相加合成二行,然后我们这里只有3组数据,然后对数据进行稍微处理一下,首先把其中的两行进行排序,头两行进行从大到小的排序,最后一行从小到大排序,然后我们遍历第一行,作为外循环,然后从第二行的第一个开始(每次遍历都从第二行的第一个开始的),把tempt下标停到第三行足够大的位置上,也就是满足前面两个加上该位置的值大于等于0,因为前面两行数据都是递减排列的,前面不满足后面肯定不满足,所以下次讨论的时候只需要从tempt位置开始讨论,这样节约了很多不必要的时间。以后的讨论都从上次的tempt的位置开始,因为前面与第三个加起来小于0,我遍历下去的值肯定也是小于0,所以只需要从tempt开始。

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 302
using namespace std;
int B[N*N],s[3][N*N],A[5][N*N],cnt[5][N*N],num[5];
int get(int n,int k,int C[]){
	int i,j;
	for(i=0;i<=n;i++)
		cnt[k][i]=0;
	j=0;
	s[k][0]=C[0];
	cnt[k][0]=1;
	for(i=1;i<n;i++){
		if(s[k][j]!=C[i])
			s[k][++j]=C[i];
		cnt[k][j]++;//这个是记录各个情况的次数的
	}
	num[k]=j+1;
	return 0;
}
int cmp(int a,int b){
	return a>b;
}
int main(){
	int cas,n,i,j,tempt,pos,ans,k;
	int xx;
	scanf("%d",&cas);
	while(cas--){
		ans=0;
		for(j=0;j<=4;j++){
			scanf("%d",&n);
			num[j]=n;
			for(i=0;i<n;i++)
				scanf("%d",&A[j][i]);
		}
		sort(A[0],A[0]+num[0],cmp);
		get(num[0],0,A[0]);
		k=0;
		for(i=0;i<num[1];i++)
	 		for(j=0;j<num[2];j++)
				B[k++]=A[1][i]+A[2][j];
		num[1]=k;
		sort(B,B+num[1],cmp);
                //注意第三行是从小到大哦!
		get(num[1],1,B);
		k=0;
		for(i=0;i<num[3];i++)
			for(j=0;j<num[4];j++)
				B[k++]=A[3][i]+A[4][j];
		num[3]=k;
		sort(B,B+num[3]);
		get(num[3],2,B);
		tempt=0;
		for(i=0;i<num[0];i++){
			xx=s[0][i]+s[1][0];
			while(tempt<num[2]&&xx+s[2][tempt]<0)
				tempt++;
			if(tempt==num[2])
                    //这里说明没有任何一种情况的和是大于等于0的
                    //所以没必要讨论了 还是那句话,因为前两行   
                     //是从大到小排列的,前面的情况的和小于0后
                      //面就不用考虑了	
				break;
			if(xx+s[2][tempt]==0)
				ans+=cnt[0][i]*cnt[1][0]*cnt[2][tempt];
			pos=tempt;
			for(j=1;j<num[1];j++){
				xx=s[0][i]+s[1][j];
				while(pos<num[2]&&xx+s[2][pos]<0)
					pos++;
				if(pos==num[2])
						break;
				if(xx+s[2][pos]==0)
					ans+=cnt[0][i]*cnt[1][j]*cnt[2][pos];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

 

POJ (2739 Sum of Consecutive Prime Numbers)

题目分析:直接枚举就可以了 二重循环!

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[10000],k;
bool flag[10001];
int get_pri(){
	int i;
	memset(flag,true,sizeof(flag));
	pri[1]=2;
	k=1;
	for(i=4;i<=10000;i+=2)
		flag[i]=false;
	for(i=3;i<=10000;i+=2)
		if(flag[i]){
			pri[++k]=i;
			for(int j=i*2;j<=10000;j+=i)
				flag[j]=false;
		}
	return 0;
}
int main(){
	int i,j;
	int n,ans,sum;
	get_pri();
	while(scanf("%d",&n),n){
		ans=0;
		int x=n/2;
		for(i=1;pri[i]<=x;i++){
			sum=0;
			for(j=i;j<=x;j++){
				sum+=pri[j];
				if(sum==n){
					ans++;
					break;
				}
				if(sum>n)
					break;
			}
		}
		if(flag[n])
			ans++;
		printf("%d\n",ans);
	}
	return 0;
}

 

HDU 1568(非常经典微妙的 斐波纳契计算)

Problem Description
2007年到来了。经过2006年一年的修炼,数学神童zouyu终于把0到100000000的Fibonacci数列
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。
接下来,CodeStar决定要考考他,于是每问他一个数字,他就要把答案说出来,不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了,可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。
 

Input
输入若干数字n(0 <= n <= 100000000),每个数字一行。读到文件尾。
 

Output
输出f[n]的前4个数字(若不足4个数字,就全部输出)。
 

Sample Input
0
1
2
3
4
5
35
36
37
38
39
40
 
Sample Output
0
1
1
2
3
5
9227
1493
2415
3908
6324
1023

题目分析:这个题目非常精美!首先题目要求求第N个斐波纳契数的前四位,前提是他不止四位哦!

然后引用到的知识点,斐波纳契的计算公式:(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)

还有对数log()的作用,先让我们回忆一下log 的运算性质吧~

1)log(a*b)=log(a)+log(b); 2)log(a/b)=log(a)-log(b);

其实在数学里面,log可以求一个大数的科学计数法的数值部分,比如说123456

首先log10(1234567)=log(1.234567*10^6)=log(1.234567)+6; 然后log10(1.234567)就是log10(1234567)的小数位

然后10^log10(1.234567)=1.234567,所以通过这样的转换 我们可以很巧妙的得到了一个很大的数的科学计数法的表示值!

然后您要取4位就拿4位!要多少位就拿多少位!

既然这样可以我们就干下去吧!

斐波纳契的计算公式:(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)

log10((1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n])

化简一下得到:

-0.5*log10(5.0)+((double)n)*log(f)/log(10.0)+log10(1-((1-√5)/(1+√5))^n)其中f=(sqrt(5.0)+1.0)/2.0;

在这里  log10(1-((1-√5)/(1+√5))^n)无穷小可以忽略不计!

最后得到 log10(an)=-0.5*log10(5.0)+((double)n)*log(f)/log(10.0)   !

然后就是直接贴代码了

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int s[21]={0,1,1,2};
const double f=((double)sqrt(5)+1)/2.0;
void get_Fibonacci(int x){
	if(x<=20)
		printf("%d\n",s[x]);
	else{
		double ans=(-0.5)*log(5.0)/log(10.0)+(double(x))*log(f)/log(10.0);
		ans=ans-floor(ans);
		double k=pow(10.0,ans);
		//cout<<"k= "<<k<<endl;
		while(k<1000.0)
			k*=10.0;
		printf("%d\n",(int)k);
	}
	
}
int main(){
	int x,i;
	for(i=3;i<=20;i++)
		s[i]=s[i-1]+s[i-2];
      //在这里为了区别其他多于4位的答案我先把4位以内的
     //都计算好存起来!
	while(~scanf("%d",&x)){
		if(x==0){
			printf("0\n");
			continue;	
		}
		get_Fibonacci(x);
	}
	return 0;
}

 

HDU 1717(小数化分数2 --非常犀利)

题目大意:

Problem Description
Ray 在数学课上听老师说,任何小数都能表示成分数的形式,他开始了化了起来,很快他就完成了,但他又想到一个问题,如何把一个循环小数化成分数呢?
请你写一个程序不但可以将普通小数化成最简分数,也可以把循环小数化成最简分数。
 
Input
第一行是一个整数N,表示有多少组数据。
每组数据只有一个纯小数,也就是整数部分为0。小数的位数不超过9位,循环部分用()括起来。
 
Output
对每一个对应的小数化成最简分数后输出,占一行。
 
Sample Input
3
0.(4)
0.5
0.32(692307)
 
Sample Output
4/9
1/2
17/52

题目大意分析:这个思路非常精妙,刚开始的时候我推到一半,差点就出来了,但是还是没自信以为这样是错的,后来看完各位神牛的思路,果断肯定了 。这个题目的解题思路非常值得学习!

首先跟你一个小数 令X= 0 . s1 s2 ..sn ( y1 y2 y3..ym ) 这样的话我们把小数点分为三个部分,分别用三种颜色标记了!

我们可以把表达式转换成:X * 10 ^n=s1s2..sn+0.y1y2..ym;    我们用S1替换 s1s2..sn ,Y替换 0.(y1y2..yn), 然后可以把表达式写成: X * 10^n=S1 + Y;  然后 Y=0.(y1y2..ym) 变形一下:Y * 10 ^m=y1y2..ym + Y; 在这里我们另y1y2..ym等于S2;

宗上所述:我们得到两个表达式 X * 10^n=S1 +  Y;    Y * 10^m=S2 + Y; 然后将两个式子合并成一个用表达式,

$$\frac{s2 + (10^m-1)*s1}{10^n * ( 10^m -1 )}$$然后就可以根据这个公式,求出分子分母的 最大公约式 然后化简 就可以了{^_^}

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int gcd(int x,int y){
	int c;
	if(x<y){
		c=y;	y=x;
		x=c;
	}
	if(y==0)
		return x;
	return gcd(y,x%y);
}
int main(){
	char ch[25];
	int cas,i,p1,k1,p2,k2;
	int t1,t2,len;
	scanf("%d",&cas);
	while(cas--){
		scanf("%s",ch);
		len=strlen(ch);
		//cout<<"len = "<<len<<endl;
		i=0;	
		while(ch[i]!='.')
			i++;
		p1=0;	k1=1;
		while((ch[++i]!='(')&&(i<len)){
			p1=p1*10+ch[i]-'0';
			k1*=10;
		}
		//cout<<"p1 = "<<p1<<"k1 = "<<k1<<endl;
		p2=0;	k2=1;
		while(ch[++i]!=')'&&i<len){
			p2=p2*10+ch[i]-'0';
			k2*=10;
		}
		//cout<<"p2 = "<<p2<<"k2 = "<<k2<<endl;
		if(p2){
			t1=p1*(k2-1)+p2;
			t2=(k2-1)*k1;
		}
		else{
			t1=p1;
			t2=k1;
		}
		int w=gcd(t1,t2);
		printf("%d/%d\n",t1/w,t2/w);
	}
	return 0;
}

 

HDU 1271(整数对 经典!)

题目大意:

Problem Description
             Gardon和小希玩了一个游戏,Gardon随便想了一个数A(首位不能为0),把它去掉一个 数字以后得到另外一个数B,他把A和B的和N告诉了小希,让小希猜想他原来想的数字。不过为了公平起见,如果小希回答的数虽然不是A,但同样能达到那个条 件(去掉其中的一个数字得到B,A和B之和是N),一样算小希胜利。而且小希如果能答出多个符合条件的数字,就可以得到额外的糖果。
所以现在小希希望你编写一个程序,来帮助她找到尽可能多的解。
例如,Gardon想的是A=31,B=3 告诉小希N=34,
小希除了回答31以外还可以回答27(27+7=34)所以小希可以因此而得到一个额外的糖果。
 

Input
输入包含多组数据,每组数据一行,包含一个数N(1<=N<=10^9),文件以0结尾。
 
Output

对于每个输入的N,输出所有符合要求的解(按照大小顺序排列)如果没有这样的解,输出"No solution."

题目分析:第一次,我的思路是从一半开始枚举,发现这样超时了

TLE代码:

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int s[1000];
inline int solve(int x){
	int k,ans,i,j;
	int c,sum,t,times=1;
	while(c){
			c/=10;
			k++;
		}
	int xx=pow(10,k-2);
	for(i=xx;i<=x;i++){
		k=0;	c=i;
		while(c){
			c/=10;
			k++;
		}
		for(j=1;j<=k;j++){
			c=i;
			sum=0;
			int w=(int)pow(10,k-j);
			if(j==1){
				sum=c%w;
			}
			if(j==k){
				sum=c/10;
			}
			if(j!=k&&j!=1){
				t=c%w;
				int p=c/w;
				p/=10;
				p=p*((int)pow(10,k-j));
				sum=p+t;
			}
			if(sum+i==x){
				s[times++]=i;
			}
		}
	}
	return times-1;
}
int main(){
	int x,t,i;
	while(scanf("%d",&x),x){
		t=solve(x);
		if(t==0)
			printf("No solution.\n");
		else{
			for(i=1;i<=t;i++)
				printf("%d ",s[i]);
			printf("\n");
		}
	}
	return 0;
}

后来看了一下解题报告,后来终于理解了,现在让我来说说这题的做法跟规律吧{^_^}

首先假设X的第k位拿走,然后加上加上X的和正好等于N!

这样的话 我们可以把X 分解成:X= a+b * 10^k +c * 10^( k+1 );  这里特别强调一下, a代表的是比第k位后面的低位数子,可能是多位,b仅仅代表一个数值,即你选择拿开的那位数,c代表的是比k位高的高位数字,例如:12345 您想拿走3的话 这时候a=45,c=12,b=3;   然后拿走之后就会组合成另一个数:Y=a + c * 10^k; 然后X+Y=2 * a + b * 10 ^k +11 * c * 10^k;

现在如果N=X+Y;他必定满足上面那种结构!所以我们考虑这种结构特征就可以了,首先上述表达式的低位是2*a 可能发生进位!

所以b的值可能是10,但是 都不影响c的值, 这个时候只需要分两种不同的b的情况,来求出a,然后验证一下 是不是等于N就可以了!

AC代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
void solve(int x,set<int> &result){
	int k,high,b2,a;
	int c,sum,b1;
	for(k=1;k<=x;k*=10){
		high=x/k;
		c=high/11;
		c*=k;
		b1=high%11;
		if((b1!=0||c!=0)&&b1<10){
			b1*=k;
			a=(x-b1-11*c)/2;
			if(2*a+b1+11*c==x)
				result.insert(a+b1+c*10);	
		}
		b2=high%11-1;
		if((b2!=0||c!=0)&&b2>=0){
			b2*=k;
			int a2=(x-b2-11*c)/2;
			if(x==2*a2+b2+11*c)
				result.insert(a2+b2+10*c);
		}
	}
}
int main(){
	int x,i;
	while(cin>>x,x){
		set<int>result;
            //set结构不仅可以排序,而且可以去除重复的
            //下次要多多学习,总结!
		solve(x,result);
		if(result.empty()){
			printf("No solution.\n");
		}
		else{
			set<int>::iterator it=result.begin();
			printf("%d",*it);
			while(++it!=result.end())
				printf(" %d",*it);
			printf("\n");
		}
	}
	return 0;
}

还有一种代码思路一样

AC代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int s[1000],times;
int cmp(int x,int y){
	return x<y;
}
int solve(int x){
	int k,high,b2,a;
	int c,sum,b1;
	times=0;
	for(k=1;k<=x;k*=10){
		high=x/k;
		c=high/11;
		c*=k;
		b1=high%11;
		if((b1!=0||c!=0)&&b1<10){
			b1*=k;
			a=(x-b1-11*c)/2;
			if(2*a+b1+11*c==x)
				s[++times]=a+b1+c*10;	
		}
		b2=high%11-1;
		if((b2!=0||c!=0)&&b2>=0){
			b2*=k;
			a=(x-b2-11*c)/2;
			if(x==2*a+b2+11*c)
				s[++times]=a+b2+10*c;
		}
	}
	return 0;
}
int main(){
	int x,t,i;
	while(scanf("%d",&x)&&x){
		solve(x);
		if(times==0){
			printf("No solution.\n");
		}
		else{
			sort(s+1,s+1+times,cmp);
			printf("%d",s[1]);
			 for(i=2;i<=times;i++){
    				if(s[i]!=s[i-1])
   				printf(" %d",s[i]);
   			}
			printf("\n");
		}
	}
	return 0;
}

题目总结:今后一定要大量深入学校STL函数!还有这题的去除重复不能忘记,同时要深刻认识本题的思路,太巧妙,强大了

HDU 1215(七夕节)

题目大意:您的编号N的因子和就是您的另一半的编号!数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).

题目分析:其实是水题!一开始想复杂了,后来想想看,我们只要找i :1->sqrt(N)然后用通过N/i 找到比sqrt(N)大的满足要求的因子!

这样最坏情况下也才500000*3000最多!还是不会超时的

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int solve(int x){
	int i,j,sum=0;
	double tempt=sqrt(x);
	for(i=2;i<=tempt;i++){
		if(x%i==0){
			sum+=i;
			int t=x/i;
			if(t!=i){
				sum+=t;	
                          //是在里面判断比sqrt(N)大的因子合法与否!
			}
		}
	}
	sum+=1;
	return sum;
}
int main(){
	int cas,t,ans;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&t);
		ans=solve(t);
		printf("%d\n",ans);
	}
	return 0;
}

 

HDU 2504(又见GCD)

题目:

有三个正整数a,b,c(0<a,b,c<10^6),其中c不等于b。若a和c的最大公约数为b,现已知a和b,求满足条件的最小的c。

刚刚开始的时候写错了,没考虑太多,直接a/b如果不等于1 就a/b-1然后乘以b!

其实枚举就行了:

#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int x,int y){
	int c;
	if(x<y){
		c=y;
		y=x%y;
		x=c;
	}
	while(y){
		c=y;
		y=x%y;
		x=c;
	}
	return x;
}
int main(){
	int a,b,c,flag,cas;
	cin>>cas;
	while(cas--){
		scanf("%d %d",&a,&b);
		for(int i=2;;i++){
			if(gcd(a,i*b)==b){
				flag=i;
				break;
			}
		}
		printf("%d\n",flag*b);
	}
	return 0;
}

总结:唉,汗颜!下次细心!UP!

HDU 1722(分蛋糕 规律性题目)

一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食.

题目分析:p+q-gcd(p+q)

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int a,int b){
	int c;
	if(a<b){
		c=a;	a=b;
		b=c;
	}
	while(b){
		c=b;
		b=a%b;
		a=c;
	}
	return a;
}
int main(){
	int x,y;
	while(~scanf("%d %d",&x,&y)){
		printf("%d\n",x+y-gcd(x,y));
	}
	return 0;
}

 

猴子分桃(很有趣的规律题)

题目大意:老猴子辛苦了一辈子,给那群小猴子们留下了一笔巨大的财富——一大堆桃子。
老猴子决定把这些桃子分给小猴子。
第一个猴子来了,它把桃子分成五堆,五堆一样多,但还多出一个。它把剩下的一个留给老猴子,自己拿走其中的一堆。
第二个猴子来了,它把桃子分成五堆,五堆一样多,但又多出一个。它把多出的一个留给老猴子,自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有n只小猴子,请你写个程序计算一下在开始时至少有多少个桃子,以及最后老猴子最少能得到几个桃子。

题目分析:其实题目不是很难,但是我很悲剧的是,因为学校服务器的问题,害我WA了20多次,后来都别的网站上提交,1Y就过了!

这里表示非常不淡定。。。

废话不说了让我们看题目吧:假设有X个桃子,第一次把X个桃子分成5份,恰好多了1,然后拿走一份!再这里,您应该想到借他4个不就正好5份了麽?然后每次都不是5份了麽?最后当前猴子拿走的也没多拿不是麽?举个例子说明一下吧,假设有5只猴子,第一次每份

(X-1)/5;如果我们借给他4个,每份不就是(X+4)/5吗?然后您会发现,(X+1)/5=(X-1)/5+1;每次都是如此,然后每次都能被5整除,这很显然,所以您应该懂了吧~{^_^}X=5^n-4  老猴子得到=n+(X+4)*(4/5)^n-4(您得还我的呀!对吧 嘿嘿)

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int main(){
	long long total_num,old_num;
	int n;
	while(cin>>n,n){
		total_num=pow(5,n)-4;
		old_num = n + (total_num+4)*(pow(0.8,n))-4;
		cout<<total_num<<" "<<old_num<<endl;
	}
	return 0;
}