Tc SRM 681

YYY posted @ 2016年3月14日 21:24 in 算法竞赛 with tags DP 概率论暴力二分答案膜敦爷 , 612 阅读

_THIS_IS_START_OF_ARTICLE_

------------------------------------------------------------------

做一做TC以前的题...

------------------------------------------------------------------

250:

二分答案然后贪心

每个零件，优先选卖这个零件的店中右界最小的那个，选够mid个为止，选不够就返回false

------------------------------------------------------------------

500:

发现这个加密方式是可以向前推的

所以暴力就好

假设当前长度为n，最大值在t这个位置

时间复杂度是f(n)=min{t,n-t+1}+f(t)+f(n-t+1)

题解说这个是O(n)的

至于你信不信，我反正不信...

后来问了下skydec这个的复杂度

敦爷：我觉得最大的情况应该还是对半分，嗯...就是f(n)=n/2+2f(n/2)，这个是nlog的..

我：那10^7为什么能过

敦爷：这个常数很小，大概是1/4...而且卡满的数据并不好造...

我:我竟无言以对..

------------------------------------------------------------------

900:

------------------------------------------------------------------

_THIS_IS_END_OF_ARTICLE_

YYY