跳转至

程序设计进阶实践

资源

PTA 习题答案

二叉树的递归遍历

void PreorderTraversal(BinTree BT) {
    if (BT == NULL) return;
    printf("%c", BT->Data);
    PreorderTraversal(BT->Left);
    PreorderTraversal(BT->Right);
}
void InorderTraversal(BinTree BT) {
    if (BT == NULL) return;
    InorderTraversal(BT->Left);
    printf("%c", BT->Data);
    InorderTraversal(BT->Right);
}
void PostorderTraversal(BinTree BT) {
    if (BT == NULL) return;
    PostorderTraversal(BT->Left);
    PostorderTraversal(BT->Right);
    printf("%c", BT->Data);
}

二叉排序树查找操作

BSTree SearchBST(BSTree T, ElemType e) {
    if (T == NULL) return NULL;
    if (e == T->data) return T;
    if (e < T->data) return SearchBST(T->lchild,e);
    if (e > T->data) return SearchBST(T->rchild,e);
}

浦島太郎の玉手箱開き

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 输入性能优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, maxVal = 0, minVal = 100000001;
    cin >> n;
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int> > minHeap;
    for (int i = 0; i < n; i++) {
        int now;
        cin >> now;
        maxVal = max(maxVal, now);
        minVal = min(minVal, now);
        if (maxHeap.empty() || now <= maxHeap.top()) {
            maxHeap.push(now);
        } else {
            minHeap.push(now);
        }
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
        int median;
        if (maxHeap.size() == minHeap.size()) {
            median = (maxVal + minVal + maxHeap.top() + minHeap.top()) / 4;
        } else {
            median = (maxVal + minVal + maxHeap.top() ) / 3;
        }
        cout << median << " \n"[i == n - 1];
    }
}

完全二叉树权值

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> w(n);
    for (int i = 0; i < n; ++i) cin >> w[i];
    int max_sum = -1e6;
    vector<int> depths;
    int depth = 1, start = 0;
    while (start < n) {
        int end = min(start + (1 << (depth - 1)) - 1, n - 1);
        int sum = 0;
        for (int i = start; i <= end; ++i) sum += w[i];
        if (sum > max_sum) {
            max_sum = sum;
            depths = {depth};
        } else if (sum == max_sum) {
            depths.push_back(depth);
        }
        start = end + 1;
        depth++;
    }
    cout << max_sum << endl;
    for (int i = 0; i < depths.size(); ++i) {
        if (i) cout << " ";
        cout << depths[i];
    }
    cout << endl;
    return 0;
}

郁闷的语文课代表

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n, min_score;
    cin >> n >> min_score;
    vector<int> students;
    int delta = 0;
    int left_count = 0;
    for (int i = 0; i < n; i++) {
        char cmd;
        int k;
        cin >> cmd >> k;
        if (cmd == 'I') {
            if (k >= min_score) {
                students.insert(lower_bound(students.begin(), students.end(), k - delta), k - delta);
            }
        } else if (cmd == 'A') {
            delta += k;
        } else if (cmd == 'S') {
            delta -= k;
            auto it = lower_bound(students.begin(), students.end(), min_score - delta);
            left_count += it - students.begin();
            students.erase(students.begin(), it);
        } else if (cmd == 'F') {
            if (students.size() < k) {
                cout << -1 << '\n';
            } else {
                cout << students[students.size() - k] + delta << '\n';
            }
        }
    }
    cout << left_count;
    return 0;
}

选择排序

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
        int minVal = arr[i], minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if(arr[j] < minVal){
                minVal = arr[j];
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
        cout << (i == n - 1 ? "sorted array: " : "step " + to_string(i + 1) + ": ");
        for (int j = 0; j < n; j++) {
            cout << arr[j] << (j == n - 1 ? " \n" : " ");
        }
    }
}

冒泡排序

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> arr(5);
    for (int i = 0; i < 5; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i < 5; i++) {
        for (int j = 1; j < 5; j++) {
            if (arr[j] < arr[j - 1]){
                swap(arr[j], arr[j - 1]);
                for (int k = 0; k < 5; k++) {
                    cout << arr[k] << " \n"[k == 4];
                }
            }
        }
    }
}

前缀和

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> arr(n + 1);
    for (int i = 0; i < n; i++) {
        int now;
        cin >> now;
        arr[i + 1] = arr[i] + now;
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        cout << arr[r] - arr[l - 1] << endl;
    }
}

