题目描述

印尼首都雅加达市有 $N$ 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 $0$ 到 $N − 1$。除了这 $N$ 座摩天楼外,雅加达市没有其他摩天楼。

有 $M$ 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 $0$ 到 $M − 1$。编号为 $i$ 的 doge 最初居住于编号为 $B_i$ 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 $i$ 的 doge 的跳跃能力为 $P_i$ ($P_i > 0$)。

在一次跳跃中,位于摩天楼 $b$ 而跳跃能力为 $p$ 的 doge 可以跳跃到编号为 $b − p$ (如果 $0 \leq b − p < N$)或 $b + p$ (如果 $0 \leq b + p < N$)的摩天楼。

编号为 $0$ 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编 号为 $1$ 的 doge。任何一个收到消息的 doge 有以下两个选择:

  1. 跳跃到其他摩天楼上;
  2. 将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 $0$ 号 doge 传递到 $1$ 号 doge 所需要的最少总跳跃步数,或者告诉它们消息永远不可能传递到 $1$ 号 doge。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行,每行包含两个整数 $B_i$ 和 $P_i$。

输出格式

输出一行,表示所需要的最少步数。如果消息永远无法传递到 $1$ 号 doge,输出 $−1$。

子任务

所有数据都保证 $0 \leq B_i < N$。

  • 子任务 1 (10 分)
    • $1 \leq N \leq 10$
    • $1 \leq P_i \leq 10$
    • $2 \leq M \leq 3$
  • 子任务 2 (12 分)
    • $1 \leq N \leq 100$
    • $1 \leq P_i \leq 100$
    • $2 \leq M \leq 2000$
  • 子任务 3 (14 分)
    • $1 \leq N \leq 2000$
    • $1 \leq P i ≤ 2000$
    • $2 \leq M \leq 2000$
  • 子任务 4 (21 分)
    • $1 \leq N \leq 2000$
    • $1 \leq P_i \leq 2000$
    • $2 \leq M \leq 30000$
  • 子任务 5 (43 分)
    • $1 \leq N \leq 30000$
    • $1 \leq P_i \leq 30000$
    • $2 \leq M \leq 30000$

分析1

并不想思考前三部分分着怎么打啊?

很直观的就可以想到,在可以达到的doge之间连有向边,代价为方向上的走向所需要的步数

直接跑一遍裸的dijkstra就有36分了咯.....

为了代码文章看起来好一点,就把头文件去掉了

int n,m,b[30010],p[30010];
int a[2010][2010],f[30010];
bool v[30010];
const int inf=100000000;

int main()
{
    read(n);read(m);
    for (int i=1;i<=m;i++)
        read(b[i]),read(p[i]);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=m;j++)
            a[i][j]=inf;
    for (int i=1;i<=m;i++)
        for (int j=1;j<=m;j++)
            if (i!=j && abs(b[i]-b[j])%p[i]==0)
                a[i][j]=abs(b[i]-b[j])/p[i];
    for (int i=1;i<=m;i++)
        f[i]=inf;
    f[1]=0;int x=1;
    memset(v,0,sizeof(v));
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=m;j++)
            if (f[x]+a[x][j]<f[j]) f[j]=f[x]+a[x][j];
        v[x]=1;x=0;
        for (int j=1;j<=m;j++)
            if (!v[j]&&(x==0||f[x]>f[j])) x=j;
    }
    if (f[2]==inf) puts("-1");else print(f[2]); 
    return 0;
}

分析2

思考bfs

用数组\(f[i][j]\)表示\({doge}_{i}\)到建筑\(j\)的最少步数

初始\(f[0][B_0]=0\),每次用\(f[i][j]\)去尝试拓展\(f[i][j\pm P_i]\)和位置\(j\pm P_i\)其他doge

一旦拓展到\({doge}_{1}\),直接输出答案即可,时间复杂度\(O(NM)\),期望得分57

代码同样,暂时去掉了头文件

int n,m,p[30010],f[30001][2001];
vector<int> b[2010];
const int inf=100000000;
struct data
{
    int x,y;
    data(int a=0,int b=0):x(a),y(b){}
};
queue<data> q;
bool v[2010];

int main()
{
    read(n);read(m);
    int x,y;
    for (int i=1;i<=m;i++)
    {
        read(x),read(p[i]),b[x].push_back(i);
        if (i==1) y=x;  
    }
    memset(v,0,sizeof(v));
    for (int i=1;i<=m;i++)
        for (int j=0;j<n;j++)
            f[i][j]=inf;
    v[y]=1;
    for (int i=0;i<b[y].size();i++)
        q.push(data(b[y][i],y)),f[b[y][i]][y]=0;
    while(!q.empty())
    {
        int x=q.front().x,y=q.front().y;q.pop();
        if (x==2){print(f[x][y]);return 0;}
        if (y-p[x]>=0 && !v[y-p[x]])
        {
            v[y-p[x]]=1;
            for (int i=0;i<b[y-p[x]].size();i++)
                f[b[y-p[x]][i]][y-p[x]]=f[x][y]+1,q.push(data(b[y-p[x]][i],y-p[x]));
        }
        if (y+p[x]<n && !v[y+p[x]])
        {
            v[y+p[x]]=1;
            for (int i=0;i<b[y+p[x]].size();i++)
                f[b[y+p[x]][i]][y+p[x]]=f[x][y]+1,q.push(data(b[y+p[x]][i],y+p[x]));
        }
        if (y-p[x]>=0)
        {
            if (f[x][y]+1<f[x][y-p[x]]) f[x][y-p[x]]=f[x][y]+1,q.push(data(x,y-p[x]));
        }
        if (y+p[x]<n)
        {
            if (f[x][y]+1<f[x][y+p[x]]) f[x][y+p[x]]=f[x][y]+1,q.push(data(x,y+p[x]));
        }
    }
    puts("-1");
    return 0;
}

