Jove's Blog

I love what I do

发表于 更新于

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

看似简单的题目，把我WA到哭啊，强烈推介这个题目，我自己做的是后总超时。

其中如何优化自己的算法是最重要的，这也是为什么OJ系统都有时间限制的原因，

我的算法是这样的：

比如题目中的1 2 3 4 5

我们可以看见每两个之间的距离，也就是就是这个数与其他数的差，所以就想到了相加的算法，现开始因为数据类型错误还WA了几次就不说了。

最原始的代码是：

1
2
3
4
5
6
for(i=0;i<m;i++)
	for(j=0;j<m;j++)
		if(i!=j)
			s+=(num[i]>=num[j])?(num[i]-num[j]):(num[j]-num[i]);
cout<<s<<endl;

超时没商量，我了个去哦，后来想到对于一个序列的排序，都会有重复状况，优化算法排除其中相互成对的情况，优化代码如下：

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
for(i=0;i<m;i++)
	for(j=i+1;j<m;j++)
		s+=(num[i]>=num[j])?(num[i]-num[j]):(num[j]-num[i]);
cout<<2*s<<endl;


```最后代码如下：

```cpp
/*Problem: 2231		User: awq123
**Memory: 296K		Time: 563MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
	int m,i,j,num[10002];
	long long int s=0;
	cin>>m;
	for(i=0;i<m;i++)
		scanf("%d",&num;[i]);
	for(i=0;i<m;i++)
		for(j=i+1;j<m;j++)
			s+=abs(num[i]-num[j]);
	cout<<2*s<<endl;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	long long int m,i,s=0,num[10002];
	cin>>m;
	for(i=0;i<m;i++)
		cin>>num[i];
	sort(num,num+m);
	for(i=0;i<m-1;i++)
		s += (m-1-i) * (num[m-1-i] - num[i]);
	cout<<s*2<<endl;
}

发表于 更新于

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

一个看似复杂的题目，其实算法都已经给出，要求你求出i到j之间最大循环次数，水题，最近做的水题还真是多，没办法东西还是要一点点的学，这个题目不难但是有个小细节需要掌握，就是输入i j 时若i>j那么要从j开始算，现开始我完成代码也不知道什么问题，后来看了解题报告才知道的！！

代码如下：

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
/*Problem: 1207		User: awq123
**Memory: 252K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
	int a,b,i,j,m,key,t,max;
	while(cin>>a>>b)
	{
	
		i=a;j=b;
		if(i>j)
		{
			t=i;i=j;j=t;
		}
		max=0;
		for(m=i;m<=j;m++)
		{
			t=1;
			key=m;
			while(key!=1)
			{
				if(key%2)
					key=3*key+1;
				else
					key=key/2;
				t++;;
			}
			if(t>max)
				max=t;
		}
		cout<<a<<" "<<b<<" "<<max<<endl;
	}
}

发表于 更新于

一个半成品，

花了我一下午，但是还是有点小问题，累了，睡觉去的，改天继续。

问题就是搜索顺序不对，我是按顺序搜索的，他是排完序搜索的，结果无问题，在G++下编译，

懒得解释题目了，郁闷

代码如下：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> 
using namespace std;

typedef struct node
{
	char c[7];
	char y[7];
	int n;
}NODE;

/*int cmp(const void *a,const void *b)
{
    return strcmp( (*(node *)a)->str , (*(node *)b)->str );
}*/

int main()
{
	//freopen("input.txt", "r", stdin);
	NODE node[101];
	string str;
	int t=0,i,j,temp,flag;
	while(cin>>str&&str;!="XXXXXX")
	{
		node[t].n= str.length();
		for(i=0;i<node[t].n;i++)
		{
			node[t].y[i]=str[i];
			node[t].c[i]=str[i];
		}
		sort(&node;[t].c[0],&node;[t].c[str.length()]);
		t++;
	}
	//qsort(node,t,sizeof(node[0]),cmp);
	while(cin>>str&&str;!="XXXXXX")
	{
		flag=0;
		sort(&str;[0],&str;[str.length()]);
		for(i=0;i<t;i++)
		{
			if(int(str.length())==node[i].n)
			{
				temp=1;
				for(j=0;j<node[i].n;j++)
				{
					if(node[i].c[j]!=str[j])
					{
						temp=0;
						break;
					}
				}	
				if(temp==1)
				{
					cout<<node[i].y<<endl;
					flag=1;
				}
			}
		}
		if(flag==0)
			cout<<"NOT A VALID WORD"<<endl;
		cout<<"******"<<endl;
	
	}
}

