PAT 刷题

PAT甲级真题链接

PAT题目分类

PAT甲级题目分类
水题									1136、1139、1143、1148
字符串处理							1001、1005√、1035√、1061√、1073、1077、1082、
									1108、1140、1152
模拟									1002、1009、1017、1026、1042、1046、1065、
									1105
查找元素								1006、1011、1036√
动态规划								1007、1040√、1045√、1068√
二分法								1010 √、1044√、1085√
双指针								1029、1085√、1089
排序									1012、1016、1025、1026、1028、055、1062、
									1075、1080、1083、1095、1098、1101、1113、
									1125√、1146、1153
逻辑题								1093√、1096√、1109、1116√、1117、1128、
数学问题								1008、1049、1069、1104、1132、
素数表的建立							1059
科学计数法							1060
分数四则运算							1081、1088
队列应用(queue)						1014√、1056
素数									1015√
回文数								1019
不定长vector、stl					1039√、1047√
集合set、stl的使用					1063、1120、1121、1129、1149、
map映射、stl的使用					1022、1054、1071√、1095、1100、1154、1112、
									1124、1037、1141、1144、1153
Hash散列								1041、1048、1050、1084、1092、1134、1145
大整数运算							1023、1024
栈模拟								1051
进制转化								1027、1058
图形打印								1031
链表									1032、1052、1074、1097、1133、
贪心算法								1033√、1037√、1038√、1067、1070、1125√
二次方探查法							1078
并查集								1107、1114 、1118
完全二叉树							1110、
二叉树遍历，后序中序转层序				1020
二叉树BST							1043、1064、1099
平衡二叉树(AVL树)						1066、1123
树的遍历								1053、1086、1090、1102、1106、1115、1119、
									1038、1147、1151(LCA算法)、
树形数组								1057
图论									1122、1142、1150
连通图								1126、
图的遍历、统计连通分量的个数				1013、1021、1034
Dijikstra算法						1003、1018、1030√、1072、1087、1111 、
DFS、BFS、层序遍历					1004、1018、1021、2076、1079、1087、1091、
									1094√、1103、1106、1127、1130、1131
红黑树								1135、
深度回溯								1155

1044 Shopping in Mars

题目链接求一串的数字中连续的一段，使得这个连续的段内数字的和恰好等于所期望的值m。如果不能找到恰好等于，就找让自己付出最少的价格因为上诉的条件，不能简单用unorder_map解决，可以用二分法处理。 int k = (left+right) / 2; left = k | right = k+1;

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <unordered_map>
using namespace std;

using ll = long long;

