TC SRM 682
BZOJ4361: isn

Tc SRM 681

YYY posted @ 2016年3月14日 21:24 in 算法竞赛 with tags DP 概率论 暴力 二分答案 膜敦爷 , 241 阅读
------------------------------------------------------------------
做一做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:
------------------------------------------------------------------
LOL

登录 *


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