[CodeChef]2014 September Challenge

xllend3 posted @ 2014年9月10日 08:53 in 刷比赛记录 with tags codechef , 1403 阅读

前五道不说了。

CHEFINV:动态逆序对树套树还要想吗?不过总感觉这题离线可做。

SEABUB:[tex]dp[i][j][/tex]表示剩[tex]i[/tex]步逆序对为[tex]j[/tex]时的期望。首先[tex]k\leqslant n^2[/tex]所以暴力是[tex]O(n^4T)[/tex]然后发现第i步的状态很有规律,可以直接存然后就[tex]O(n^3+n^2T)[/tex]了。然后我预处理比较浪就成了[tex]O(n^3T)[/tex]慢的要死。

QRECT:相交数=总数-右边-上面-左边-下面+四个角。边上一维数点角上二维数点。

FIBTREE:我想吐槽出这种题有意思吗,简直像fcuk_zjoi_2014一样。CF-#FF-C + llj树链剖分 + 主席树。没了。

CHALLENGE:这次challenge太神了,除了暴力以外根本没想法。。。然后靠多组数据小技巧骗了点分。。。大概就是每次暴力期望最高的那组数据然后卡下时。。。由于比较懒直接上的python。。。但是python实在是太慢了python实在是太慢了,因为很重要所以说两遍。然后发现王松靠常数优化轻松拿刀orzorzorz

Avatar_small
skr 说:
2014年10月06日 04:25

Hey, i have been trying to solve sereja and strings problem and even after many attempts still not able to do so.My solution is weighted operation levenshtien distance with cut-off distance.. solution is O(nk).. If u can give some pointers towards the possible solution.. thanx in advance


登录 *


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