Jove's Blog

I love what I do

发表于 更新于

题目链接：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;
				}
			}
	}

}

发表于 更新于

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

2405

纯数学问题，给出D和咬去的V求d，先开始一直再查圆台的体积公式，是这样的：
V＝πh(R2＋Rr＋r2)/3
r－上底半径
R－下底半径
h－高

然而解方程真不方便，后来看到大神用定积分来解题，一下觉得自己高数没学好，真实损失大，直接d的三次方-6v除派再开三次方

代码如下：

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

int main()
{
	//freopen("input.txt", "r", stdin);
	int d,v;
	while(cin>>d>>v&&d;&&v;)
		cout<<fixed<<setprecision(3)<<pow(d*d*d-6*v/3.1415926,1.0/3)<<endl;


}

发表于 更新于

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

解释下题意，依次用（a×c+r）%m取随机数，直到循环，然后求在这些随机数里哪个区间最大，是多少！

这个题我很是郁闷了一晚上，做到完全想不出有什么问题了，还是WA，后来百度直到问的别人，我原来的代码是

1
2
3
temp=0;flag=0;max=0;


1
2
3
if(d[i]==0&&flag;==1)


1
2
3
if(d[i]==1&&flag;==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
/*Problem: 2381		User: awq123
**Memory: 62928K		Time: 1891MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
int d[16000002];
int main()
{
	long long int a,c,m,r,i,flag,temp,max;
	cin>>a>>c>>m>>r;
	memset(d,0,sizeof(d));
	d[r]=1;
	while(!d[(a*r+c)%m])
	{
		r=(a*r+c)%m;
		d[r]=1;
	}
	temp=0;flag=0;max=-1;
	for(i=0;i<m;i++)
	{
		if(d[i]==1&&flag;==0)
			flag=1;
		else if(d[i]==0&&flag;==1)
			temp++;
		else if(d[i]==1&&flag;==1)
		{
			if(temp>max)
				max=temp;
			temp=0;
		}
	}
	cout<<max+1<<endl;

}

发表于 更新于

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

中文题目，不错，哈哈，不多说，拿笔画！

PS：用int会超时哦！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <cstring> 
using namespace std;
int main()
{
	unsigned int m,n,a,sum;
	while(cin>>a)
	{
		m=a;
		while(1)
		{
			if((a*a+1)%m==0)
				break;
			m++;
		}
		n=(a*a+1)/m;
		sum=2*a+m+n;
		cout<<sum<<endl;
	}
}

发表于 更新于

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

题目要求我们求出和最大的子矩阵。

我输入数据的时候，做了个小处理，就是用这个坐标表示到原点的矩阵和，这样后面只要计算对角线点的值就行了，不过这题for语句真的好多，这样的矩阵题还是比较熟的。

不多解释，不难！

代码如下：

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

int main()
{
	//freopen("input.txt", "r", stdin);
	int d[101][101];
	memset(d,0,sizeof(d));
	int i,j,x,y,n,temp,max=0;
	cin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			cin>>temp;
			d[i][j]=temp+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
		}
	for(i=0;i<=n;i++)
		for(j=0;j<=n;j++)
			for(x=i;x<=n;x++)
				for(y=j;y<=n;y++)
				{
					temp=d[x][y]-d[x][j]-d[i][y]+d[i][j];
					if(temp>max)
						max=temp;
				}
	cout<<max<<endl;	

	

}

发表于 更新于

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

水题，文字还一大串，题意就是那个半圆每年增加50平米，问多少年到(x，y)这个点

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*Problem: 1005		User: awq123
**Memory: 252K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
	float x,y;
	int t,n,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x>>y;
		t=3.1415926*(x*x+y*y)/2;
		cout<<"Property "<<i<<": This property will begin eroding in year "<<t/50+1<<"."<<endl;
	}
	cout<<"END OF OUTPUT."<<endl;
}

发表于 更新于

完成1183后，我就突破10000了，也是对自己的一种肯定，虽然这个假期目标完成的有点早但是该做的还有很多，

一个字

爽

发表于 更新于

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

水题，让我们求成绩高于平均成绩的百分比，然而这题没有给我们巨大的数据量，普通硬做就是了，不解释了！

代码如下：

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

int main()
{
	int t,n,i,a[1000];
	float sum,num;
	scanf("%d",&t;);
	while(t--)
	{
		sum=0;
		num=0;
		scanf("%d",&n;);
		for(i=0;i<n;i++)
		{
			scanf("%d",&a;[i]);
			sum+=a[i];
		}
		sum/=n;
		for(i=0;i<n;i++)
			if(a[i]>sum)
				num++;
		printf("%2.3f%%n",100*num/n);
	
	
	}
}

发表于 更新于

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

介绍下题意，给定一个偶数 n，求 n 位 lucky tickets 的个数，lucky tickets就是 n 位数可含前导 0，前 n/2 项上数字和等于后 n/2 项上数字和。

先上一种最简单的算法，我们管它叫流氓算法，再算法分类上算穷举把！

玩笑而已。之所以这样是因为我都知道答案了，而且数据不多。

代码如下：

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

int main()
{
	int n;
	cin>>n;
	if(n==2)
		cout<<10<<endl;
	if(n==4)
		cout<<670<<endl;
	if(n==6)
		cout<<55252<<endl;
	if(n==8)
		cout<<4816030<<endl;
	if(n==10)
		cout<<432457640<<endl;
}



发表于 更新于

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

这个题，有人说是水题，其实不然，很有难度的。

介绍下题目，一组字符串，可以压缩，比如

abc
atest
atext

可以写为

abc
1test
3xt

这样说就容易理解了，就是把与上个字符串相同的部分直接用数字表示，来节约位置，问压缩后用多少字符数（尽管多位数不是一个数，但是储存算一个单位）

现开始理解错了题意，以为所有字符串公用同一个j，后来WA了好多次，才知道每一个j只与上一个字符串有关！

介绍下我的算法，定义b和c两个字符串，每次c为上一个，b为新输入的字符串，然后依次扫描。有一点我觉得比较有意思的,我原来代码是

1
2
3
for(j=0;j<strlen(b);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
/*Problem: 2334		User: awq123
**Memory: 240K		Time: 94MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	int t,i,j,temp,num=0;
	char b[256],c[256];
	scanf("%d",&t;);
	scanf("%s",c);
	num+=strlen(c);
	for(i=2;i<=t;i++)
	{
		scanf("%s",b);
		temp=strlen(b);
		for(j=0;j<temp;j++)
			if(b[j]!=c[j])
				break;
		num+=(strlen(b)-j+1);
		strcpy(c,b);
	}
	cout<<num<<endl;
}