Jove's Blog

I love what I do

发表于 更新于

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

标准二叉生成树，输入一个数，求以这个数为根的最边上两个数；上图

我们来看图分析，这是个标准BST图，简单分析下，我们可以轻松的看出所有的奇数都在第一行，这点由利于提升算法的速度省去一些时间，主要来看每个节点，因为每个节点都有两个分叉，那么这个数因式分解后有几个2这个数就再第几行，然后看一个节点的数等于两边最远的两个数和的一半，还有同一行的数，与最远数的差距，同最左边的一样，比如题目中的10离9差1，其实同一行最左边的2离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
/*Problem: 2309		User: awq123
**Memory: 252K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
	long long int t,m,n;
	int count;
	cin>>t;
	while(t--)
	{
		cin>>m;
		n=m;
		count=0;
		while(n%2==0)
		{
			n/=2;
			count++;
		}
		if(count==0)
			cout<<m<<" "<<m<<endl;
		else
			cout<<m-(long long int)pow(2.0,count)+1<<" "<<m+(long long int)pow(2.0,count)-1<<endl;
		
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <math.h>
using namespace std;
int main(){
	int nCase;
	scanf("%d",&nCase;);
	while(nCase--){
		int n;
		scanf("%d",&n;);
		int k=n&(-n);
		k--;
		printf("%d %dn",n-k,n+k);	
	}
	return 0;
}

发表于 更新于

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

一早上起来，水一把！

a小于b或者ab奇偶性不同时输出impossible其他输出和的一半，差的一半

代码如下：

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

int main()
{
	int t,a,b,m,n;
	cin>>t;
	while(t--)
	{
		cin>>a>>b;
		m=(a+b)/2;
		n=(a-b)/2;
		if(a<b||(a+b)%2==1)
			cout<<"impossible"<<endl;
		else
			cout<<m<<" "<<n<<endl;
	}
}

发表于 更新于

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

一个博弈的题目，要求每次从多的里面拿少的倍数的棋子直到最后拿到0就算输。

一个关键的转折点a/b>1，谁碰到这个点就能赢，代码中排除几种特殊情况，既a＝b的情况，至于gcd函数就是求多少次会出现转折点！

代码如下：

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

int gcd(int n,int m)
{
	int i=1;
	while(i++)
	{
		if(n<m)
			{int tmp=m;m=n;n=tmp;}  
		if(n/m>1)
			break;
		n-=m;
		if(m==0)
			break;
	}
	return i;
}


int main()
{
	int a,b;
	while(cin>>a>>b&&a;&&b;)
	{
		if(a==b)
			cout<<"Stan wins"<<endl;
		else if(gcd(a,b)%2)
			cout<<"Ollie wins"<<endl;
		else
			cout<<"Stan wins"<<endl;
	}
}


发表于 更新于

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

这个题很熟悉书上就有，输出一个数写成两个素数的和的形式；

看到题的时候就可以想到，如果针对每一次输入去判断素数会很费时间，那么我们先用一个数组去判断素数，再统一运算。

讲下我的算法，由小到大，依次判断，如果这个数为素数，那么它和任意数的乘积都不是素数，依次推出所有的情况。

后面的不说了，没什么好说的！

对了，为什么我没有判断，不存在的情况也能过？不是应该加个else吗？这是因为，no else，每一个数都能写成两个素数的形式，这是哪个老家伙说的啊？不是很记得了！

代码如下：

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

int main()
{
	int n[1000000],i,j,t;
	memset(n,0,sizeof(n));//0是1不是
	for(i=2;i<1000000;i++)
		if(n[i]==0)
			for(j=2;i*j<1000000;j++)
				n[i*j]=1;
	while(cin>>t&&t;)
	{
		for(i=3;i<=t/2;i+=2)
			if(n[i]==0&&n;[t-i]==0)
			{
				cout<<t<<" = "<<i<<" + "<<t-i<<endl;
				break;
			}
	}
}

发表于 更新于

放假快一半的时间了，自己的就业理想算是没戏了，妈不是我不去是真的找不到短工做啊！

不过放假，在家学习了不少算法知识，acm也算稍微入门了点，看看自己小站，满满都是解题报告，我了个去，是不是最近太关注acm了，其实平常有看新闻啊，有些有价值的我也抄过来，现在才知道，转载写明出处，是这么有素质的事。

每天9点起12点睡，妈妈都说我懒了，呵没办法，早上这么凉快，不想起来啊，

起来就想做几个水题热下身，哈哈，不过有些题真麻烦，一想就是一天，没有解题报告的，错在哪都不知道，还有这个英语。。。。有待提高。

简单说生活就是简洁，充实了，希望上学也能充实的过下去，对了今天星期四了，明天火影特别版哦，呵呵。期待！

说实话思科的每怎么看，看不进啊，上学了找彪一起看，下学期主要重点放在英语上！加油了！

发表于 更新于

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

解释下题意，给出一个最多13个数的序列，从其中抽出6个数，输出所有的可能序列，按顺序输出。

查了一些资料，最好的方法就是DFS了，平时自己独立做DFS少，就当练习下了。其实我更觉得这样的是简单的递归，也不全算DFS吧。

我的思路是这样的每个数有两种情况，也就是取它和不取它，定义一个函数void dfs(int d,int p)，其中d代表已经取的数目，p代表查看过的数目！这样针对每个情况我们调用两次，分别是取它和不取它，标准dfs其实在取它算完后应该回溯到原样，但是不取它会覆盖这一条数据，也就省了这一步了。

这个题我在结束条件上纠结了下，现开始我用的d==6然后最后一列就不正确了，其实我自己有时利用数组的a[1]做第一个数据，就会总犯一些错误，一些细节的把握不好，最近做题都没有用调试，1是不方便在linux下用，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
27
28
29
30
31
32
33
34
35
36
37
38
/*Problem: 2245		User: awq123
**Memory: 252K		Time: 32MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
using namespace std;

int n,i,j,a[14],b[7];

void dfs(int d,int p)//d表示已经搜索到的数也就是深度，p表示搜索过的数
{
	if(p>n+1)//搜索完，结束
		return;
	if(d==7)//已搜索到6个数，输出
	{
		for(int m=1;m<=6;m++)
			cout<<b[m]<<" ";
		cout<<endl;
		return;
	}
	b[d]=a[p];
	dfs(d+1,p+1);//如果搜索到的结果
	dfs(d,p+1);//没搜索到的结果，b[dep]会自己覆盖
}

int main()
{
	//freopen("input.txt", "r", stdin); 
	while(cin>>n&&n;)
	{
		for(i=1;i<=n;i++)
			cin>>a[i];
		dfs(1,1);
		cout<<endl;
	}
}

发表于 更新于

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

题目给出三个点坐标，求经过三个点的圆的周长。

纯数学问题，没什么好说的

其中fixed是用来输出纯浮点，也就是不使用科学计数法，若要使用科学计数法应该使用scientific

代码如下：

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

double square(double x)
{
	return x*x;
}
int main()
{
	double X1, X2, X3, Y1, Y2, Y3;
	double PI = 3.141592653589793;
	while(cin>>X1>>Y1>>X2>>Y2>>X3>>Y3)
	{
		double a = sqrt(square(X1 - X2) + square(Y1 - Y2));
		double b = sqrt(square(X1 - X3) + square(Y1 - Y3));
		double c = sqrt(square(X2 - X3) + square(Y2 - Y3));
		double p = (a + b + c) / 2;
		double s = sqrt(p * (p - a) * (p - b) * (p - c));
		double r = a * b * c / (s * 4);
		cout<<fixed<<setprecision(2)<<2 * PI * r<<endl;
	}
}

发表于 更新于

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

此题为随机博弈题目。随机博弈指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：
1〉每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子；
2〉如果谁取到最后一枚石子就胜

也就是尼姆博弈（Nimm Game）这种博弈的最终状态是：最后剩下一堆石子，当前取石子的人一次取完剩下的全部石子获胜。当石子剩下两堆，每堆1颗的时候，当前取的人显然必败；再来讨论一种情况，当石子剩下两堆，其中一堆只剩下1颗，另一堆剩下多于1颗石子时，当前取的人只需将多于1颗的那一堆取到剩余1颗，则局面变为刚才提到的必败局面。这个过程就是当前取石子的人如果有必胜策略，那么就迫使局面由必胜局面转化到必败局面，也就是说如果当前的局面是必败局面，那么经过2次取，局面又回到必败局面。无穷下降法不同于反证法之处也在此：在“下降”的过程中，状态一直保持不变（在证明费马猜想n=4的情形时，状态就是该三元组是方程的解）；而在随机博弈过程中，状态即局面，下降的是石子数目，由于石子总数目一直在减少，因此最终会“下降”到终极必败状态：最后一颗石子已经被胜者拿走，当前没有石子剩余。现在的问题是：
1〉确定一个方法（或者称之为一个从某一局面映射集合{必胜局面，必败局面}的函数），能够快速判断出当前局面是否为必胜（必败）局面；
2〉是否存在一种满足规则的转化状态方法（或者称之为一个从必胜局面映射到必败局面的函数），满足只要当前不是必败局面，取一次后均可以转化到必败局面。

如果仅仅是两堆石子，那么上述两个问题很好解决：
1〉当两堆石子数目相等的时候，当前局面为必败局面，否则为必胜局面，显然，两堆均为0颗是满足这个方法的；
2〉如果当前局面是必胜局面，那么从石子较多的那一堆里面取，使得两堆石子数相等，这样便转化到了必败局面。

然而，对多于两堆石子，1〉可以照旧，但是这样一来2〉远远没有这么简单，因为不太可能取后使得所有堆数目都一样（除非除了石子最多的一堆之外其它所有堆石子数目都相等）。因此需要找一组更加有效的方法，有个叫张一飞的人作过这个研究，他想到的方法是这样的：
1〉把所有堆的石子数目用二进制数表示出来，当全部这些数按位异或结果为0时当前局面为必败局面，否则为必胜局面；
2〉（定理0）一组自然数中必然存在一个数，它大于等于其它所有数按位异或的结果。因此在必胜局面下，因为所有数按位异或的结果是大于零的，那么通过一次取，将这个（大于其它所有数按位异或的结果的）数下降到其它所有数按位异或的结果，这时局面就变为必败局面了。

算法转载自http://hi.baidu.com/lewutian/blog/item/8184f3d9a23d932710df9b34.html

代码如下：

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

int main()
{
	int n,i,sum;
	long int a[23];
	while(cin>>n)
	{
		for(i=0; i<n; i++)
			cin>>a[i];
		sum=a[0];
		for(i=1; i<n; i++)
			sum=sum^a[i];
		if(sum==0)
			cout<<"No"<<endl;
		else
			cout<<"Yes"<<endl;
	}
}

发表于 更新于

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

一个新的石头剪刀布游戏，大概的玩法是，大家选择一个，然后坐成一圈，任意选择一个人，逆时针比较，输的淘汰，平局算这个人赢，问可能由多少人可以赢！

算法不难，不是我子集想出来的，比如，由F C S那么这三个可以通过F可以让C先打败S在打败C，其他同理。

如果却少一种，比如只有F C那么C必输，每一个F都可能赢，其他同理，

如果缺少两种，都是一样的，那么谁都能赢！

由于三种可以交换，我在判断是时候就用了个小技巧，没有一一判断，不过先开始没有加break，导致输出了三遍！

题目不难，思路一说就简单的，

代码如下：

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

int main()
{
	int n,i,f,c,s;
	char a[1001];
	while(cin>>n)
	{
		f=0;c=0;s=0;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			switch(a[i])
			{
				case 'F':f++;break;
				case 'C':c++;break;
				case 'S':s++;break;
			}
		}
		for(i=0;i<3;i++)
		{
			if(f&&c;&&s;)
			{
				cout<<n<<endl;
				break;
			}	
			else if(f&&c;==0&&s;==0)
				cout<<n<<endl;
			else if(f&&c;&&s;==0)
				cout<<f<<endl;
			int temp=f;
			f=c;c=s;s=temp;
		}
	}
}

发表于 更新于

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

这个题意简单，我没看翻译都看懂了，哈哈，玩笑而已，英语还要提高！

题目要求给出一个数分解成由2的幂次相加的形式，问由多少种分解方式。

我们来分析下，n=1和n=2是很容易判断，为1和2。

n为基数的时候，相当于把n-1的排列每个都加上1，n为偶数的时候，可以看成两种形式，也就是n-2的排列加上两个1，或者所有的数都是偶数的情况，这种情况的数目既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
27
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int dj(int n)
{
	if(n==1||n==2)
		return n;
	else if(n%2==1)
		return dj(n-1);
	else
		return dj(n-2)+dj(n/2);
}

int main()
{
	//freopen("input.txt", "r", stdin); 
	int n;
	cin>>n;
	cout<<dj(n);

}



不过还是WA了几次，因为output种的这样一句话

Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

自然数据会大于这个数，不过我认为int的情况也可能由问题，不过果料儿也就没多想，数据比较好把！

最终代码如下：

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

int main()
{
	//freopen("input.txt", "r", stdin); 
	int n,a[1000001];
	for(n=1;n<=1000000;n++)
	{
		if(n==1||n==2)
			a[n]=n;
		else if(n%2==1)
			a[n]=a[n-1];
		else
			a[n]=a[n-2]+a[n/2];
		if(a[n]>=1000000000)
			a[n]%=1000000000;
	}
	cin>>n;
	cout<<a[n]<<endl;
}