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 个:
d[A,i] + d[B,i] = d[AB]
d[B,i] + d[C,i] = d[BC]
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]
,如果 A
或 B
在 i
到达另一点的路径上,那么 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 折线:
最近几次 TC 都没啥做好的。一开始 2034 ,想一次涨红还是有可能的;一次之后是 2142 ,一次涨红还是可以的;又一次之后是 2158 ,一次涨红还是可以的;又过了一次是 2174 ……我彻底无语了。不过这次红了还是蛮好的。
吐槽
我肿么又和 ahxun2006
一个 room ?这是连续几次了?