【BZOJ4070】[Apio2015]雅加达的摩天楼
Description
印尼首都雅加达市有 N 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 0 到 N−1。除了这 N 座摩天楼外，雅加达市没有其他摩天楼。
有 M 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 0 到 M−1。编号为 i 的 doge 最初居住于编号为 Bi 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 i 的 doge 的跳跃能力为 Pi （Pi>0）。
在一次跳跃中，位于摩天楼 b 而跳跃能力为 p 的 doge 可以跳跃到编号为 b−p （如果 0≤b−p<N）或 b+p （如果 0≤b+p<N）的摩天楼。
编号为 0 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编 号为 1 的 doge。任何一个收到消息的 doge 有以下两个选择:
跳跃到其他摩天楼上；
将消息传递给它当前所在的摩天楼上的其他 doge。
请帮助 doge 们计算将消息从 0 号 doge 传递到 1 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 1 号 doge。
Input
输入的第一行包含两个整数 N 和 M。
接下来 M 行，每行包含两个整数 Bi 和 Pi。
Output
输出一行，表示所需要的最少步数。如果消息永远无法传递到 1 号 doge，输出 −1。
Sample Input
5 3
0 2
1 1
4 1
0 2
1 1
4 1
Sample Output
5
explanation
下面是一种步数为 5 的解决方案：
0 号 doge 跳跃到 2 号摩天楼，再跳跃到 4 号摩天楼（2 步）。
0 号 doge 将消息传递给 2 号 doge。
2 号 doge 跳跃到 3 号摩天楼,接着跳跃到 2 号摩天楼，再跳跃到 1 号摩天楼（3 步）。
2 号 doge 将消息传递给 1 号 doge。
explanation
下面是一种步数为 5 的解决方案：
0 号 doge 跳跃到 2 号摩天楼，再跳跃到 4 号摩天楼（2 步）。
0 号 doge 将消息传递给 2 号 doge。
2 号 doge 跳跃到 3 号摩天楼,接着跳跃到 2 号摩天楼，再跳跃到 1 号摩天楼（3 步）。
2 号 doge 将消息传递给 1 号 doge。
HINT
子任务
所有数据都保证 0≤Bi<N。
子任务 1 （10 分）
1≤N≤10
1≤Pi≤10
2≤M≤3
子任务 2 （12 分）
1≤N≤100
1≤Pi≤100
2≤M≤2000
子任务 3 （14 分）
1≤N≤2000
1≤Pi≤2000
2≤M≤2000
子任务 4 （21 分）
1≤N≤2000
1≤Pi≤2000
2≤M≤30000
子任务 5 （43 分）
1≤N≤30000
1≤Pi≤30000
2≤M≤30000
题解：一开始以为没收到情报的doge也能跳。。。GG~
先考虑暴力建图，对于一个doge<B,P>，我们从B向所有它能跳到的楼连边，但是这样连出的边是O(nm)的。于是我们发现，对于P和B%P都相同的doge，它们能跳到的点是相同的，对于一个它们都能跳到的点x，我们可以贪心的选取离它最近的两个doge与之连边，然后在相邻的doge之间再连边，这样做与暴力连边是等价的，但是略去了许多没有意义的边。
那么最后的边数是什么级别的呢？个人推测应该是O(n*sqrt(n))的，这个可以用分块的思想去理解一下（虽然我觉得我的做法要比分块高级一点）。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
int n,m,p1,p2,cnt,tot,S,T,siz;
set<int> s;
set<int>::iterator it;
queue<int> q;
int dis[300010],next[10000000],val[10000000],to[10000000],inq[300010],head[300010];
struct node
{
int B,P;
}p[30010];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
bool cmp(node a,node b)
{
return (a.P==b.P)?((a.B%a.P==b.B%b.P)?(a.B<b.B):(a.B%a.P<b.B%b.P)):(a.P<b.P);
}
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
int main()
{
n=rd(),m=rd(),tot=n;
int i,u;
memset(head,-1,sizeof(head));
for(i=1;i<=m;i++) p[i].B=rd(),p[i].P=rd();
S=p[1].B,T=p[2].B;
sort(p+1,p+m+1,cmp);
for(p2=p1=1;p1<=m;p2=++p1)
{
for(;p1<m&&p[p1+1].B%p[p1+1].P==p[p1].B%p[p1].P&&p[p1+1].P==p[p1].P;p1++);
siz=p[p1].P,s.clear();
for(i=p2;i<=p1;i++) s.insert(p[i].B);
for(i=p2+1;i<=p1;i++) add(p[i].B,p[i-1].B,(p[i].B-p[i-1].B)/siz);
for(i=p[p1].B%siz;i<n;i+=siz)
{
it=s.lower_bound(i);
if(it!=s.end()&&i!=(*it)) add((*it),i,((*it)-i)/siz);
if(it!=s.begin()) --it,add((*it),i,(i-(*it))/siz);
}
}
memset(dis,0x3f,sizeof(dis));
q.push(S),dis[S]=0;
while(!q.empty())
{
u=q.front(),q.pop(),inq[u]=0;
for(i=head[u];i!=-1;i=next[i])
{
if(dis[to[i]]>dis[u]+val[i])
{
dis[to[i]]=dis[u]+val[i];
if(!inq[to[i]]) inq[to[i]]=1,q.push(to[i]);
}
}
}
if(dis[T]==0x3f3f3f3f) printf("-1");
else printf("%d",dis[T]);
return 0;
}