Tc SRM 681

------------------------------------------------------------------
做一做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:
这次考试的T2
------------------------------------------------------------------