Jove's Blog

I love what I do

发表于 更新于

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

植物大战僵尸，这个题水的太离谱了！

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

int main()
{
	int t,m,n;
	cin>>t;
	while (t--)
	{
		cin>>m>>n;
		if(m>=n)
			cout<<"MMM BRAINS"<<endl;
		else
			cout<<"NO BRAINS"<<endl;
	}

}

发表于 更新于

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

简单的题虽然代码简单，但是思路不简单，这样的题适合初学者，比如我，哈哈

解释下思路，递归求解，dj函数返回，m苹果还剩n个空盘子的情况每当只有一个空盘子，或者没有苹果的之后情况唯一，当苹果少于盘子的时候，多于的盘子永远装不满，转换为m个苹果放m盘子的情况，一半情况就是m<n的情况，可以分两种情况，也就是m-n个苹果还剩n个空盘子，和m个苹果，省n-1个空盘子的状况！

代码如下

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

int dj(int m,int n)
{
	if(m==0||n==1)
		return 1;
	if(m<n)
		return dj(m,m);
	else
		return dj(m-n,n)+dj(m,n-1);
}

int main()
{
	int t,m,n;
	cin>>t;
	while (t--)
	{
		cin>>m>>n;
		cout<<dj(m,n)<<endl;
	}

}

发表于 更新于

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

水题，输出一组数中，又两杯关系的数对的个数。没什么好说的！

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

int main()
{
	//freopen("input.txt", "r", stdin);
	int d[20],i,j,k,count;
	while(cin>>d[0]&&d;[0]!=-1)
	{
		count=0;
		for(i=1;1;i++)
		{
			cin>>d[i];
			if(d[i]==0)
				break;
		}
		sort(d,d+i);
		for(j=0;j<i;j++)
			for(k=j+1;k<i;k++)
				if(2*d[j]==d[k])
				{
					count++;
					break;
				}
		cout<<count<<endl;
	}
}

发表于 更新于

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

题意不难，就是将两个数逆序排列，相加，再逆序输出，比如123和456，就应该是321+654=975，那么输出579.

其实这题用字符串的操作函数会方便很多atoi函数，但是自己动手编写简单的函数，还有又用的，我们来看看atoi函数：

1
2
3
4
5
6
7
8
//int atoi(const char *nptr);
char a[5]="1234";
printf("%d",atoi(a)+1);
//输出1235




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

void swap(char* str)
{
	char temp[100];
	int i,len;
	len=strlen(str);
	strcpy(temp,str);
	for(i=0;i<len;i++)
		*(str+i)=temp[len-1-i];
}

int main()
{
	char str1[100],str2[100];
	int num1,num2,num3,num4,len1,len2,t,i;
	cin>>t;
	while(t--)
	{
		cin>>str1>>str2;
		swap(str1);
		swap(str2);
		len1=strlen(str1);
		len2=strlen(str2);
		num1=0;
		num2=0;
		num4=0;
		for(i=0;i<len1;i++)
			num1=10*num1+str1[i]-'0';
		for(i=0;i<len2;i++)
			num2=10*num2+str2[i]-'0';
		num3=num1+num2;
		while(num3!=0)
		{
			num4=10*num4+num3%10;
			num3/=10;
		}
		cout<<num4<<endl;
	}
}

发表于 更新于

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

又一个LCS的题，不过这个题范围扩大到了这个字符串，和他的逆向字符串。

讲下思路，先输入字符串找出最短的一个，依次枚举每一种长度，以及这种长度下，每一种子串是否符合所有字符串，若有则输出，没有则最后输出0，其中逆向字符串花了我好多时间，不知道怎么表示，最后用另一个字符串拷贝过来的，

这个题我又学会了一个函数

1
2
3
4
const char * strstr ( const char * str1, const char * str2 );
      char * strstr (       char * str1, const char * str2 );


题目不难，要细心，还有什么i,j,k的关系一定要搞清楚，我先开始就是数据弄混了

代码如下：

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

int main()
{
	char d[105][105]，min[105],str1[105],str2[105];
	int t,n,i,j,k,len,flag;
	cin>>t;
	while(t--)
	{
		len=200;
		flag=0;
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>d[i];
			if((int)strlen(d[i])<len)
			{
				len=strlen(d[i]);
				strcpy(min,d[i]);
			}
		}
		for(i=len;i>=1&&flag;==0;i--)
		{
			for(j=0;j<=len-i&&flag;==0;j++)
			{
				for(k=0;k<i;k++)
				{
					str1[k]=min[j+k];
					str2[i-k-1]=min[j+k];
				}
				str1[i]='\00';
				str2[i]='\00';
				for(k=0;k<n;k++)
					if(strstr(d[k],str1)==NULL&&strstr;(d[k],str2)==NULL)
						break;
				if(k==n)
				{
					cout<<i<<endl;
					flag=1;
				}
			}
		}
		if(flag==0)
			cout<<0<<endl;
	}
}

发表于 更新于

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

一个简单的历法转换，一种是365天20个月，一种是260天13个月，先计算出由第一天开始的天数，再进行转换，不难，注意月份的字符串就是了！

代码如下：

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

