PAT甲级题目

作者: 冒绿光的盒子 | 来源:发表于2020-03-30 17:06 被阅读0次

先把会做的做了，emmmm

1006

水题，关键就是在于如何切分字符串而已，考的应该也就是字符串了：


class sepration {
public:
    int hour = -1;
    int min = -1;
    int second = -1;

    sepration() {}

    sepration(int hour, int min, int second) {
        this->hour = hour;
        this->min = min;
        this->second = second;
    }
};

sepration getSepration(string time) {
    int sum = 0;
    sepration s;
    for (int i = 0; i < time.size(); ++i) {
        if (time[i] != ':') {
            sum = sum * 10 + (time[i] - '0');
        } else {
            if (s.hour == -1) {
                s.hour = sum;
            } else if (s.min == -1) {
                s.min = sum;
            }
            sum = 0;
        }
    }
    s.second = sum;
    return s;
}

1007

这个题目大名鼎鼎，一看就知道是动态规划，然鹅我不懂动态规划，用分治法做了，结果不过。牛客网看了一下，直接给了个9万多的数据，这样递归不爆炸才怪，先留着，学了动态规划再做了。

int getMax(int *array, int l, int r, int &left, int &right) {
    if (l == r) {
        left = right = array[l];
        return array[l];
    }
    int mid = (l + r) / 2;
    int maxLeft = INT_MIN;
    int maxLeftIndex = -1;
    int tempLeft = 0;
    for (int i = mid; i >= l; --i) {
        tempLeft += array[i];
        if (tempLeft > maxLeft) {
            maxLeftIndex = i;
            maxLeft = tempLeft;
        }
    }


    int maxRight = INT_MIN;
    int maxRightIndex = -1;
    int tempRight = 0;
    for (int i = mid + 1; i <= r; ++i) {
        tempRight += array[i];
        if (tempRight > maxRight) {
            maxRightIndex = i;
            maxRight = tempRight;
        }
    }


    int Lleft, Lright;
    int Rleft, Rright;

    int midSum = maxLeft + maxRight;
    int maxLeftSum = getMax(array, l, mid, Lleft, Lright);
    int maxRightSum = getMax(array, mid + 1, r, Rleft, Rright);


    int max = midSum;
    left = array[maxLeftIndex], right = array[maxRightIndex];


    if (max <= maxLeftSum) {
        max = maxLeftSum;
        left = array[Lleft];
        right = array[Lright];
    }
    if (max < maxRightSum) {
        max = maxRightSum;
        left = array[Rleft];
        right = array[Rright];
    }


    return max;

}

分治法思路也很简单，最大子串不是在左边就是在右边或者是跨越两边，分三个情况递归讨论即可。

1008

这个题目感觉有点小问题，特么的如果两层相同的话不应该只算等5秒吗？比如3 3，两个都是3层，那等5秒不就好了，然而去掉这个限制就过了。

//
// Created by GreenArrow on 2020/3/30.
//
#include <iostream>
#include <vector>

using namespace std;

vector<int> seperator(string s) {
    int sum = 0;
    vector<int> arr;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != ' ')
            sum = sum * 10 + (s[i] - '0');
        else {
            arr.push_back(sum);
            sum = 0;
        }
    }
    arr.push_back(sum);
    return arr;
}

int main() {
    int n;
    vector<int> array;
    cin >> n;
    for (int j = 0; j < n; ++j) {
        int num;
        cin >> num;
        array.push_back(num);
    }
    int time = 0;
    int pre = 0;
    for (int i = 0; i < array.size(); ++i) {
        int cur = array[i];
        if (cur - pre > 0) {
            time += (cur - pre) * 6;
        } else if (cur - pre < 0) {
            time += (pre - cur) * 4;
        }

        time += 5;
        pre = cur;
    }
    cout << time;
}

1048

这个题目很明显就是索引，关键就是看你怎么存这个数字了，数据存储方式选的好，就简单。用一个数组存储次数即可。


int main() {
    int visited[MAX];
    fill(visited, visited + MAX, 0);
    int n, total;
    cin >> n >> total;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        visited[num]++;
    }

    int v1 = -1, v2 = -1;

    for (int j = 0; j < MAX; ++j) {
        if (visited[j]) {
            visited[j]--;
            if (total > j && visited[total - j]) {
                cout << j << " " << total - j;
                return 0;
            }
        }
    }

    cout << "No Solution";

}

1011

这个题目就比较水了，就是比较大小套公式就好了：

//
// Created by GreenArrow on 2020/4/1.
//
#include <iostream>

