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