int main()
{
	char hm[19][10]={
		"pop","no","zip","zotz","tzec","xul",
		"yoxkin","mol","chen","yax","zac",
		"ceh","mac","kankin","muan","pax",
		"koyab","cumhu","uayet"
	};
	char tm[20][10]={
		"imix","ik","akbal","kan","chicchan",
		"cimi","manik","lamat","muluk","ok",
		"chuen","eb","ben","ix","mem",
		"cib","caban","eznab","canac","ahau"
	};
	int i,t,n,y,d;
	char m[10];
	scanf("%d",&t;);
	printf("%dn",t);
	while(t--)
	{
		scanf("%d. %s %d",&d;,m,&y;);
		for(i=0;i<19;i++)
			if(strcmp(m,hm[i])==0)
				break;
		n=365*y+20*i+d;
		printf("%d %s %dn",n%260%13+1,tm[n%20],n/260);
	}
}

发表于 更新于

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

解释下题意，通过字母的移位进行加密，但是加密的算法不知道，问是否破解。

比如加密算法是A==>E C==>B
那么加密AAACC就成为EEEBB，虽然这样的加密算法我们不知道，但是要能破解，那么字母的数量是不便的，比如这个例子中，一共；两种字母数量分别是2 3，那么就能完成一一对应的关系。从而完成加密过程，我们将每个字母的数量记录下然后排序，看是否满足，数量相同。

代码如下：

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: 2159		User: awq123
Memory: 200K		Time: 47MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int a[26],b[26],len1,len2,i;
	char str1[105],str2[105];
	cin>>str1>>str2;
	len1=strlen(str1);
	len2=strlen(str2);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for(i=0;i<len1;i++)
		a[str1[i]-65]++;
	for(i=0;i<len2;i++)
		b[str2[i]-65]++;
	sort(a,a+26);
	sort(b,b+26);
	for(i=0;i<26;i++)
		if(a[i]!=b[i])
		{
			cout<<"NO"<<endl;
			return 0;
		}
	cout<<"YES"<<endl;
}

发表于 更新于

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

简单排序题，要求我们根据逆序对的数量进行升序排序排序！

解释下逆序对，我也是刚接触这么个概念的，比如一列数3 4 2 5 1 那么在后面的数比前面小就是一组，32 42 51 31 41 21 51 ，

通过结构体来整体排序会简单点，不过要自己编写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
/***************************************
Problem: 1007		User: awq123
Memory: 244K		Time: 16MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct dna
{
	int n;
	char ch[55];
}DNA;

int cmp(DNA a,DNA b)
{
	return a.n<b.n;
}

int main()
{
	DNA d[105];
	int i,j,k,n,m;
	cin>>n>>m;
	for(i=0;i<m;i++)
	{
		cin>>d[i].ch;
		d[i].n=0;
		for(j=0;j<n;j++)
			for(k=j+1;k<n;k++)
				if(d[i].ch[j]>d[i].ch[k])
					d[i].n++;
	}
	sort(d,d+m,cmp);
	for(i=0;i<m;i++)
		cout<<d[i].ch<<endl;
}

发表于 更新于

今天真的很高兴，完成了几个不错的题，下午忙了一下午的主题修改，汉化，本来这些应该是前几天就应该完成的，可是家里宽带除了点问题下午才好，嘿嘿，说实话在网上收集一个自己喜欢的主题，还要修改到与自己的插件，模板完全适合，还是很累的，估计近段时间也不会更换主题了。

看看日历，今天还真是个吉利的日子，汉化其实是一个很要耐心的事情，对着模板一点点调试，一点点修改，然后查看，花了我不少时间，单是那个搜索框就花了我不少时间，不过还是很开心，这个简洁的主题蛮好看的，以前也试过一些比较绚丽的主题，但是考虑到，自己要写一些代码，不方便显示，也就没多花心思。

程序员的生活不难，但很充实！

发表于 更新于

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

DP初学者的好题，题意也简单，找2维数组，最长降序数列。

DP解题的经典问题，利用记忆搜索，也是我们平常的递归运算。

讲一下思路，递归4方向搜索，求最大的数，我利用的一个方向数组来完成四个方向的！

其中，两个问题拦住了我的AC，

第一个先开始，纯利用递归，导致重复计算量过大，TLE了，我们观察下其实每个点开始的最长降序数列的长度都是固定的，我们利用dp数组储存每个点的信息，可以避免重复计算，

第二个是，我在dfs函数中先开始，判断的条件是

1
2
3
if(map[m][n]>0)


1
2
3
4
if(m>=1&&m;<=c&&n;>=1&&n;<=r)



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

int r,c,map[105][105],dp[105][105],step[8]={1,0,0,1,-1,0,0,-1};

int dfs(int x,int y)
{
	if(dp[x][y]!=0)
		return dp[x][y];
	int max=1,temp;
	for(int i=0;i<8;i+=2)
	{
		int m=x+step[i],n=y+step[i+1];
		if(m>=1&&m;<=c&&n;>=1&&n;<=r)
			if(map[m][n]<map[x][y])
			{
				temp=dfs(m,n)+1;
				if(temp>max)
					max=temp;
			}
	}
	return max;
}

int main()
{
	int i,j,max=1;
	memset(map,0,sizeof(map));
	memset(dp,0,sizeof(dp));
	cin>>r>>c;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
			cin>>map[j][i];
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
		{
			dp[j][i]=dfs(j,i);
			if(dp[j][i]>max)
				max=dp[j][i];
		}
	cout<<max<<endl;
}