BZOJ – Tgotp-Blog

5299: [Cqoi2018]解锁屏幕

令f[i][j]表示状态为i,最后到达点为j的方案数,

那么考虑下一个点,

能到达的情况就是最后一个点和现在这个点中间没有点或者所有点都在i状态内

这东西用差积判判可以预处理出来,然后跑状压dp就可以了,i大于4个1的时候加进答案就可以了

复杂度O(2^nn^2)然而[......]

Read more

5104: Fib数列

首先发现递推是解决不了这个问题的.

考虑用通项公式解决.

有公式f_n=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n)

那么即求解:

$$ a \equiv \frac{1}{\sq[......]

Read more

4541: [Hnoi2016]矿区

平面图转对偶图

c++代码如下:

 

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-5c985fa01def28105266[......]

Read more

4247: 挂饰

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

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

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

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

Read more

1098: [POI2007]办公楼biu

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

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

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

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

Read more

3572: [Hnoi2014]世界树

虚树经典题目

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

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

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

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

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

Read more