Jove's Blog

I love what I do

发表于 更新于

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

题目给出一些高度的木箱，问至少移动多少步，可以移动到同以高度！水题，没什么好说的！

代码如下：

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

int main()
{
	int t,i,j=1,d[105];
	while(cin>>t&&t;)
	{
		int sum=0,ans=0;
		for(i=0;i<t;i++)
		{
			cin>>d[i];
			sum+=d[i];
		}
		sum/=t;
		for(i=0;i<t;i++)
		{
			int temp=sum-d[i];
			ans+=(temp>0?temp:-temp);
		}
		cout<<"Set #"<<j<<endl;
		cout<<"The minimum number of moves is "<<ans/2<<"."<<endl;
		cout<<endl;
		j++;
	}
}

发表于 更新于

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

题目先开始没有读清楚，结果思路一直是错的，解释下题意，一列顺序为1，2，3。。的列车通过一个中转站后是否能变为给出的序列，其中这个站，类似于那个栈，利用他暂时保留车辆，以调整顺序，比如
3辆车想变为1，3，2，那么2号进站，等三号出来后在从站里出来跟在3后面

天然的栈运用，我们用stack模拟中转站中存的车辆

依次比较出来的序列是否和进站的一样或者于栈顶的一样，否则将这车推入栈，等待后面的判断，最后要是可以的话，栈里的元素应该全部推出！我用i计数进站的车，用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
/*Problem: 1363		User: awq123
**Memory: 264K		Time: 266MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;

int main()
{
	int d[1005],n,i;
	stack <int> s;
	while(cin>>n&&n;)
	{
		while(cin>>d[1]&&d;[1])
		{
			for(i=2;i<=n;i++)
			{
				cin>>d[i];
			}
			int i=1,k=1;
			while(i<=n+1&&k;<=n)
			{
				if (d[k]==i)
				{
					i++;k++;
				}
				else if (s.empty()==0&&d;[k]==s.top())
				{
					s.pop();
					k++;
				}
				else
				{
					s.push(i);
					i++;
				}
			}
			if(s.empty())
				cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
			while(s.empty()==0)
				s.pop();
		}
		cout<<endl;
	}
}

发表于 更新于

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

第一个自己做的最小生成树的题，利用的prim算法，虽然其中编写时调试还是参考了一些文章，不过对prim算法有了一些了解

题意，就是求给出数据的最小生成树。

prim简单的来说就是每次加上与已选择点相连的最短线。利用了贪心的思路。具体见注释！

代码如下：

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
76
77
78
79
80
/*Problem: 1251		User: awq123
**Memory: 264K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x7FFFFF

int n,map[30][30];

int min(int a,int b)
{
	return a>b?b:a;
}

void prim()
{
	int i,mark[30],lcos[30];//mark标记是否被选择
	memset(mark,0,sizeof(mark));
	for(i=1;i<=n;i++)//初始话lcos为极大
		lcos[i]=INF;
	lcos[1]=0;
	while(1)
	{
		int mins=INF,v=-1;
		for(i=1;i<=n;i++)//寻找最短的相连线段
			if(mark[i]==0&&lcos;[i]<mins)
			{
				mins=lcos[i];
				v=i;
				//记录这个点
			}
		if(v==-1)//如果没有，跳出
			break;
		mark[v]=1;//标记已选
		for(i=1;i<=n;i++)
			if(!mark[i])
				lcos[i]=min(lcos[i],map[v][i]);
				//更新lcos的值
	}

	int sum=0;
	for(i=1;i<=n;i++)
		sum+=lcos[i];
	cout<<sum<<endl;
	//输出结果
	return;
}
int main()
{
	int i,j;
	while(cin>>n&&n;)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				map[i][j]=INF;
				map[j][i]=INF;
			}
		//初始化map
		char a;
		int an;
		for(i=1;i<n;i++)
		{
			cin>>a>>an;
			while(an--)
			{
				char b;
				int bn;
				cin>>b>>bn;
				map[a-'A'+1][b-'A'+1]=bn;
				map[b-'A'+1][a-'A'+1]=bn;
			}
		}
		prim();
	}
}

发表于 更新于

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

题目不解释了，看不懂就没办法了！

我没有用数组储存数据，而是依次用结构体保存每个位置的坐标，因为按顺序输入的，我就没排序了，接下来的就是DFS+回溯，在这些点里取出k个点，且要满足不在同一列上。我利用两个数组来指示行和列是否已被占用，具体见注释把！

PS：这题可以剪枝到0MS，不过可能测试数据松点，暴力DFS就行了！
代码如下：

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

struct NODE//坐标保存在结构体数组里
{
	int x;
	int y;
}map[64];

int c,t,n,k,xused[9],yused[9];//两个指示数组

void DFS(int start,int left)
//start表示判断第几个元素，left表示还要找的数目
{
	if(left==0)//如果找完了，计数+1
	{
		t++;
		return;
	}
	if(start>=c)//超过结构体有效范围
		return;
	if(xused[map[start].x]==0&&yused;[map[start].y]==0)
	//如果这个点满足条件
	{
		xused[map[start].x]=1;
		yused[map[start].y]=1;
		//表示已选，搜索下一个
		DFS(start+1,left-1);
		xused[map[start].x]=0;
		yused[map[start].y]=0;
		//回溯
	}
	DFS(start+1,left);
	return;
}

int main()
{
	int i,j;
	while(cin>>n>>k&&n;+k+2)
	{
		c=0;
		t=0;
		memset(xused,0,sizeof(xused));
		memset(yused,0,sizeof(yused));
		//初始化指示数组
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=n;j++)
			{
				char temp;
				cin>>temp;
				if(temp=='#')
				{
					map[cpp].x=i;
					map[cpp].y=j;
					c++;
				}
			}
		}
		DFS(0,k);//由第0个开始找k个
		cout<<t<<endl;
	}
}

发表于 更新于

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

题目问，在一个字符串里至少加几个字母能组成回文词，所谓回文词，就是反着读和正着一样的字符串，以输入例子来看
Ab3bd
可以变成
Adb3bdA
也可以变成
dAb3bAd
虽然答案不唯一，但是增加的数量是有限的。

我们利用DP解这题，具体思路是，由字符串两端开始比较，若两格字母相同，那么同时去掉这两个的话，答案是不变的，若不同，就由两种情况，分别是在左边加上右边的字母，或者在右边加上左边的字母，我们取两中情况的最小值，然后递归调用下去，用dp[i][j]表示左边第i个开始，和右边第j个开始的最小数量

DP思路简化为：

1
2
3
4
5
6
7
if(str[i]==str[j])
	dp[i][j]=dp[i+1][j-1];
else
	dp[i][j]=min(dp[i][j-1],dp[i+1][j])+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
/*Problem: 1159		User: awq123
**Memory: 49332K		Time: 532MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

short min(short a,short b)
{
	return a>b?b:a;
}
short dp[5005][5005];

int main()
{
	short len,i,j;
	char str[5005];
	cin>>len>>str;
	memset(dp,0,sizeof(dp));
	for(i=len-2;i>=0;i--)
		for(j=i+1;j<len;j++)
		{
			if(str[i]==str[j])
				dp[i][j]=dp[i+1][j-1];
			else
				dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;
		}
	cout<<dp[0][len-1]<<endl;
}

发表于 更新于

不短的暑假过去了，过的蛮充实的，虽然没有像预想的那样去打工，自己仍然学会了一些东西，今天老段大电话给我，的确让我很是惊讶，不过想来看看，也知道他担心什么，高中3年，辛苦他照顾我们这个班级，虽然他已经做得很好，我们班也考得全校最好，他仍然感觉对几个人抱歉，呵呵，其中就有我，说实话他说着我感触很深，高中是个不错的过程，尽管他得变化没有在他意料之中，不过余璇后来的加入还是带给我了一些，嘿嘿，老师不用抱歉什么，每个人有每个人的路，超过余璇，詹彬齐，不是能跟你保证的事 ，他们有他们有他们的发展，凭什么说自己比别人强。

回忆起，军训到毕业的每个细节，我很庆幸呆在五班，没有哪个班有这样的氛围，给一个紧张的高三一个快乐的结局。

说起小黄洁，其实我都忍不住告诉您他谈朋友了，你爷不必为那些事担心，她会幸福的，至少现在很快乐！

其实说起回忆，还是想起了小K，没办法忘记她给我的改变，不过她很快乐现在，也就够了，有机会再去找她玩吧，嘿嘿。

大二了，我想大，不想二，自由的时间该变变了，我也改稍微认真点了，虽然比我的计划早点，不过不影响。

加油了Jove Sky

发表于 更新于

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

解释下题意，先输入字符串得长度，和字符串，然后输出所有前n位重复得情况例如输入例子
字符串为aabaabaabaab
前2位也就是aa是a重复2次
前6位也就是aabaab是aab重复2次
前9位也就是aabaabaab是aab重复3次
前12位也就是aabaabaabaab是aab重复4次

利用KMP算法，匹配最长重复子串，然后针对每个长度找出符合条件得情况

代码如下：

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

int main()
{
	int i,j,t,len,next[1000005];
	char str[1000005];
	t=1;
	while(scanf("%d",&len;)&&len;)
	{
		scanf("%s",str);
		next[0]=-1;
		i=0;
		j=-1;
		while(str[i]!='\00')
		{
			if(j==-1||str[i]==str[j])
			{
				i++;
				j++;
				next[i]=j;
			}
			else
				j=next[j];
		}
		printf("Test case #%dn",t++);
		for(i=2;i<=len;i++)
		{
			j=i-next[i];  //求循环节得长度
			if(i%j==0&&i;!=j)  //长度整除这个子串长度，且不为本身
				printf("%d %dn",i,i/j);
		}
		printf("n");
	}
}

发表于 更新于

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

题意是，给出一个数，求出最小的n，使得1,2,3…n中间加上+或-得到这个数

我们一直由1开始加，知道sum>=这个数，如果等于就直接输出，如果大于，再判断sum-这个数是否为奇数，若为奇数，则变化任何一个+为-变化量为偶数，无论怎么样都无法实现，直接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
/*Problem: 1844		User: awq123
**Memory: 252K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
	int n=1,t;
	cin>>t;
	while(1)
	{
		int sum=(n+1)*n/2;
		if(sum==t)
			break;
		if(sum>t&&(sum-t)%2==0)
			break;
		n++;
	}
		cout<<n<<endl;
}

发表于 更新于

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

求第n个，因式只有2，3，5的树，打表做最好了，算法借鉴别人的，设d[]数组保存这个数列，这样，可以设三个指针p2，p3，p5，分别指向数列中的三个数（可以相同），取d[p2]*2，d[p3]*3，d[p5]*5中的最小者作为下一个数，并将该所对应的指标加1。不断重重该过程，直到求出第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
/*Problem: 1338		User: awq123
**Memory: 256K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
	int d[1505];
	int p2=1,p3=1,p5=1,v2,v3,v5,i,n;
	d[1]=1;
	for(i=2;i<=1500;i++)
	{
		v2=d[p2]*2;
		v3=d[p3]*3;
		v5=d[p5]*5;
		if(v2<=v3&&v2;<=v5)
			d[i]=v2;
		if(v3<=v2&&v3;<=v5)
			d[i]=v3;
		if(v5<=v3&&v5;<=v2)
			d[i]=v5;
		if(d[i]==v2)
			p2++;
		if(d[i]==v3)
			p3++;
		if(d[i]==v5)
			p5++;
	}
	while(cin>>n&&n;)
	{
		cout<<d[n]<<endl;
	}
}

发表于 更新于

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

简单题，六个分数去掉一个最高分，去掉一个最低分，然后取平均值，然而这题的难点在于输出要求：

(without unnecessary decimal points and/or zeros.)

也就是输出浮点数，但不输出多余的0，其实要是用printf输出，我觉得很麻烦，还要判断这那的，不过C++中cout对浮点的输出会自动优化这些，嘿嘿，又偷懒了！

代码如下：

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

int main()
{
	int i,d[6];
	while(1)
	{
		float sum=0;
		for(i=0;i<6;i++)
		{
			cin>>d[i];
			sum+=d[i];
		}
		if(sum==0)
			break;
		sort(d,d+6);
		sum-=d[0];
		sum-=d[5];
		sum/=4;
		cout<<sum<<endl;
	}
}