PAT乙1013和1014

发表于 | 分类于

1013 数素数

题目

令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。

输入格式：

输入在一行中给出M和N，其间以空格分隔。

输出格式：

输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。

输入样例：
5 27
输出样例：
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

思路

我的思路是，先写一个用来判断是否为素数的函数，然后再在自然数中查找。符合第m到第n个的素数就加入vector，之后再根据要求的格式进行输出

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
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;

bool judge(int n){
	double sqr = sqrt(n);
	int divider = 2;
	bool result = true;
	while(divider <= sqr){
		if(n%divider == 0){
			result = false;
			break;
		}
		divider++;
	}
	return result;
}

int main(){
	int m, n;
	scanf("%d%d", &m, &n);
	int cnt = 0;
	vector<int> prime;
	for(int i=2;;i++){
		if(judge(i) == true){
			cnt++;
			if(cnt >= m && cnt <= n){
				prime.push_back(i);
			}
		}
		if(cnt > n){
			break;
		}
	}
	
	int ct = 0;
	for(int i=0; i<prime.size(); i++){
		cout<<prime[i];
		if((i+1)%10 != 0 && i != prime.size()-1)
			cout<<' ';
		else
			cout<<endl; 
//		ct++;
//		if(ct == 1){
//			printf("%d", prime[i]);
//		}
//		else if(ct == 10){
//			printf(" %d\n", prime[i]);
//			ct = 0;
//		} 
//		else{
//			printf(" %d", prime[i]);
//		}
//		if(i == prime.size()-1){
//			printf("\n");
//		}
	}
//	if(ct != 10){
//		printf("\n");
//	}
	return 0;
}

上面的注释代码暴露了我的一个缺点，喜欢没事设置变量。。。从上面的代码段可以看到，我原先所设置的ct变量，完全可以用i来判断，这样也避免了之后因为i=10的时候而导致的问题。嗯，还有，要注意临界值，边界值！（二水马原话，这些点都是得特殊考虑的）

1014 福尔摩斯的约会

题目

大侦探福尔摩斯接到一张奇怪的字条：“我们约会吧！ 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”。大侦探很快就明白了，字条上奇怪的乱码实际上就是约会的时间“星期四 14:04”，因为前面两字符串中第1对相同的大写英文字母（大小写有区分）是第4个字母’D’，代表星期四；第2对相同的字符是’E’，那是第5个英文字母，代表一天里的第14个钟头（于是一天的0点到23点由数字0到9、以及大写字母A到N表示）；后面两字符串第1对相同的英文字母’s’出现在第4个位置（从0开始计数）上，代表第4分钟。现给定两对字符串，请帮助福尔摩斯解码得到约会的时间。

输入格式：

输入在4行中分别给出4个非空、不包含空格、且长度不超过60的字符串。

输出格式：

在一行中输出约会的时间，格式为“DAY HH:MM”，其中“DAY”是某星期的3字符缩写，即MON表示星期一，TUE表示星期二，WED表示星期三，THU表示星期四，FRI表示星期五，SAT表示星期六，SUN表示星期日。题目输入保证每个测试存在唯一解。

输入样例：
3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm
输出样例：
THU 14:04

思路

哎，这一题的题目真的是，出得太模棱两可了，好坑啊！题目中的相同的字母或数字，是指在两个字符串中对应位置相同的，而不是像我以为的是只要出现了相同的字母或数字就当做一对。这一题提交了十几次… 都是被这个地方给坑的，三个匹配的相同对都要求是在位置上来匹配，真的题目，如果能说清楚就好了~

先附上未删掉注释的乱七八糟的代码：

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
95
96
97
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

/*
大坑题！相同的英文字母，是指字符串对应相同的位置上，字母也相同。。。 
*/

//常见字符的ASCII码值如下：空格的ASCII码值为32；数字0到9的ASCII码值分别为48到57；
//大写字母"A"到"Z"的ASCII码值分别为65到90;小写字母"a"到"z"的ASCII码值分别为97到122。

string week(char c){
    switch(c){
        case 'A': return "MON"; break;
        case 'B': return "TUE"; break;
        case 'C': return "WED"; break;
        case 'D': return "THU"; break;
        case 'E': return "FRI"; break;
        case 'F': return "SAT"; break;
        case 'G': return "SUN"; break;
    }
}