分析3

一口毒奶......这题好毒啊......

考虑分块来做

\(P_i>\sqrt n\)时,可以直接暴力来做,因为最多只会有\(n\sqrt n\)条边

\(P_i\le \sqrt n\)时,我们可以发现有大量的边重合,考虑把他们合并起来

具体的合并方法:

不妨对每个点建\(\sqrt n\)个额外点,设第\(i\)个点的第\(j\)个额外点为\(P_{i,j}\)。我们在\(P_{i,j}\)\(P_{i+j,j}\)连长度为\(1\)的双向边(因为每一次跳跃的花费为\(1\))

再由所有\(P_{i,j}\)\(i\)连长度为\(0\)的边。对于\(vi≤C\)的doge,我们就由\(xi\)\(P_{xi,vi}\)连长度为\(0\)的边即可,很容易理解

然后剩下的,就是跑一下最短路了......我直接写了一发SPFA...

内存很坑爹啊...RE了无数次...总算是把官方数据跑过了...hack的数据...实在是无能为了了

在调试的时候,发现不应该取\(\sqrt n\),实际表明,取\(\sqrt {\frac {n}{logn}}\)附近的时候比较优

为了更达到减小内存的目的,稍微增大时间,我手动的把\(\sqrt {\frac {n}{logn}}\)减小一个常数,多次提交.....

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;
 
inline char nc(){
    /* 
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
    */return getchar(); 
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline int read(char *s)
{
    char c=nc();int len=1;
    for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0;
    for(;(c>='a' && c<='z');s[len++]=c,c=nc());
    s[len++]='\0';
    return len;
}
 
inline void read(char &x){
  for (x=nc();!(x>='A' && x<='Z');x=nc());
}
 
int wt,ss[19];
inline void print(int x){
    if (x<0) x=-x,putchar('-'); 
    if (!x) putchar(48); else {
    for (wt=0;x;ss[++wt]=x%10,x/=10);
    for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
    if (x<0) x=-x,putchar('-');
    if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,m,b[30010],p[30010],f[6000010];
bool v[30010];
struct data
{
    int x,y;
    data(int a=0,int b=0):x(a),y(b){}
};
struct cmp
{
    bool operator()(data x,data y)
    {
        if (x.y==y.y) return x.x>y.x;
        return x.y>y.y;
    }
};
vector<data> a[6000010];
const int inf=1000000000;

int calc(int x,int y,int z)
{
    return n+x*z+y-1;
}

void write(int x)
{
    if (x==inf) print(-1);else print(x);
    puts("");
}

int main()
{
    read(n);read(m);
    int x=(int)sqrt(n/log(n)+0.5);
    x=max(x,0);
    x-=10;x=max(x,0);                       //手动减小常数
    for (int i=0;i<m;i++)
    { 
        read(b[i]),read(p[i]);
        if (p[i]<=x) a[b[i]].push_back(data(calc(b[i],p[i],x),0));
        else
        {
            int s=0,j=b[i];
            while (j-p[i]>=0) 
                s+=1,j-=p[i],a[b[i]].push_back(data(j,s));
            s=0,j=b[i];
            while (j+p[i]<n)
                s+=1,j+=p[i],a[b[i]].push_back(data(j,s));
        }
    }
    for (int i=0;i<n;i++)
    {
        for (int j=1;j<=x;j++)
        {
            //print(calc(i,j,x)),putchar(' '),print(calc(i+j,j,x)),puts("");
            if (i+j<n) a[calc(i,j,x)].push_back(data(calc(i+j,j,x),1)),
                       a[calc(i+j,j,x)].push_back(data(calc(i,j,x),1));
            a[calc(i,j,x)].push_back(data(i,0));
        }
    }
    n=calc(n-1,x,x);
    for (int i=0;i<=n;i++)
        f[i]=inf;
    f[b[0]]=0;
    memset(v,0,sizeof(v));
    priority_queue<data,vector<data>,cmp> q;
    q.push(data(b[0],0));
    while (!q.empty())
    {
        int x=q.top().x,y=q.top().y;q.pop();
        while (y>f[x])
        {
            if (q.empty()) break;
            x=q.top().x,y=q.top().y,q.pop();
        }
        if (y>f[x]) break;
        for (int j=0;j<a[x].size();j++)
            if (f[x]+a[x][j].y<f[a[x][j].x])
                f[a[x][j].x]=f[x]+a[x][j].y,q.push(data(a[x][j].x,f[a[x][j].x]));
    }
    write(f[b[1]]);
    return 0;
}