刷题中期总结

虽然pat乙级的灵魂是用代码模拟题意就能AC，但在前34题的训练中，我发现有的地方比如输出格式、素数、字符串处理、hash散列等技巧不熟练，这部分我得类似“多级索引”，把它们再索引出来，让自己加深记忆，下次就能快速反应并完美使用它；另外还有我的代码、我的逻辑能AC，但是有的人的思路值得借鉴，怎么说呢，我持有这种态度也经历了一个过程，反正用我自己的逻辑编写出的代码提交后卡在某个测试点，我一定会想自己哪没考虑完备，反正就修改自己的原始代码，不想看别人之间AC的“佳作”，好了，经过一番消耗时间的折腾，我也过了。这个时候，突然发现这道题和之前的某些题，别人都用的一种方法，代码量小，只要明白这个思想，很快就能解决这道题，我的代码绕了很多弯，而且下次再这么做不划算，还是学别人的好思维。大概就是上述两个原因，加上我的学习观是：一直刷，刷完乙级的110题，还不如中途回顾下，我这段时间通过的这几十道题，相较于我没做它们，到底收获了啥新的知识和技能。很明显，把做过的题按类型归纳分档，然后找到每类题最好的解法，以及自己刷题中卡了的某些小功能，一些方法，把它们“二级索引”，让以后的自己不用大浪淘沙又重刷一遍，之后回顾就直接看这些中期后期总结就能抓住重难点，这不，这才是真正的“卷王”，是动脑子的卷。

1033 分别输入坏键和应该输入的字符串，输出是实际输入的字符串。当上档键坏了，所有大写字母都不能输入。坏键中的字母键都是以大写字母的形式给出。

我的1033：

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
/*字符串处理*/
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    string bad,input;
    int i,j,flag=0;
    getline(cin,bad);
    getline(cin,input);
    if(bad.length()==0){
        cout<<input;
        return 0;
    }
    for(int i=0;i<bad.length();i++){
        if(bad[i]=='+'){
            flag=1;
        }
    }
    for(i=0;i<input.length();i++){
        for(j=0;j<bad.length();j++){
            if(input[i]==bad[j]){
                break;
            }
            if(flag==1 && input[i]>='A' && input[i]<='Z'){
                        break;    
                    }
            if(isalpha(input[i])){
                if(toupper(input[i])==bad[j]){
                    break;
                }
            }
        }
        if(bad[j]=='\0'){
            cout<<input[i];
        }
    }
}

柳婼的1033：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cctype>
using namespace std;
int main() {
  string bad, should;
  getline(cin, bad);
  getline(cin, should);
  for (int i = 0, length = should.length(); i < length; i++) {
    if (bad.find(toupper(should[i])) != string::npos) continue;//字母键坏了，字母键中出现的字母若等于should[i]的大写 输不出
    if (isupper(should[i]) && bad.find('+') != string::npos) continue;//是大写字母且上档键坏了 
    cout << should[i];
  }
  return 0;
}

看了是不是觉得可以学习下思路，在知道她1029也是用很简洁的代码AC后，而且这两道题，她都用的Hash散列这个知识，这个时候，是个人都知道，我一定要学会她的思想！

1029题意：分别输入理应输入的字符串和实际输入的字符串，输出坏键。

柳婼的1029：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string s1, s2, ans;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); i++)
        if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos)//理应输入的字符没出现在实际输入的字符中，它的大写也不再ans中 加入ans 第二个条件是确保相同坏键只输出一次 比如s1[i]=7 在s2中找不到 它toupper后是55 
            ans += toupper(s1[i]);//是坏键的英文字母只输出大写
    cout << ans;
    return 0;
}