#define MAX 3
using namespace std;

int main() {
    double arr[MAX][MAX];
    int index_[MAX] = {-1};
    for (int i = 0; i < MAX; ++i) {
        double max = -1;
        for (int j = 0; j < MAX; ++j) {
            cin >> arr[i][j];
            if (max < arr[i][j]) {
                index_[i] = j;
                max = arr[i][j];
            }
        }
    }

    string a, b, c;
    double sum = 1;

    for (int k = 0; k < MAX; ++k) {
        if (index_[k] == 0) {
            cout << "W";
        } else if (index_[k] == 1) {
            cout << "T";
        } else if (index_[k] == 2) {
            cout << "L";
        }
        cout << " ";

        sum *= arr[k][index_[k]];

    }

    sum = (sum * 0.65 - 1) * 2;

    printf("%.2lf", sum);


}

1012

这个题目很简单，就是排序，但是有点小坑。和正常思维不一样，比如如果有并列，应该是1,1,2,3,4这样，但是这里是1,1,3,4,5，相同的也要算进去，测试点2就是这个情况，稍微处理一下即可。算法写的很麻烦，就是分开几个排序即可。

typedef struct student {
    string id;
    int A;
    int rankA;
    int C;
    int rankC;
    int M;
    int rankM;
    int E;
    int rankE;
    int origin;

    student(string id, int C, int M, int E) {
        this->id = id;
        this->C = C;
        this->M = M;
        this->E = E;
        this->A = (C + M + E) / 3;
    }
};

用一个结构体存储学生所有信息，包括原先排名，因为还准备了一个map存储数据索引。

    sort(students.begin(), students.end(), cmpA);
    setRankA(students);

    sort(students.begin(), students.end(), cmpC);
    setRankC(students);

    sort(students.begin(), students.end(), cmpM);
    setRankM(students);

    sort(students.begin(), students.end(), cmpE);
    setRankE(students);

    sort(students.begin(), students.end(), cmp);

分别排序之后进行排名赋值：

void setRankE(vector<student> &students) {
    int rank = 1;
    if (students.size() == 0)
        return;
    students[0].rankE = rank;
    for (int i = 1; i < students.size(); ++i) {
        if (students[i].E == students[i - 1].E) {
            students[i].rankE = students[i - 1].rankE;
            rank++;
        } else {
            students[i].rankE = ++rank;
        }
    }
}

赋值操作也很简单，注意特殊情况即可。

1015

这个题目就很明显是水题了，问你把相应进制的数字颠倒过来看看是不是还是一个素数。首先判断没变化前的数字是不是素数，然后判断变化之后是不是素数即可。

vector<int> getReverse(int number, int radix) {
    vector<int> results;
    while (number >= radix) {
        results.push_back(number % radix);
        number /= radix;
    }

    results.push_back(number);
    return results;
}

把数字变成进制的形式，不用翻转了，比如23的二进制，按照23%2进result，23/=2的形式，result里面就已经是翻转过来的了。

int radix2number(vector<int> result, int radix) {

    int sum = 0;
    for (int i = 0; i < result.size(); ++i) {
        sum = sum * radix + result[i];
    }

    return sum;

}

把result里面的进制转换成十进制。

int main() {
    int number, radix;
    cin >> number;
    while (number > 0) {
        cin >> radix;

        if (isPrime(number)) {

            int reversNumber = radix2number(getReverse(number, radix), radix);
            if (isPrime(reversNumber)) {
                cout << "Yes" << endl;
            } else
                cout << "No" << endl;

        } else {
            cout << "No" << endl;
        }
        cin >> number;
    }
    return 0;
}

主运行程序。

1019

这个题目很明显，水题，就是进制转换然后看看是不是回文串即可。

//
// Created by GreenArrow on 2020/4/6.
//
#include <iostream>
#include <vector>

using namespace std;

vector<int> getNumber(int number, int radix) {
    vector<int> sequences;
    while (number >= radix) {
        sequences.push_back(number % radix);
        number /= radix;
    }
    sequences.push_back(number);
    return sequences;
}

bool isPalindromic(vector<int> sequences) {
    for (int i = 0, j = sequences.size() - 1; i < j; ++i, j--) {
        if (sequences[i] != sequences[j]) {
            return false;
        }
    }
    return true;
}

