本蒟蒻只会个倍增lca，实在太菜了。
稍微灵活一下的倍增就不会了，所以开一个倍增专题，先把倍增练熟
1.跑路
由每次走 2k米很容易想到倍增。
map[k][i][j]表示从i走2k米能否走到 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走2k步的距离。
对于每一个询问倍增求解即可。
#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; }
上一篇：[luoguP2672] 推销员（贪心 + 树状数组 + 优先队列）
下一篇：[luoguP1074] 靶形数独（搜索）
倍增 Floyd
