Jove's Blog

I love what I do

发表于 更新于

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

发表于 更新于

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

题目是一种压缩算法，比如11111是5个1就写成51，222333是3个2和3个3写成3233。依次类推。利用计数记录下相连的数的个数，当不连续的时候输出，不过这个题我的方法，循环完后还要输出漏掉的一次！

代码如下：

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

int main()
{
	int t;
	char d[1005];
	scanf("%d",&t;);
	while(t--)
	{
		scanf("%s",d);
		int i,c=1;
		int len=strlen(d);
		for(i=1;i<len;i++)
		{
			if(d[i]==d[i-1])
			{
				c++;
			}
			else
			{
				printf("%d%c",c,d[i-1]);
				c=1;
			}
		}
		printf("%d%cn",c,d[i-1]);
	}

}

发表于 更新于

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

题目很简单，去掉一个最高分，去掉一个最低分，求平均分，小日本的题目还是很简单的！

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

int main()
{
	int n,d[105];
	while(cin>>n&&n;)
	{
		int sum=0;
		for(int i=0;i<n;i++)
		{
			cin>>d[i];
			sum+=d[i];
		}
		sort(d,d+n);
		sum-=d[0];
		sum-=d[n-1];
		sum/=n-2;
		cout<<sum<<endl;
	}
}

发表于 更新于

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

题目给你一些数，让你找出一个子序列，子序列计算的规则是：奇数位相加偶数位相减。要求这个子序列计算的值最大为多少！

也就是总数+奇数位-偶数位的子串；

先开始没什么思路，查阅了下解体报告，发现，我们只要找比相邻都高的数为奇数位，比相邻都底的数做偶数位就可能得到最大的值！

代码如下

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

int main()
{
	int i,n,d[150005];
	scanf("%d",&n;);
	for(i=1;i<=n;i++)
		scanf("%d",&d;[i]);
	int flag=1,sum=0;
	for(i=1;i<=n;i++)
		if(flag)
		{
			if(d[i]>=d[i+1]&&d;[i]>=d[i-1])
			{
				sum+=d[i];
				flag=0;
			}
		}
		else
		{
			if(d[i]<=d[i+1]&&d;[i]<=d[i-1])
			{
				sum-=d[i];
				flag=1;
			}
		}
	printf("%dn",sum);
}

发表于 更新于

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

题目是一个变相的汉诺塔，问4个塔至少移动多少步！

先开始没看题以为就是普通汉诺塔，然后WA了半天才发现，本来汉诺塔我们可以套用公式，但4塔的我就没办法了！多塔问题，参考了维基百科

其中这样描述的：

令f(n,k)为在有k个柱子时，移动n个圆盘到另一柱子上需要的步数，则：
对于任何移动方法，必定会先将m(1<=m<=n-1)个圆盘移动到一个中间柱子上，再将第n到第n-m个圆盘通过剩下的k-1个柱子移到目标柱子上，最后将m个在中间柱子上的圆盘移动到目标柱子上。这样所需的操作步数为2f(m,k) + f(n − m,k − 1)。

进行最优化，易得: 1958

这个递归公式适用于大于3的所有情况，但是我们只考虑4的情况，也就修改了下，具体见代码！

代码如下：

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

int main()
{
	int d[13];
	d[1]=1;
	d[2]=3;
	for(int i=3;i<=12;i++)
	{
		int min=999999;
		for(int j=1;j<i;j++)
		{
			if(min>2*d[j]+pow(2.0,(i-j))-1)
				min=2*d[j]+pow(2.0,(i-j))-1;
		}
		d[i]=min;
	}
	for(int i=1;i<=12;i++)
		printf("%dn",d[i]);
}

发表于 更新于

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

题目没什么好说的，给出了递归算法，但是单纯模拟题意，你会发现递归过多，严重超时。这里我们利用DP里的记忆搜索，开一个数组记录已经求出的值，减少递归的计算次数，单纯优化运行速度，对于这样的题OJ系统的数据是不可想象的，就算你的能运行，在OJ系统里的数据也过不了！

代码如下：

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

int map[25][25][25];

