Jove's Blog

I love what I do

发表于 更新于

题目链接：http://poj.org/problem?id=1775

不难，解释下题意 判断一个数是否能写为多个阶乘的和

先打表，计算出0-9的阶乘，然后深搜每一个数的组合，其中回溯的方式表示成了||这样搜索不算效率，也能AC！

不过有一点，我没注意，就是0的情况，害我WA了半天，加上个排除就好了！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*Problem: 1775		User: awq123
**Memory: 216K		Time: 500MS
**Language: C++		Result: Accepted
*/
#include <IOSTREAM>
using namespace std;

int num[10]={1,1,2,6,24,120,720,5040,40320,362880};

int dfs(int n,int i)
{
	if(n==0)
		return 1;
	if(n<0)
		return 0;
	if(i>9)
		return 0;
	return dfs(n-num[i],i+1)||dfs(n,i+1);
}

int main()
{
	int n;
	while(cin>>n&&n;>=0)
	{
		if(n==0)
			cout<<"NO"<<endl;
		else if(dfs(n,0))
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}

}

发表于 更新于

题目链接：http://poj.org/problem?id=2521

水题，计算一系列交易后，因假币损失的钱，理清思路后不难，本来应该赚的是m-n，然后亏的钱就是那个假币，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*Problem: 2521		User: awq123
**Memory: 224K		Time: 32MS
**Language: C++		Result: Accepted
*/
#include <IOSTREAM>
using namespace std;

int main()
{
	int n,m,p,c;
	while(cin>>n>>m>>p>>c&&n;+m+p+c)
	{
		cout<<p-(m-n)<<endl;
	}

}

发表于 更新于

题目链接：http://poj.org/problem?id=2365

题目比较简单给出每个点的坐标，以及每个钉子的半径，求一圈连线的长度，我们知道连线的距离就是没两个点之间的距离相加在加上一个钉子的周长，

不过自己比较傻，先开始r定义成了int，然后一直WA,

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <IOSTREAM>
#include <CMATH>
using namespace std;
#define PI 3.1415926

double dis(double x1,double x2,double y1, double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
	int i,n;
	double x[110],y[110],r,sum=0;
	cin>>n>>r;
	cin>>x[0]>>y[0];
	for (i=1;i<n;i++)
	{
		cin>>x[i]>>y[i];
		sum+=dis(x[i],x[i-1],y[i],y[i-1]);
	}
	sum+=dis(x[n-1],x[0],y[n-1],y[0]);
	sum+=2*PI*r;
	printf("%.2lfn",sum);
}

发表于 更新于

最近开始阅读这本书，《算法艺术与信息学竞赛》，让我觉得耳目一新，跟其他ACM书不同的是，里面没有任何一题的程序代码，全部是思路讲解，刚学习了贪心，把搁了好久的POJ1042搞懂了，代码算是写出来了，其实ACM学习了这么久，不难，要的是耐心！

发表于 更新于

题目链接：http://poj.org/problem?id=1042

这题是《算法艺术与信息学竞赛》p13的例题，也算是我学习贪心法的入门把，

解释下题意，有n个湖，给出钓鱼时间，每个湖的钓鱼量，以及每个湖钓一次后的钓鱼量的减少量，一个从第一个湖开始每两个之间的行走时间，我们以第一个例子来看，

2
1
10 1
2 5
2

意思是（一次就是5分钟）

有2个湖
钓鱼1小时
每次钓鱼量分别是10，1
掉一次后下次的钓鱼量减少2，5
从第一个湖到第二个湖要2次的时间

利用贪心的做法解题，假设在i出停止钓鱼，我们事先把行走的时间减去，就可以认为他在湖之间的移动是瞬间的，然后每次取钓鱼量最大的湖掉一次，直到时间钓完，没有鱼就在第一个点蹲着！

写这个题没有点麻烦，一开始没想到有这么多数组，到用的时候才定义，名字有点乱，一开始超时，后来加了一个符号解决了：

while(th>0) //原来是(th)

