下面的代码并不保证最优的时间复杂度，前两题都 ac 了。
第三题在笔试时忘了优先队列自定义函数怎么写了，笔试结束后才完成，测例能够通过，仅作为参考。
参考代码
第一题《身份证号》：深搜
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
int n = 18;
vector<int> W{7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
string M = "10X98765432";
auto check = [&](string s) -> bool {
int sum = 0;
for (int i = 0; i < n - 1; ++i) {
sum += W[i] * (s[i] - '0');
}
return M[sum % 11] == s[n - 1];
};
cin >> T;
while (T--) {
string s;
cin >> s;
int ans = 0;
function<void(int)> Dfs = [&](int k) {
if (k == n - 1) {
if (check(s)) {
ans += 1;
}
return ;
}
if (s[k] != '*') {
Dfs(k + 1);
} else {
for (int i = 0; i < 10; ++i) {
s[k] = i + '0';
Dfs(k + 1);
}
s[k] = '*';
}
};
Dfs(0);
cout << ans << '\n';
}
return 0;
}
/*
2
34088119480815*663
520123200501169**4
1
9
*/ 第二题《比赛排名》：拓扑排序
#include <bits/stdc++.h>
using namespace std;
void solve() {
int N, M, C;
cin >> N >> M;
vector<unordered_set<int>> children(N + 1), parent(N + 1);
while (M--) {
cin >> C;
int pre = -1, x;
while (C--) {
cin >> x;
if (pre != -1) {
children[pre].emplace(x);
parent[x].emplace(pre);
}
pre = x;
}
}
vector<int> indeg(N + 1);
queue<int> q;
for (int i = 1; i <= N; ++i) {
indeg[i] = parent[i].size();
if (indeg[i] == 0) {
q.emplace(i);
}
}
vector<int> ans;
while (!q.empty()) {
if (q.size() != 1) {
break;
}
int u = q.front();
ans.emplace_back(u);
q.pop();
while (!children[u].empty()) {
int v = *children[u].begin();
if (--indeg[v] == 0) {
q.emplace(v);
}
children[u].erase(v);
}
}
if (ans.size() != N) {
cout << "NO\n";
} else {
for (int i = 0; i < N; ++i) {
cout << ans[i] << " \n"[i == N - 1];
}
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
4
3 2
2 1 3
2 1 2
4 3
3 1 2 3
2 1 3
2 1 4
4 1
4 1 2 3 4
4 3
3 1 2 4
3 1 3 4
2 3 2
NO
NO
1 2 3 4
1 3 2 4
*/ 第三题《永远的七日之都》：优先队列（本题只是作为参考，因为笔试时忘了优先队列自定义函数怎么写了）
#include <bits/stdc++.h>
using namespace std;
#define MOD 1'000'000'007
void solve() {
int N, K, p, w;
cin >> N >> K;
auto lt_cmp = [&](auto &lhs, auto &rhs) {
auto [l_base, l_inc, l_p] = lhs;
auto [r_base, r_inc, r_p] = rhs;
return 1.0 * (l_base + l_inc) / l_base < 1.0 * (r_base + r_inc) / r_base;
};
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(lt_cmp)> q(lt_cmp);
long long ans = 1;
while (N--) {
cin >> p >> w;
int base = p * w + 100 - p;
if (p != 100) {
q.emplace(base, w - 1, p);
} else {
ans = (ans * base) % MOD;
}
}
while (K--) {
if (q.empty()) {
break;
}
auto [base, inc, p] = q.top();
q.pop();
if (p + 1 == 100) {
ans = (ans * (base + inc)) % MOD;
} else {
q.emplace(base + inc, inc, p + 1);
}
}
while (!q.empty()) {
auto [base, inc, p] = q.top();
q.pop();
ans = (ans * base) % MOD;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
3
3 2
0 2
0 3
0 4
3 2
0 4
0 4
1 4
5 6
0 4
0 4
0 4
0 4
0 4
1060000
1092727
930393309
*/ 
全部评论
(1) 回帖