倍增 – Tgotp-Blog

3306: 树

树剖随便搞搞就行了

c++代码如下:

 

3551: [ONTAK2010]Peaks加强版

双倍经验。。。

这题是去掉强化版的在线版本

也是noi2018d1t1的强化版qaq

在并查集树上主席树合并即可,查询时用倍增就好了.

详细描述可以参照noi2018d1t1的题解qaq

c++代码如下:

Read more

3670: [Noi2014]动物园

仔细看完题以后,发现肯定和kmp有关,先搞出 next 数组

然后发现答案就是某一个next <i/2时的值

但是这个样子的话极限情况时n^2,发现瓶颈在于找next,然后考虑倍增一下就出来了.

注意卡常

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

Read more

2500: 幸福的道路

先两遍dfs处理出对于每个点能达到的最大幸福度,

然后问题转化为求序列  最长子段区间最大值与最小值差 <= m的长度

先用st表预处理出 就可以o(n)解决。

c++代码如下:

 

1706: [usaco2007 Nov]relays 奶牛接力跑

令f[q][x][y] 表示x 到 y点经过了2^q个跑道的最小花费,那么把n二进制拆分,

令g[i][j]表示i到j的最小花费,对于n&(1<<q)的部分直接将f[q]加入g中,因为一定从g和f中各挑一半,那么用临时数组h来存储当前答案,最后把再把h重新赋给g。

同[......]

Read more

2165: 大楼

对于这道题,观察n得范围 <= 100 那么考虑倍增Floyd

d[z][x][y] 表示x ,y 跳了2^z次方次所上升得楼层。

对于不连通得两点令d[0][x][y]  = -inf。然后倍增。

对于当前倍增后如果值大于m就跳出,类似于倍增求lca,所以最后答案应该 +[......]

Read more

T11837 s2 lca模板(倍增版)

lca模板

第一份写萎了

c++代码如下:

当然都能ac

第二份。

实际上 路径的长度为depth[x] + depth[y] - 2* depth[lca]

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

Read more

NOIP2012 开车旅行

好难呀。。。

花了一早上来肝这道题,我认为真心不好做。

首先思路是倍增:

令F[I][J]表示以I出发2^J个点所到达的点

令A[I][J]表示以I出发2^J个点a所行驶的距离

令B[I][J]表示以I出发2^J个点b所行驶的距离

首先,你需要找到n个点距离他最近的点与次近的点。

显而[......]

Read more

疫情控制 NOIP2012 T6

二分答案 + 贪心;

你会发现,其实对于每个点,我们只要能往上(不是根节点)一定是更优的,如果是根节点,我们先看看这个点通不通,不通的话这个点判通,返回,不然的话进入根节点找最小不通的点。

最后一个点恶心的菊花图,所以对于这道题的极限数据,你倍增不倍增都没卵用,我也懒得帖我倍增+桶排的代[......]

Read more