代码如下，有简单的注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*Problem: 1042		User: awq123
**Memory: 164K		Time: 47MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int max,time[26],i,j,f[26],fb[26],d[26],t[26],n,h;
	while(scanf("%d",&n;)&&n;)
	{
		memset(time,0,sizeof(time));
		max=-1;
		//依次输入数据
		scanf("%d",&h;);
		h*=60;
		for(i=1;i<=n;i++)
			scanf("%d",&fb;[i]);
		for(i=1;i<=n;i++)
			scanf("%d",&d;[i]);
		t[1]=0;
		//这里我们记录的是一共走的时间
		for(i=2;i<=n;i++)
		{
			int temp;
			scanf("%d",&temp;);
			t[i]=t[i-1]+temp;
		}
		//分别计算在每个湖停止的最好情况
		for(i=1;i<=n;i++)
		{
			memcpy(f,fb,(i+1)*sizeof(f[0]));
			int sum=0;
			//减去走的时间
			int th=h-t[i]*5;
			int temp[26];
			memset(temp,0,sizeof(temp));
			//直到把时间取完
			while(th>0)
			{
				int maxn=0,maxi=1;
				//选取最大的一个湖
				for(j=1;j<=i;j++)
					if(f[j]>maxn)
					{
						maxn=f[j];
						maxi=j;
					}
				//运算数据
				temp[maxi]+=5;
				sum+=maxn;
				f[maxi]-=d[maxi];
				th-=5;
			}
			//比较是否为最好情况
			if(sum>max)
			{
				max=sum;
				memcpy(time,temp,(i+1)*sizeof(f[0]));
			}
		}
		//输出
		for(i=1;i<n;i++)
			printf("%d, ",time[i]);
		printf("%dn",time[n]);
		printf("Number of fish expected: %dnn",max);
	}
}

发表于 更新于

今天上C++课时突然想起了昨天做的一个POJ的题，利用map来模拟字典查询，如果利用c语言编写数组储存，然后二分查找，其实时间可以少点，但是代码会长很多，也算偷懒。至少当时是这样想的！

但是今天上课突然想起了看过的一片文章，大意有一句是这样的，既然别人已经在你要解决的问题上给出了解决办法，为什么不去用呢，然后把时间花在没解决的问题上。

的确，我在学习了STL后就没用过别的什么冒泡排序什么的了，POJ我希望能够锻炼下思路，而不是一味的CODE，这样一个想法通了，我觉得明朗很多，创新本来就是个学习的过程，为什么要浪费时间做别人做过的事，就像有人在提倡国人编写自己的操作系统来应对windows，其实我觉得作用不大，在计算机行业，中国发展仅仅是晚了点，而不思缺乏人才，在别的方面都能做的很好，虽然QQ是被人骂的东西，但是他确实是个不错的软件，仅仅是这个软件我，不是附加服务！！

所以嘛，编自己的代码，让别人说去把！

发表于 更新于

题目链接：http://poj.org/problem?id=1088

解释下题意，给出进制b的两个数p，m问满足p=a*m+k的最小正k值，其实我们变换下就是k=p%m

我的开始的思路就是利用字符串模拟取余的过程，没参考什么算法，写得很笨拙，完全无法模拟高精度的取余

贴下我的超时代码，可能还有问题！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	freopen("Input.txt", "r", stdin);
	int i,j,b,lenp,lenm;
	char p[1005],m[1005];
	while (scanf("%d",&b;)&&b;)
	{
		scanf("%s %s",p,m);
		lenp=strlen(p);
		lenm=strlen(m);
		for(i=0;i<lenp/2;i++)
		{
			char temp;
			temp=p[i];
			p[i]=p[lenp-i-1];
			p[lenp-i-1]=temp;
		}
		for(i=0;i<lenm/2;i++)
		{
			char temp;
			temp=m[i];
			m[i]=m[lenm-i-1];
			m[lenm-i-1]=temp;
		}
		while (lenp>=lenm)
		{
			for(i=0;i<lenm;i++)
			{
				j=i;
				if(p[lenp-lenm+i]<m[i])
				{
					p[lenp-lenm+i+1]--;
					while (p[lenp-lenm+j+1]<'0')
					{
						p[lenp-lenm+j+2]--;
						p[lenp-lenm+j+1]+=b;
						j++;
					}
					p[lenp-lenm+i]+=b;
				}
				p[lenp-lenm+i]-=m[i]-'0';
			}
			while (p[lenp-1]=='0')
			{
				lenp--;
			}
			p[lenp]='\00';
		}
		for(i=lenp-1;i>=0;i--)
			printf("%c",p[i]);
		printf("n");
	}
}



