PAT甲級2019秋季真題題解

題目及AC代碼下載

A Foreover

??熱身題，結合求最大公約數、檢查是否為素數、DFS回溯，很綜合的一道題目，注意剪枝，否則資料過大可能會TLE，

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

#define ac cin.tie(0);cin.sync_with_stdio(0);
using namespace std;
string s;
//n和A
typedef pair<int, string> PAIR;
vector<PAIR> ans;
int n, k, m;
//按照題目輸出順序排序
bool cmp(const PAIR &a, const PAIR &b) {
    if (a.first != b.first)
        return a.first < b.first;
    else
        return a.second < b.second;
}
//回傳最大公約數
long long gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
//檢查是否為素數
bool check(int a) {
    if (a <= 2)
        return false;
    for (int i = 2; i * i <= a; i++)
        if (a % i == 0)
            return false;
    return true;
}
//求解
void dfs(int lev, int res) {
    if (lev == k) {
        if (!res) {
            long long tmp = stoll(s) + 1;
            int nn = 0;
            while (tmp) {
                nn += tmp % 10;
                tmp /= 10;
            }
            if (check(gcd(nn, m)))
                ans.push_back(PAIR(nn, s));
        }
        return;
    }
    //剪枝
    if (res > 9 * (k - lev) || res < 0)
        return;

    for (int i = 0; i <= 9; i++) {
        if (lev == 0 && i == 0)
            continue;
        s.push_back('0' + i);
        res -= i;
        dfs(lev + 1, res);
        s.pop_back();
        res += i;
    }
}

int main() {
    ac

    cin >> n;
    for (int i = 1; i <= n; i++) {
        ans.clear();
        cout << "Case " << i << endl;
        cin >> k >> m;
        dfs(0, m);
        if (ans.size()) {
            sort(ans.begin(), ans.end(), cmp);
            for (PAIR i:ans)
                cout << i.first << " " << i.second << endl;
        } else
            cout << "No Solution\n";
    }

    return 0;
}

B Merging Linked Lists

??一道很好的資料結構鏈表的考題，細心即可，

#include<cstdio>
#include<algorithm>

using namespace std;
const int MAXN = 100010;
int val[MAXN], nxt[MAXN];
int head1, head2;
int n;

int main() {
    int a;

    scanf("%d %d %d", &head1, &head2, &n);
    while (n--) {
        scanf("%d", &a);
        scanf("%d %d", &val[a], &nxt[a]);
    }

    int cnt1 = 0, cnt2 = 0, tmp = head1;
    while (tmp != -1) {
        ++cnt1;
        tmp = nxt[tmp];
    }
    tmp = head2;
    while (tmp != -1) {
        ++cnt2;
        tmp = nxt[tmp];
    }
    //確定那個鏈表長、那個鏈表短，使得L1永遠是長的那個
    if (cnt1 < cnt2)
        swap(head1, head2);

    //Reverse L2
    int pre = -1;
    tmp = head2;
    while (tmp != -1) {
        int nxx = nxt[tmp];
        nxt[tmp] = pre;
        pre = tmp;
        tmp = nxx;
    }
    head2 = pre;
    //保留頭指標
    tmp = head1;

    while (head1 != -1 && head2 != -1) {
    	//跳過一個L1節點
        head1 = nxt[head1];
        //如果到末尾則跳出
        if (head1 == -1)
            break;
        //保留L2的下一個節點，因為要操作L2的next指標
        int nxx = nxt[head2];
        //這兩步把L2插入L1
        nxt[head2] = nxt[head1];
        nxt[head1] = head2;
        //L2重新取得原本該下一個的指標
        head2 = nxx;
		//兩次next就為原本的L1下一個
        head1 = nxt[head1];
        head1 = nxt[head1];
    }


    //輸出
    while (tmp != -1) {
        if (nxt[tmp] != -1)
            printf("%05d %d %05d\n", tmp, val[tmp], nxt[tmp]);
        else
            printf("%05d %d -1\n", tmp, val[tmp]);
        tmp = nxt[tmp];
    }
    return 0;
}

C Postfix Expression

??二叉樹，較簡單，DFS，

#include<iostream>
#include<string>

#define ac cin.tie(0);cin.sync_with_stdio(0);

using namespace std;
const int MAXN = 30;
int le[MAXN], ri[MAXN];
string val[MAXN];
bool vis[MAXN];
int n, root;

void dfs(int root) {
    if (root == -1)
        return;

    cout << "(";
    //注意題目陷阱，只有左子樹或者右子樹operator要提前
    if (le[root] != -1 && ri[root] != -1) {
        dfs(le[root]);
        dfs(ri[root]);
        cout << val[root] << ")";
    } else {
        cout << val[root];
        dfs(le[root]);
        dfs(ri[root]);
        cout << ")";
    }
}

int main() {
    ac

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> val[i] >> le[i] >> ri[i];
        if (le[i] >= 1)
            vis[le[i]] = true;
        if (ri[i] >= 1)
            vis[ri[i]] = true;
    }

    //find root
    for (int i = 1; i <= n; i++)
        if (!vis[i]) {
            root = i;
            break;
        }

    dfs(root);

    return 0;
}

Dijikstra Sequence

??PAT圖論模板題，

#include<iostream>
#include<cstring>
#include<algorithm>

#define ac cin.tie(0);cin.sync_with_stdio(0);

using namespace std;
const int MAXN = 1010;
int G[MAXN][MAXN], dist[MAXN], arr[MAXN];
bool vis[MAXN];
int n, m, k;
//PAT式迪杰斯特拉演算法
bool solve() {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[arr[1]] = 0;
    int cnt = 1;

    for (int i = 1; i <= n; i++) {
        int k = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (k == -1 || dist[j] < dist[k]))
                k = j;
        //判斷是否合法
        if (dist[k] != dist[arr[cnt++]])
            return false;
        vis[k] = true;
        for (int j = 1; j <= n; j++) {
            if (vis[j])
                continue;
            if (dist[j] > dist[k] + G[k][j])
                dist[j] = dist[k] + G[k][j];
        }
    }
    return true;
}

int main() {
    ac
    int a, b, c;

    memset(G, 0x3f, sizeof(G));

    cin >> n >> m;
    while (m--) {
        cin >> a >> b >> c;
        G[a][b] = G[b][a] = c;
    }

    cin >> k;
    while (k--) {
        for (int i = 1; i <= n; i++)
            cin >> arr[i];
        if (solve())
            cout << "Yes";
        else
            cout << "No";
        if (k)
            cout << endl;
    }

    return 0;
}