编程竞赛题目解析
问题 A: 字符串倍数判断
判断输入字符串的长度是否为5的倍数。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
if (s.length() % 5 == 0) {
cout << "是的" << endl;
} else {
cout << "不是" << endl;
}
return 0;
}问题 B: 人员变动统计
计算人员变动前后的差异值。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> old(m + 1), new_(m + 1);
for (int i = 1; i <= n; ++i) {
int a, b;
cin >> a >> b;
old[a]++;
new_[b]++;
}
for (int i = 1; i <= m; ++i) {
cout << new_[i] - old[i] << endl;
}
}
int main() {
solve();
return 0;
}问题 C: 集合操作
实现一个支持插入和删除小于特定值元素的集合操作。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int q;
cin >> q;
multiset<int> s;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
s.insert(x);
cout << s.size() << endl;
} else {
int x;
cin >> x;
auto it = s.lower_bound(x);
while (s.begin() != it) {
s.erase(s.begin());
}
s.erase(x);
cout << s.size() << endl;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}问题 D: 美数构造
构造所有长度不超过9位的美数（由2的幂次拼接而成）。
方法一: 深度优先搜索
#include <bits/stdc++.h>
using namespace std;
vector<long long> len;
set<long long> res;
vector<long long> fact;
long long pow10[22];
void dfs(long long x, int length) {
res.insert(x);
for (int i = 0; i <= 31; ++i) {
if (length + len[i] <= 9) {
long long next = x * pow10[len[i]] + fact[i];
dfs(next, length + len[i]);
}
}
}
void solve() {
int n;
cin >> n;
for (int i = 0; i <= 31; ++i) {
fact.push_back(1LL << i);
string s = to_string(1LL << i);
len.push_back(s.size());
}
for (int i = 0; i < 32; ++i) {
dfs(fact[i], len[i]);
}
int count = 0;
while (count < n) {
count++;
res.erase(res.begin());
}
cout << *res.begin() << endl;
}
int main() {
pow10[0] = 1;
for (int i = 1; i <= 20; ++i) {
pow10[i] = pow10[i-1] * 10;
}
solve();
return 0;
}方法二: 广度优先搜索
#include <bits/stdc++.h>
using namespace std;
vector<long long> len, fact;
set<long long> res;
long long pow10[22];
const int MAX_QUEUE = 3e6 + 10;
long long queue[MAX_QUEUE];
int front = 0, back = -1;
void bfs() {
for (int i = 0; i < 32; ++i) {
queue[++back] = fact[i];
}
while (front <= back) {
long long current = queue[front++];
res.insert(current);
string s = to_string(current);
int length = s.size();
for (int i = 0; i < 32; ++i) {
if (length + len[i] <= 9) {
long long next = current * pow10[len[i]] + fact[i];
queue[++back] = next;
}
}
}
}
void solve() {
int n;
cin >> n;
for (int i = 0; i <= 31; ++i) {
fact.push_back(1LL << i);
string s = to_string(1LL << i);
len.push_back(s.size());
}
bfs();
int count = 0;
while (count < n) {
count++;
res.erase(res.begin());
}
cout << *res.begin() << endl;
}
int main() {
pow10[0] = 1;
for (int i = 1; i <= 20; ++i) {
pow10[i] = pow10[i-1] * 10;
}
solve();
return 0;
}问题 E: 树距离验证
验证给定的图是否可以唯一生成一个满足特定距离要求的树。
方法一: Kruskal算法
#include <bits/stdc++.h>
using namespace std;
class DSU {
private:
vector<int> parent, size;
public:
DSU(int n) {
parent.resize(n+1);
size.resize(n+1, 1);
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != parent[parent[x]]) {
parent[x] = parent[parent[x]];
}
return parent[x];
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (size[x] <= size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
}
bool same(int x, int y) { return find(x) == find(y); }
};
struct Edge {
int to, weight;
};
bool bfsValidation(const vector<vector<Edge>>& graph, const vector<vector<int>>& distance, int start) {
queue<pair<int, int>> q;
q.push({start, 0});
vector<bool> visited(distance.size(), false);
while (!q.empty()) {
auto [u, dis] = q.front();
q.pop();
if (visited[u]) continue;
visited[u] = true;
if (distance[start][u] != dis) return false;
for (const auto& e : graph[u]) {
q.push({e.to, dis + e.weight});
}
}
return true;
}
void solve() {
int n;
cin >> n;
vector<vector<int>> distance(n+1, vector<int>(n+1));
vector<array<int, 3>> edges;
for (int i = 1; i <= n; ++i) {
for (int j = i+1; j <= n; ++j) {
int w;
cin >> w;
distance[i][j] = w;
distance[j][i] = w;
edges.push_back({w, i, j});
}
}
sort(edges.begin(), edges.end());
DSU dsu(n+1);
vector<vector<Edge>> graph(n+1);
for (const auto& e : edges) {
int u = e[1], v = e[2], w = e[0];
if (dsu.same(u, v)) continue;
dsu.merge(u, v);
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
for (int i = 1; i <= n; ++i) {
if (!bfsValidation(graph, distance, i)) {
cout << "不符合条件" << endl;
return;
}
}
cout << "符合条件" << endl;
}
int main() {
solve();
return 0;
}方法二: Prim算法
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, weight;
};
bool bfsValidation(const vector<vector<Edge>>& graph, const vector<vector<int>>& distance, int start) {
queue<pair<int, int>> q;
q.push({start, 0});
vector<bool> visited(distance.size(), false);
while (!q.empty()) {
auto [u, dis] = q.front();
q.pop();
if (visited[u]) continue;
visited[u] = true;
if (distance[start][u] != dis) return false;
for (const auto& e : graph[u]) {
q.push({e.to, dis + e.weight});
}
}
return true;
}
void primAlgorithm(const vector<vector<int>>& distance, vector<vector<Edge>>& graph) {
int n = distance.size() - 1;
vector<bool> visited(n+1, false);
vector<int> minDistance(n+1, 0x3f3f3f3f);
vector<int> parent(n+1, 0);
minDistance[1] = 0;
for (int i = 1; i <= n; ++i) {
int u = -1;
for (int j = 1; j <= n; ++j) {
if (!visited[j] && (u == -1 || minDistance[j] < minDistance[u])) {
u = j;
}
}
visited[u] = true;
for (int j = 1; j <= n; ++j) {
if (!visited[j] && distance[u][j] < minDistance[j]) {
minDistance[j] = distance[u][j];
parent[j] = u;
}
}
if (i != 1) {
graph[u].push_back({parent[u], distance[u][parent[u]]});
graph[parent[u]].push_back({u, distance[u][parent[u]]});
}
}
}
void solve() {
int n;
cin >> n;
vector<vector<int>> distance(n+1, vector<int>(n+1));
for (int i = 1; i <= n; ++i) {
for (int j = i+1; j <= n; ++j) {
int w;
cin >> w;
distance[i][j] = w;
distance[j][i] = w;
}
}
vector<vector<Edge>> graph(n+1);
primAlgorithm(distance, graph);
for (int i = 1; i <= n; ++i) {
if (!bfsValidation(graph, distance, i)) {
cout << "不符合条件" << endl;
return;
}
}
cout << "符合条件" << endl;
}
int main() {
solve();
return 0;
}