二分搜索

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
bool check(int k, int R, int C, const std::vector<std::string>& matrix) {
    set<string> unique_columns;
    for (int j = 0; j < C; ++j) {
        string current_column = "";
        for (int i = k; i < R; ++i) {
            current_column += matrix[i][j];
        }
        if (unique_columns.count(current_column)) {
            return false;
        }
        unique_columns.insert(current_column);
    }
    return true;
}
int main() {
    int R, C;
    cin >> R >> C;
    vector<string> matrix(R);
    for (int i = 0; i < R; ++i) {
        cin >> matrix[i];
    }
    int low = 0, high = R - 1, ans = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid, R, C, matrix)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << ans << endl;
}

贝茜放慢脚步

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int main() {
    int N;
    cin >> N;
    priority_queue<int, vector<int>, greater<int>> time_events;
    priority_queue<int, vector<int>, greater<int>> dist_events;
    for (int i = 0; i < N; ++i) {
        char type;
        int x;
        cin >> type >> x;
        if (type == 'T') {
            time_events.push(x);
        } else {
            dist_events.push(x);
        }
    }
    double current_time = 0.0;
    double current_dist = 0.0;
    int speed_denominator = 1;
    while (current_dist < 1000.0) {
        double next_time_event_val = time_events.empty() ? -1.0 : static_cast<double>(time_events.top());
        double next_dist_event_val = dist_events.empty() ? -1.0 : static_cast<double>(dist_events.top());
        bool has_time_event = next_time_event_val != -1.0;
        bool has_dist_event = next_dist_event_val != -1.0;
        double time_to_reach_next_dist = has_dist_event ? (next_dist_event_val - current_dist) * speed_denominator : -1.0;
        double event_time;
        if (!has_time_event && !has_dist_event) {
            event_time = current_time + (1000.0 - current_dist) * speed_denominator;
        } else if (has_time_event && has_dist_event) {
            event_time = min(next_time_event_val, current_time + time_to_reach_next_dist);
        } else if (has_time_event) {
            event_time = next_time_event_val;
        } else {
            event_time = current_time + time_to_reach_next_dist;
        }
        double dist_covered_in_interval = (event_time - current_time) / speed_denominator;
        current_time = event_time;
        current_dist += dist_covered_in_interval;
        const double EPS = 1e-9; 
        if (has_time_event && abs(current_time - next_time_event_val) < EPS) {
            time_events.pop();
            speed_denominator++;
        }
        if (has_dist_event && abs(current_dist - next_dist_event_val) < EPS) {
            dist_events.pop();
            speed_denominator++;
        }
    }
    long long rounded_time = static_cast<long long>(round(current_time));
    cout << rounded_time << endl;
    return 0;
}

图的深度优先遍历

#include <iostream>
#include <vector>
using namespace std;
void dfs(int cur, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& result) {
    visited[cur] = true;
    result.push_back(cur);
    for (int neighbor : graph[cur]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited, result);
        }
    }
}
int main() {
    int N, M, S;
    cin >> N >> M >> S;
    vector<vector<int>> graph(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i = 1; i <= N; ++i) {
        sort(graph[i].begin(), graph[i].end());
    }
    vector<bool> visited(N + 1, false);
    vector<int> result;
    dfs(S, graph, visited, result);
    for (int node : result) {
        cout << node << " ";
    }
    bool allVisited = true;
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            allVisited = false;
            break;
        }
    }
    if (!allVisited) {
        cout << endl << "Non-connected";
    }
    return 0;
}

双十一

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
void floydWarshall(vector<vector<int>>& dist, int n) {
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}
int main() {
    int n, e;
    while (cin >> n >> e) {
        vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; ++i) {
            dist[i][i] = 0;
        }
        for (int i = 0; i < e; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            dist[a][b] = c;
            dist[b][a] = c;
        }
        floydWarshall(dist, n);
        int minSum = INT_MAX;
        int bestCity = 0;
        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = 0; j < n; ++j) {
                sum += dist[i][j];
            }
            if (sum < minSum) {
                minSum = sum;
                bestCity = i;
            }
        }
        cout << bestCity << endl;
    }
}

发言顺序

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int n, e;
    cin >> n >> e;
    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);
    for (int i = 0; i < e; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        inDegree[b]++;
    }
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) {
            pq.push(i);
        }
    }
    vector<int> result;
    while (!pq.empty()) {
        int current = pq.top();
        pq.pop();
        result.push_back(current);
        for (int neighbor : graph[current]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                pq.push(neighbor);
            }
        }
    }
    for (int num : result) {
        cout << num << " ";
    }
}

