POJ 1002

发表于

poj 1002题

OUTPUT：

输入值为: TEL number
输出值为: TEL tel.frequence

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
#include<iostream>
#include<stdlib.h>
#include<cstring>
using namespace std;
int main(){
	int num;
	string str="ITSEASY";
	string st;
	int n=0;
	int i=0;
	int j=0;
	for(i=0,j=0;i<str.length();i++){
	if(str[i]=='-'){}
	else if(str[i]>='A'&&str[i]<='Z'){
		if(str[i]<='P'){
		st+=(str[i]-'A')/3+2+'0';
		j++;}
		else if(str[i]>='P'){
		st+=(str[i]-'A'-1)/3+2+'0';
		j++;
		}
	}else if(str[i]>='0'&&str[i]<='9'){
		st+=str[i];
		j++;
	}
	}
	cout<<st<<endl;
}

完成了基本的读取，剩下的很容易。当然这里题目给挖了个坑，我也是深陷不能自拔，数据中没有Q这个映射关系
下面写一个正确答案，但是答案提示是Time Limit Exceeded

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
#include<iostream>
#include<string>
#define MAX 100000
using namespace std;
int main(){
	int num;
	string str;
	string st;
	int n=0;
	int i=0;
	int j=0;
	int k=0;
	int m=0;
	cin>>n;
	string s[MAX];
	string t[MAX],q[MAX];
	int freq[MAX];
	while(k<n){
	cin>>str;
	for(i=0,j=0;i<str.length();i++){
		if(j==3) {
		st+='-';
		j++;}
	if(str[i]=='-'){
	}else if(str[i]>='A'&&str[i]<='Z'){
			if(str[i]<='P'){
			st+=(str[i]-'A')/3+2+'0';
			j++;
			}else if(str[i]>='P'){
			st+=(str[i]-'A'-1)/3+2+'0';
			j++;
			}
	}else if(str[i]>='0'&&str[i]<='9'){
		st+=str[i];
		j++;
	}
	}
	s[k]=st;
	str.clear();
	st.clear();
	k++;
	}
	t[0]=s[0];
	k=1;
	freq[0]=1;
	for(i=1;i<n;i++){
		for(j=0;j<k+1;j++){
			if(s[i]==t[j]){
				freq[j]+=1;
				break;
			}else if(j==k){
				k++;
				t[k]=s[i];
				freq[k]=1;
				m++;
				break;
			}
		}
	}
int z=0;
	for(j=0;j<=k;j++){
		if(freq[j]>=2){	
		q[z]=t[j];
		q[z]+=' ';
		q[z]+=(freq[j]+'0');
		z++;
		}
	}
for(i=0;i<z;i++){
	for(j=0;j<z-i;j++){
		if(q[j]>q[j+1]){
			string temp=q[j];
			q[j]=q[j+1];
			q[j+1]=temp;			
		}
	}
}
for(j=0;j<=z;j++){
	cout<<q[j]<<endl;
}
}

这段答案始于我忘记题设中有排序这个问题，加上排序之后导致程序冗长而且超出时间限制.

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
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<string>
#define MAX 100000
using namespace std;
void Qsort(string a[],int low,int high){
	if(low>=high){
		return;
	}
	int first=low;
	int last=high;
	string key=a[first];
	while(first<last){
		while(first<last&&a[last]>key){
			--last;
		}
		a[first]=a[last];
		while(first<last&&a[first]<=key){
			++first;
		}
		a[last]=a[first];
	}
	a[first]=key;
	Qsort(a,low,first-1);
	Qsort(a,first+1,high);
}
int main(){
	int num;
	string str;
	string st;
	int n=0;
	int i=0;
	int j=0;
	int k=0;
	int m=0;
	cin>>n;
	string s[MAX];
	string t[MAX],q[MAX];
	int freq[MAX];
	while(k<n){
	cin>>str;
	for(i=0,j=0;i<str.length();i++){
		if(j==3) {
		st+='-';
		j++;}
	if(str[i]=='-'){
	}else if(str[i]>='A'&&str[i]<='Z'){
			if(str[i]<='P'){
			st+=(str[i]-'A')/3+2+'0';
			j++;
			}else if(str[i]>='P'){
			st+=(str[i]-'A'-1)/3+2+'0';
			j++;
			}
	}else if(str[i]>='0'&&str[i]<='9'){
		st+=str[i];
		j++;
	}
	}
	s[k]=st;
	str.clear();
	st.clear();
	k++;
	}
	t[0]=s[0];
	k=1;
	freq[0]=1;
	for(i=1;i<n;i++){
		for(j=0;j<k+1;j++){
			if(s[i]==t[j]){
				freq[j]+=1;
				break;
			}else if(j==k){
				k++;
				t[k]=s[i];
				freq[k]=1;
				m++;
				break;
			}
		}
	}
int z=0;
	for(j=0;j<=k;j++){
		if(freq[j]>=2){	
		q[z]=t[j];
		q[z]+=' ';
		q[z]+=(freq[j]+'0');
		z++;
		}
	}
Qsort(q,0,z); 
for(j=0;j<=z;j++){
	cout<<q[j]<<endl;
}
}

用快速排序对程序进行缩减，然而并不能解决之前的问题。
关于这个问题我想不继续去续写了，关于本题有几点内容需要反思和思考：
1.C++的操作不熟练，在本机编译成功而提交上去之后编译失败因为自己对C版本认识欠缺。
2.审题问题，关于题中Q，以及本身缺失排序导致结果错误。
3.全程使用字符串操作，不可避免的使数据量上升之后导致超时。
4.多余变量设置复杂。
在参考了网上诸多答案之后，以及向各位大神请教，对代码的改进方案有些许认识：
1.使用整形变量进行操作，可以提高运算效率。
2.使用一个新建的函数完成A-Y的映射关系。
3.将整个算法设计思路明确之后进行计算。。
现阶段还不是很成熟，慢慢去练吧。