Topcoder-578

感觉再不发就要坑了。

TC 你的官方 solution 真是慢到家了。于是看别人的代码外加自己 YY 把题目搞完了。没坑真是太开心了。

小号回红了不错。

Solution

250 pts

把距离不超过 \(d\) 的两个 v 连一条边，则同一个联通块内的点必定都是鹅或都是鸭。然后 dp 或者直接计算都可以。

500 pts

这个题有个很简单的 dp 。

令 \(f_{i, j}\) 表示最后的两只狼的位置分别是 \(i, j \quad (i < j)\) 的方案数。枚举下一只狼在哪里即可。由于需要判断是否有一只区间内包含了三只狼，我们可以对于每个位置 \(i\) ，预处理出假如 \(i\) 是倒数第三只狼，最后一只狼的位置至少是多少。这就是一个简单的区间覆盖问题了。

代码超好写，我一开始想丑了 T_T

1000 pts

容易知道，一定存在一条边，使得最优的两棵子树在这条边的两端，且其中一棵子树的根是这条边的一个端点。我们枚举这条边，再枚举这个端点是 \(a\) ，再枚举另一棵最优解的子树的根 \(r\) 。

于是我们的问题变成：给定两棵有根树，要求给这两棵树删掉一些子树，使得删掉子树后的两棵树同构。由于枚举了根，判断两棵树同构的条件可以简化为点是否一一对应，即：根是否对应，根的每个儿子是否一一对应，根的儿子的儿子是否一一对应……

考虑 dp 。令 \(f_{i, j}\) 表示在第一棵树中子树 \(i\) 对应为第二棵树中子树 \(j\) ，最多可以对应多少个点。首先根肯定与根对应，对于 \(i\) 的每个孩子 \(x\) 与 \(j\) 的每个孩子 \(y\) ，将子树 \(x\) 对应为子树 \(y\) 的最大数目为 \(f_{x, y}\) 。于是这就变成了一个匹配问题：如何合理选择配对方式，使得总数目最大？费用流即可。

SPFA 都可以写错我真是没救了。

situation

早上八点起床八点半到机房。前一段时间的 TX 对我的身体（特别是视力）造成了极大的摧残 →_→ 所谓封闭开发简直是用生命在开玩笑。

刚好 ryz 也准备做，早上 9 点的 TC 不多见的。

开场后先开了 250 ，发现是大水题，于是开写发现各种脑残。本来只要并查集就好了的我还建了个图 →_→ 最后就只剩 180+ 了。

然后开 500 。第一反应居然是如果包含了其余线段那么这根线段没用（有没有发现这个想法完全倒了？）。顺着这个错误思路继续想居然想到了 dp 。然后考虑预处理发现我这个想法是错的 233 ，应该是被其余线段包含则没用了。于是发现预处理好写极了～于是发现 dp 也好写极了～但是前面一段时间蛋疼的绕了很久于是分数很低 T_T 果然写之前应该想清楚么。

1000 pts 的看了就没啥想法。考后看了 CLJ 的程序看到用了费用流，又想起以前一道题，两个想法合起来发现就可以做了。复杂度神马都是浮云～

最后没有 FST 真是太开心了。

others

WJMZBMR 过了 1000 pts 于是 #5 大涨。目测快要 target 了～

我似乎前两题手速不差混到了 #30 啦啦啦回红了。（可是我明明两个题都脑残了好久的，特别是第二题…… XLk 要做的话目测可以 #10-）

scottai #31 被怒踩 233

cgy FST * 2 真是太凄凉了。 #129

ryz 第一题手残导致大部分时间都在第一题上了于是 500 pts 的没写完 #171

似乎 liouzhou_101 爆零了。他最近一段时间都没状态？