int main(){
    int n,target;
    int tmp;
    cin>>n>>target;
    vector<int> sumArr(n+1,0);
    vector<pair<int,int> > ans;
    for(int i=1; i<=n; i++){
        cin>>tmp;
        sumArr[i] = sumArr[i-1]+tmp;
    }
    int sum_find = sumArr[n];
    for(int i=1;i<=n;i++){
        int left=i;
        int right=n;

        while(left<right){
            int mid = (left+right)/2;
            int sum = sumArr[mid]-sumArr[i-1];
            if(sum>=target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        int curSum = sumArr[left]-sumArr[i-1];
        if(curSum >= target && curSum < sum_find){
            ans.clear();
            ans.push_back(make_pair(i,left));
            sum_find = curSum;
        }else if(curSum == sum_find){
            ans.push_back(make_pair(i,left));
        }
    }

    for(pair<int,int> p :ans){
        cout<<p.first<<"-"<<p.second<<endl;
    }
}

1068 Find More Coins

题目链接总之这道题可以转换为weight[i]==value[i]的背包问题：容量大小为M的背包，最重可以装多少的重量。看是否能找到正好装满装量M的方案。$dp[n][m]==m$ $dp[n][m]$ 的值就表示

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int arr[10003];

int main() {
    int n, m;
    cin>>n>>m;
    // 10的4次方
    for(int i=1; i <= n; i++) {
        cin>>arr[i];
    }
    sort(arr+1, arr+n+1, greater<int>());
    vector<vector<int> > dp(n+1, vector<int>(m+1,0));
    vector<vector<bool> > choose(n+1, vector<bool>(m+1,false));
    // 初始状态
    for(int i=1; i<=n;i++){
        for(int j=0;j<=m;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j>=arr[i] && dp[i][j]<=dp[i-1][j-arr[i]]+arr[i]){
                dp[i][j] = dp[i-1][j-arr[i]]+arr[i];
                choose[i][j]=true;
            }
        }
    }
    if(dp[n][m] != m) {
        cout<<"No Solution";
        return 0;
    }
    int cur = m;
    int i = n;
    vector<int> ans;
    while(i>=1 && cur>0){
        while(i>=1 && choose[i][cur]==false){
            i--;
        }
        ans.push_back(arr[i]);
        cur-=arr[i--];
    }
    cout<<ans[0];
    for(int k=1;k<ans.size();k++){
        cout<<" "<<ans[k];
    }
}

题目链接

题目有点迷惑，按照题目意思，两个没有共同爱好的人都有可能是同一个cluster。关键就在于，Union时，怎么确定该和哪一个节点Union。每行输入任意hobby时，使用hobby数组保存这个hobby有哪一个节点，直接与之关联。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

vector<int> parent, isRoot;

int Find(int x){
    return x == parent[x] ? x : ( parent[x] = Find(parent[x]));
}

void Union(int x, int y) {
    // 记录每一个 集合的 “根节点”
    int px = Find(x);
    int py = Find(y);

    if(px!=py){
        // py 设置为 px 的父
        parent[px]=py;
    }
}

int main(){
    int n;
    int k,h;
    int cnt=0;
    scanf("%d",&n);
    int hobby[1001]={0};
    
    // 初始化vector体积
    parent.resize(n+1);
    isRoot.resize(n+1);
    memset(hobby,0,sizeof(hobby));

    for(int i=1;i<=n;i++){
        parent[i]=i;
    }

    for(int i=1; i <= n; i++) {
        // 每一行输入格式：3: 2 7 10
        scanf("%d:", &k);
        for(int j=0; j<k; j++) {
            scanf("%d", &h);
            if(hobby[h]==0) {
                hobby[h]=i;
            }
            Union(i, Find(hobby[h]));
        }
    }

    // 统计节点，到最后统计
    for( int i=1; i <= n; i++)
        isRoot[Find(i)]++;
    
    for(int i = 1; i <= n; i++) {
        if(isRoot[i] != 0)
            cnt++;
    }

    printf("%d\n", cnt);
    sort(isRoot.begin(), isRoot.end(), greater<int>());
    for(int i = 0; i < cnt; i++) {
        printf("%d", isRoot[i]);
        if(i != cnt - 1) printf(" ");
    }
    return 0;
}

1061 Dating

题目链接

我觉得题目给的不够清晰，share the same character，同一个位置的相同字符才叫share。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    string f1,f2;
    string l1,l2;
    cin >> f1 >> f2 >> l1 >> l2;
    char t[2];
    int pos, i = 0, j = 0;
    while(i < f1.size() && i < f2.size()) {
        if (f1[i] == f2[i] && (f1[i] >= 'A' && f2[i] <= 'G')) {
            t[0] = f1[i];
            break;
        }
        i++;
    }
    i++;
    while(i < f1.size() && i < f2.size()) {
        if (f1[i] == f2[i] && ((f1[i]>='A' && f1[i]<='N') || isdigit(f1[i]))){
            t[1] = f1[i];
            break;
        }
        i++;
    }

    while( j < l1.size() && j < l2.size() ){
        if (l1[j]==l2[j] && isalpha(l1[j])){
            pos = j;
            break;
        }
        j++;
    }
    const string day[7]={"MON","TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    int m = isdigit(t[1]) ? t[1]-'0' : t[1]-'A'+10;
    cout<<day[t[0]-'A']<<" ";
    printf("%02d:%02d", m, pos);
}

1066 Root of AVL Tree

题目链接

考察AVL树，插入时候的旋转操作

需要旋转的情况分为

左左
右右
左右
右左：先右旋，变为 2. 右右型，再左旋。

旋转操作分为：

rotateLeft表示左旋，
rotateRight表示右旋，
rotateLeftRight表示先左旋后右旋，
rotateRightLeft表示先右旋后左旋，
getHeight表示获取传入结点的子树的高度，
insert表示插入建树的过程，
- 如果root为空，直接新建结点插入即可～
- 如果当前要插入的值小于root->val，则插入root的左子树；如果当前要插入的值大于root->val，则插入root的右子树～
- 如果插入后左右子树高度差大于1，再根据值的大小比较进行旋转调整使树平衡～
- 插入完成后返回root指针赋值给main函数里的root～最后输出root的val值

漫话：什么是平衡(AVL)树？

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

struct node {
    int val;
    node *left, *right;
};

node *rotateLeft(node* root) {
    // 要求 右节点 t 有自己的 右子节点。t->left
    node* t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}

node* rotateRight(node* root) {
    // 要求 左节点 t 有自己的 左子节点。t->left
    node* t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}

node* rotateLeftRight(node* root) {
    //现在是 左右类型，先左转左节点
    node* t = rotateLeft(root->left);//变成 左左类型
    root->left = t;
    // 然后右转
    return rotateRight(root);
}

node* rotateRightLeft(node* root) {
    //现在是 右左类型，先右转 右节点
    node* t = rotateRight(root->right);
    root->right = t;
    return rotateLeft(root);
}

int getHeight(node* root) {
    if (root==NULL) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}

// 插入 AVL数
node* insert(node* root, int val) {
    if (root==NULL) {
        root = new node();
        root->val = val;
        root->left = root->right = NULL;
    } else if (val < root->val) {
        // 需要放在左边
        root->left = insert(root->left, val);
        // 只需要检查 左子树 是否比 右子树 高 2
        if(getHeight(root->left) - getHeight(root->right) == 2) {
            // 如果 val < root->left->val 这是左左的情况 反之就是左右的情况
            return val < root->left->val ? rotateRight(root) : rotateLeftRight(root);
        }
    } else if (val > root->val) {
        root->right = insert(root->right, val);
        if(getHeight(root->right) - getHeight(root->left) == 2) {
            return val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);
        }
    }
    return root;
}