公路村村通

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};
vector<int> parent;
int find(int u) {
    if (parent[u] != u) {
        parent[u] = find(parent[u]);
    }
    return parent[u];
}
bool unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return false;
    parent[v] = u;
    return true;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    sort(edges.begin(), edges.end());
    parent.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
    int total = 0, cnt = 0;
    for (const Edge& e : edges) {
        if (unite(e.u, e.v)) {
            total += e.w;
            if (++cnt == n - 1) break;
        }
    }
    if (cnt == n - 1) {
        cout << total << endl;
    } else {
        cout << -1 << endl;
    }
}

共享电车

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 1e18;
int main() {
    int n, m, L;
    cin >> n >> m >> L;
    vector<vector<long long>> dist(n+1, vector<long long>(n+1, INF));
    for (int i=1; i<=n; i++) dist[i][i] = 0;
    for (int i=0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c < dist[a][b]) {
            dist[a][b] = c;
            dist[b][a] = c;
        }
    }
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
    vector<vector<int>> new_graph(n+1);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i != j && dist[i][j] <= L) {
                new_graph[i].push_back(j);
            }
        }
    }
    vector<vector<int>> steps(n+1, vector<int>(n+1, -1));
    for (int s=1; s<=n; s++) {
        queue<int> q;
        steps[s][s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : new_graph[u]) {
                if (steps[s][v] == -1) {
                    steps[s][v] = steps[s][u] + 1;
                    q.push(v);
                }
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        if (steps[s][t] == -1) {
            cout << -1 << endl;
        } else {
            cout << steps[s][t] - 1 << endl;
        }
    }
}

最好的文档

#include <iostream>
using namespace std;
int main() {
    cout << "Good code is its own best documentation.";
}

什么是机器学习

#include <iostream>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b;
    int c = a + b;
    cout << c - 16 <<endl;
    cout << c - 3 <<endl;
    cout << c - 1 <<endl;
    cout << c;
}

程序员买包子

#include <iostream>
using namespace std;
int main() {
    int n, m, k;
    string x;
    cin >> n >> x >> m >> k;
    if (k == n)
        cout << "mei you mai " << x << " de";
    else if (k == m)
        cout << "kan dao le mai " << x << " de";
    else
        cout << "wang le zhao mai " << x << " de";
}

进化论

#include <iostream>
using namespace std;
int main() {
    int n, a, b, c;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        if (c == a * b)
            cout << "Lv Yan" << endl;
        else if (c == a + b)
            cout << "Tu Dou" << endl;
        else
            cout << "zhe du shi sha ya!" << endl;
    }
}

猜帽子游戏

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, k;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        vector<int> g(n);
        bool correct = false, wrong = false;
        for (int j = 0; j < n; j++) {
            int now;
            cin >> now;
            if (now == a[j])
                correct = true;
            if (now != 0 && now != a[j])
                wrong = true;
        }
        if (correct && !wrong)
            cout << "Da Jiang!!!" << endl;
        else
            cout << "Ai Ya" << endl;
    }
}

剪切粘贴

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<char> cut(vector<char> &s, int beginIndex, int endIndex) {
    vector<char> res(s.begin() + beginIndex - 1, s.begin() + endIndex);
    s.erase(s.begin() + beginIndex - 1, s.begin() + endIndex);
    return res;
}
void paste(vector<char> &s, vector<char> n, string beginString, string endString) {
    string unitedString = beginString + endString;
    vector<char> unitedStringVec(unitedString.begin(), unitedString.end());
    auto iterator = search(s.begin(), s.end(), unitedStringVec.begin(), unitedStringVec.end());
    if (iterator == s.end())
        s.insert(iterator, n.begin(), n.end());
    else
        s.insert(iterator + beginString.length(), n.begin(), n.end());
}
int main() {
    int n, beginIndex, endIndex;
    string s, beginString, endString;
    cin >> s;
    vector<char> sVec(s.begin(), s.end());
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> beginIndex >> endIndex >> beginString >> endString;
        vector<char> res = cut(sVec, beginIndex, endIndex);
        paste(sVec, res, beginString, endString);
    }
    for (int i = 0; i < sVec.size(); i++) {
        cout << sVec[i];
    }
}

分寝室

#include <iostream>
using namespace std;
int main() {
    int n0, n1, n, minVal = 100000, minRes = -1;
    cin >> n0 >> n1 >> n;
    for (int i = 1; i < n; i++) {
        if(n0 % i == 0 && n1 % (n - i) == 0 && n0 / i > 1 && n1 / (n - i) > 1) {
            if(abs(n0 / i - n1 / (n - i)) < minVal) {
                minVal = abs(n0 / i - n1 / (n - i));
                minRes = i;
            }
        }
    }
    if (minRes == -1) cout << "No Solution";
    else cout << minRes << ' ' << n - minRes;
}

