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

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

先写感想?

有人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$小。爽。

稳定多米诺覆盖

稳定好像是个可以容斥做的事情,那就先考虑不容斥的多米诺覆盖,$O(3^nnm)$的dp很简单吧

老子先在wikipedia上看到一个$O(nm)$的利用$\cos$函数计算答案的公式。。写了一发结果精度挂了($n=m=14$时挂了100多,$n=m=16$的时候数量级不对)

稳定的话枚举割哪些直线,$O(2^{n+m})$。。

其实只需要枚举割哪些横线,竖线dp就好。$f_{i,j}$表示前$i$列分成$j$块的方案数,$j$只需要记录奇偶。。

这部分复杂度$O(2^mn^2)$

话说然后就可以打表了,最终复杂度$O(1)$

 

nonsense

打完比赛之后听着根本不知道在说什么的日语歌,什么也不想,然后在这个blog上胡言乱语以及看着王某在打dota2

真是美好的享受啊

Space Colony的翻新版马上就要出了。。拭目以待中。。

XLightGod 说:
2016年5月26日 19:12

%%%

我也要打dota2!


登录 *


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