题目： 1832: [AHOI2008]聚会 解析： 偶尔做做水题挺爽的 两两之间先求出LCA，发现至少有两个LCA是相同的，这个重复LCA也是深度最浅的那个，那我们就选择那个不重复的LCA，因为若选这个重复的LCA的话，这个重复的LCA到另一个LCA的路径会走两遍，反之只会走一遍 三点间的距离就是 \(dis[x] + dis[y] + dis[z] - dis[LCA(x, y)]- dis[LCA(x, z)]- dis[LCA(y, z)]\) 代码： #include <bits/stdc++.h> using namespace std; const int N = 1...

题目： 1799: [Ahoi2009]self 同类分布 解析： 设\(f[pos][SumDigit][rem]\)为第\(pos\)位，各位数和为\(SumDigit\)，当前余数为\(rem\)的数的个数 要求\(n\)可以被各位数整除，也就是\(n\%SumDigit==0\) 这个题，我们枚举一下各位数的和\(sum\)可能是多少，对每一个\(sum\)都记忆化搜索一下，看\(SumDigit==sum\)时有多少数满足条件，然后累加答案 代码： #include <bits/stdc++.h> #define int long long using namespace...

题目： 3209: 花神的数论题 解析： 二进制的数位DP 因为\([1,n]\)中每一个数对应的二进制数是唯一的，我们枚举\(1\)的个数\(k\)，计算有多少个数的二进制中有\(k\)个\(1\) 设\(n\)的二进制一共有\(num\)位，有\(sum[i]\)个数的二进制中有\(k\)个\(1\)， 答案就是\(\prod_{i=1}^{num}i^{sum[i]}\) 用数位DP搞一下就好了 设\(f[i][j]\)表示到第\(i\)位有\(j\)个\(1\)时有多少个数 枚举\(k\)，记搜一下。 由于可能会有很多数的二进制中有\(k\)个\(1\)，所以用快速幂维护一下 相似思路...

题目： 1040: [ZJOI2008]骑士 解析： 假设骑士\(u\)讨厌骑士\(v\)，我们在\(u\)，\(v\)之间连一条边，这样我们就得到了一个奇环树（奇环森林），既然是一颗奇环树，我们就先考虑把环断开，设断开边边连接的两点是\(rt1\)，\(rt2\)，断环的话直接标记这条边不能经过就好了 根据题意，我们要求的是相邻两个节点不能同时选时的最大价值，这不就是奇环树版的没有上司的舞会吗。 那么很容易的得到转移方程 设\(f[u][1/0]\)表示以\(u\)为根，选/不选可以得到的最大价值 \[\begin{cases} f[u][1] += f[v][0]\\\\ f[u][0] ...

题目： 1864: [Zjoi2006]三色二叉树 解析： 用\(f[u][0/1/2]\)表示以\(u\)为根，颜色为绿/红/蓝时最多的数量 转移没啥好说的 \(f[u][0] = max(f[l][1] + f[r][2], f[l][2] + f[r][1]) + 1\) \(f[u][1/2] = max(f[l][0] + f[r][2/1], f[l][2/1] + f[r][0])\) 最小值同理 建树的话递归建树就可以了 代码： #include <bits/stdc++.h> using namespace std; const int N = 5e5 +10; ...