Jove's Blog

I love what I do

发表于 更新于

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

发表于 更新于

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

题目问，一共有几块池塘，8方向相连就算一块！

简单DFS，我用used数组记录每一块，若发现新的一块就编号，然后从这个点开始8方向深搜，有相连还没编号的一起编上号，看左后一共编了几个号！

代码如下：

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

int n,m,used[105][105],dir[16]={1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1};
char map[105][105];

void dfs(int i,int j)
{
	for(int k=0;k<16;k+=2)
	{
		int p=i+dir[k];
		int q=j+dir[k+1];
		if(0<=p&&p;<n&&0<=q&&q;<m)//不出界
		{
			if(map[p][q]=='W'&&used;[p][q]==0)//若没编号
			{
				used[p][q]=used[i][j];
				dfs(p,q);//由新的点开始继续深搜
			}
		}
	}
}

int main()
{
	int i,j,t;
	t=1;
	memset(used,0,sizeof(used));
	memset(map,'.',sizeof(map));
	cin>>n>>m;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			cin>>map[i][j];
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			if(map[i][j]=='W'&&used;[i][j]==0)
			{
				used[i][j]=t++;//若发现没编号的
				dfs(i,j);
			}
		}
	cout<<t-1<<endl;
}

发表于 更新于

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

题意让我们判断所给的字符串是否满足所给的条件：
1，至少有一个元音字母
2，不能出现三个元音连续或者三个辅音连续
3，除了ee和oo不能出现两格字母连续

我用j1，j2，j3分别判断这三个条件，其中j2的if语句还是写得有点特色的，看是否三个或和三个且的值一样，嘿嘿

具体见代码：

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

char ch[25];
int len;

bool y(char q)
{
	if (q=='a'||q=='e'||q=='i'||q=='o'||q=='u')
		return 1;
	return 0;
}

bool j1()
{
	for(int i=0;i<len;i++)
		if(y(ch[i]))
			return 1;
	return 0;
}

bool j2()
{
	if(len<3)
		return 1;
	for(int i=0;i<=len-3;i++)
		if((y(ch[i])&&y;(ch[i+1])&&y;(ch[i+2]))==(y(ch[i])||y(ch[i+1])||y(ch[i+2])))
			return 0;
	return 1;
}

bool j3()
{
	if(len<2)
		return 1;
	for(int i=0;i<=len-2;i++)
		if((ch[i]==ch[i+1])&&ch;[i]!='e'&&ch;[i]!='o')
			return 0;
	return 1;
}

int main()
{
	while(cin>>ch)
	{
		if(strcmp(ch,"end")==0)
			break;
		len=strlen(ch);
		cout<<"<"<<ch<<"> is ";
		if(!(j1()&&j2;()&&j3;()))
			cout<<"not ";
		cout<<"acceptable."<<endl;
	}
}