【APIO2015】Jakarta Skyscrapers

题目描述

印尼首都雅加达市有 $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 有以下两个选择:

跳跃到其他摩天楼上；
将消息传递给它当前所在的摩天楼上的其他 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;

}

巴特西

【APIO2015】Jakarta Skyscrapers

题目描述

输入格式

输出格式

子任务

分析1

分析2

分析3

最新文章

热门文章