我的1029：

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
#include<iostream>
#include<set>
#include <algorithm>
#include<cstring>
using namespace std;
int main(){
    string input,real_input;
    set<char> s1,s2,s3;
    cin>>input>>real_input;
    for(int i=0;i<input.length();i++){
        if(input[i] >= 'a'&& input[i] <='z')
            input[i] = toupper(input[i]);
        s1.insert(input[i]);
    }
    for(int i=0;i<real_input.length();i++){
        if(real_input[i] >= 'a'&& real_input[i] <='z')
            real_input[i] = toupper(real_input[i]);
        s2.insert(real_input[i]);
    }
    //找s1有的 而s2没有的
    for(auto it=s1.begin();it!=s1.end();it++){
        if(s2.find(*it)==s2.end()){
            s3.insert(*it);
        }
    } 
    string new_input;
    for(size_t i=0;i<input.size();i++){
        size_t j=0;
        for(;j<new_input.size();j++){
            if(new_input[j]==input[i]){//已经出现过的 不再添加到new_input
                break;
            }
        }
        if(j==new_input.size()){
            new_input+=input[i];
        }
    }
   int count =0;
   for(int i=0;i<new_input.length(),count<s3.size();i++){
       for(auto it=s3.begin();it!=s3.end();it++){
           if(new_input[i] == *it){
            cout<<*it;
            count++;
            break;
           }
       }
   }
}

展开全文 >>

PAT_Basic_1034 有理数四则运算

本题要求编写程序，计算 2 个有理数的和、差、积、商。

输入格式：

输入在一行中按照 a1/b1 a2/b2 的格式给出两个分数形式的有理数，其中分子和分母全是整型范围内的整数，负号只可能出现在分子前，分母不为 0。

输出格式：

分别在 4 行中按照 有理数1 运算符 有理数2 = 结果 的格式顺序输出 2 个有理数的和、差、积、商。注意输出的每个有理数必须是该有理数的最简形式 k a/b，其中 k 是整数部分，a/b 是最简分数部分；若为负数，则须加括号；若除法分母为 0，则输出 Inf。题目保证正确的输出中没有超过整型范围的整数。

输入样例 1：

1
2/3 -4/2

输出样例 1：

1
2
3
4
2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)

输入样例 2：

1
5/3 0/6

输出样例 2：

1
2
3
4
1 2/3 + 0 = 1 2/3
1 2/3 - 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

思路：

pat乙级题统一思路：模拟题意。这道题我归纳为是繁琐模拟题。考场遇到这种题，只有硬写，关键在于输出标准化分数，即最简化形式的分数，能抽象出功能函数是快速AC1035的必要条件。

