0%

Topcoder-573

我勒个去,等了几天了居然还没发 Analysis …… TC 效率是有多低啊,看来只能怒坑一把了。

solution

250 pts

显然是贪心,每次取最大的一个元素,然后去能超过他的最小的两个就好了。

直接用 set 暴力搞。

450 pts

我勒个去这都会想错……

首先一个很简单的结论就是:一定存在一组最优解,使得不会出现新的种类的高度。

有了这个结论就好做了。点的范围只有 50 ,于是直接 f[i][j] 表示第 i 个点的高度为 j ,且 0 号点能到达 i 号点时的最小修改代价。显然可以用最短路来做。构不构图随你,反正范围很小。

我居然很脑残的写了个 bellman-ford ……还是个错的 bellman-ford ……

850 pts

为了填这个坑我容易么我。等 TC 的题解等了这么久,今天晚上终于出来了。

首先很明显,坐标轴需要转一下。然后目标点就被限制在一个矩形范围内了。现在我们要统计所有的初始点到达矩阵中某个点的方案数的和。 注意到每次移动对于 x 和 y 的改变是不相关的 ,也就是说 x 和 y 可以分开解决。知道了这一点一切都好做了。

由于可以分开解决,那么啥问题都没有了,不妨假设要求 x 吧。枚举最后的 x ,再枚举每个点,方案数可以由一个组合数表达出来,所以可以 O(1) 解决。总复杂度就是 O(nm)

居然没想到 x、y 分开解决,诶……

situation

早上给小朋友发了题后开始刷水,在八点四十多发现今天的 TC 是早上九点而不是晚上,怒开小号注册。

似乎我在 room 排名蛮低的?桑心~

250 pts 似乎是水题,秒掉。

450 pts 不会做,乱猜了个结论,感觉是对的(的确是对的)。于是开始敲代码。不想构图了,于是 YY 了一个算法,用 dp 来做。结果一测发现连样例都没过 = =|| 然后想着这个算法没错啊,于是又加了一层循环怒过样例。后来一想这是哪门子的算法啊,错的妥妥的……

既然过了样例就没想了,看着第三题只有 850 pts 觉得可做于是就做了一下……发现这不是个数学题吗?蛮合我口味的。感觉是个组合数学题?也还可以。于是 YY 来 YY 去还是没想法……

看完 Analysis 后瞬间发现我脑残了,分开考虑就很简单了。

最后 450 pts 的当然 FST 。排名 #173 如果没有 FST 的话前 20 应该没问题……

由于是小号所以还是可以涨的。但是……这会不会对自已要求太松了点?

others

AC_Rush 时隔多年之后终于回来了!但是 #36 似乎有点不合人意啊……(不要给我)

我们 room 的 NaHS 前两题开的很慢,刚交完的时候是 room 的 #10+ 。但是不知怎么的慢慢慢慢就到了 #2 了,最后 #35 怒压教主。

cherudim9 #49 感觉 450 pts 的有 300+ 应该是不难的。

liouzhou_101 #95 主要是 450 pts 的交慢了吧。

UESTC_elfness 居然 FST 了 250 pts 的,出乎我想象。

ryz #165 ,250 的比我快……

huzecong 蛮好玩的,他的 250 是我们 room 交得最快的,后来他重交了一遍,就只有 75 pts 了。450 速度也还可以,然后又重交了一遍就只有 135 pts 了,最后 250 的 FST 了还 cha 错一个人囧……

另外求 @xiaodao 小号 ID ……

有人 -150 什么心态 = =||