代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*Problem: 2305		User: awq123
**Memory: 232K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int i,j,b,lenp,lenm;
	long int pa,mb;
	char p[1005],m[1005];
	while (scanf("%d",&b;)&&b;)
	{
		scanf("%s %s",p,m);
		lenp=strlen(p);
		lenm=strlen(m);
		pa=0;
		mb=0;
		for(i=0;i<lenm;i++)
		{
			mb*=b;
			mb+=m[i]-'0';
		}
		for(i=0;i<lenp;i++)
		{
			pa*=b;
			pa+=p[i]-'0';
			if(pa>=mb)
				pa=pa%mb;
		}
		if(pa==0)
		{
			cout<<0<<endl;
			continue;
		}
		else
		{
			i=0;
			while(pa!=0)
			{
				p[i++]=pa%b+'0';
				pa/=b;
			}
			p[i]='\00';
			lenp=strlen(p);
			for(i=lenp-1;i>=0;i--)
				cout<<p[i];
			cout<<endl;
		}
	}
}

发表于 更新于

题目链接：http://poj.org/problem?id=2503

题目给出大量的字典数据，然后在一空行后开始查询，要是用c语言就麻烦点，我偷了点懒，用STL的map做的，对于这样的一一对应的关系map还是很好用的，只是听说，在时间上会长点

思路就不解释了，上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*Problem: 2503		User: awq123
**Memory: 10516K		Time: 1125MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;


int main()
{
	map <string,string>mymap;
	string line;
	while (getline(cin,line))
	{
		if(line.length()==0)
			break;
		string a="",b="";
		bool flag=0;
		for(unsigned int i=0;i<line.length();i++)
		{
			if(line[i]==' ')
				flag=1;
			else
			{
				if(flag)
					b+=line[i];
				else
					a+=line[i];
			}
		}
		mymap[b]=a;
	}
	while(cin>>line)
	{
		if(mymap[line].length())
			cout<<mymap[line]<<endl;
		else
			cout<<"eh"<<endl;
	}

}

发表于 更新于

题目链接：http://poj.org/problem?id=1079

最长上升子串，利用动态规划解题。

对于给定数列E，元素个数为n,最长上升子序列Q满足对任意1<=i<j<=n，有Q[i]<Q[j]，且E[i]<E[j]。
容易得出O(n^2)的DP递推公式：
D[i]=max{D[j]}+1;(1<=j<i且E[j]<E[i])
D[i]为以元素i结尾的最长子序列个数。
这样经过两重循环一次遍历可以得到最长上升子序列。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*Problem: 2533		User: awq123
**Memory: 268K		Time: 32MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int i,j,t,d[1005],dp[1005];
	cin>>t;
	int max=-1;
	for(i=1;i<=t;i++)
	{
		cin>>d[i];
		dp[i]=1;
		for(j=1;j<i;j++)
		{
			if(d[j]<d[i]&&dp;[i]<dp[j]+1)
				dp[i]=dp[j]+1;
		}
		if(max<dp[i])
			max=dp[i];
	}
	cout<<max<<endl;
}

发表于 更新于

题目链接：http://poj.org/problem?id=3077

解释下题意，要求我们由个位开始在前面有一位的情况下进行四舍五入。

简单模拟四舍五入的运算，但是要注意就是第一位为9时会被动的多一位！废话不多说看代码

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*Problem: 3077		User: awq123
**Memory: 1228K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	char d[1000000];
	int i,t;
	cin>>t;
	while(t--)
	{
		cin>>d;
		int len=strlen(d);
		if(len>1)
		{
			for(i=len-1;i>=1;i--)
			{
				if(d[i]>'4')
					d[i-1]++;
				d[i]='0';
			}
		}
		if(d[0]=='9'+1)
		{
			d[0]='0';
			cout<<'1';
		}
		cout<<d<<endl;
	}
}