代码：

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
#include<iostream>
#include<cstdio>
using namespace std;
long long GCD(long long a, long long b) { //求最大公约数   
    return b==0 ? a:GCD(b,a%b);
}  
void PrintFraction(long long a, long long b) {  //将一个分数以规定形式输出 
    long long k = 1;  
    if(b == 0) {  //分母为0
        printf("Inf");  
        return;  
    }  
    if(a < 0) {  //负号只可能出现在分子前
        a = -a;  
        k = -1;  
    }  
    long long gcd = GCD(a, b);  
    a /= gcd;                       //分子分母分别除以最大公约数完成约分 
    b /= gcd;  
    //a不为0又小于b
    if(a / b == 0 && a != 0) {      //因为正负号储存在k里，k为0的时候无法区别，在这一步处理 
        if(k > 0)  //处理符号
            printf("%lld/%lld", a, b);  
        else  
            printf("(-%lld/%lld)", a, b);  
        return;  
    }  
    k = k * a / b;      //得到整数部分 
    a %= b;             //得到分子部分 
    if(b == 1 && k < 0)  
        printf("(%lld)", k);  
    else if(b == 1 && k >= 0)    //分子为0,或者分母为1，结果都是整数，直接输出分子部分（不输出分母） 
        printf("%lld", k);  
    else if(k < 0)  
        printf("(%lld %lld/%lld)", k, a, b);  
    else  
        printf("%lld %lld/%lld", k, a, b);  
}  
void Print(long long a1, long long b1, long long a2, long long b2, char ch) {   //输出一个表达式 
    long long c1, c2;  
    PrintFraction(a1, b1);          //范式输出第一个操作数 
    printf(" %c ", ch);             //输出操作符 
    PrintFraction(a2, b2);          //范式输出第二个操作数 
    printf(" = ");                  //输出等号 
    switch(ch) {                    //范式输出结果 
    case '+':  
        c1 = a1 * b2 + a2 * b1;  
        c2 = b1 * b2;  
        PrintFraction(c1, c2);  
        printf("\n");  
        break;  
    case '-':  
        c1 = a1 * b2 - a2 * b1;  
        c2 = b1 * b2;  
        PrintFraction(c1, c2);  
        printf("\n");  
        break;  
    case '*':  
        c1 = a1 * a2;  
        c2 = b1 * b2;  
        PrintFraction(c1, c2);  
        printf("\n");  
        break;  
    case '/':  
        c1 = a1 * b2;  
        c2 = b1 * a2;  
        if(c2 < 0) {     //确保PrintFraction函数的b是正数 
            c2 = -c2;  
            c1 = -c1;  
        }  
        PrintFraction(c1, c2);  
        printf("\n");  
        break;  
    }  
}  
int main() {  
    long long a1, b1, a2, b2;  
    scanf("%lld/%lld %lld/%lld", &a1, &b1, &a2, &b2);  
    Print(a1, b1, a2, b2, '+');  
    Print(a1, b1, a2, b2, '-');  
    Print(a1, b1, a2, b2, '*');  
    Print(a1, b1, a2, b2, '/');  

    return 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
#include <iostream>
#include <cmath>
using namespace std;
long long a, b, c, d;
//gcd函数 求出t1 t2的最大公约数
long long gcd(long long t1, long long t2) {// 12 8 gcd(8,4) gcd(4,0)
    return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}
void func(long long m, long long n) {
    if (m * n == 0) {
        printf("%s", n == 0 ? "Inf" : "0");//当分子为0 输出0 当分母为0 输出Inf
        return ;
    }
    bool flag = ((m < 0 && n > 0) || (m > 0 && n < 0));//flag标记异号
    m = abs(m); n = abs(n);//取绝对值
    long long x = m / n;//整数部分
    printf("%s", flag ? "(-" : "");//如果异号 输出负号
    if (x != 0) printf("%lld", x);//输出整数部分
    if (m % n == 0) {//后面没有小分数 如果是负数 加上右括号
        if(flag) printf(")");
        return ;//没有小分数 爽歪歪
    }
    if (x != 0) printf(" ");
    m = m - x * n;
    long long t = gcd(m, n);
    m = m / t; n = n / t;
    printf("%lld/%lld%s", m, n, flag ? ")" : "");
}
int main() {
    scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);// 2/3 -4/2 a=2 b=3 c=-4 d=2
    func(a, b); printf(" + "); func(c, d); printf(" = "); func(a * d + b * c, b * d); printf("\n");
    func(a, b); printf(" - "); func(c, d); printf(" = "); func(a * d - b * c, b * d); printf("\n");
    func(a, b); printf(" * "); func(c, d); printf(" = "); func(a * c, b * d); printf("\n");
    func(a, b); printf(" / "); func(c, d); printf(" = "); func(a * d, b * c);
    return 0;
}

展开全文 >>

PAT_Basic_1033 旧键盘打字

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键，打出的结果文字会是怎样？

输入格式：

输入在 2 行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出；每段文字是不超过 105 个字符的串。可用的字符包括字母 [a-z, A-Z]、数字 0-9、以及下划线 _（代表空格）、,、.、-、+（代表上档键）。题目保证第 2 行输入的文字串非空。

注意：如果上档键坏掉了，那么大写的英文字母无法被打出。

输出格式：

在一行中输出能够被打出的结果文字。如果没有一个字符能被打出，则输出空行。

输入样例：

1
2
7+IE.
7_This_is_a_test.

输出样例：

1
_hs_s_a_tst

思路：

将坏键以字符串输入，记为bad，应该输入的字符串记为input。当bad字符串为空，直接输出input就完事。否则首先判断bad字符串中是否含有上档键+,用flag标记其存在。对input中每个字符考察，其内层嵌套对坏键字符串各字符的for循环。一个字符与bad[j]相等则无法输出；如果flag为1，即上档键坏了，若此时input[i]为大写字母，则无法输出；若input[i]是字母且它toupper()变成大写字母后与bad[j]相等则无法输出。熬过这三关，此input[i]可以输出。

