BZOJ – 第24页 – Tgotp-Blog

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)

平衡树模板

1036: [ZJOI2008]树的统计Count

典型的树链剖分,就是一道模型题。

小z的袜子

莫队算法入门题,关于这道题的解释到处都是,这里只放代码了。