int main() {
    int n, val;
    scanf("%d", &n);
    node *root = NULL;
    for(int i = 0; i < n; i++) {
        scanf("%d", &val);
        root = insert(root, val);
    }
    printf("%d", root->val);
    return 0;
}

1059 Prime Factors

题目链接

需要建立素数表从2开始遍历，到 sqrt(num)。 50000以内找素数素数表：

从2开始招找素数，需要一个isPrime的函数，是素数就放进全是素数的vector里面
2～50000全部标记为1表示素数，然后将所有不是素数的标记为0, 下面的代码采用这种办法

#include <cstdio>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

// 怎么搜索呢
/*
从2开始遍历，到 sqrt(num)。 50000以内找素数
素数表：
1. 2～50000全部标记为1表示 素数，然后将所有不是素数的标记为0
2. 从2开始招找素数，需要一个isPrime的函数
*/
vector<int> prime(50000, 1);
int main() {
    for(int i=2; i * i < 50000; i++)
        for(int j = i; j*i < 50000; j++)
            prime[j*i] = 0;
    
    long int n;
    cin>>n;
    cout<<n<<"=";
    if (n == 1)
        cout<<"1";
    bool state = false;
    for(int i = 2; i < 50000 && n >= 2 && i <= n; i++) {
        int cnt = 0, flag = 0;
        while(prime[i] == 1 && n % i == 0) {
            cnt++;
            n = n / i;
            flag = 1;
        }
        if (flag) {
            if(state) cout<<"*";
            cout<<i;
            state=true;
        }
        if (cnt>=2) {
            cout<<"^"<<cnt;
        }
    }
    if (n>1) cout<<(state ? "*":"")<<n;
}

1036 Boys vs Girls

题目链接比较简单

