BZOJ – Tgotp-Blog

1495: [NOI2006]网络收费

观察到层数最多只有10,那么状压层数,
发现对于第i层,若是设为na <nb,那么在子树遍历的时候,以当前层为lca的点为a时能产生价值,反之同理。
令f[i][j]表示第i个点,下面有j个a点,以及记录当前层包含区间[L,R],那么对于na < nb时只能更新[L,mid]反之只能[......]

Read more

3306: 树

树剖随便搞搞就行了

c++代码如下:

 

3720: Gty的妹子树

正解貌似很麻烦,我直接用分块搞了。。。

具体见代码。

c++代码如下:

 

3262: 陌上花开

cdq分治裸题。

c++代码如下:

 

2982: combination

lucas定理模板

c++代码如下:

 

1038: [ZJOI2008]瞭望塔

容易发现:

1.一个点如果能看见面上所有点,那么一定是折线的半平面交内的点。

2.塔一定在半平面交上的交点或者折线交点上。

接下来就是模板题了。

c++代码如下:

 

4552: [Tjoi2016&Heoi2016]排序

对于单独的一个数字可以用线段树搞,那么考虑二分一个数字

最后看q这个位置上数字的大小关系即可

c++代码如下:

 

5436: 三元组

没有限制a <= b <= c的话可以fft搞

限制的话具体见:三元组

c++代码如下:

 

3211: 花神游历各国

水题,容易发现开根很少次数就始终为1了

暴力线段树即可

c++代码如下:

 

1502: [NOI2005]月下柠檬树

容易发现一个平行平面的投影是不会变的,

一个圆柱的投影是两个面的投影+这两个圆的外切线所构成的图形

求出所有外切线再用simpson积分搞搞就行了。

至于求外切线的方法自己推一推,具体见代码。

注意这题是不能删去被包含的圆。

(这代码一开始以为会t,结果竟然过了[......]

Read more