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 爆零了。他最近一段时间都没状态?