题目

题目大意

给你一个矩阵，从\((1,1)\)开始，每次往右上、右、右下三个格子中权值最大的那个跳。

第一行上面是第\(n\)行，第\(m\)列右边是第\(1\)列。反之同理。

有两个操作：跳\(K\)步和修改某行某列的权值。

\(n,m\leq 2000\)

思考历程

一开始觉得似乎可以倍增，但这个修改操作太烦人，想了很久感觉倍增不可做。

最终打暴力+判断循环节。然而爆\(10\)了。

后来发现少打了个\(+1\)，加上之后，居然水了\(85\)分。

正解

设\(jump_i\)表示\(i\)行\(1\)列开始跳\(m\)步会到哪一行。

有了这个东西，询问就很好做了。先跳到\(1\)列，然后每次\(m\)步\(m\)步地跳，判一下循环节。

重点是这个东西怎么维护。

按照题解做法，在某个点修改之后往前搞。由于改变方向的点都是在一个区间之内的，所以维护左端点和右端点，一直做到\(1\)列即可。

然而……

无数人有实践表明，这样打不出啊！！！

细节太多了……

于是有个造福人类的线段树做法。

我们可以计算出\(i\)列到\(i+1\)列的映射，用个长度为\(n\)的数组存下来。

然后利用线段树合并，处理出\(1\)列到\(n+1\)列的映射，也就是\(jump\)数组。

查询的时候一模一样。至于修改，直接单点修改，单次修改复杂度\(O(n\lg m)\)

也就比题解做法多了一个\(lg\)而已，但代码可要方便很多。

代码

（线段树做法）

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 2010

inline int input(){

	char ch=getchar();

	while (ch<'0' || '9'<ch)

		ch=getchar();

	int x=0;

	do{

		x=x*10+ch-'0';

		ch=getchar();

	}

	while ('0'<=ch && ch<='9');

	return x;

}

int n,m;

int a[N][N];

int nowx=1,nowy=1;

inline int dn(int x){return x==n?1:x+1;}

inline int up(int x){return x==1?n:x-1;}

inline int ri(int x){return x==m?1:x+1;}

inline int le(int x){return x==1?m:x-1;}

inline int nxt(int x,int y){

	y=ri(y);

	int ux=up(x),dx=dn(x);

	if (a[ux][y]>a[x][y])

		x=ux;

	if (a[dx][y]>a[x][y])

		x=dx;

	return x;

}

inline void get_next(int &x,int &y){

	x=nxt(x,y);

	y=ri(y);

}

int jump[N<<4][N];

int vis[N],BZ,tim[N];

void build(int k,int l,int r){

	if (l==r){

		for (int i=1;i<=n;++i)

			jump[k][i]=nxt(i,l);

		return;

	}

	int mid=l+r>>1;

	build(k<<1,l,mid);

	build(k<<1|1,mid+1,r);

	for (int i=1;i<=n;++i)

		jump[k][i]=jump[k<<1|1][jump[k<<1][i]];

}

void change(int k,int l,int r,int y){

	if (l==r){

		for (int i=1;i<=n;++i)

			jump[k][i]=nxt(i,y);

		return;

	}

	int mid=l+r>>1;

	if (y<=mid)

		change(k<<1,l,mid,y);

	else

		change(k<<1|1,mid+1,r,y);

	for (int i=1;i<=n;++i)

		jump[k][i]=jump[k<<1|1][jump[k<<1][i]];

}

int main(){

	freopen("jump.in","r",stdin);

	freopen("jump.out","w",stdout);

	n=input(),m=input();

	for (int i=1;i<=n;++i)

		for (int j=1;j<=m;++j)

			a[i][j]=input();

	build(1,1,m);

	int Q;

	scanf("%d",&Q);

	char op[7];

	while (Q--){

		scanf("%s",op);

		if (*op=='m'){

			int k=input(),i;

			for (;k && nowy!=1;--k)

				get_next(nowx,nowy);

			if (k==0){

				printf("%d %d\n",nowx,nowy);

				continue;

			}

			vis[nowx]=++BZ;

			tim[nowx]=i=0;

			while (k>=m){

				k-=m;

				++i;

				nowx=jump[1][nowx];

				if (vis[nowx]!=BZ){

					vis[nowx]=BZ;

					tim[nowx]=i;

					continue;

				}

				k%=m*(i-tim[nowx]);

				break;

			}

			for (;k>=m;k-=m)

				nowx=jump[1][nowx];

			for (;k;--k)

				get_next(nowx,nowy);

			printf("%d %d\n",nowx,nowy);

		}

		else{

			int x=input(),y=input(),c=input();

			a[x][y]=c;

			change(1,1,m,le(y));

		}

	}

	return 0;

}

总结

好多时候都可以用到线段树呢……

巴特西

[JZOJ6278] 2019.8.5【NOIP提高组A】跳房子

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章