Jove's Blog

I love what I do

发表于 更新于

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

解释下题意，有一些硬币，又一枚是假的重量跟其他的不一样，通过多次称量，求出这个的编号

这个题和1013几乎一模一样，不同的是，1013题目一定可以求出结果，这个不能，不过也就是多了一个判断罢了，还是差不多！

大家可以参考 POJ 1013 Counterfeit Dollar C++版

思路就不说了，跟1013一样！懒一下拉！

代码如下：

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
81
82
83
84
85
86
87
88
89
90
/***************************************
Problem: 1029		User: awq123
Memory: 272K		Time: 32MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int i,j,len,n,k,d[1005],temp[1005],left[505],right[505];
	char cmp[5];
	memset(d,0,sizeof(d));
	cin>>n>>k;
	while(k--)
	{
		cin>>len;
		for (i = 0; i < len; i++)
			cin>>left[i];
		for (i = 0; i < len; i++)
			cin>>right[i];
		cin>>cmp;
		if(cmp[0]=='=')
		{
			for(j=0;j<len;j++)
			{
				d[left[j]]=1;
				d[right[j]]=1;
			}
		}
		else if(cmp[0]=='>')
		{
			memset(temp,0,sizeof(temp));
			for(j=0;j<len;j++)
			{
				if(d[left[j]]==-1)
					d[left[j]]=1;
				else if(d[left[j]]==0)
					d[left[j]]=2;
				if(d[right[j]]==2)
					d[right[j]]=1;
				else if(d[right[j]]==0)
					d[right[j]]=-1;
				temp[left[j]]=1;
				temp[right[j]]=1;
			}
			for(j=0;j<=n;j++)
				if(temp[j]==0)
					d[j]=1;
		}
		else if(cmp[0]=='<')
		{
			memset(temp,0,sizeof(temp));
			for(j=0;j<len;j++)
			{
				if(d[left[j]]==2)
					d[left[j]]=1;
				else if(d[left[j]]==0)
					d[left[j]]=-1;
				if(d[right[j]]==-1)
					d[right[j]]=1;
				else if(d[right[j]]==0)
					d[right[j]]=2;
				temp[left[j]]=1;
				temp[right[j]]=1;
			}
			for(j=0;j<=n;j++)
				if(temp[j]==0)
					d[j]=1;
		}
	}
	int count=0,answer;
	for (i = 1; i <=n ; i++)
	{
		if(d[i]!=1)
		{
			count++;
			answer=i;
		}
	}
	if (count==1)
		cout<<answer<<endl;
	else
		cout<<0<<endl;

}

发表于 更新于

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

解释下题意，对一列数进行转换依次升序输出数字输出的次数和这个数字，比如
31123314中，1有3个，2有一个，3有3个，4有1个，那么转换为31123314，

题目要求写出数子的特性，有如下几种

  • 自我循环，既转换一次后就与原来相同；
  • j步转换后有与前一次相同的数字，之后开始循环；
  • j步转换后与与前面，但不是前一次的相同那么永远不能循环：
  • 15次转换后都没有结果！

这题利用了string，这个字符串比普通char强大太多，对于数组的添加写入分离，以及计算都方便太多了，有普通整形数组应该也能做，不过麻烦点！

解释下思路，编写work完成一次转换，其中利用w保存每个数的次数，其中应该注意，次数如果大于9就要输出两格了，然后循环15次一次转换字符串，每次转换后与前面的情况比较，看是否有相同的，如果相同则跳出，根据循环次数，以及对比的次数，分析各种情况；

  • 循环1次
  • 循环i次后，对比了j次；
  • 循环i次后，对比了不到j次；
  • 循环了15次！

其中有个小问题让我郁闷了半天C++提交老是编译错误，我G++编译就没问题，后来搞了半天才知道C++里不叫cstring叫string！郁闷！

代码如下：

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

string str[16];
void work(int t)
{
	int i,w[10]={0};
	for(i=0;i<(int)str[t].size();i++)
		w[str[t][i]-'0']++;
	string s="";
	for(i=0;i<10;i++)
		if(w[i]>0&&w;[i]<10)
		{
			s+=w[i]+'0';
			s+=i+'0';
		}
		else if(w[i]>=10)
		{
			s+=w[i]/10+'0';
			s+=w[i]%10+'0';
			s+=i+'0';
		}
	str[t+1]=s;
}

int main()
{
	int i,j,flag;
	while(cin>>str[0]&&str;[0][0]!='-')
	{
		for(i=0;i<15;i++)
		{
			flag=0;
			work(i);
			for(j=0;j<=i;j++)
				if(str[i+1]==str[j])
				{
					flag=1;
					break;
				}
			if(flag==1)
				break;
		}
		if(flag)
		{
			if(i==0)
				cout<<str[0]<<" is self-inventorying"<<endl;
			else if(j==i)
				cout<<str[0]<<" is self-inventorying after "<<i<<" steps"<<endl;
			else
				cout<<str[0]<<" enters an inventory loop of length "<<i-j+1<<endl;
		}
		else
			cout<<str[0]<<" can not be classified after 15 iterations"<<endl;
	}
}

发表于 更新于

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

解释下题意，有12个硬币，有一个是假的跟其他重量不一样，要求你通过三次称量找出这个硬币！称量不用你考虑，题目说了三次称量一定能找到这个硬币，我们所做的就是分析数据！

我们来讲解下称量：
even则盘两边的必然都是真的
up左盘有轻假硬币或者右盘有重假硬币
down右盘有轻假硬币或者左盘有重假硬币

其中有点需要特别说明，也是解题的要点，就是up和down的情况下没有称的一定是真的！没有这个判断是完成不了题目的！

这道题花了我大概3个小时，百思不得其解，一直我定义的cmp都是4个字节，觉得也没问题，但是最后改成5就AC了，我擦，当时就想骂人了，原来忘记了，一个字符串需要’\00’做结尾，我是说怎么数据都对还能错的，还是自己大意了！

具体的思路看注释吧

代码如下：

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
81
82
83
84
85
86
87
88
/*Problem: 1013		User: awq123
**Memory: 176K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int i,j,len,n,d[12],temp[12];
	char left[12],right[12],cmp[5];
	scanf("%d",&n;);
	while(n--)
	{
		//d数组表示真假性-1表示可能假0不知道1真2可能真
		memset(d,0,sizeof(d));
		for(i=0;i<3;i++)
		{
			scanf("%s%s%s",left,right,cmp);
			len=strlen(left);
			if(cmp[0]=='e')//even
			{
				for(j=0;j<len;j++)
				{
					d[left[j]-'A']=1;
					d[right[j]-'A']=1;
					//标记真的
				}
			}
			else if(cmp[0]=='u')//up
			{
				memset(temp,0,sizeof(temp));
				for(j=0;j<len;j++)
				{
					if(d[left[j]-'A']==-1)
						d[left[j]-'A']=1;
					//若既可能真，也可能假，则为真
					else if(d[left[j]-'A']==0)
						d[left[j]-'A']=2;
					//否则将不知道的标记为可能真
					//下面的不一一列举
					if(d[right[j]-'A']==2)
						d[right[j]-'A']=1;
					else if(d[right[j]-'A']==0)
						d[right[j]-'A']=-1;
					temp[left[j]-'A']=1;
					temp[right[j]-'A']=1;
					//标记这次比较用过的数
				}
				for(j=0;j<12;j++)
					if(temp[j]==0)
						d[j]=1;
				//给没用过的数标记成真
			}
			else if(cmp[0]=='d')//down
			{
				memset(temp,0,sizeof(temp));
				for(j=0;j<len;j++)
				{
					if(d[left[j]-'A']==2)
						d[left[j]-'A']=1;
					else if(d[left[j]-'A']==0)
						d[left[j]-'A']=-1;
					if(d[right[j]-'A']==-1)
						d[right[j]-'A']=1;
					else if(d[right[j]-'A']==0)
						d[right[j]-'A']=2;
					temp[left[j]-'A']=1;
					temp[right[j]-'A']=1;
				}
				for(j=0;j<12;j++)
					if(temp[j]==0)
						d[j]=1;
			}
		}
		for(i=0;i<12;i++)//扫描输出结果
		{
			if(d[i]==-1)
				printf("%c is the counterfeit coin and it is light.n",i+'A');
			if(d[i]==2)
				printf("%c is the counterfeit coin and it is heavy.n",i+'A');
		}	
	}
}

发表于 更新于

今天和张钧还有王子堃出去玩，完美的一天最后就是没有一个好的结局，晚上走的时候我看有线路可以不用转两道就等了571，这一等不要紧，一下就是一个小时，每次看到一辆来又发现不是571的时候，我都告诉自己下一量一定是的，事实证明不现实，没来就是没来，张钧还笑我是地狱来得倒霉鬼，还好它陪我等，不然无聊死了，后来，我放弃了改换576走了。

郁闷了，今天，一个公交搭纠结了，等的时间，我都快到家了！

下次再不坐571了，纯坑爹！

发表于 更新于

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

解释下题意，要求对照表将字符串转换成号码，然后输出不唯一的号码及其个数。

这个题目是我疏忽了，在一个小问题上WA了半天，最先开始是没有No duplicates. 这个一会就解决了，但是还是WA，然后看到了discuss种有0的数据才恍然大悟，自己的输出是打不出数字前面的0的，也正是这，学会了种完整输出电话的方法

1
2
3
4
int a=12345;
printf("%08d",a);


00012345

也算是学了点东西把，但是还是WA，无奈，在网上找了点原始数据，尼玛原来我temp有40都不够，我了个去，直接改成1000过的，我算是发现了，那些没告诉的值定大点总没错，有时WA的真的没有头绪，郁闷

解释下我的思路把，其实蛮简单的，就是针对每个字符进行转换，每次乘10加新的，那么就转换成了一个数字，在进行排序，然后利用相同的相邻的关系计数，其中因为计数最后一个可能出现问题我们单独再进行依次判定，用flag来确定是否有结果否则输出No duplicates.

代码如下：

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

int get(char a)
{
	int num[26]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0};
	return num[a-'A'];
}

int main()
{
	int num[100001];
	memset(num,0,sizeof(num));
	char temp[1000];
	int t,i,j,n,len;
	scanf("%d",&t;);
	for(i=0;i<t;i++)
	{
		scanf("%s",temp);
		len=strlen(temp);
		for(j=0;j<len;j++)
		{
			if(temp[j]>='0'&&temp;[j]<='9')
				num[i]=num[i]*10+temp[j]-'0';
			if(temp[j]>='A'&&temp;[j]<='Z')
				num[i]=num[i]*10+get(temp[j]);
		}
	}
	sort(num,num+t);
	n=1;
	int flag=0;
	for(i=1;i<t;i++)
	{
		if(num[i]==num[i-1])
			n++;
		else if(n!=1)
		{
			printf("%03d-%04d %dn",num[i-1]/10000,num[i-1]%10000,n);
			n=1;
			flag=1;
		}
	}
	if(num[t-1]==num[t-2])
	{
		printf("%03d-%04d %dn",num[i-1]/10000,num[i-1]%10000,n);
		flag=1;
	}
	if(flag==0)
		printf("No duplicates.n");	
}

发表于 更新于

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

经典的约瑟夫问题的变形，什么？约瑟夫问题是什么？来，哥给你个传送门

解释下题意，有k个好人和k个换人依次围成一个环，从第一个人开始数，数到m杀掉这个人，问m为多少，使坏人都在好人前面死

由于数据量不大，如果你自己已经打好表，那么有种简单的方法，纯粹为了0MSAC，代码如下：

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

int main()
{
	int Joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};
	int k;
	while(cin>>k&&k;)
		cout<<Joseph[k]<<endl;
}


1
2
3
4
p[i]=(p[i-1]+m-1)%(n-i+1);//p[i]为第i个杀的人n=2*k,m为所求！



由于oj系统反复利用这15组数据解题，打表，以避免超时

完整代码如下

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

int main()
{
	int joseph[14]={0},p[29];
	int k,n,m,i;
	while(cin>>k&&k;)
	{
		if(joseph[k])
		{
			cout<<joseph[k]<<endl;
			continue;
		}
		n=2*k;
		m=1;
		memset(p,0,sizeof(p));
		for(i=1;i<=k;i++)
		{
			p[i]=(p[i-1]+m-1)%(n-i+1);
			if(p[i]<k)
			{
				i=0;
				m++;
			}
		}
		joseph[k]=m;
		cout<<joseph[k]<<endl;
	}
}

发表于 更新于

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

这个题是1999年的世界决赛，看似很简单，其实很难，对精度的要求很高！我一直WA到哭，没办法才找到原始数据比对，需要原始数据的可以留言我！

强烈推介下这个题！

解释下题意，有m*n的矩形地，每块100平米，提供每块地的高度，问给定一定的下雨量，水面的高度，及水面的覆盖率！

题目不难，只是因为这个是世界决赛，原始数据就有2500条！囧了！看到上面鲜红Special Judge

分析下思路，我们把高度排序，那么模型变为一个阶梯状的图形，可以补齐为矩形，然后利用每一个的底面积都是100，来计算，其中sum为已经计算过的了高度，d为每一个的高度，依次补齐诚矩形，当不够的时候，那么就是临界状况，然后利用v/100+d[i-1]计算出所有高度，再除以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
27
28
29
30
31
32
33
34
/*Problem: 1877		User: awq123
**Memory: 256K		Time: 47MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int d[900],sum[900];
	int m,n,i,j=1,v;
	while(cin>>m>>n&&m;&&n;)
	{
		for(i=0;i<m*n;i++)
			scanf("%d",&d;[i]);
		scanf("%d",&v;);
		sort(d,d+m*n);
		sum[0]=d[0];
		for(i=1;i<m*n;i++)
			sum[i]=d[i]+sum[i-1];
		for(i=1;i<m*n;i++)
		{
			if((d[i]*i-sum[i-1])*100>=v)
				break;
		}
		printf("Region %dn",j++);
		printf("Water level is %.2f meters.n",(v/100.0+sum[i-1])/i);
		printf("%.2f percent of the region is under water.nn",100.0*(float)i/(m*n));
	}
}

发表于 更新于

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

解释下题意，一些小木棒是一些同样长的大木棒折断成的，求大木棒的最小长度

比如1 2 3 4
就是由两根5折断成的！

简单DFS但是我做了半天都是超时，原因是自己的dfs是处理型的算法上不够简洁，处理过多，递归层数有点大，然后一直TLE，没办法后来借鉴别人的才AC，其中的剪枝有些技巧，比如对于木棒长度的控制，以及剩余长度的控制，还有就是像前面如果有个同样大的数，没有成功的话，那么这个数的情况久不用考虑的，等等，

先上我原来TLE的代码：

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;

int d[70],used[70],len,n,sum,ok;

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

void dfs(int a,int b,int c)
{
	if(ok==1)
		return;
	else if(a==n+1)
		return;
	else if(c>sum||b>len)
		return;
	else if(c==sum&&b;==len)	
		ok=1;
	else if(b==len)
		dfs(0,0,c);
	else if(used[a+1]==1)
		dfs(a+1,b,c);
	else
	{
		used[a+1]=1;
		dfs(a+1,b+d[a+1],c+d[a+1]);
		used[a+1]=0;
		dfs(a+1,b,c);
	}
}

int main()
{
	int i;
	while(cin>>n&&n;)
	{
		sum=0;ok=0;
		d[0]=0;
		for(i=1;i<=n;i++)
		{
			cin>>d[i];
			sum+=d[i];
		}
		sort(d+1,d+1+n,cmp);
		for(i=d[1];i<=sum;i++)
		{
			if(ok==1)
				break;
			if(sum%i==0)
			{
				memset(used,0,sizeof(used));
				len=i;
				dfs(0,0,0);
			}
		}
		cout<<len<<endl;
	
	}
}


再来看看AC的代码，代码如下

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
/*Problem: 1011		User: awq123
**Memory: 164K		Time: 63MS
**Language: C++		Result: Accepted
*/
#include <stdio.h>
#include <stdlib.h>
int sticks[100],n;
bool used[100];
int cmp(const void *x,const void *y)
{
    return *(int *)y - *(int *)x;
}
bool find(int left,int num,int len)
{
    int i;
    if(left == 0 && num == 0)
    return 1;
    if(left == 0)
    left = len;
    for(i = 0;i < n;i ++)
    {
	if(sticks[i] <= left && !used[i])
	{
	    used[i] = 1;
	    if(find(left - sticks[i],num-1,len))
	    return 1;
	    used[i] = 0;
	    if(sticks[i] == left || left == len)
	    return 0;
	}
    }
    return 0;
}