int w(int a,int b,int c)
{
	if(a<=0||b<=0||c<=0)
		return map[0][0][0]=1;
	else if(a>20||b>20||c>20)
		return map[20][20][20]=w(20,20,20);
	else if(map[a][b][cpp])
		return map[a][b][cpp];
	else if(a<b&&b;<c)
		return map[a][b][cpp]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
	else
		return map[a][b][cpp]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}

int main()
{
	memset(map,0,sizeof(map));
	int a,b,c;
	while(scanf("%d %d %d",&a;,&b;,&c;)==3&&!(a==-1&&b;==-1&&c;==-1))
		printf("w(%d, %d, %d) = %dn",a,b,c,w(a,b,c));
}

发表于 更新于

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

解释下题目，问是否能在一个字符串正顺序，或者逆顺序中，删除一些字母组成另一个字符串。

注意：正序是以’\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
/*Problem: 3302		User: awq123
**Memory: 236K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	char s[105],t[105];
	int n;
	cin>>n;
	while(n--)
	{
		cin>>t>>s;
		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++;
		}
		ps=s;
		while(1)
		{
			if(ok)
				break;
			if(*ps=='\00')
			{
				ok=1;
				break;
			}
			if(pt==t-1)
				break;
			if(*ps==*pt)
				ps++;
			pt--;
		}
		if(ok)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
}

发表于 更新于

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

题意简单，求C(n，k)的奇偶性，

我的方法不简单，但分析简单，不过今天还看到个大神的分析，让我很是佩服

我门知道C(n，k)=n!/k!/(n-k)!那么就通过分析这三项的2的阶数来分析C(n，k)的2的阶数，也就是n!的阶数<=k!的阶数+(n-k)!阶数，则为奇数。

其中n!的2的阶数求解的方法为n/2+n/4+n/8….我就是用的这个方法，

1
2
3
4
5
6
7
8
9
int y(int d)
{
	int s=0;
	for(int i=2;d/i;i*=2)
		s+=d/i;
	return s;
}


1
2
3
4
5
6
7
8
9
10
int y(int d)
{
    int s=0;
    while((d=d>>1)!=0)
	s+=d;
    return s;
}



::cpp
/*Problem: 3219        User: awq123
**Memory: 244K        Time: 32MS
**Language: C++        Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int y(int d)
{
    int s=0;
    for(int i=2;d/i;i*=2)
        s+=d/i;
    return s;
}

int main()
{
    int n,k;
    while (cin>>n>>k)
    {
        if(k>n-k)
            k=n-k;
        if(y(n)<=y(n-k)+y(k))
            cout<<1<<endl;
        else
            cout<<0<<endl;
    }
}

这个题还见到了一种大神的做法

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

int main()
{
	int n,k;
	while (cin>>n>>k)
	{
		if((k&n;)==k)
			cout<<1<<endl;
		else
			cout<<0<<endl;
	}
}


发表于 更新于

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

解释下题意，Snoopy想问下，若有n枚硬币，这n枚硬币的初始状态是任意的，则至少需要翻转几次，才能保证对于任何一种初始状态而言，都能变成n枚硬币全为正或全为反。

分析：

1：若为偶数

那么正反数目就有奇奇和偶偶两种情况，很明显奇数的翻转不适合偶数，偶数的翻转不适合奇数
例如： ○○●●●● 则翻转 2,4,6,8……次均可。
例如： ○○○○○● 则翻转 1,3（先将●翻为○，再将任一个○翻两下）,5,7……次均可。

2：若为奇数
若所有硬币一开始就同一面向上那么翻转次数一定为偶数，那么对于其他情况，我们必须翻转偶数面来完成目标
例如： ○○○○●●● 则翻转4,6,8,10……次均可，其中最小为4。要保证对7枚硬币的任意初始状态都可行，则最小应为 7-1=6
这样我们就能推出，至少应该翻转n-1次

代码如下：

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

int main()
{
	int n;
	while (cin>>n&&n;)
	{
		if (n%2==0)
			cout<<"No Solution!"<<endl;
		else
			cout<<n-1<<endl;	
	}
}