倍增专题

本蒟蒻只会个倍增lca，实在太菜了。

稍微灵活一下的倍增就不会了，所以开一个倍增专题，先把倍增练熟

1.跑路

由每次走 2^k米很容易想到倍增。

map[k][i][j]表示从i走2^k米能否走到 j

如果 map[k1][i][l]==1 && map[k1][l][j] == 1，那么map[k][i][j] == 1

如果 map[k][i][j]==1 那么就可以一次走过去，dis[i][j]=1

然后floyd求最短路（其他方法也行，数据小，且floyd好写）

#include <cstdio> #include <cstring> #include <iostream> #define N 101 #define min(x, y) ((x) < (y) ? (x) : (y)) int n, m; int map[N][N][N], dis[N][N]; inline int read() int main()

2.[POI2010]ZABFrog

可以用一个队列来求出每个点第k远的点（神奇）

然后倍增搞，但是MLE，需要滚动数组。

#include <cstdio> #include <iostream> #define N 1000001 #define LL long long int n, k; LL m, a[N]; int f[2][N], ans[N]; int main() for(i = 1; i <= n; i++) ans[i] = i; for(i = 1; m; i++, m >>= 1) for(j = 1; j <= n; j++) for(i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; }

　　

3.开车旅行

noip超恶心倍增题。

预处理出来小A和小B在每个位置所到的点，这个可以从后往前扫，将每一个扫到的数放到一个集合里面，因为集合可以自动排好序。

然后对于i，小A和小B能到的点只有可能是排好序后的i1,i2,i+1,i+2。

开一些倍增数组，因为小A和小B轮流开车，如果开两个倍增数组，一个表示小A，一个表示小B，那么倍增的时候要考虑奇偶性，非常麻烦，所以精妙的地方就来了。

把A走一次和B走一次合起来，算作一步，开个倍增数组f[N][21]，另开两个倍增数组disA[N][21]，disB[N][21]表示A和B走2^k步的距离。

对于每一个询问倍增求解即可。

#include <set> #include <cstdio> #include <iostream> #include <algorithm> #define N 100001 #define abs(x) ((x) < 0 ? (x) : (x)) using namespace std; double val = ~(1 << 31), A, B; int n, m, tmp, cnt, ans = 1, X, S; int f[N][21], disA[N][21], disB[N][21], a[N], b[N]; struct node }h[N + 4]; set <node> s; set <node> :: iterator it; inline int read() inline bool cmp(node x, node y) inline double ask(int x) int main() for(i = n; i >= 1; i) it++; } if(++it != s.end()) std::sort(h + n + 1, h + n + cnt, cmp); if(cnt > 1) b[i] = h[n + 1].id; if(cnt > 2) a[i] = h[n + 2].id; } for(i = 1; i <= n; i++) if(a[i]) for(j = 1; j <= 20; j++) for(i = 1; i <= n; i++) f[i][j] = f[f[i][j 1]][j 1], disA[i][j] = disA[i][j 1] + disA[f[i][j 1]][j 1], disB[i][j] = disB[i][j 1] + disB[f[i][j 1]][j 1]; X = read(); for(i = 1; i <= n; i++) printf("%d\n", ans); m = read(); for(i = 1; i <= m; i++) return 0; }

　　

上一篇：[luoguP1040] 加分二叉树（DP）

下一篇：[luoguP1494] 岳麓山上打水 &amp;&amp; [luoguP2744] [USACO5.3]量取牛奶Milk Measuring

---

倍增 Floyd