Jove's Blog

I love what I do

发表于 更新于

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

题意简化为，每人输入长，宽，高，名字，根据每个的体积，输出最大的和最小的名字！

利用结构体储存数据，然后排序输出，不难。我看到有童鞋用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
/*Problem: 1547		User: awq123
**Memory: 244K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct node
{
	int a,b,c,s;
	char name[10];
}d[10];

int cmp(node n1,node n2)
{
	return n1.s<n2.s;
}

int main()
{
	int t,i;
	while(cin>>t&&t;!=-1)
	{
		for(i=0;i<t;i++)
		{
			cin>>d[i].a>>d[i].b>>d[i].c>>d[i].name;
			d[i].s=d[i].a*d[i].b*d[i].c;
		}
		sort(d,d+t,cmp);
		cout<<d[t-1].name<<" took clay from "<<d[0].name<<"."<<endl;
	}


}

发表于 更新于

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

解释下题意，S顺时针走E逆时针走，每走过一个点，加上这个数，问在哪相遇可以使两个和相同，输出两个的位置，否则输出不行！

简单模拟题，根据题意，模拟每个点相遇的情况比较每次的和！

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

int main()
{
	int i,j,n,d[35],sume,sums;
	while(cin>>n&&n;)
	{
		for (i=0;i<n;i++)
			cin>>d[i];
		for (i=0;i<n;i++)
		{
			sume=0;
			sums=0;
			for(j=0;j<i;j++)
				sums+=d[j];
			for(j=i;j<n;j++)
				sume+=d[j];
			if(sume==sums)
				break;
		}
		if(sume==sums)
			cout<<"Sam stops at position "<<i<<" and Ella stops at position "<<i+1<<"."<<endl;
		else
			cout<<"No equal partitioning."<<endl;
	}
}

发表于 更新于

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

水题，要我们求给出本金m，y年后按，r计算后的本息和。注意数据大小！

代码如下：

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

int main()
{
	double r,m,y;
	scanf("%lf%lf%lf",&r;,&m;,&y;);
	for(int i=0;i<y;i++)
		m*=(100+r)/100;
	printf("%.0lf",m-0.5);
}

发表于 更新于

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

简单解释下题意，包括@在内，与其连通的.有多少个！

简单DFS，每次标记一个点已经使用，再四方向深搜，每发现一个，计数t++，这样最后t+1，就是答案，因为@算一个所以要加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
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
/***************************************
Problem: 1979		User: awq123
Memory: 256K		Time: 47MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char d[25][25];
int h,w,t,used[25][25],dir[8]={0,1,1,0,0,-1,-1,0};

bool check(int m,int n)
{
	if(m>=0&&m;<h&&n;>=0&&n;<w)
		return true;
	return false;
}

void dfs(int y,int x)
{
	for(int i=0;i<8;i+=2)
	{
		int m=y+dir[i];
		int n=x+dir[i+1];
		if(used[m][n]==0&&check;(m,n))
		{
			t++;
			used[m][n]=1;
			dfs(m,n);
		}
	}
	return;
}
int main()
{
	int startx,starty;
	while(cin>>w>>h&&w;+h)
	{
		t=0;
		memset(used,0,sizeof(used));
		for(int i=0;i<h;i++)
			for(int j=0;j<w;j++)
			{
				cin>>d[i][j];
				if(d[i][j]=='@')
				{
					startx=j;
					starty=i;
				}
				if(d[i][j]=='#')
					used[i][j]=1;
			}
			used[starty][startx]=1;
		dfs(starty,startx);
		cout<<t+1<<endl;
	}
}

发表于 更新于

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

题目问是否能在字符串t中去掉一些字母组成字符串s，一个简单的题目，用指针轻松解决，可是WA了3次才发现我输出的yesno是小写，郁闷了半天

代码如下：

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

int main()
{
	char s[100005],t[100005];
	while(cin>>s>>t)
	{
		int ok=0;
		char *ps=s,*pt=t;
		while(1)
		{
			if(*ps=='\00')
			{
				ok=1;
				break;
			}
			if(*pt=='\00')
				break;
			if(*ps==*pt)
				ps++;
			pt++;
		}
		if(ok)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
}

发表于 更新于

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

题目要求我们判断它给出的长度的木棍是否能组成一个正方形。

题目其实类似1011，要说难度，其实没有那个难，因为已经固定了一共四条木棍，但是这题的数据比那题复杂，如果剪枝不好的话，就会TLE，我虽然过了，但是算法应该可以还优化，因为别人有0msAC的。

利用DFS对每种情况，分析，其中num代表已经找到的木棍数，len表示这条边已经完成的长度，原本统一都是从0开始搜索的，可是TLE，后来主要优化了，dfs内的搜索开始位置，每次从i+1开始搜索，如果一条边完了，从0开始搜索，

其中有个小细节，就是降序排列，能省一些功夫，。

代码如下：

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

bool used[25];
int d[25],n,side;

int cmp(int a,int b)
{
	return a>b;
}

bool dfs(int begin,int num,int len)
{
	if(len==side&&num;==n)
		return 1;
	if(len==side)
		len=0;
	for(int i=begin;i<n;i++)
	{
		if(i&&d;[i]==d[i-1]&&used;[i-1]==0)
			continue;
		if(d[i]<side-len&&used;[i]==0)
		{
			used[i]=1;
			if(dfs(i+1,num+1,len+d[i]))
				return 1;
			used[i]=0;
		}
		if(d[i]==side-len&&used;[i]==0)
		{
			used[i]=1;
			if(dfs(0,num+1,len+d[i]))
				return 1;
			used[i]=0;
		}
	}
	return 0;
}

int main()
{
	int t,sum;
	scanf("%d",&t;);
	while(t--)
	{
		sum=0;
		scanf("%d",&n;);;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&d;[i]);
			sum+=d[i];
		}
		if(sum%4)
		{
			printf("non");
			continue;
		}
		side=sum/4;
		sort(d,d+n,cmp);
		memset(used,0,sizeof(used));
		if(dfs(0,0,0))
			printf("yesn");
		else
			printf("non");
	}
}

发表于 更新于

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

解释下题意，一个锁的表盘可以转动，共40格，输入abcd四个数，最开始表盘停在a上，先顺时针转两圈，然后顺时针转到b，再逆时针转一圈，在逆时针转到c，最后顺时针转到d，问一共转了多少度，注意是度不是上面的刻度，其中像0到30直接减会出现负数，我就加上个40然后取余数，就解决了

简单模拟，就是题意太难懂，

代码如下：

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

int main()
{
	int a,b,c,d,s;
	while(cin>>a>>b>>c>>d&&a;+b+c+d)
	{
		s=720;
		s+=(a-b+40)%40*360/40;
		s+=360;
		s+=(c-b+40)%40*360/40;
		s+=(c-d+40)%40*360/40;
		cout<<s<<endl;
	}
}

发表于 更新于

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

解释下题意把，要求我们根据输入的猜测，来判断是否正确

我用l和r来表示区间的最小数和最大数，注意正确区间的更新，我的思路是
如果一个数too high但它小于l那么说谎，如果在l和r之间，更新r
如果一个数too low但它大于r那么说谎，如果在l和r之间，更新l
如果判断数时不在区间内，就是说谎。

代码如下：

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

int main()
{
	int l=0,r=11,n,flag=0;
	char ch[10];
	while(scanf("%d",&n;)&&n;)
	{
		getchar();
		scanf("%[^n]",ch);
		if(ch[4]=='t')
		{
			if(n<=l||n>=r)
				flag=1;
			if(flag)
				printf("Stan is dishonestn");
			else
				printf("Stan may be honestn");
			flag=0;
			l=0;
			r=11;
		}
		if(ch[4]=='h')
		{
			if(n<=l)
				flag=1;
			else
				if(n<r)
					r=n;
		}
		if(ch[4]=='l')
		{
			if(n>=r)
				flag=1;
			else
				if(n>l)
					l=n;
		}
	}
}

发表于 更新于

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

题目要求我们求组合数
公式如下

其中我们可以优化下算法，因为

这样k和n-k就取小的计算就是了，其中fixed指不使用科学计数法，其实用printf输出方便的多

代码如下：

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

int main()
{
	double n,k,i,ans;
	while(cin>>n>>k&&n;+k)
	{
		ans=1;
		if(k>n-k)
			k=n-k;
		for(i=n;i>=n-k+1;i--)
			ans*=i;
		for(i=1;i<=k;i++)
			ans/=i;
		cout<<fixed<<setprecision(0)<<ans<<endl;
	}
}