int char2num(char c){ //为了转小时而设置的,A对应10点 
    if(c >= '0' && c <= '9'){
        return c-'0';
    }
    else if(c >= 'A' && c <= 'N'){
        return c-'A'+10; //!!!
    }
    return -1;
}

int main(){
    string a1,a2,b1,b2;
    cin >> a1 >> a2 >> b1 >> b2;
    string result_week;
    int hour;
    int flag = 0; //前两对字符串判断标志 
    int j_index;
    for(int i=0; i<a1.length(); i++){
        if(flag == 0){
            /*
            if(a1[i]>='A' && a1[i]<='G'){ //找到第一个相同的大写字母 
                for(int j=0; j<a2.length(); j++){
                    if(a1[i] == a2[j]){
                        result_week = week(a1[i]) + " ";
                        flag = 1;
                        j_index = j;
                        break;
                    }
                }
            }
            */
            if((a1[i]>='A' && a1[i]<='G') && a1[i] == a2[i]){
                result_week = week(a1[i]) + " ";
                flag = 1;
                //j_index = i+1;
                //j_index = i;
                // break;
            }
            
        }
        else if(flag == 1){ //找第二对相同的字符 
        
//          if((a1[i]>='A'&&a1[i]<='N') || a1[i]>='0'&&a1[i]<='9'){
            if(char2num(a1[i])>=0 && a1[i]==a2[i]){
//              for(int j=j_index; j<a2.length(); j++){
//                  if(a1[i] == a2[j]){
//                      hour = char2num(a1[i]);
////                        cout << hour << endl;
////                        cout << a1[i] << endl;
//                      flag = 2;
//                      break;
//                  }
//              }
                hour = char2num(a1[i]);
                break;
//              flag = 2;
//              break;
            }
        }
        //if(flag == 2) break;      
    }
    int minute;
    for(int i=0; i<b1.length(); i++){
        //也是在相同位置上的 
        if(((b1[i]>='a'&&b1[i]<='z')||(b1[i]>='A'&&b1[i]<='Z')) && (b1[i]==b2[i])){
            minute = i;
            break; 
        }
    }
    cout << result_week;
    printf("%d%d:",hour/10,hour%10);
    printf("%d%d\n",minute/10,minute%10);
}

把删掉后的简短代码贴上来：

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
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
string week(char c){
    switch(c){
        case 'A': return "MON"; break;
        case 'B': return "TUE"; break;
        case 'C': return "WED"; break;
        case 'D': return "THU"; break;
        case 'E': return "FRI"; break;
        case 'F': return "SAT"; break;
        case 'G': return "SUN"; break;
    }
}

int char2num(char c){ //为了转小时而设置的,A对应10点 
    if(c >= '0' && c <= '9'){
        return c-'0';
    }
    else if(c >= 'A' && c <= 'N'){
        return c-'A'+10; //!!!
    }
    return -1;
}

int main(){
    string a1,a2,b1,b2;
    cin >> a1 >> a2 >> b1 >> b2;
    string result_week;
    int hour;
    int flag = 0; //前两对字符串判断标志 
    int j_index;
    for(int i=0; i<a1.length(); i++){
        if(flag == 0){
            if((a1[i]>='A' && a1[i]<='G') && a1[i] == a2[i]){
                result_week = week(a1[i]) + " ";
                flag = 1;
            }
            
        }
        else if(flag == 1){ //找第二对相同的字符 
            if(char2num(a1[i])>=0 && a1[i]==a2[i]){
                hour = char2num(a1[i]);
                break;
            }
        } 
    }
    int minute;
    for(int i=0; i<b1.length(); i++){
        //也是在相同位置上的 
        if(((b1[i]>='a'&&b1[i]<='z')||(b1[i]>='A'&&b1[i]<='Z')) && (b1[i]==b2[i])){
            minute = i;
            break; 
        }
    }
    cout << result_week;
    printf("%d%d:",hour/10,hour%10);
    printf("%d%d\n",minute/10,minute%10);
}

另外，像上面的那个char2num函数，是参考别人的。这个真的得自己多想一想，不然就是24个case了，会很浪费时间。然后后面的类似 printf(“%d%d:”,hour/10,hour%10)，也是要思考一下，而不是像我原本写的用if语句来判断。但是，最坑的还是题目啊！