BZOJ – 第24页 – Tgotp-Blog

【bzoj1010】[HNOI2008]玩具装箱toy

 

【bzoj1002】[FJOI2007]轮状病毒

高精度模板直接复制的。

思路就是:基尔霍夫矩阵(我也不知道是什么)推出f[i]=(f[i-1]*3-f[i-2]+2) 直接百度吧。

 

【bzoj1597】[Usaco2008 Mar]土地购买

思路:斜率优化dp。

这种题一般自己推一推比较好;

简单的,我们可以看出,

首先:对于x排序,可以提出某些被包含的土地块(直接打包买)

然后:可以发现dp思路:f[i] = min(f[j]+b[j+1].y*b[i].x

但是可以很容易发现时间不够;

继续发现可[......]

Read more

BZOJ4893 项链分赃

没啥补充的,就这些。

先给出结论,切的刀数一定小于等于颜色个数。

所以暴力判掉1和2,剩下输出3就行了。

你肯定会问“为什么?!”

让我尝试证明一下这个东西。

--------------------------------以下开始证(瞎)明(扯)环节---------[......]

Read more

3156: 防御准备

斜率优化

f[i] = min((i-j-1) * (i-j)/2 + f[j]) + data[i]

f[i] = min((i-1)* (i-j)/2 -j * (i-j)/2 + f[j]) + data[i]

f[i] = min(j -2*i*j+j*j + f[j]*2[......]

Read more

bzoj 3376 文理分科

n,m写反了引起的惨剧。

网络流问题。

题目大意:给定一个m*n的矩阵,每个格子的人可以学文或者学理,学文和学理各有一个满意度,如果以某人为中心的十字内所有人都学文或者学理还会得到一个额外满意度,求最大满意度之和

令S集为学文,T集为学理

每个人学文或者学理的满意度很好连边[......]

Read more

1999: [Noip2007]Core树网的核

【题目大意】

求无根树的直径上一段不超过S长的链,使得偏心距最小。具体概念见原题

【思路】

首先明确几个性质:

(1)对于树中的任意一点,距离其最远的点一定是树的直径的某一端点。

(2)所有的直径是等价的,即任意一条所能求出的该最小偏心距相等。

于是我们可以用两[......]

Read more

1857[Scoi2010]传送带

代码有点难看啊。无所谓了。

一道三分模板题,会做二分就会。

【bzoj1085】[SCOI2005]骑士精神

a*算法,即启发式搜索,其实就是在dfs的基础上提前去判断有没有必要再次向下搜索。

2017年5月25日 0 / /
Tag:  No Tags

P3369/BZOJ3224 【模板】普通平衡树(Treap/SBT)

平衡树模板