6
16
2015
0

论蒟蒻的自我修养之TopCoder练习记

昨天终于get了TopCoder的正确使用姿势

于是打几把线下赛练练手,顺便感受一下tc题目的温(sang)暖(bing)

现在做了几道:

                  5

【SRM661A】首先$ans<=2*n$,然后很容易想到可以对每个质因子分开考虑,不妨设当前考虑的质因子是$p$,那么不妨设

$1-n$中出现的$p$的最大次数是$x$,$n+1$到中出现的$p$的最大次数是$y$,那么$lcm(1,2,……,m)=lcm(n+1,n+2,……,m)$的充要条件是对于所有的质因子$p$有$y>=x$。所以我们就可以暴力分解然后判一判了。

【SRM661B】打表可以发现$ans=\prod_{i=1}^{n}{k+(i-1)*k}$  现在要对$m$取模。很简单,我们可以发现在模$m$意义下,括号里的式子走不超过$m$步就会进入一个循环节,所以后面就可以直接算了。也可以直接将$m$长度作为我们的循环节,这是因为 $(k+m*k)\%m=k\%m$

【SRM661C】显然答案具有单调性,然后考虑如何判断一个值x是否可行。我们可以考虑$dp$。然后被割开的一段不妨设为$[l,r]$,除了本身必须满足两两之间的距离$<=x$(显然这个可以预处理)外,还必须到前面的所有点距离$<=x$,而这个只与$[1,l-1]$到$l$的最短路的最大值有关。因此我们可以考虑用$dp_{i,j}$表示在$i$连了一条边,总共连了$j$条边,前面的所有点到$i$的最短距离的最大值是多少。然后转移就十分好搞了。所以说$dp$的关键还是在于设计状态。注意要预处理一大堆东西$lmx_{l,r}$表示如果在$l$切一下$r$切一下,所有点到$l$的最短路的最大值,$rmx_{l,r}$类似,$mx_{l,r}$则表示$l-r$两两之间的最短路的最大值。

【SRM660A】首先$O(knm)$的暴力是过不去的,我们考虑把与每个点有交集的所有点预处理出来,这样就可以做到$O(k^2nm+n^2m^2)$了

【SRM660B】概率题我们可以考虑对每个数单独算贡献。一般需要用到容斥,不妨设当前在考虑$x$,那么我们先$ans+=1$,然后我们减去$a[x]$出现在$x$前面的概率,再加上此条件下$a[a[i]]$出现在$a[i]$前面的概率依次类推。复杂度是$O(n^2)$。

Category: topcoder | Tags: | Read Count: 602

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com