Jove's Blog

I love what I do

发表于 更新于

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

题目要求我们求组合数
公式如下

其中我们可以优化下算法，因为

这样k和n-k就取小的计算就是了，其中fixed指不使用科学计数法，其实用printf输出方便的多

代码如下：

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

int main()
{
	double n,k,i,ans;
	while(cin>>n>>k&&n;+k)
	{
		ans=1;
		if(k>n-k)
			k=n-k;
		for(i=n;i>=n-k+1;i--)
			ans*=i;
		for(i=1;i<=k;i++)
			ans/=i;
		cout<<fixed<<setprecision(0)<<ans<<endl;
	}
}

发表于 更新于

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

这个题给我们了字符串的对应关系，要求我们根据变换顺序转换n次输出字符串，如：
3
2 1 3
1 abc
那么就是abc经过一次转换，根据对应关系得bac。

我们来分析下题目的例子
1 2 3 4 5 6 7 8 9 10
4 5 3 7 2 8 1 6 10 9
那么原来第一位上的数经过一次变换就到了第四位上，其他同理，我们要是纯模拟，一定会超时。我们来观察下数列变化，其实变化时一个循环，只是每一位的循环长度不同，
1—>4—>7—>1
2—>5—>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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/***************************************
Problem: 1026		User: awq123
Memory: 244K		Time: 141MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int key[205],t[205];
	int n,m,i,j;
	char ch[500],ans[500];
	while(cin>>n&&n;)
	{
		for(i=1;i<=n;i++)//输入对应关系
			cin>>key[i];
		for(i=1;i<=n;i++)//测量该位循环长度
		{
			int temp=key[i];
			int count=1;
			while(temp!=i)//是否循环
			{
				temp=key[temp];
				count++;
			}
			t[i]=count;
		}
		while(cin>>m&&m;)
		{
			getchar();//这句一定不能掉，我调试的时候发现ch前多读入了一个空格。
			cin.getline(ch,n+1);
			int len=strlen(ch);
			for(i=len;i<n;i++)//补齐位数不够的空格
				ch[i]=' ';
			ch[n]='\00';//加上结束符
			for(i=1;i<=n;i++)//处理字符串
			{
				int temp=i;
				for(j=1;j<=m%t[i];j++)//寻找对应关系
					temp=key[temp];
				ans[temp-1]=ch[i-1];
			}
			ans[n]='\00';//加上结束符
			cout<<ans<<endl;
		}
		cout<<endl;//这句害我wa了半天
	}
}

发表于 更新于

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

解释下题意，输入文件系统，dir*就是定义一个文件夹，]就是结束这个文件夹的定义，其中我们观察第2个例子可以看出，每个文件夹里的文件要排序输出，这点要注意

查阅了几篇文章，看到个用vector做的，其中利用了string，不禁感叹，用string表示字符串数组真实太方便了，其中排序，量长度，大小都有函数，总的来说思路算是DFS但是不是搜索，利用递归输入文件，每一次输入新的文件夹，递归输入一次，正好符合题目的输入格式，输出的时候也是，只不过多了个n表示数据层次，方便输出分隔符，也就是|。具体思路看注释把！

至于为什么有两个string头文件，因为我用g++编译的但是用的c++提交，其中这个是没有c的！

代码如下：

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

struct node//文件夹结构体
{
	vector<string> file;//包含的文件
	vector<node> dir;//包含的文件夹
	string name;//文件夹的名字
};

node root;//这句可以不要但是好像会多花点时间

bool end=0;//标记是否结束

void fileinput(node& now)//输入文件系统
{
	string temp;
	while (1)
	{
		cin>>temp;
		if (temp[0]=='#')
		{
			end=1;
			break;
		}
		else if(temp[0]=='f')//如果是文件推入文件序列
			now.file.push_back(temp);
		else if(temp[0]=='d')//如果是文件夹
		{
			node d;//定义一个新的结构体
			d.name=temp;//新文件夹名称
			fileinput(d);//输入新文件夹内容
			now.dir.push_back(d);//将新文件夹推入文件夹序列
		}
		else
			break;
	}
	sort(now.file.begin(),now.file.end());//对文件夹里的文件名称进行升序排列
}

void fileprint(node& now,int n)
{
	int i,j;
	for(i=0;i<n;i++)//输入包含的文件夹名
		cout<<"|     ";
	cout<<now.name<<endl;
	for(i=0;i<(int)now.dir.size();i++)//搜索输出子目录
		fileprint(now.dir[i],n+1);
	for(i=0;i<(int)now.file.size();i++)//输出包含文件名
	{
		for(j=0;j<n;j++)
			cout<<"|     ";
		cout<<now.file[i]<<endl;
	}
}

int main()
{
	//freopen("Input.txt", "r", stdin);
	int i;
	for(i=1;;i++)
	{
		node root;//这句一定不能掉，算是root的初始化
		root.name="ROOT";
		fileinput(root);
		if(end)
			break;
		cout<<"DATA SET "<<i<<":"<<endl;
		fileprint(root,0);
		cout<<endl;
	}
}

发表于 更新于

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

高精度加法，要求输出所有输入的数的和；

100位的数，无法用变量储存，解题方法不难，简单模拟加法的过程；也就是满10进位的方法，我们利用数组，储存每一位数，然后由个位开始相加在加上上一位的进位数，得出这个位上的数，和下一个进位数，其中有一点需要注意，也是我一直WA的一个地方，

1
2
3
num[num[0]+1]+=jw;


我用的数组的第一位数储存，字符串长度，

代码如下：

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

int main()
{
	int i,j,jw,sum,num[105];
	char str[105];
	memset(num,0,sizeof(num));
	while(1)
	{
		cin>>str;
		if(strcmp(str,"0")==0)
			break;
		num[0]=strlen(str);
		jw=0;sum=0;
		for(j=1;j<=num[0];j++)
		{
			sum=num[j]+str[num[0]-j]-'0'+jw;
			num[j]=sum%10;
			jw=sum/10;
		}
		num[num[0]+1]+=jw;
	}
	int flag=0;
	for(i=104;i>=1;i--)
	{
		if(num[i]!=0)
			flag=1;
		if(flag==1)
			cout<<num[i];
	}
	cout<<endl;
}

发表于 更新于

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

解释下题意，一个由nc格字母组成的字符串，求有多少种长度为n的子串！比如
“daababac”就有5种长度为3的字符串”daa”; “aab”; “aba”; “bab”; “bac”

分析下题意，要求分辨子串是否不同，纯字符判断会花很多时间，我们构建一个nc进制的数列，将所有字符转换为0，1，2。。nc-1的数字，求每个子串对应的值是否相同就可以间接反映子串是否相同，

其中ch为字符串，used记录是否出现过，hash分配数字，

代码如下

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

bool used[20000000];
int hash[300];
char ch[1000000];
int main()
{
	int n,nc,count=0,num=0;
	memset(used,0,sizeof(used));
	memset(hash,-1,sizeof(hash));
	scanf("%d%d%s",&n;,&nc;,ch);
	int len=strlen(ch);
	for(int i=0;i<=len-n;i++)
	{
		int sum=0;
		for(int j=i;j<i+n;j++)
		{
			if(hash[ch[j]-'a']==-1)
				hash[ch[j]-'a']=count++;
			sum=nc*sum+hash[ch[j]-'a'];
		}
		if(used[sum]==0)
		{
			used[sum]=1;
			num++;
		}
	}
	cout<<num<<endl;
}

发表于 更新于

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

将2进制的ip地址转换为10进制，每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
/***************************************
Problem: 2105		User: awq123
Memory: 248K		Time: 0MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int d[8],i,j,t,n;
	char temp;
	cin>>t;
	while(t--)
	{
		for(i=0;i<4;i++)
		{
			n=0;
			for(j=7;j>=0;j--)
			{
				cin>>temp;
				d[i]=temp-'0';
				n+=pow(2.0,j)*d[i];
			}
			if(i==0)
				cout<<n;
			else
				cout<<"."<<n;
		}
		cout<<endl;
	}
}

发表于 更新于

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

先开始一天，每天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: 2000		User: awq123
Memory: 248K		Time: 16MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int n,m,i,sum;
	while(cin>>n&&n;)
	{
		sum=0;
		m=0;
		for(i=1;sum<=n;i++)
		{
			m+=i*i;
			sum+=i;
		}
		m-=(sum-n)*(i-1);
		cout<<n<<" "<<m<<endl;
	}

}

发表于 更新于

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

给出每段时间的速度，求出长度，分段计算就是了

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

int main()
{
	int n,i,d[11][2],sum;
	while(cin>>n&&n;!=-1)
	{
		d[0][1]=0;
		sum=0;
		for(i=1;i<=n;i++)
		{
			cin>>d[i][0]>>d[i][1];
			sum+=d[i][0]*(d[i][1]-d[i-1][1]);
		}
		cout<<sum<<" miles"<<endl;

	}

}

发表于 更新于

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

最近光做水题！

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

int main()
{
	int d[5],i,t;
	cin>>t;
	while(t--)
	{
		for(i=0;i<4;i++)
			cin>>d[i];
		if(d[1]-d[0]==d[2]-d[1]&&d;[2]-d[1]==d[3]-d[2])
			d[4]=d[3]+d[3]-d[2];
		if(d[1]/d[0]==d[2]/d[1]&&d;[2]/d[1]==d[3]/d[2])
			d[4]=d[3]*d[3]/d[2];
		for(i=0;i<5;i++)
			cout<<d[i]<<" ";
		cout<<endl;
	}

}

发表于 更新于

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

根据公式计算输出就是了，不过这个公式是求e的，还找了下e的计算原理！

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

int main()
{
	printf("n en- -----------n0 1n1 2n2 2.5n");
	double s=2.5,t=6;
	int a=3;
	while(a<10)
	{
		printf("%d %.9lfn",a,s=s+1/t);
		t*=++a;
	}
}