int main() {
    int number, radix;
    cin >> number >> radix;
    vector<int> sequences = getNumber(number, radix);
    if (isPalindromic(sequences)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    for (int i = sequences.size() - 1; i >= 0; --i) {
        cout << sequences[i];
        if (i != 0) {
            cout << " ";
        }
    }
}

1022

这个题目考的是字符串的处理，没有什么特别的地方。但是有个坑的地方，如果id是用int存储，注意需要把7位给补齐了，否则后面三个测试点过不去。我用了一个class来存储数据，keywords数量有点多，怕超时，放在map映射，keywords为key，包含了这个关键字的id放进来，如果查询keyword直接打印map里面的数据即可，不需要遍历了，其他情况就遍历。

//
// Created by GreenArrow on 2020/4/9.
//
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>

using namespace std;

map<string, vector<int>> keyWords_id;

class book {
public:
    int ID;
    string title;
    vector<string> keyWords;
    string author;
    string publisher;
    string publish_year;

    book() { keyWords.clear(); }

    book(int id, const string &title, const vector<string> &keyWords, const string &author, const string &publisher,
         const string &publishYear) : ID(id), title(title), keyWords(keyWords), author(author), publisher(publisher),
                                      publish_year(publishYear) {}
};

vector<string> getKeyWords(string keyWords, int id) {
    vector<string> keywords_contain;
    string result;
    for (int i = 0; i < keyWords.size(); ++i) {
        if (keyWords[i] != ' ') {
            result += keyWords[i];
        } else {
            keywords_contain.push_back(result);
            if (keyWords_id.count(result) > 0) {
                keyWords_id[result].push_back(id);
            } else {
                vector<int> ids;
                ids.push_back(id);
                keyWords_id[result] = ids;
            }
            result = "";
        }
    }
    keywords_contain.push_back(result);
    if (keyWords_id.count(result) > 0) {
        keyWords_id[result].push_back(id);
    } else {
        vector<int> ids;
        ids.push_back(id);
        keyWords_id[result] = ids;
    }
    return keywords_contain;
}

void print_vector(vector<int> ids) {
    if (ids.size() == 0) {
        cout << "Not Found" << endl;
        return;
    }
    for (int i = 0; i < ids.size(); ++i) {
        printf("%07d\n", ids[i]);
    }
}

int main() {
    vector<book> books;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int id;
        string title;
        string author;
        string keyWords_string;
        string publisher;
        string publish_year;
        cin >> id;
        cin.ignore();
        getline(cin, title);
        getline(cin, author);
        getline(cin, keyWords_string);
        getline(cin, publisher);
        cin >> publish_year;
        cin.ignore();
        vector<string> keyWords = getKeyWords(keyWords_string, id);
        book Book(id, title, keyWords, author, publisher, publish_year);
        books.push_back(Book);
    }

    int m;
    cin >> m;
    cin.ignore();
    for (int j = 0; j < m; ++j) {
        vector<int> result;
        string query;
        getline(cin, query);
        char flag = query[0];
        string target = query.substr(3, query.size() - 3);
        if (flag == '1') {
            for (int i = 0; i < books.size(); ++i) {
                if (books[i].title == target) {
                    result.push_back(books[i].ID);
                }
            }
            sort(result.begin(), result.end());
        } else if (flag == '2') {
            for (int i = 0; i < books.size(); ++i) {
                if (books[i].author == target) {
                    result.push_back(books[i].ID);
                }
            }
            sort(result.begin(), result.end());
        } else if (flag == '3') {
            result = keyWords_id[target];
            sort(result.begin(), result.end());
        } else if (flag == '4') {
            for (int i = 0; i < books.size(); ++i) {
                if (books[i].publisher == target) {
                    result.push_back(books[i].ID);
                }
            }
            sort(result.begin(), result.end());
        } else if (flag == '5') {
            for (int i = 0; i < books.size(); ++i) {
                if (books[i].publish_year == target) {
                    result.push_back(books[i].ID);
                }
            }
            sort(result.begin(), result.end());
        }

        cout << query << endl;
        print_vector(result);
    }
}

算法笔记里面有另一种做法，是用map存储，效果好像更好些。

1023

考的是大数乘法。

char int2string(int num) {
    stringstream ss;
    ss << num;
    return ss.str()[0];
}

void reverse(string &s) {
    for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
        char c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

string doubleNumber(string s) {
    int addC = 0;
    string S = s;
    reverse(S);
    for (int i = 0; i < S.size(); ++i) {
        char c = S[i];
        int number = (c - '0') * 2 + addC;
        S[i] = int2string(number % 10);
        addC = number / 10;
    }

    if (addC != 0) {
        S += int2string(addC);
    }
    reverse(S);
    return S;
}

PAT甲级题目

1006

1007

1008

1048

1011

1012

1015

1019

1022

1023

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读