BZOJ – Tgotp-Blog

4378: [POI2015]Logistyka

容易发现,一个位置对于答案的贡献最多为s,

那么序列能分的次数的就是 \lfloor\frac{\sum_{i=1}^{n} min(a[i],s)}{c}\rfloor

我第一次写用的splay,每次查询找到第一个大于等于s的位置,然后左右分别考虑。。。

然而splay常[......]

Read more

2260: 商店购物 && 4349: 最小树形图 朱刘算法

2260的数据应该有误,存在自环,然而网上的题解一看都是一个样子。。。

简直了。。。重点是还能跑出来?!

这题就是最小树形图的板子题。

我的代码必须强行跑一次朱刘才能过2260

 

思路大致如下:
考虑到不存在自环时,每个点一定除了第一次以外均会被以最优方式[......]

Read more

4631: 踩气球

对于每个点维护一下这个点能向右跑的最远距离,这个很显然能用并查集维护。

然后考虑每个点建一棵线段树,然后根据左右两点的关系合并线段树。

那么在记录的最远距离左边的点一定都是已经可以加入答案的点,删去即可。

c++代码如下:
[crayon-5bf095e9df5749776858[......]

Read more

4247: 挂饰

容易贪心的想到,既有挂钩又有正价值的点一定能加入,即可以把这个挂在手机上,把原来的接上去。

做这一步的时候要考虑原来是否已经有加入,有的话挂钩量要减一。

然后考虑对于负价值的点,令f[i]表示能提供i个挂钩的最小价值,做一遍dp

然后和原来的合并即可,因为原来的是按顺序加入,那么扫[......]

Read more

2018年9月28日 0 / /
Tag: 

1098: [POI2007]办公楼biu

做完以后看了看题解,貌似用链表会快的多,标记一下哪些点是当前点能到的,链表访问时跳过即可。

说下我自己的,容易发现就是一个补图上维护并差集,但是补图上边太多,不是很好搞。

容易想到从一个点开始,寻求哪些点一定会和这个点在一个集合,那么就可以得到解。

通过set维护一下剩余点,算算时[......]

Read more

3572: [Hnoi2014]世界树

虚树经典题目

对于每次查询建立虚树,然后在树上dfs找出每个点最近的标记点。

然后考虑不在虚树上的点,如果是两点之间的点,看两点的从属,不一样就倍增找分界点

还有一些点和虚树上一个点下面,这种直接从属这个点就好了。

这题说来简单,就是调起来比较麻烦。

c++代码如下:[......]

Read more

3874: [Ahoi2014&Jsoi2014]宅男计划

容易发现,答案随f成单峰函数。

那么考虑三分,剩下的就是些细节...

c++代码如下:

 

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++代码如下: