Closed Wizmann closed 3 years ago
Code Contest
给一个无向图G，有N个顶点，编号从1\~N。 对于点1 \~ N-1，一定有一条从顶点i \~ i+1的边。对于给定的点X和Y，也有一条边。
问对于每一个k（1 <= k <= N - 1），有多少个点对(i, j)，使得i到j的最短路径为k。
不考虑边XY，那么任意两点之间的距离为两点编号的差的绝对值 。 考虑边XY，两点之间（记为A、B）的距离为以下三者的最小值。
时间复杂度为O(N^2)
因为每条边的边长为1，所以可以将其视为一般的迷宫，使用BFS flood fill（洪泛）法求解。
时间复杂度也是O(N^2)。
你挑选X个红苹果和Y个绿苹果。 A个红苹果分别有权值p1....pA。B个绿苹果有权值q1....qB。还有C个无色苹果，权值为r1....rC。 无色的苹果可以被涂成红色的或者绿色的。
问挑选出来的苹果的权值和最大为多少。
不考虑无色苹果，我们先出红苹果和绿苹果中权值最高的X和Y个即可。
考虑无色苹果的话，我们需要替换掉最多C个权值最小的红苹果或/及绿苹果。
简单排序即可。
有一个N个节点的树，节点编号为1\~N。
从树中选定一个编号为k的点，将其标记为1。然后在其相邻的任意点，标记为2。以此类推，直到标记树上的所有点。
问对于每一个k （1 <= k <= N），一共有多少种不同方法标记这棵树。
我们首先假设根是固定的。对于一棵（子）树，我们首先会把可用的标记分配给其子树，此时记录分配的种类数。然后向子树递归，求子树的标记方法。最后将结果相乘即可。
伪码如下：
def f(cur): res = 1 nodes = 1 for next in g[cur]: subtree_size = tree_size(next) nodes += subtree_size res *= f(next) * C(nodes - 1, subtree_size) return res
递归求解即可得出答案。
接下来需要考虑根是可变的。
由于根是可变的，所以对于每一棵子树，我们需要记录其根节点以及根节点的父节点。整棵树的父节点不存在，记为-1。
所以一共有2 * (N - 1)棵子树（每一条边的两个方向）。由于这个数据规模并不大，我们就会产生错觉，认为可以直接做DP，记录所有子树的值进行状态转移。
问题在于，状态数是有限的，但是状态转移数是O(N ^ 2）的。会造成程序的超时。
首先计算以0点为根的情况。
然后递归计算每一棵子树的答案。首先将父节点从树上取下来，然后将父节点插入做为新的子节点。这两个操作只限于计算，不涉及树的结构的改变。
参考链接
Code Contest
D. Line++
题意
给一个无向图G，有N个顶点，编号从1\~N。 对于点1 \~ N-1，一定有一条从顶点i \~ i+1的边。对于给定的点X和Y，也有一条边。
问对于每一个k（1 <= k <= N - 1），有多少个点对(i, j)，使得i到j的最短路径为k。
解法
方法1（正规解法）
不考虑边XY，那么任意两点之间的距离为两点编号的差的绝对值 。
考虑边XY，两点之间（记为A、B）的距离为以下三者的最小值。
时间复杂度为O(N^2)
方法2（套模板）
因为每条边的边长为1，所以可以将其视为一般的迷宫，使用BFS flood fill（洪泛）法求解。
时间复杂度也是O(N^2)。
E. Red and Green Apples
题意
你挑选X个红苹果和Y个绿苹果。
A个红苹果分别有权值p1....pA。B个绿苹果有权值q1....qB。还有C个无色苹果，权值为r1....rC。
无色的苹果可以被涂成红色的或者绿色的。
问挑选出来的苹果的权值和最大为多少。
解法
不考虑无色苹果，我们先出红苹果和绿苹果中权值最高的X和Y个即可。
考虑无色苹果的话，我们需要替换掉最多C个权值最小的红苹果或/及绿苹果。
简单排序即可。
F. Distributing Integers
题意
有一个N个节点的树，节点编号为1\~N。
从树中选定一个编号为k的点，将其标记为1。然后在其相邻的任意点，标记为2。以此类推，直到标记树上的所有点。
问对于每一个k （1 <= k <= N），一共有多少种不同方法标记这棵树。
解法
我们首先假设根是固定的。对于一棵（子）树，我们首先会把可用的标记分配给其子树，此时记录分配的种类数。然后向子树递归，求子树的标记方法。最后将结果相乘即可。
伪码如下：
递归求解即可得出答案。
接下来需要考虑根是可变的。
错误方法：直接DP（TLE）
由于根是可变的，所以对于每一棵子树，我们需要记录其根节点以及根节点的父节点。整棵树的父节点不存在，记为-1。
所以一共有2 * (N - 1)棵子树（每一条边的两个方向）。由于这个数据规模并不大，我们就会产生错觉，认为可以直接做DP，记录所有子树的值进行状态转移。
问题在于，状态数是有限的，但是状态转移数是O(N ^ 2）的。会造成程序的超时。
正确方法：换根DP
首先计算以0点为根的情况。
然后递归计算每一棵子树的答案。首先将父节点从树上取下来，然后将父节点插入做为新的子节点。这两个操作只限于计算，不涉及树的结构的改变。
参考链接