当前位置：首页 > news >正文

混杂的题目

news 2026/3/26 18:37:13

A - 最短 Hamilton 路径

具体做法见这里。戳我喵~

B - Barn Painting G

做法

一眼树形\(DP\)

首先，观察这个需不需要换根。

并没有求从每个点出发的答案，所以以任意一个点为起点即可。

\(dp_{u,c}\)表示以\(u\)为根的子树染成\(c\)颜色的方案数

初始化呢，我们需要把\(dp_{u,1}\)、\(dp_{u,2}\)、\(dp_{u,3}\)都变为\(1\)，为后面的乘法能够正常使用。

那么中间就是转移三种不同的颜色了。

\[dp_{u,c} = \prod_{v \in son_u} (dp_{v, c_1} + dp_{v,c_2}),c_1 \not= c_2 \not= c \]

但是有一些节点固定了颜色怎么办？

固定了颜色的节点就直接把另外两种颜色的值变为\(0\)，即：

\[dp_{u,c_1} = dp_{u,c_2} = 0,c_1 \not= c_2 \not= color_u \]

哦，对了，不要忘记取模了！\(\color{white}不然就没有母了喵~！\)

代码

戳我捏~

#include <bits/stdc++.h>
#define IAKIOI ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);const int N = 5e5 + 10, INF = 0x3f3f3f3f;using namespace std;using lint = long long;
using ulint = unsigned long long;
using pii = pair<int, int>;const int mod = 1e9 + 7;lint dp[N][4], col[N]; //dp[u][c]表示以u为根的子树染成c颜色的方案数
vector<int> g[N];void dfs(int u, int fa) {dp[u][1] = dp[u][2] = dp[u][3] = 1;for (auto v : g[u]) {if (v == fa) continue;dfs(v, u);dp[u][1] = (dp[u][1] * ((dp[v][2] + dp[v][3]) % mod)) % mod;dp[u][2] = (dp[u][2] * ((dp[v][1] + dp[v][3]) % mod)) % mod;dp[u][3] = (dp[u][3] * ((dp[v][1] + dp[v][2]) % mod)) % mod;}if (col[u]) for (int i = 1; i <= 3; i++) if (i != col[u]) dp[u][i] = 0;
}int main() {
//		freopen("paint.in", "r", stdin);
//		freopen("paint.out", "w", stdout);IAKIOIint n, k;cin >> n >> k;for (int i = 1, u, v; i < n; i++) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);for (int i = 1, u; i <= k; i++) cin >> u >> col[u];dfs(1, 0);cout << (dp[1][1] + dp[1][2] + dp[1][3]) % mod << '\n';
}

C - 树的同构对统计

做法

树哈希模版。

做法可参考这个戳我喵~

只需要在这个基础上更改一下即可，其实就是用unordered_map或者map存下来哈希值的总和即可。

代码

戳我喵~

#include <bits/stdc++.h>
#define IAKIOI ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);const int N = 1e5 + 10, INF = 0x3f3f3f3f;using namespace std;using lint = long long;
using ulint = unsigned long long;
using pii = pair<int, int>;mt19937_64 rd(time(nullptr));const ulint mask = rd();ulint f(int x) {x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= x << 19, x ^= mask;return x;
}ulint Hash[N], G[N];
vector<int> g[N];void dfs1(int u, int fa) {Hash[u] = 1;for (auto v : g[u]) {if (v == fa) continue;dfs1(v, u);Hash[u] += f(Hash[v]);}
}void dfs2(int u, int fa) {for (auto v : g[u]) {if (v == fa) continue;G[v] = Hash[v] + f(G[u] - f(Hash[v]));dfs2(v, u);}
}unordered_map<ulint, int> mp;int main() {//		freopen("tree.in", "r", stdin);//		freopen("tree.out", "w", stdout);IAKIOIint T, ans = 0;cin >> T;for (int k = 1; k <= T; k++) {int n;cin >> n;for (int i = 1; i <= n; i++) g[i].clear();for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;g[u].push_back(v), g[v].push_back(u);}dfs1(1, 0), G[1] = Hash[1], dfs2(1, 0);ulint cnt = 0;for (int i = 1; i <= n; i++) cnt += f(G[i]);ans += mp[cnt], mp[cnt]++;}cout << ans << '\n';
}