发表于 更新于

慢慢养成每天做点ACM的题目，每天学习点算法的习惯，慢慢习惯写解题报告，记录自己的收获，学习是一个长久的过程，要在其中得到快乐。

假期在家本来想学习下CCNA的基础的，看来现在时间都给了ACM。

的确，自己编写代码，自己修改，自己调试，然后自己排错，最后AC的感觉真的不错，学习计算机，喜欢的就是那份自在，那份成就感把。

争取，假期内能突破1w名把，前面好多人慢慢追把。

不知道为什么习惯一个人编写程序，晚上爸妈回来了就去玩，也许是一个人静些把。

高兴的是，主机的速度开始正常点了，不像前端时间，连ping都丢包，虽然仍然是个没人访问的小站，但是相信一定会有的，我所做的就是在充实内容，让亲爱的google注意到我。

发表于 更新于

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

题意给出许多点，每个点代表一个猴子，猴王就是没有横坐标和纵坐标都大于他的猴子，问有几个猴王？

这个题目的算法已经给我们了，就是在一个点位原点的坐标系内，第一象限没有点，不包括坐标轴。

思路是这样的，利用结构体构造点阵，先对结构题中的x排序，对于每个相同的x，取最大的y，这样排除了靠里面不可能的点，然后由x最大的那个点开始，往前扫描,如果出现某个猴子的y大于当前最大y时，代表其满足条件，那么计数更新，再由这个点开始，向前找，依次求出，因为永远会有最大值，所以至少有一个，计数的初值为1，在本机上错过一次因为没注意结尾的0，多输出了个1。

代码不算复杂，但是完成这个题第一次AC用了922ms，主要是因为这个题需要大量的输入，那么c++的类输入会造成很大的浪费，修改为c语言普通输入输出，结果219ms，还算不错

