Topcoder-565

Solution

250pts

比较水啊。稍微转换一下思路就可以想出来的。 f(i,j) 表示前 i 个怪物用 j 块钱最多可以得到多少的伤害值,然后枚举当前怪物是买还是打就可以了。不过我还不知道 cha 点呢。

500pts

也不难吧。

首先是要把 SG 求出来。这个我是马上打了一个表然后就找出来了, x 的 SG 值就是 x 的质因数的指数和。这相当于普通 nim 游戏中,石子有不同种类(2,3,5,7 之类的),每一堆直接由这一堆石子的积表示出来。

由于区间长度较小,直接 O(L log L) 求 SG 就可以了。从小到达枚举质数,上界为 sqrt(R) 。超过上界仍然分解不完全,那计数器再加一。

至于统计答案嘛,告诉你用前缀 SG xor 和你还不会?

很多人被 cha 目测是 sqrt 分解质因数去了。

1000

只看了题目,不会做。 update: 2012-12-23 已经会做了。某次失眠时 YY 了一个做法 ms 是对的。

如果我们知道了 ABC 彼此之间的距离,剩下的就简单了。那么 AB、BC、CA 三条路径会覆盖若干个点,一个点被这三条路径覆盖的条件是以下条件至少满足 2 个:

  1. d[A,i] + d[B,i] = d[AB]
  2. d[B,i] + d[C,i] = d[BC]
  3. d[C,i] + d[A,i] = d[CA]

这种点的位置是唯一的。对于其它的点 x ,我们一定可以找到一些点 y ,使得 d[A, x] - d[A, y] = d[B, x] - d[B, y] = d[C,x] - d[C,y] > 0 。对于这些点,我们任意找一个连上去即可。

现在还存在一个问题:如何找出所有可能的 AB、BC、CA 的距离?如果 AB 中存在非 C 的点,那么 AB 的距离等于最小的 d[A, i] + d[B, i] ,如果 ABi 到达另一点的路径上,那么 AB 距离等于最大的 \|d[A, i] - d[B, i]\| ,如果以上都不是,那么 AB 还可以等于 d[A, i] + d[B, i] - 2 d[C, i] ,这种情况就是一条 A-C-B 的链,然后某点通过 C 连出去。

既然 AB、BC、CA 都只有 3 种可能,爆枚即可。

others

rejudge 强力 target 。

tourist 悲剧 500pts 的没出。

XLk 凭手速又虐我。

zcwwzdjn 虐我 1 分多一点。

大叔又一次没爆零,真是太开心啦。不过他 250pts 的只交了 98pts ,结果被某人以不交程序怒 cha 得 100pts 强踩。

话说 XLk 跟我讲了他上次 rank1 后的事。有人对他产生怀疑,于是 t-mac 的管理员就和他扯淡去了,然后他的方法和 rng_58 的还不一样。

nonsense

好开心啊,终于涨红了。这是 rating 折线:

Sorry, the picture can't be loaded

最近几次 TC 都没啥做好的。一开始 2034 ,想一次涨红还是有可能的;一次之后是 2142 ,一次涨红还是可以的;又一次之后是 2158 ,一次涨红还是可以的;又过了一次是 2174 ……我彻底无语了。不过这次红了还是蛮好的。

吐槽

我肿么又和 ahxun2006 一个 room ?这是连续几次了?

另外最囧的是明明是 SRM-565 的题我标题写个啥 SRM-564