bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊(分块算法)

时间:2021-11-11 15:19:22

传送门

题意:

  中文题意,不再赘述。

题解:

  下午在补分块算法的相关知识,看到某大神博客推荐的这道题目,就试着做了做;

  TLE了一下午可还行;

  bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊(分块算法)

  我的思路:

  将这 n 个点分成 sqrt(n) 块;

int belong[maxn];//belong[i]:第i个点所属的块
int L[maxn];//L[i]:i块的左端点
int nex[maxn];//nex[i]:从i点通过i+a[i],(i+a[i])+a[(i+a[i])]....来到belong[i]+1块的编号
int jump[maxn];//jump[i]:i点到达下一块的nex[i]点弹跳的次数