PAT 甲级|2021春季真题AC代码+分析

第一题

朴素的枚举思想：暴力遍历所有可能的差值（1 - maxp/(n-1))，在某一差值下，从后往前遍历所有的点作为等差数列的末位数，这样 d + an 就可以确定该数列，此时只需要判断余下的数字即可

第一题

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 100;
int isprime[maxn]; // false是 true不是 

void primechoice(int maxp) {
    isprime[0] = 1;
    isprime[1] = 1;
    for (int i = 2; i <= maxp; i++) {
        if (isprime[i] == false) {
            for (int j = i + i; j <= maxp; j += i) {
                isprime[j] = true;
            }
        }
    }
}

int main() {
    int n, maxp;
    cin>>n>>maxp;
    primechoice(maxp);
    int flag = 0;
    if (n != 1) {
        for (int d = maxp / (n - 1); d > 0; d--) {
            for (int i = maxp; i >= 0; i--) {
                if (isprime[i]) continue;
                int k = 0;
                for (k = 0; k < n; k++) {
                    if (i <= k * d) break;
                    if (isprime[i - k * d] != 0) break;
                }
                if (k == n) {
                    flag = 1;
                    for (int j = n - 1; j >= 0; j--) {
                        cout<<i - j * d;
                        if (j != 0) cout<<" ";
                        else cout<<endl;
                    }
                    break;
                }
            }
            if (flag == 1) break;
        }
    }
    if (flag == 0) {
        while(isprime[maxp]) maxp--;
        cout<<maxp<<endl;
    }
    
}

---

第二题

贪心：每次选择最早离开的人

第二题

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2 * 1e3 + 5;
int n;
struct person{
    int enter, exit;
}per[maxn];

bool cmp (person a, person b) {
    if (a.exit != b.enter) return a.exit < b.exit;
    return a.enter < b.enter;
}

int main() {
    cin>>n;
    for (int i = 0; i < n; i++) {
        int h1, h2, m1, m2, s1, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        per[i].enter = h1 * 3600 + m1 * 60 + s1;
        per[i].exit = h2 * 3600 + m2 * 60 + s2;
    }
    sort(per, per + n, cmp);
    int count = 1;
    int nex = per[0].exit;
    for (int i = 1; i < n; i++) {
        if (per[i].enter >= nex) {
            count++;
            nex = per[i].exit;
        }
    }
    cout<<count<<endl;
}

---

第三题

最大堆的建立，每插入一个数就需要调整一次，而不是全部放入后再调整

字符串的分类，考虑数字没有在大顶堆中出现的情况

第三题

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 4;
int ori[maxn];
int n, m;

void maxHeap(int l, int r) {
    int father = l;
    int son = 2 * l + 1;
    while (son <= r) {
        if (son + 1 <= r && ori[son] < ori[son + 1]) son++;
        if (ori[son] > ori[father]) {
            swap(ori[son], ori[father]);
            father = son;
            son = 2 * son + 1;
        } else {
            return;
        }
    }
}