代码如下：

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
/*Problem: 1828		User: awq123
**Memory: 556K		Time: 219MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct point
{
int x,y;
}p[50001];

int cmp(const void *a,const void *b)
{
	if(((point *)a)->x==((point *)b)->x)
		return ((point *)a)->y>((point*)b)->y ?1:-1;
	else
		return ((point *)a)->x>((point *)b)->x ?1:-1;
}

int main()
{
	int t,i,max,temp;
	while(scanf("%d",&t;)&&t;)
	{
		for(i=0;i<t;i++)
			scanf("%d%d",&p;[i].x,&p;[i].y);
		qsort(p, t, sizeof(p[0]), cmp);
		max=1;
		temp=p[t-1].y;
	for(i=t-2;i>=0;i--)
	{
	    if(temp<p[i].y)
	    {
	        temp=p[i].y;
	        max++;
	    }
	}
	printf("%dn",max);

	}
}

发表于 更新于

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

这个题要求根据他给出的坐标组成的多边形求边长，不过这个幸好没有斜边，所有的都是横边与竖边，这样画出一个简单的坐标系，先求出全部的横边，再求出所有的竖边，利用qsort语句给结构体排序，先按x排求相邻两个相同的y的x差值加进s中，同理求出相邻两个相同的x的y差值，这样和就是总边长了。
其中两个比较的cmp函数写的很不错在这学习了！！

代码如下

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
/*Problem: 1788		User: awq123
**Memory: 256K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct point
{
	int x,y;
}p[100001];

int cmp1(const void *a,const void *b)
{
	if(((point *)a)->x==((point *)b)->x)
		return ((point *)a)->y>((point*)b)->y ?1:-1;
	else
		return ((point *)a)->x>((point *)b)->x ?1:-1;
}
int cmp2(const void *a,const void *b)
{
	if(((point *)a)->y==((point *)b)->y)
		return ((point *)a)->x>((point*)b)->x ?1:-1;
	else
		return ((point *)a)->y>((point *)b)->y ?1:-1;
}

int main()
{
	int n,i,s;
	while(cin>>n&&n;)
	{
		for(i=0;i<n;i++)
			cin>>p[i].x>>p[i].y;
		s=0;
		qsort(p,n,sizeof(p[0]),cmp1);
		for(i=0;i<n-1;)
		{
			if(p[i].x==p[i+1].x)
			{
				s+=abs(p[i].y-p[i+1].y);
				i=i+2;
			}
			else
				i++;
		}
		qsort(p,n,sizeof(p[0]),cmp2);
		for(i=0;i<n-1;)
		{
			if(p[i].y==p[i+1].y)
			{
				s+=abs(p[i].x-p[i+1].x);
				i=i+2;
			}
			else
				i++;
		}
		cout<<"The length of the fence will be "<<s<<" units.n";
	}
}

发表于 更新于

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

题目给出很多士兵的坐标，求把这些士兵移动到一条线上的最小步数，这年头没google翻译还是很难看懂题目，那些ACM大神一定英语很好，其实把，我的提升空间还是很大的，嘻嘻！！

其中利用了的sort函数大大节约了排序的时间！

解释下算法，转换成y坐标相同的排序，分开x和y坐标处理。

对y坐标排序之后就可以轻松求出中位数，进而计算出移动步数。

麻烦一点的是x坐标。首先我们对输入的点按照x坐标递增排序。排序后所有点的相对位置和最终要求的排列的相对位置是一致的。 如果排序后点p在q左边，而最终的排列q在p左边，那么可以通过交换两者的位置，一个步数增加，一个步数减少，总和是不变的。

我们现在的任务是，找出一个标准点，让所有点从这条左边线开始依次排列。由于排序后的点相对位置和最终是一致的，我们按照排序后的下标依次x[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
/*Problem: 1723		User: awq123
**Memory: 332K		Time: 94MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int main()
{
	int n,x[10001],y[10001];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>x[i]>>y[i];
	sort(x,x+n);
	sort(y,y+n);
	for (int i=0;i<n;i++)
		x[i]-=i;
	sort(x,x+n);
	int m =0;
	for (int i=0;i<n/2;i++)
		m+=x[n-1-i]-x[i]+y[n-1-i]-y[i];
	cout<<m<<endl;
}

发表于 更新于

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

这个题就是求1<=m<=10^7的阶乘的位数

现开始自己用的老方法试了下，结果很容易想象，超时，搜索了网上的解体报告，对比了好多，找到了个最好的方法就是利用log函数巧妙的求位数，其中的原理还有点不明白，慢慢研究，数学不好的孩子伤不起啊！！

代码如下，很简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*Problem: 1423		User: awq123
**Memory: 260K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int main()
{
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
	cout<<(int)(log10(sqrt(2*3.1415926*n))+n*(log10(1.*n)-log10(exp(1.))))+1<<endl;
	}

}

发表于 更新于

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

题意是先输入4个数，前两个分别代表输入矩阵的行和列，后两个数是起始点的坐标，然后输入字符矩阵，来判断与坐标点八方向相连的点组成的图形的边长。

看到个说是用DFS但是我看了下算法，与DFS还是有区别的，我用map来记录字符数组，用mapnum数组来记录是否访问过，dir数组来实现8方向扫描，具体搜索算法，见注释把，应该看的懂，呵，尤其是何时增加计数的判断条件，有点麻烦。

代码如下

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
/*Problem: 1111		User: awq123
**Memory: 256K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

char map[21][21];
int mapnum[21][21];
int dir[16]={1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1,0,1};
int r,c,a,b,sum;
void search(int a,int b)
{
	int x,y;
	mapnum[a][b]=1;
	for(int i=0;i<16;i+=2)
	{
	x=a+dir[i];
	y=b+dir[i+1];
	if(x>=1&&x;<=r&&y;>=1&&y;<=c)//扫描点不越界
		{
			if(map[x][y]=='X'&&mapnum;[x][y]==0)//未被搜索
				search(x,y);
			else if(map[x][y]=='.'&&(x==a||y==b))//在上下左右方向 计数+1
				sum++;
		}
		else if(x==a||y==b)//在上下左右方向越界的话 计数+1
			sum++;
	}
}
int main()
{
	int x,y;
	while(cin>>r>>c>>x>>y&&r;)
	{
		memset(mapnum,0,sizeof(mapnum));
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
				cin>>map[i][j];
		sum=0;
		search(x,y);
		cout<<sum<<endl;
	}
}

发表于 更新于

时间过的很快，已经过去一年了，去年的今天一个傻傻的女孩被我骗了，呵，真的很怀念，他给我了许多快乐，欢笑，让我知道了什么是关系，什么是合拍，什么是默契，但是残酷的大学拦住了我们，虽然不能怪别人，只能说我们之间的感情不够深厚把，但是我不会忘记她的，至少她仍然是我见过女孩中最好的。

去年的这个早上她，走进了我得身旁，带给我了不一样的快乐，不再是玩闹能代替的，呵 ，我仍然记得我们的第一个拉手，第一个拥抱，第一个吻，我感谢她对我的毫无保留，我会永远记得有过这么段感情，

将来的事将来再说，有缘的话，自然会相聚。

爱你 小K