I.一起看很美的日落！
求解树中所有联通块的两两异或和。这道题直接看不太好处理，所以要一边写一边分析：
首先拆位必然。设dp[i]为当前子树中的总贡献。则对于i中的每个子树j，其对dp[i]贡献都将是dp[j]乘以其他子树的构造种类数。据此，设op[i]为该子树中联通块的选择方案数。
但上述这些没有考虑i中的不同子树之间01组合的贡献。于是，我们再设hav[i][0/1]，表示子树内0/1所能提供的贡献（注意这个贡献不是点数，官方题解里也有提及）。
最后的答案即为每个子树内dp（贡献）之和。时间复杂度：
。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
#define B bitset<M>
const int inf = 4e18;
const int N = 1e6 + 5;
const int M = 32;
const int mod = 1e9 + 7;
int n, u, v, dep, res;
B arr[N];
int fa[N];
int pow2[N];
vector<int> g[N];
int dp[N], op[N]; // op为选择的方案数
int hav[N][2]; // hav为0/1能提供的总对数
void dfs(int pos)
{
dp[pos] = 0, op[pos] = 1, hav[pos][0] = hav[pos][1] = 0;
for (int i : g[pos])
{
if (i == fa[pos])
continue;
fa[i] = pos;
dfs(i);
(dp[pos] = dp[pos] * (op[i] + 1) % mod + dp[i] * op[pos] % mod) %= mod;
(dp[pos] += hav[pos][0] * hav[i][1] % mod + hav[pos][1] * hav[i][0] % mod) %= mod;
for (int j = 0; j < 2; j++)
(hav[pos][j] = hav[pos][j] * (op[i] + 1) % mod + hav[i][j] * op[pos] % mod) %= mod;
(op[pos] *= (op[i] + 1) % mod) %= mod;
}
(hav[pos][arr[pos][dep]] += op[pos]) %= mod;
(dp[pos] += hav[pos][arr[pos][dep] ^ 1]) %= mod;
(res += dp[pos] * pow2[dep] % mod) %= mod;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
pow2[0] = 1;
for (int i = 1; i <= 30; i++)
(pow2[i] = pow2[i - 1] * 2) %= mod;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> u;
arr[i] = u;
}
for (int i = 1; i < n; i++)
{
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (dep = 0; dep <= 30; dep++)
dfs(1);
(res *= 2) %= mod;
cout << res;
return 0;
}
M.那是我们的影子
求解的，且可能已经填了部分数字的异形数独的合法种类数。合法的定义为：任意九宫格内
恰好各出现1次。
很有趣的一道题！重点在于要想到编号mod 3结果相同的列里面的数应当是一样的，比如说第一列是，那第
列也应当是
。
在这个结论的基础上，我们只需要枚举第一个九宫格内的情况，就能轻松地解出此题。至于不存在的情况，只需要判断每个九宫格内是否合法+所有编号的列里面是否只出现了最多
种数即可。
时间复杂度：。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
const int inf = 4e18;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int Add[4] = {1, 1, 2, 6};
int t = 1, n, res;
int arr[N][4];
string s;
bool g[3][12]; // 记录编号%3的这些列中对应的数是否出现过
int sum[3], tmp[3]; // 记录编号%3的这些列中出现的数的种类数
int gg[12]; // 记录3*3九宫格内的数
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
while (t--)
{
cin >> n, res = 0;
for (int i = 1; i <= 3; i++)
{
cin >> s;
for (int j = 1; j <= n; j++)
arr[j][i] = (s[j - 1] == '?' ? 0 : s[j - 1] - '0');
}
bool valid = 1;
// 判断编号%3相同的列是否合法（最多只能出现3种不同的数）
for (int i = 0; i < 3; i++)
{
sum[i] = 0;
for (int j = 0; j <= 9; j++)
g[i][j] = 0;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 3; j++)
g[i % 3][arr[i][j]] = 1;
for (int i = 0; i < 3; i++)
{
for (int j = 1; j <= 9; j++)
sum[i] += g[i][j];
if (sum[i] > 3)
valid = 0;
}
for (int i = 0; i < 3; i++)
sum[i] = 3 - sum[i]; // 此时sum表示可以接受的其他数数量
// 判断每个3*3的格子里是否有重复的数
for (int i = 0; i <= 9; i++)
gg[i] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= 3; j++)
if ((++gg[arr[i][j]] > 1) && (arr[i][j]))
valid = 0;
if (i > 2)
for (int j = 1; j <= 3; j++)
gg[arr[i - 2][j]]--;
}
if (!valid)
{
cout << "0\n";
continue;
}
// 计算对于每个合法的第一个3*3可增加的答案
int add = 1;
for (int i = 4; i <= n; i++)
{
int tot = 0;
for (int j = 1; j <= 3; j++)
if (!arr[i][j])
tot++;
(add *= Add[tot]) %= mod;
}
// 枚举第一个3*3内的情况
vector<int> all{1, 2, 3, 4, 5, 6, 7, 8, 9};
do
{
valid = 1, tmp[1] = tmp[2] = tmp[0] = 0;
for (int i = 0; i < 9; i++)
{
if ((arr[i / 3 + 1][i % 3 + 1]) && (all[i] != arr[i / 3 + 1][i % 3 + 1]))
valid = 0;
if (!g[(i / 3 + 1) % 3][all[i]])
if (++tmp[(i / 3 + 1) % 3] > sum[(i / 3 + 1) % 3])
valid = 0;
}
if (valid)
(res += add) %= mod;
} while (next_permutation(all.begin(), all.end()));
cout << res << '\n';
}
return 0;
}
L.还会再见吗？
给定一棵有道题的树形刷题库，每道题目完成后能给各种各样颜色的气球（气球总数
），并可以跳转到任何一道与之相连的题目（可以是已经做过的，但已经做过的题目不会再给气球），求获得重复种类气球的最少跳转次数。
显然地，要把每种颜色的气球拆分出来考虑。我们先考虑这样一个子问题：如果只有一种颜色的气球，那该怎么办？
考虑。设
分别为向下最短的，向下次短的（和最短的不在一条路径上）和向上最短的（包括向上但不在虚树的根->该点这条路径上的关键点），
为对应答案的来源，
为这个点的答案（最少重复跳转次数，初始
）。定义关键点为有这种气球的点。
显然地，如果该点有两个及以上该种气球，则直接=
（不需要跳转）；对于关键点而言，必定有
=
,
=
。接下来第0维和第1维的更新只需要一个dfs+分类讨论跑完就可以了。然后我们再跑一遍dfs处理第2维，对于一组u->v，如果u->v是最短边，则
=
+
，否则就是
=
+
（在向上和向下两个中选一个小的，加上u->v）。
现在扩展到多个。这下问题就来了：前面的过程中，需要把整棵树都遍历一遍，而对于这么多种颜色组成的这么多种树，我们是肯定不能接受的做法的。所以我们在此对于每种颜色建立虚树（建立方式可以参照oi wiki），由于每两个实点最多可以召唤出一个虚点，因此这样建立起来的树，点数总和一定不会超过
。
在跑完每种颜色组成的虚树后，我们还需要最后跑一遍最短路（因为之前求解的只是那些关键点的ans）。
时间复杂度：常数很大的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
const int N = 5e5 + 5, inf = 4e18;
int n, q, m, num, cnt;
int son[N], top[N], siz[N], dfn[N], dep[N], fa[N];
int ask[N << 1], mark[N]; // ask数组为每次询问（开2倍），mark标记关键点
vector<int> all[N];
vector<PII> p[N]; // 虚树
map<int, vector<int>> mp;
void dfs1(int pos)
{
siz[pos] = 1, dfn[pos] = ++cnt, dep[pos] = dep[fa[pos]] + 1;
for (int i : all[pos])
{
if (i == fa[pos])
continue;
fa[i] = pos;
dfs1(i);
siz[pos] += siz[i];
if (siz[i] > siz[son[pos]])
son[pos] = i;
}
}
void dfs2(int pos, int gtop)
{
top[pos] = gtop;
if (son[pos])
dfs2(son[pos], gtop);
for (int i : all[pos])
{
if (i == son[pos] || i == fa[pos])
continue;
dfs2(i, i);
}
}
int LCA(int m1, int m2)
{
while (top[m1] != top[m2])
{
if (dep[top[m1]] < dep[top[m2]])
swap(m1, m2);
m1 = fa[top[m1]];
}
if (dep[m1] > dep[m2])
return m2;
return m1;
}
int cmp(int x, int y) { return dfn[x] < dfn[y]; }
int ans[N];
int dp[3][N], from[3][N]; // dp为对应的值，from为从哪个节点推得的结果
// dp的第0,1,2维分别代表向下最短的，向下次短的和向上最短的（包括向上但不在1~该点这条路径上的关键点）
void dfs3(int pos)
{
if (mark[pos]) // 如果自己就是关键点，那最短的就是自己
dp[0][pos] = 0, from[0][pos] = pos;
for (PII i : p[pos])
{
dfs3(i[0]);
if (dp[0][i[0]] + i[1] <= dp[0][pos]) // 可以更新第一小
{
dp[1][pos] = dp[0][pos], from[1][pos] = from[0][pos];
dp[0][pos] = dp[0][i[0]] + i[1], from[0][pos] = i[0];
}
else if (dp[0][i[0]] + i[1] < dp[1][pos]) // 可以更新第二小
dp[1][pos] = dp[0][i[0]] + i[1], from[1][pos] = i[0];
}
}
void dfs4(int pos) // 更新向上的
{
for (PII i : p[pos])
{
if (from[0][pos] == i[0])
dp[2][i[0]] = min(dp[1][pos], dp[2][pos]) + i[1];
else
dp[2][i[0]] = min(dp[0][pos], dp[2][pos]) + i[1];
dfs4(i[0]);
}
}
void solve()
{
priority_queue<PII, vector<PII>, greater<PII>> pr;
for (int i = 1; i <= n; i++)
pr.push({ans[i], i});
while (!pr.empty())
{
PII now = pr.top();
pr.pop();
for (int i : all[now[1]])
if (ans[i] > ans[now[1]] + 1)
{
ans[i] = ans[now[1]] + 1;
pr.push({ans[i], i});
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
int u, T;
cin >> T, ans[i] = inf;
while (T--)
{
cin >> u;
mp[u].push_back(i);
}
}
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
all[u].push_back(v);
all[v].push_back(u);
}
dfs1(1);
dfs2(1, 1);
for (auto [key, vec] : mp)
{
m = vec.size();
for (int i = 1; i <= vec.size(); i++)
{
ask[i] = vec[i - 1];
if (mark[ask[i]]) // 如果某个地方出现了不止一次同种气球，则直接ans=0（无须跳转）
ans[ask[i]] = 0;
mark[ask[i]] = 1;
}
sort(ask + 1, ask + m + 1, cmp);
num = m;
for (int i = 2; i <= m; i++)
{
int lca = LCA(ask[i], ask[i - 1]);
ask[++num] = lca;
}
sort(ask + 1, ask + num + 1);
num = unique(ask + 1, ask + num + 1) - (ask + 1);
sort(ask + 1, ask + num + 1, cmp);
for (int i = 2; i <= num; i++)
{
int lca = LCA(ask[i], ask[i - 1]);
p[lca].push_back({ask[i], dep[ask[i]] - dep[lca]}); // 建立虚树的时候只要建立一条边就行了
}
for (int i = 1; i <= num; i++)
for (int j = 0; j < 3; j++)
dp[j][ask[i]] = inf, from[j][ask[i]] = -1;
dfs3(ask[1]);
dfs4(ask[1]);
for (int i = 1; i <= num; i++) // 求解ans && 撤销虚树
{
int u = ask[i];
if (mark[u])
{
ans[u] = min(ans[u], dp[0][u] + dp[2][u]);
ans[u] = min(ans[u], dp[0][u] + dp[1][u]);
mark[u] = 0;
}
p[u].clear();
}
}
solve();
while (q--)
{
int u;
cin >> u;
if (ans[u] == inf)
cout << "IMPOSSIBLE!\n";
else
cout << ans[u] << "\n";
}
return 0;
}
京公网安备 11010502036488号