BSG白山极客挑战赛题解和感♂想

r_64 posted @ 2016年5月21日 00:52 in 未分类 with tags 51nod , 1858 阅读

先写感想?

有人1h AK。。罗教主1.5h AK，杜教紧随其后。。太可怕了

我真的不适合手速场。。真的

T3T4T6花了太多时间简直就是在浪费。。mgj

事实上好像后4个题每个题都想错了一两下。。尤其是最后那个题完全是在弃疗状态下想的

数数字

相当于$\underbrace{111~\cdots~111}_{n个1}\times ab$的结果内$d$的个数。

如果$ab<10$，(就很简单了吧)

如果$ab\ge 10$，令$ab$的十位数字为$x$，个位数字为$y$，如果$x+y<10$那么就考虑$d=x,y,x+y$的情况(下面表格是竖式)

	$y$	$\dots$	$\dots$	$y$
$x$	$\dots$	$\dots$	$x$
$x$	$x+y$	$\dots$	$x+y$	$y$

否则还要考虑$x+y-9$和$x+y-10$的情况(同样地下面表格是竖式)

	$y$	$\dots$	$\dots$	$\dots$	$\dots$	$y$
$x$	$\dots$	$\dots$	$\dots$	$\dots$	$x$
$x+1$	$x+y-9$	$\dots$	$x+y-9$	$x+y-9$	$x+y-10$	$y$

好像$n$小的时候会有bug?我不确定，但是$n$小的时候暴力就好了嘛。

AVL树的种类

当时我太懒了结果去stackexchange上面抄了个dp式子幸亏是对的(雾

$$a_{n,h} = \sum_{k=1}^n \bigl(a_{k-1,h-1}a_{n-k,h-1} + a_{k-1,h-1}a_{n-k,h-2} + a_{k-1,h-2}a_{n-k,h-1}\bigr)$$

复杂度$O(n^2\log n)$，$h=O(\log n)$但是事实上可以到达$16$(反正大于$14$，导致我WA了好几发)。

upd.群里有人说树高上界是$\log_{1.618}n$，下界是$\log_2 n$。所以应该是到不了$16$的但是可以到$15$?没仔细想。

B君的圆锥

开始脑残以为答案是输入的正比例函数，WA了之后觉得是xlk在卡精度就用python又求了一发函数的系数还去搜了高精度$\pi$。

我真是脑残啊，时间就这么被浪费了

后来写了个三分就过了

关键是初中数学，$V=\frac{1}{3}\pi r^2\sqrt{l^2-r^2},S=\pi(r^2+lr)$，其中$r$是底面半径，$l$是母线长(就是说$\sqrt{l^2-r^2}$是高啦)。然后对于$r$根据确定的$S$求出$l$之后求$V$作为函数，三分就好。

树上的最远点对

吉丽出过一个题叫“思考熊”。。看了那个题的题解之后知道对于边权都是正数的树，点$x$到点集$S$的最大距离就是$x$到$u$的距离与$x$到$v$的距离的最大值，其中$u,v$是$S$内相互距离最远的一对点。

我们可以使用线段树，节点$[l,r]$维护编号为$l\dots r$的点集的最大距离$d$和相应的两个点$u,v$。考虑合并两个节点$(d_1,u_1,v_1)$和$(d_2,u_2,v_2)$得到$(d,u,v)$，那么有

$$d=\max(d_1,d_2,dis(u_1,u_2),dis(u_1,v_2),dis(v_1,u_2),dis(v_1,v_2)$$

根据上面式子$d$值的来源可以更新$u,v$。例如$d=d_1$那么$u=u_1,v=v_1$；$d=dis(v_1,u_2)$则$u=v_1,v=u_2$；等等。

询问的时候求出$[a,b]$的$d,u,v$和$[c,d]$的$d,u,v$，答案就是$u_{[a,b]},v_{[a,b]}$中选一个点与$u_{[c,d]},v_{[c,d]}$中选一个点的距离的max。

然后，这个题很恶心。。开始写了个倍增交上去T了，赶忙改成树链剖分。。改了一半觉得写个RMQ可能靠谱些(毕竟少个log)，好不容易写完了dfs爆栈(咦51nod会爆栈?)。。最终一顿乱改才过

复杂度$O((n+m)\log n)$。

第$K$大区间2

二分答案$ans$，然后令$f_i$为前$i$个数中$\le ans$的数的个数减去$>ans$的数的个数，推一推就可以$O(n\log n)$求出中位数$\le ans$的长度为奇数的区间个数。总复杂度$O(n\log^2 n)$(怕卡常离散化了所以不是$n\log n\log a$)。把第$K$大看成了第$K$小。爽。