昨天终于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）$。
评论 (0)