int main()
{
    int i,sum = 0;
    while(scanf("%d",&n;) != EOF && n)
    {
	sum = 0;
	for(i = 0;i < n;i ++)
	{
	    scanf("%d",&sticks;[i]);
	    sum += sticks[i];
	    used[i] = 0;
	}
	qsort(sticks,n,sizeof(int),cmp);
	for(i = sticks[0];i <= sum;i ++)
	{
	    if((sum % i == 0) && find(i,n,i))
	    {
	        printf("%dn",i);
	        break;
	    }
	}
    }
    return 0;
}

发表于 更新于

strlen()是用来求字符串长度的一个函数,sizeof()是用来求指定变量或者变量类型等所占内存大小的操作符。

这两个虽然都是量取长度的，但有本质的不同我们通过几个例子来看看！

1
2
3
4
5
char ss[]="0123456789";
printf("%dn",sizeof(ss));
printf("%dn",sizeof(*ss));


11 ss是数组，计算到’’一共10+1
1 *ss指第一个字符，所以为1 

1
2
3
4
5
char* ss="0123456789";
printf("%dn",sizeof(ss));
printf("%dn",sizeof(*ss));


4 ss是指向字符串常量的字符指针，长整形的，所以为4
1 *ss是第一个字符，为1 

1
2
3
4
5
char ss[100]="0123456789";
printf("%dn",sizeof(ss));
printf("%dn",strlen(ss));


100 ss再内存中规定的大小就是100
10 ss有10个字符，所以长度为10 

1
2
3
4
5
int ss[100]="0123456789";
printf("%dn",sizeof(ss));
printf("%dn",strlen(ss));


理论上第一个应该输出400 因为100长度再内存中占用100×4
第二个错误 strlen后只能接字符指针

发表于 更新于

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

解释下题意，就是问一个字符串可以看成一个子串循环最多多少次组成，比如
abcd就是abcd循环1次
aaaa就是a循环4次
ababab就是ab循环3次

由1开始扫描每种可能的节长，一一对比，直到到串尾还满足！

花了900多ms好像也有简单的方法，改天研究下！

代码如下：

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

int main()
{
	char c[1000001];
	int i,j,len,flag;
	start:
	scanf("%s",c);
	len=strlen(c);
	if(c[0]=='.')
		return 0;
	for(i=1;i<=len;i++)
	{
		flag=1;
		if(len%i==0)
			for(j=0;j<len;j++)
			{
			
				if(c[j%i]!=c[j])
				{
					flag=0;
					break;
				}
				if(j==len-1&&flag;)
				{
					cout<<len/i<<endl;
					goto start;
				}
			}
	}

}