代码：

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
/*字符串处理*/
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    string bad,input;
    int i,j,flag=0;
    getline(cin,bad);
    getline(cin,input);
    if(bad.length()==0){
        cout<<input;
        return 0;
    }
    for(int i=0;i<bad.length();i++){
        if(bad[i]=='+'){
            flag=1;
        }
    }
    for(i=0;i<input.length();i++){
        for(j=0;j<bad.length();j++){
            if(input[i]==bad[j]){
                break;
            }
            if(flag==1 && input[i]>='A' && input[i]<='Z'){
                        break;    
                    }
            if(isalpha(input[i])){
                if(toupper(input[i])==bad[j]){
                    break;
                }
            }
        }
        if(bad[j]=='\0'){
            cout<<input[i];
        }
    }
}

展开全文 >>

PAT_Basic_1032 挖掘机技术哪家强

为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式：

输入在第 1 行给出不超过 105 的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出格式：

在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：

1
2
3
4
5
6
7
6
3 65
2 80
1 100
2 70
3 40
3 0

输出样例：

1
2 150

思路：

测试点2最高分为0，所以是it->second >= max光大于过不了测试点2。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*查找元素*/
#include<iostream>
#include<map>
using namespace std;
int main(){
    int N,id,score;
    map <int,int> m;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>id>>score;
        m[id]+=score;
    }
    int max=0,flag;
    for(auto it=m.begin();it!=m.end();it++){
        if(it->second >= max){
            max=it->second;
            flag=it->first;
        }
    }
    cout<<flag<<' '<<m[flag];
}

展开全文 >>

PAT_Basic_1031 查验身份证

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：

首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：

1
2
Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2

现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。

输入格式：

输入第一行给出正整数N（≤100）是输入的身份证号码的个数。随后N行，每行给出1个18位身份证号码。

输出格式：

按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出All passed。

输入样例1：

1
2
3
4
5
4
320124198808240056
12010X198901011234
110108196711301866
37070419881216001X

输出样例1：

1
2
3
12010X198901011234
110108196711301866
37070419881216001X

输入样例2：

1
2
3
2
320124198808240056
110108196711301862

输出样例2：

1
All passed

思路：

以字符串存每个18位的身份证号，若前17位有非数字则打印，设置flag标志避免被第二遍打印，因为前17位均为数字但第18位的校验码计算错误的字符串会的代码逻辑在不设置flag标志时会把前17位有非数字的字符串打印。

代码：

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
/*简单模拟题*/
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){
    int N,count=0;
    cin>>N;
    vector<string> v,v1;
    map<int,int>m;
    map<int,char>m1;
    m.insert({{0,7},{1,9},{2,10},{3,5},{4,8},{5,4},{6,2},{7,1},{8,6},{9,3},
    {10,7},{11,9},{12,10},{13,5},{14,8},{15,4},{16,2}});
    m1.insert({{0,'1'},{1,'0'},{2,'X'},{3,'9'},{4,'8'},{5,'7'},{6,'6'},{7,'5'},{8,'4'},{9,'3'},{10,'2'}});
    for(int i=0;i<N;i++){
        string s;
        cin>>s;
        v.push_back(s);
    }
    for(int i=0;i<v.size();i++){
        string ss = v[i];
        int sum=0,Z,M,flag=0;
        for(int j=0;j<ss.length()-1;j++){
            if(ss[j]-'0'<0 || ss[j]-'0'>9){//前17位不全为数字
                cout<<ss<<endl;
                flag=1;//为了这个字符串不再打印第二遍
                count++;
                break;
            }
            sum+=(ss[j]-'0')*m[j];
        }
        Z=sum%11;
        if(m1[Z]!=ss[17] && flag==0){//前17位满足全是数字 但最后一位检验码计算错误
            cout<<ss<<endl;
            count++;
        }
        }
        if(count==0){
            cout<<"All passed"<<endl;
        }
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

假如我不再敷衍.