Jove's Blog

I love what I do

发表于 更新于

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

解释下题意，给出一组字符串，问是否能将这些字符串首尾相接组成一个长字符串，首尾两个字母一样才能连接。

简化题目，我们只考虑首尾字母，组成的有向欧拉回路，要能够相连，必须全部入度等于出度或者除了两个外其他点的入度等于出度，且不相等的一个入度比出度大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
62
63
64
65
66
67
68
69
/*Problem: 1386		User: awq123
**Memory: 252K		Time: 688MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int fa[26];

int find_set(int x)
{
	if(fa[x]==x)
		return x;
	fa[x]=find_set(fa[x]);
	return fa[x];
}
int main()
{
	//freopen("Input.txt", "r", stdin);
	int in,out,i,t,n,d1[26],d2[26],vis[26];
	char str[1005];
	cin>>t;
	while(t--)
	{
		memset(d1,0,sizeof(d1));
		memset(d2,0,sizeof(d2));
		memset(vis,0,sizeof(vis));
		cin>>n;
		for(i=0;i<26;i++)
			fa[i]=i;
		while(n--)
		{
			cin>>str;
			in=str[0]-'a',out=str[strlen(str)-1]-'a';
			d1[in]++;
			d2[out]++;
			vis[in]=1;
			vis[out]=1;
			fa[find_set(in)]=find_set(out);
		}
		int flag=1,flag1=0,flag2=0;
		for(i=0;i<26&&flag;i++)
		{
			if(vis[i]&&d1;[i]!=d2[i])
			{
				if(d1[i]==d2[i]+1)
					flag1++;
				else if(d1[i]==d2[i]-1)
					flag2++;
				else
					flag=0;
			}
		}
		for(i=0;i<26;i++)
			if(vis[i]&&find;_set(out)!=find_set(i))
				flag=0;
		if(flag)
		{
			if((flag1==1&&flag2;==1)||(flag1==0&&flag2;==0))
				cout<<"Ordering is possible."<<endl;
		}
		else
			cout<<"The door cannot be opened."<<endl;
	}
}

发表于 更新于

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

题意不难，求小于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
/*Problem: 1543		User: awq123
**Memory: 256K		Time: 47MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int n,i,j,k,l;
	cin>>n;
	for(i=3;i<=n;i++)
	{
		for(j=2;j<n;j++)
			for(k=j+1;k<n;k++)
				for(l=k+1;l<n;l++)
					if(i*i*i==j*j*j+k*k*k+l*l*l)
					{
						cout<<"Cube = "<<i<<", Triple = ("<<j<<","<<k<<","<<l<<")"<<endl;
						break;
					}
	}
}

发表于 更新于

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

标准prim题，无变化，利用简单prim算法解决，先开始WA了一次，后来发现这题，是多数据输入的，修改了个while循环过了！

代码如下：

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
/*Problem: 1258		User: awq123
**Memory: 300K		Time: 63MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 105
#define INF 0xFFFFF

int prim(int graph[][MAX], int n)
{
	int lowcost[MAX],mst[MAX];
	int i, j, min, minid, sum = 0;
	for (i = 2; i <= n; i++)
	{
		lowcost[i] = graph[1][i];
		mst[i] = 1;
	}
	mst[1] = 0;
 	for (i = 2; i <= n; i++)
	{
		min = INF;
		minid = 0;
 		for (j = 2; j <= n; j++)
		{
			if (lowcost[j] < min && lowcost[j] != 0)
			{
				min = lowcost[j];
				minid = j;
			}
		}
 		sum += min;
 		lowcost[minid] = 0;
		for (j = 2; j <= n; j++)
		{
			if (graph[minid][j] < lowcost[j])
			{
				lowcost[j] = graph[minid][j];
 				mst[j] = minid;
			}
		}
	}
	return sum;
}

int main()
{
	int i,j,n,map[MAX][MAX];
	while(cin>>n)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				cin>>map[i][j];
		cout<<prim(map,n)<<endl;
	}
}

发表于 更新于

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

解释下题意，n个人围着一个桌子坐，可以交换两个人的位置，问至少交换多少次，可以使座次左右相反！比如原来使12345，要变成54321，但是注意桌子使圆的也可以变为43215同样满足条件！

说起交换，不由想起了冒泡排序，我们这样看讲12345用冒泡排序降序排列，交换次数为n*(n-1)/2,但是我们可以讲这些数分为两块，分别交换，计算推论我们可以知道，两堆越接近越少,那么12345变为32154或21543交换次数最少.

代码简单，纯数学问题，重在思考！

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

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		cout<<(n/2)*(n/2-1)/2+(n-n/2)*(n-n/2-1)/2<<endl;
	}
}

发表于 更新于

说来好笑，为什么大家都很在意新来的学妹，难道是身边的女孩看厌了！
93

开学的日子里，看的多了，还是讨论学妹的，不一定是认真的，但多少还是感兴趣的，一觉起来，照例看看空间，人人，好像新生报道了啊，什么今天不上班了啊，去迎接学妹啊，呵，幸好我在家里，快两周没回来看爸妈了，还是在家里呆着好了，不是因为家里舒服，而是家里自由温馨！

想想，现在要看到新生们要军训了，第一感觉就是过了一年了！相比大一的基础课，大二的专业课还是蛮难的，虽然C++的我也学过，但是多数是对付ACM用的STL，面向对象这一思路我一直认为他会用JAVA教，失误了，呵

总的来说大二，要让自己忙，我不想无聊下去！

发表于 更新于

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

题意要求我们模拟高精度加法运算，我们把数字横过来看就是正常加法了。不多说模拟进位运算，现开始用整型数组保存数据，结果一直超时，于是用字符数组试了下，事实证明，输出字符串，比没一个字母输出快！

PS：其中输入时，后面加上了n也可以在输入语句后加上getchar()代替！

代码如下：

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: 2602		User: awq123
**Memory: 3112K		Time: 1500MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1000005],b[1000005],sum[1000005];
int main()
{
	int n,i,jw;
	scanf("%dn",&n;);
	for(i=0;i<n;i++)
		scanf("%c %cn",&a;[i],&b;[i]);
	jw=0;
	for(i=n-1;i>=0;i--)
	{
		int temp=a[i]-'0'+b[i]-'0'+jw;
		sum[i]=temp%10+'0';
		jw=temp/10;
	}
	sum[n]='\00';
	if(jw!=0)
		printf("%d",jw);
	printf("%s",sum);
}

发表于 更新于

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

题意，求小于n的数中和n互质的数的个数！

这题，我先开始的思路是针对每个小于n的数求最大公约数，但是用辗转相除法，递归层数过高！后来想开个数组，标记互质的数，但是n太大，无法开出来，搜索了一下，有一个函数，是用来解决这一问题的，就是欧拉函数，我参看维基百科，写出算法！

欧拉函数的求解，可以简化为，将n写成a1^n1a2^n2….an^nn的形式，那么这个数的欧拉函数表达式为a1^(n1-1)(a1-1) * a1^(n2-1)*(a1-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
/*Problem: 2407		User: awq123
**Memory: 260K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
	int n,i,num;
	while(cin>>n&&n;)
	{
		num=1;
		for(i=2;i<=n;i++)
		{
			int t=0;
			while(n%i==0)
			{
				t++;
				n/=i;
			}
			if(t!=0)
				num*=(pow((float)i,t-1)*(i-1));
		}
		cout<<num<<endl;
	}
}

发表于 更新于

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

题意：股票经纪人要在一群人中散布一个传言，传言只能在认识的人中传递，题目将给出人与人的关系（是否认识），以及传言在某两个认识的人中传递所需的时间，要求程序给出以哪个人为起点，可以在好事最短的情况下，让所有人收到消息。

简化为有向连同图的最短路径问题，用floyd算法算法最简单，flyod算法的实现，我根据伪代码编写的：

1
2
3
4
5
6
7
8
9
10
11
void floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d[i][k]+d[k][j]<d[i][j])
					d[i][j]=d[i][k]+d[k][j];
	return;
}


代码如下：

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

int n,d[105][105];

void floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d[i][k]+d[k][j]<d[i][j])
					d[i][j]=d[i][k]+d[k][j];
	return;
}

int main()
{
	int i,j,m;
	while(cin>>n&&n;)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i==j)
					d[i][j]=0;
					//相同初始化为0
				else
					d[i][j]=INF;
					//不同初始化为极大值
		for(i=1;i<=n;i++)//输入数据
		{
			cin>>m;
			for(j=1;j<=m;j++)
			{
				int p,c;
				cin>>p>>c;
				d[i][p]=c;
			}
		}
		floyd();//floyd算法
		int p,min=INF,max;
		for(i=1;i<=n;i++)
		{
			max=0;
			for(j=1;j<=n;j++)
				if(d[i][j]>max)
					max=d[i][j];
			if(max<min)
			{
				min=max;
				p=i;
			}
		}
		if(min==INF)
			cout<<"disjoint"<<endl;
		else
			cout<<p<<" "<<min<<endl;
	}
}

发表于 更新于

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

上学了，时间不多，先水一把！
题目给出了算法，其中A代表1，依此类推，注意含空格的字符串的输入，我们一般用gets，其实注释掉的那句也可以的！

代码如下：

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

int main()
{
	char str[300];
	while (1)
	{
		//scanf("%[^n]n",str);
		gets(str);
		if(str[0]=='#')
			break;
		int i,sum=0,len=strlen(str);
		for(i=0;i<len;i++)
		{
			if(str[i]!=' ')
				sum+=(str[i]-'A'+1)*(i+1);
		}
		cout<<sum<<endl;
	}

}

发表于 更新于

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

这个题，原本我想模拟做的，但是其实又更简单的办法，让我很惊讶，难道是小学奥术没学好？？

把一个数字的各位相加得到一个和，这个和又是一个新的数，把这个数的各位再次相加又得到一个和，如此一直重复做，直到最后的数字之和是一位数。这个数就是原数除以9的余数，我们把这个余数称之为原数的”数字根”。这道题肯定没有告诉你数字根和各位相加对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
/*Problem: 1519		User: awq123
**Memory: 244K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	char str[2000];
	while(cin>>str&&str;[0]!='0')
	{
		int i,sum=0,len=strlen(str);
		for(i=0;i<len;i++)
			sum+=str[i]-'0';
		sum%=9;
		if(sum==0)
			cout<<9<<endl;
		else
			cout<<sum<<endl;
	}
}