注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4070][Apio2015]雅加达的摩天楼  

2015-05-18 10:58:03|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4070: [Apio2015]雅加达的摩天楼

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 71  Solved: 32
[Submit][Status][Discuss]

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

Sample Output

5 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≤N≤30000
1≤Pi≤30000
2≤M≤30000

Solution

考场上写完暴力卡个时就过了没去管。。。
如果保存图的话,根据p与sqrtN的关系分类讨论。
如果不保存图的话,dijkstra跑最短路,卡个时也是可以过的;
如果不卡时的话,那么当一个点能以p的活动半径跳到另一个能以p(的倍数)为活动半径的点的话,就不继续往下跳来更新答案。也是可以的。

Code

/**************************************************************
    Problem: 4070
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1364 ms
    Memory:7896 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 30010
int s,t,d[N],n,m,i,j,in[N],la[N],et,x,oo,cnt,L[N],R[N];
struct D{int b,p,flag;}a[N];
bool operator<(const D&a,const D&b){return a.b<b.b||a.b==b.b&&a.p<b.p;}
bool operator==(const D&a,const D&b){return a.b==b.b&&a.p==b.p&&a.flag==b.flag;}
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
struct H{int x,d;};
bool operator<(const H&a,const H&b){return a.d>b.d;}
std::priority_queue<H>q;
void upd(int pos,int dis){
    if(d[pos]>dis)q.push((H){pos,d[pos]=dis});
}
int find(int l,int r,int p){
    if(l>r)return 0;
    for(int mid;l<r;a[mid=l+r+1>>1].p<=p?l=mid:r=mid-1);
    return a[l].p==p;
}
int main(){
    for(n=F(),m=F(),i=1;i<=m;i++)a[i]=(D){F(),F()};
    s=a[1].b,t=a[2].b,a[1].flag=1,a[2].flag=2;a[0].b=-1;
    std::sort(a+1,a+1+m);m=std::unique(a+1,a+1+m)-a-1;
    for(L[0]=1,R[0]=0,i=0;i<n;i++){
        for(i?R[i]=R[i-1],L[i]=R[i]+1:1;R[i]+1<=m&&a[R[i]+1].b==i;R[i]++);
    }
    memset(d,63,sizeof(d));oo=d[0];
    for(q.push((H){s,d[s]=0});!q.empty();q.pop())
    if(x=q.top().x,!in[x])
    for(in[x]=1,i=L[x];i<=R[x];i++){
        for(cnt=d[x],j=x-a[i].p;j>=0;j-=a[i].p){
            upd(j,++cnt);
            if(find(L[j],R[j],a[i].p))break;
        }
        for(cnt=d[x],j=x+a[i].p;j<n;j+=a[i].p){
            upd(j,++cnt);
            if(find(L[j],R[j],a[i].p))break;
        }
    }
    if(d[t]==oo)puts("-1");
    else printf("%d\n",d[t]);
}
  评论这张
 
阅读(204)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018