基本情况
学到了不少，多谢雷根哥！
拼接1学了另外两种写法，拼接2学了正解，后面还学到用拓扑排序判环，以及dfs来找连通块中的点数量
充满希望的拼接质数1
MySolution
DFS，通过让下标递增来找不同方案。
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a) cin >> i;
int ans = 0;
auto check = [&](int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
return true;
};
auto dfs = [&](auto self, int ind, int sum)->void {
if (check(sum)) ans++;
for (int i = ind + 1; i < n; i++) {
self(self, i, sum + a[i]);
}
};
dfs(dfs, -1, 0);
cout << ans << endl;
return 0;
}
\(\text{RegenSolution}\)
-
DFS选或不选
int main() { int n; cin >> n; vector<int> a(n); for (auto& i : a) cin >> i; int ans = 0; auto check = [&](int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) if (x % i == 0) return false; return true; }; auto dfs = [&](auto self, int now, int sum)->void { if (now == n) { if (check(sum)) ans++;//这里要在now == n的时候才能计数，因为这个方法是选或不选，now = n时的方案才是一到n个物品中有的选有的不选的方案。 return ; } self(self, now + 1, sum);//不选当前这个 self(self, now + 1, sum + a[now]);//选当前这个 }; dfs(dfs, 0, 0); cout << ans << endl; return 0; } -
用二进制来枚举
int main() { int n; cin >> n; vector<int> a(n); for (auto& i : a) cin >> i; int ans = 0; auto check = [&](int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) if (x % i == 0) return false; return true; }; for (int j = 0; j < (1 << n); j++) {//n位代表n个物品选或不选，从0到1<<n自然覆盖了所有情况 int sum = 0; for (int i = 0; i < n; i++) { if (j & (1 << i)) sum += a[i];//拆位分析，如果该位选了，综合加上 } if (check(sum)) ans++; } cout << ans << endl; return 0; }
充满希望的拼接质数2
MySolution
这题验证方案不同的方式仅仅是数值不同，我用了两个方法都过不了。
-
数组标记
int main() { int n; cin >> n; vector<int> a(n); for (auto& i : a) cin >> i; sort(all(a)); int ans = 0; auto check = [&](int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) if (x % i == 0) return false; return true; }; array<array<bool, 1001>, 13> vis;//第step步的数不能重复，（没啥逻辑的想法） auto dfs = [&](auto self, int ind, int sum, int step)->void { if (check(sum)) ans++; for (int i = ind + 1; i < n; i++) { if (!vis[step + 1][a[i]]) { vis[step + 1][a[i]] = true; self(self, i, sum + a[i], step + 1); } } }; dfs(dfs, -1, 0, 0); cout << ans << endl; return 0; } -
暴力判断
int main() { int n; cin >> n; vector<int> a(n); for (auto& i : a) cin >> i; sort(all(a)); int ans = 0; auto check = [&](int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) if (x % i == 0) return false; return true; }; vector<vector<int> > total_res;//暴力存下所有结果，然后一个个比 auto dfs = [&](auto self, int ind, int sum, vector<int>& res)->void { if (check(sum)) { bool ok = true; for (auto vec : total_res) { if (vec.size() != res.size()) continue; for (int i = 0; i < sz(res); i++) { if (vec[i] != res[i]) ok = false; } } if (ok) total_res.emplace_back(res), ans++; } for (int i = ind + 1; i < n; i++) { res.emplace_back(a[i]); self(self, i, sum + a[i], res); res.pop_back(); } }; vector<int> t; dfs(dfs, -1, 0, t); cout << ans << endl; return 0; }
\(\text{RegenSolution}\)
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a) cin >> i;
sort(all(a));
int ans = 0;
auto check = [&](int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
return true;
};
auto dfs = [&](auto self, int now, int sum, bool flag)->void {
if (now == n) {
if (check(sum)) ans++;
return ;
}
self(self, now + 1, sum, false);//该元素不选，或者前面重复过了，不能再选
if (flag || a[now - 1] != a[now])//如果这个元素是不和上一个元素重复的，那么后面所有的方案都是唯一的，那么该元素可以选
self(self, now + 1, sum + a[now], true);
};
sort(all(a));//先排好序，这样重复的元素相邻，方便处理
dfs(dfs, 0, 0, true);
cout << ans << endl;
return 0;
}
充满希望的连通块问题
MySolution
我用的并查集，但这里雷根哥指出一个问题。
int findSet(int x) {return x == fa[x] ? x : (fa[x] = findSet(fa[x]));}
void merge(int x, int y) {
int fx = findSet(x), fy = findSet(y);
if (fx == fy) return ;
if (siz[fx] > siz[fy]) swap(fx, fy);
fa[fx] = fy;
siz[fy] += siz[fx];
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
for (int _ = 0; _ < m; _++) {
int u, v; cin >> u >> v;
merge(u, v);
}
int x, y;
cin >> x >> y;
if (findSet(x) == findSet(y))
cout << siz[findSet(x)] << endl;
else
cout << 0 << endl;
return 0;
}
这里的按秩合并是没有作用的
if (siz[fx] > siz[fy]) swap(fx, fy);
因为我已经进行了路径压缩，查找成本已经到了 \(O(1)\)。
\(\text{RegenSolution}\)
此题还可以直接DFS
int main()
{
int n, m;
cin >> n >> m;
for (int _ = 0; _ < m; _++) {
int u, v; cin >> u >> v;
add_edge(u, v); add_edge(v, u);
}
int x, y, ans = 0;
cin >> x >> y;
vector<bool> vis(n + 1);
auto dfs = [&](auto self, int u) -> void {
if (vis[u]) return ;
vis[u] = true;
ans++;
for (int i = head[u]; i; i = edge[i].next) {
self(self, edge[i].to);
}
};
dfs(dfs, x);
if (vis[y])
cout << ans << endl;
else
cout << 0 << endl;
return 0;
}
充满希望的课程安排
用拓扑排序判环。
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#define inf 0x7fffffff
#define linf 0x7fffffffffffffff
#define endl '\n'
#define sz(X) (int)(X).size()
#define all1(X) (X).begin() + 1, (X).end()
#define all(X) (X).begin(), (X).end()
#define YES cout << "YES" << '\n'
#define Yes cout << "Yes" << '\n'
#define NO cout << "NO" << '\n'
#define No cout << "No" << '\n'
#define error cout << "-1" << '\n'
#define debug1(X) cout << #X << ": " << X << '\n'
#define debug2(X) cout << #X << ": " << X << ' '
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 10;
struct Edge
{
int to, next;
} edge[N << 1];
int head[N], tot;
void add_edge(int u, int v)
{
edge[++tot].to = v, edge[tot].next = head[u];
head[u] = tot;
}
int n, m, q[N << 1], d[N + 1];
int main()
{
cin >> n >> m;
for (int _ = 0, x, y; _ < m; _++)
{
cin >> x >> y;
add_edge(x, y);
d[y]++;
}
int cnt = 0;
queue<int> q;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) q.push(i), cnt++;//先加入入度为0的点
}
while(!q.empty()) {//拓扑排序
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edge[i].next) {
int to = edge[i].to;
d[to]--;
if (d[to] == 0) q.push(to), cnt++;
}
}
if (cnt == n) YES;//所有点成拓扑序
else NO;
}