int main() {
    cin>>n>>m;
    for (int i = 0; i < n; i++) {
        cin>>ori[i];
        int len = i + 1;
        for (int j = len / 2 - 1; j >= 0; j--) maxHeap(j, len - 1);
    }
    getchar();
    string s;
    while (m--) {
        getline(cin, s);
        if (s[s.size() - 1] == 't') {
            string word = "is";
            int pos = s.find(word);
            int num = stoi(s.substr(0, pos - 1));
            if (ori[0] == num) cout<<"1";
            else cout<<"0";
        } else if (s[s.size() - 1] == 's') {
            string word = "and", word2 = "are";
            int pos1 = s.find(word);
            int num1 = stoi(s.substr(0, pos1 - 1));
            int pos2 = s.find(word2);
            int num2 = stoi(s.substr(pos1 + 3, pos2 - 1));
            int flag1 = -1, flag2 = -1;
            for (int i = 0; i < n; i++) {
                if (num1 == ori[i]) flag1 = i;
                if (num2 == ori[i]) flag2 = i;
            }
            if (flag1 != -1 && flag2 != -1 && (flag1 - 1) / 2 == (flag2 - 1) / 2) cout<<"1";
            else cout<<"0";
        } else if (s.find("parent") != -1) {
            string word = "is", word2 = "of";
            int pos1 = s.find(word);
            int num1 = stoi(s.substr(0, pos1 - 1));
            int pos2 = s.find(word2);
            int num2 = stoi(s.substr(pos2 + 2));
            int flag1 = -1, flag2 = -1;
            for (int i = 0; i < n; i++) {
                if (num1 == ori[i]) flag1 = i;
                if (num2 == ori[i]) flag2 = i;
            }
            if (flag1 != -1 && flag2 != -1 && (flag1 * 2 + 1 == flag2 || flag1 * 2 + 2 == flag2)) cout<<"1";
            else cout<<"0";
            
        } else if (s.find("left") != -1) {
            string word = "is", word2 = "of";
            int pos1 = s.find(word);
            int num1 = stoi(s.substr(0, pos1 - 1));
            int pos2 = s.find(word2);
            int num2 = stoi(s.substr(pos2 + 2));
            int flag1 = -1, flag2 = -1;
            for (int i = 0; i < n; i++) {
                if (num1 == ori[i]) flag1 = i;
                if (num2 == ori[i]) flag2 = i;
            }
            if (flag1 != -1 && flag2 != -1 && flag2 * 2 + 1 == flag1) cout<<"1";
            else cout<<"0";
            
        } else if (s.find("right") != -1) {
            string word = "is", word2 = "of";
            int pos1 = s.find(word);
            int num1 = stoi(s.substr(0, pos1 - 1));
            int pos2 = s.find(word2);
            int num2 = stoi(s.substr(pos2 + 2));
            int flag1 = -1, flag2 = -1;
            for (int i = 0; i < n; i++) {
                if (num1 == ori[i]) flag1 = i;
                if (num2 == ori[i]) flag2 = i;
            }
            if (flag1 != -1 && flag2 != -1 && flag2 * 2 + 2 == flag1) cout<<"1";
            else cout<<"0";
        }
    }
}

---

第四题

血泪教训：一定把题目读懂后，样例手推明白后再做

卡车的选择：每次都选择距离最近的编号最小的点出发。距离最近的点不一定与当前所在的点直接相连，间接相连也可以

n遍迪杰斯特拉算法 或者floyd算法 + dfs

第四题

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 205;
const int inf = 1e7;
int d[maxn][maxn];
int visit[maxn];
int n, m, dis = 0;
vector<int> path;
map<int, int> mp;

void dfs(int root) {
    visit[root] = 1;
    path.push_back(root);
    
    int mindis = inf, minid = 0;
    for (int i = 0; i <= n; i++) {
//      cout<<i<<" "<<n<<" "<<visit[i]<<endl;
        if (visit[i] == 0) {
//          cout<<i<<",,,,"<<endl;
            if (d[root][i] < mindis) {
                mindis = d[root][i];
                minid = i;
            }
            if (d[root][i] == mindis) {
                if (minid > i) minid = i; 
            }
        }
    }
    if (minid != 0) {
        dis += mindis;
        dfs(minid);
    }
}

void Floyd() {
    for (int k = 0; k <= n; k++) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (d[i][k] != inf && d[k][j] != inf && d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int main() {
    cin>>n>>m;
    int s1, s2, d12;
    fill(d[0], d[0] + maxn * maxn, inf);
    for (int i = 0; i < m; i++) {
        cin>>s1>>s2>>d12;
        d[s1][s2] = d[s2][s1] = d12;
    }

    Floyd();
    fill(visit, visit + maxn, 0);
    dfs(0);
    for (int i = 0; i < path.size(); i++) {
        if (i != 0) cout<<" ";
        cout<<path[i];
    }
    cout<<endl;
    if (path.size() == n + 1) {
        cout<<dis<<endl;
    } else {
        vector<int> lac;
        for (int i = 1; i <= n; i++) {
            if (visit[i] == 0) lac.push_back(i);
        }
        for (int i = 0; i < lac.size(); i++) {
            if (i != 0) cout<<" ";
            cout<<lac[i];
        }
    }
    
}