#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


int main() {

    string name, id;
    string gender;
    int grade;

    int n;
    cin>>n;
    int fMax = -1, mMin = 101;
    string femaleName, femaleId;
    string maleName, maleId;

    for(int i=0; i<n; i++) {
        cin>>name>>gender>>id;
        scanf("%d", &grade);
        if (gender == "F") {
            if (grade > fMax) {
                fMax = grade;
                femaleId = id;
                femaleName = name;
            }
        } else {
            if (grade < mMin) {
                mMin = grade;
                maleId = id;
                maleName = name;
            }
        }
    }
    
    if (fMax != -1) {
        cout<<femaleName<<" "<<femaleId<<endl;
    } else {
        cout<<"Absent"<<endl;
    }
    
    if (mMin != 101) {
        cout<<maleName<<" "<<maleId<<endl;
    } else {
        cout<<"Absent"<<endl;
    }

    if (fMax == -1 || mMin == 101) {
        cout<<"NA";
    } else {
        cout<<(fMax - mMin);
    }
}

1116 Come on! Let’s C

题目链接 ID为4位数字，就用int来存储。便读取边计算所属结果。

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <unordered_set>

using namespace std;

bool isPrime(int d) {
    if (d <= 2) {
        return true;
    }

    for(int i = 2; i*i <= d; i++ ) {
        if (d % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    char ranklist[10003][5];
    int ans[10004];
    memset(ans, -1, sizeof(ans));
    int N;
    int K;
    unordered_set<int> set;
    scanf("%d", &N);
    int t;
    for(int i = 1; i <= N; i++) {
        scanf("%d", &t);
        if (i==1) {
            ans[t] = 0; // champion
        } else if (isPrime(i)) {
            ans[t] = 1; // prime
        } else {
            ans[t] = 2;
        }
    }

    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
        int q;
        scanf("%d", &q);
        printf("%04d: ", q);
        if (ans[q]==-1) {
            printf("Are you kidding?\n");
            continue;
        }
        
        if (set.find(q)!=set.end()) {
            printf("Checked\n");
            continue;
        }
        set.insert(q);
        if (ans[q]==0) {
            printf("Mystery Award\n");
        } else if (ans[q]==1) {
            printf("Minion\n");
        } else if (ans[q]==2) {
            printf("Chocolate\n");
        }  
    }
}

1040 Longest Symmetric String

题目链接 1040，多种方法，动态规划，LCS 下面的代码采用记忆化搜索算法。

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

bool isPalindrome(string s, int i, int j, vector<vector<int> >& memo ) {
    if (memo[i][j] != -1)
        return memo[i][j] == 1;

    if (i>=j) { // 必须是 >=, == 不能全部AC
        memo[i][j] = 1;
        return memo[i][j] == 1;
    } 

    if (s[i] == s[j]) {
        memo[i][j] = isPalindrome(s, i+1, j-1, memo) ? 1 : 0;
    } else {
        memo[i][j] = 0;
    }
    
    return memo[i][j] == 1;
}

int main() {
    // 1040
    string ss;
    getline(cin, ss);
    int n = ss.size();

    vector<vector<int> > memo(1002, vector<int>(1002, -1));
    int ans = 0;
    // 最长1000个字符
    for (int j = 0; j < n; j++) {
        for (int i = j-ans; i >= 0; i--) {
            if (isPalindrome(ss, i, j, memo)) {
                ans = max(ans, j - i + 1);
            }
        }
    }
    
    cout<<ans;
}

1072 Gas Station

题目链接 Dijkstra最短路。最后一个用例过不了

#include <cstdio>
#include <map>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <vector>
#include <math.h>
#include <cctype>
#include <algorithm>
#include <queue>
using namespace std;

// 最短路算法
// 前 N个是 house，后面 M个是Gas Station
enum NodeType { 
    gs, // gas station
    hs // house
};

struct Node{
    NodeType type;
    int id;
    int dis;
    bool operator > (const Node& b) const{
        return dis > b.dis;
    }
    Node(){}
    Node(int id, int dis, NodeType type):id(id), dis(dis), type(type){}
};

int main()
{
    int N, M, K, Ds;
    priority_queue<Node, vector<Node>, greater<Node>> que; // 最小堆
    scanf("%d%d%d%d", &N, &M, &K, &Ds);
    char p1[6], p2[6];
    int cin_dis;
    vector<map<int,int>> edges(N+M+1, map<int,int>());
    vector<int> dist(1+N+M, INT_MAX);
    vector<bool> vis(1+N+M, false);
    
    int max_min_dis = 0;
    int min_sum = INT_MAX;
    int ans_gs_id = -1;
    for(int i = 0; i < K; i++)
    {
        scanf("%s %s", p1, p2);
        scanf("%d", &cin_dis);
        int p1_id, p2_id;
        if(p1[0]=='G'){
            p1_id = atoi(p1+1)+N;
        }else{
            p1_id = atoi(p1);
        }

        if(p2[0]=='G'){
            p2_id = atoi(p2+1)+N;
        }else{
            p2_id = atoi(p2);
        }
        
        if(edges[p1_id].find(p2_id) != edges[p1_id].end()){
            edges[p1_id][p2_id] = edges[p2_id][p1_id] = min(cin_dis, edges[p2_id][p1_id]);
        }else{
            edges[p1_id][p2_id] = edges[p2_id][p1_id] = cin_dis;
        }
    }
    
    // 测试输入处理
    // for(int i=1; i<=N+M; i++){
    //     if(edges[i].size()!=0){
    //         for(pair<int,int> p : edges[i]){
    //             printf("%d %d: %d\n", i, p.first, p.second);
    //         }
    //         printf("\n");
    //     }
    // }
    
    for(int i=1; i<=M;i++){
        // 依次看 M 个 gas station 最短路情况
        // Dijkstra 状态初始化
        fill(dist.begin(), dist.begin() + N + M + 1, INT_MAX);
        fill(vis.begin(), vis.begin() + N + M + 1, false);
        while(!que.empty()) que.pop();
        bool work = true;
        int min_dis = INT_MAX;
        int sum=0;

        dist[N+i] = 0;
        que.push(Node(N+i, 0, gs));
        
        while(!que.empty()){
            Node topNode = que.top(); que.pop();
            int u = topNode.id, u_dis = topNode.dis;
            if(vis[u]) continue;
            vis[u] = true;
            if (topNode.type == hs && u_dis > Ds){
                work = false; // 在这个位置修建 gas station 不满足the maximum service range这个要求
                break;
            }
            for(map<int,int>::iterator it = edges[u].begin(); it != edges[u].end(); it++){
                int v = it->first;
                int next_dis = it->second;
                if(vis[v]) continue;
                if(dist[v] > u_dis + next_dis){
                    dist[v] = u_dis + next_dis;
                    que.push(Node(v, dist[v], v <= N ? hs : gs));
                }
            }
        }
        if(!work){
            continue;
        }
        

        for(int i=1; i<=N; i++){
            if(dist[i] > Ds) break; // 不满足the maximum service range这个要求
            sum += dist[i];
            if(min_dis > dist[i])
                min_dis = dist[i];
            // 最小距离
        }

        if(min_dis > max_min_dis || (min_dis == max_min_dis && sum < min_sum)){
            ans_gs_id = i;
            max_min_dis = min_dis;
            min_sum = sum;
        }
    }
    

    if(ans_gs_id == -1){
        printf("No Solution");
    }else{
        printf("G%d\n", ans_gs_id);
        printf("%.1f %.1f", (float)max_min_dis, (float)min_sum/(float)N+0.05);
    }
}

链接

上篇TCP-BBR：跨国资源下载速度提升几十倍

下篇Leetcode 刷题册

PAT题目分类

1044 Shopping in Mars

1068 Find More Coins

1107 Social Clusters

1061 Dating

1066 Root of AVL Tree

1059 Prime Factors

1036 Boys vs Girls

1116 Come on! Let’s C

1040 Longest Symmetric String

1072 Gas Station

链接