谁管谁叫爹

#include <iostream>
using namespace std;
int sumDigit(int n) {
    int res = 0;
    while (n > 0) {
        res += n % 10;
        n /= 10;
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int na, nb;
        cin >> na >> nb;
        int sa = sumDigit(na), sb = sumDigit(nb);
        if(na % sb == 0 && !(nb % sa == 0)) cout << 'A' << endl;
        else if(nb % sa == 0 && !(na % sb == 0)) cout << 'B' << endl;
        else cout << (na > nb ? 'A' : 'B') << endl;
    }
}

编程解决一切

#include <iostream>
using namespace std;
int main() {
    cout << "Problem? The Solution: Programming.";
}

再进去几个人

#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    cout << b - a;
}

帮助色盲

#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    if (b != 0) {
        cout << "-" << endl;
    } else {
        if (a == 1) {
            cout << "dudu" << endl;
        } else if (a == 2) {
            cout << "-" << endl;
        } else {
            cout << "biii" << endl;
        }
    }
    if (a == 1) {
        cout << "move" << endl;
    } else {
        cout << "stop" << endl;
    }
}

四项全能

#include <iostream>
using namespace std;
int main() {
    int n, m, sum = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int now;
        cin >> now;
        sum += now;
    }
    cout << max(sum - n * (m - 1), 0);
}

别再来这么多猫娘了!

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<string> v;
    for (int i = 1; i <= n; i++) {
        string t;
        cin >> t;
        v.push_back(t);
    }
    int k;
    cin >> k;
    string s;
    cin.ignore();
    getline(cin, s);
    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        while (s.find(v[i]) != string::npos) {
            s.replace(s.find(v[i]), v[i].length(), "`");
            cnt++;
        }
    }
    while (s.find("`") != string::npos) {
        s.replace(s.find("`"), 1, "<censored>");
    }
    if (cnt >= k) {
        cout << cnt << endl;
        cout << "He Xie Ni Quan Jia!";
    } else {
        cout << s << endl;
    }
    return 0;
}

兰州牛肉面

#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    int n;
    cin >> n;
    int sold[n];
    double price[n], sum = 0;
    for (int i = 0; i < n; i++){
        cin >> price[i];
        sold[i] = 0;
    }
    while (true) {
        int index, count;
        cin >> index >> count;
        if (index == 0) break;
        sold[index - 1] += count;
    }
    for (int i = 0; i < n; i++){
        cout << sold[i] << endl;
        sum += sold[i] * price[i];
    }
    cout << fixed << setprecision(2) << sum;
}

整数的持续性

#include <iostream>
#include <vector>
using namespace std;
int persistence(int n) {
    int res = 0;
    while (n >= 10) {
        int k = n;
        n = 1;
        res++;
        while (k > 0) {
            n *= k % 10;
            k /= 10;
        }
    }
    return res;
}
int main() {
    int a, b, maxVal = -1;
    cin >> a >> b;
    vector<int> maxVec;
    for (int i = a; i <= b; i++) {
        int res = persistence(i);
        if (res > maxVal) {
            maxVal = res;
            maxVec.clear();
        }
        if (res >= maxVal) {
            maxVec.push_back(i);
        }
    }
    cout << maxVal << endl;
    for (int i = 0; i < maxVec.size(); i++){
        cout << maxVec[i];
        if (i != maxVec.size() - 1)
            cout << ' ';
    }
}

九宫格

#include <iostream>
#include <vector>
using namespace std;
bool isValid(const vector<vector<int>>& grid) {
    for (int i = 0; i < 9; ++i) {
        vector<bool> row(10, false), col(10, false), box(10, false);
        for (int j = 0; j < 9; ++j) {
            int num_row = grid[i][j];
            int num_col = grid[j][i];
            int num_box = grid[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3];
            if (num_row < 1 || num_row > 9 || row[num_row]) return false;
            if (num_col < 1 || num_col > 9 || col[num_col]) return false;
            if (num_box < 1 || num_box > 9 || box[num_box]) return false;
            row[num_row] = col[num_col] = box[num_box] = true;
        }
    }
    return true;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        vector<vector<int>> grid(9, vector<int>(9));
        for (auto &row : grid)
            for (auto &num : row)
                cin >> num;
        cout << (isValid(grid) ? '1' : '0') << endl;
    }
}