程序设计进阶实践
资源¶
- PTA 习题答案 @ 茵符草
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;
}
}