AtCoder AGC028-F：Reachable Cells

越来越喜欢AtCoder了，遍地都是神仙题。

题意：

给定一个\(N\)行\(N\)列的迷宫，每一个格子要么是障碍，要么是空地。每一块空地写着一个数码。在迷宫中，每一步只允许向右、向下走，且只能经过空地。

对于每两个连通（从一个可到达另一个）的格子，求出它们数码的乘积。问所有这种乘积的和。

\(1 \leq N \leq 500\)

思路：

容易把到达关系建成一张DAG，我们要做的就只是：对每一个点，求他所有后继的权值和。但是DAG后继数问题，众所周知只有\(O(|E||V|)\)做法，于是换思路。

我们猜测，从一个格子出发，可以达到的点集（即后继集合）大约是一个凸包的形状。

而这个猜想也大约是对的，然而要使其完全正确，还有很长的路要走。

以下用\((i,j)\)表示第\(i\)行第\(j\)列的格子。编号从1开始。

第一步

4177143673

7#########

5#1716155#

6#4#####5#

2#3#597#6#

6#9#8#3#5#

5#2#899#9#

1#6#####6#

6#5359657#

5#########

以上是样例4的网格，由嵌套的3段环状障碍组成。不妨由内而外称为一环，二环，三环。

注意到对于\((3,3)\)，他的所有后继在矩形\((3,3) - (9,9)\)里，被三环包围。然而，二环以内的部分却不是\((3,3)\)的后继，需要想办法剔除。

首先发现，如果\((i-1,j)\)和\((i,j-1)\)都是障碍，那么空地\((i,j)\)不会是其他任何格子的后继。因此，如果已经求完了\((i,j)\)自己的后继，完全可以把\((i,j)\)改成障碍。改完之后，可能会产生新的满足同样性质的空地，于是递归地改下去即可。

我们可以考虑从下到上，对每一行分别求答案。每当求完一行所有格子的答案，就把这一行里能改成障碍的都（递归地）修改掉，再进入上一行。

经过这样的操作，就可以证明：

假如第\(i+1\)行到第\(n\)行，都已执行过修改，那么对于空地\((i,j)\)，存在一个简单多边形，恰好包含\((i,j)\)的所有后继和若干障碍。

再进一步，这个多边形由一段“上边界”和一段“下边界”拼成，而每一段边界都是仅向下、向右延伸的阶梯型折线。

第二步

我们试着对\((i,j)\)，求出他的后继多边形的两段边界。以下给出了求下边界的大致的伪代码。

starting position := (i,j)

while not touching boundary:

    while adjacent empty cell exists:

        if moving down reaches empty cell:

            move down

        else:

            move right

    while (i,j) cannot reach current position:

            move right

上边界类似。

如果可以\(O(1)\)地判断，\((i,j)\)是否能够到达\(current position\)，那么这段代码的复杂度就是\(O(N)\)，总复杂度就是\(O(N^3)\)，可过。

第三步

先考虑求下边界时对连通性的判断。

引入“添加”操作，他做的事情是，把某个格子的后继中，所有被修改成障碍的空地还原。此操作的复杂度正比于被还原的格子数量，具体实现见代码中的\(add\)函数。

先清空第\(i\)行及以下的行（都改成障碍），再对第\(i\)行的前\(j\)个格子做添加操作，易证所得的网格满足：

1、\((i,j)\)的所有后继都依然是空地。

2、第\(i\)行下方的所有空地都由第\(i\)行的前\(j\)个格子可达。

3、第一步中的结论依然成立。

注意到先前那段伪代码的流程是：

（1）、沿着\((i,j)\)尽可能向下走，直到无路可走为止。

（2）、从路径尾端不断向右移，直到遇见从\((i,j)\)可达的空地。

（3）、以当前位置为起点，重复（1）。

考虑（2）中遇到的任意一个空地\(P\)，则有以下结论（画图后不难理解）：

若有\(k \leq j\)，\(P\)在以\((i,k)\)为起点的路径上，则此路径必然与一起点为\((i,j)\)的路径相交。

既然有交点，容易发现\(P\)一定由\((i,j)\)可达。于是，若使用以上算法，则（2）中遇到的所有空地都与\((i,j)\)连通。

求下边界解决了，求上边界的话，用对称大法也能同理解决。

细节不少，详见代码。

代码：

#include <bits/stdc++.h>

#pragma GCC optimize(3)

using namespace std;

#define iinf 2000000000

#define linf 1000000000000000000LL

#define ulinf 10000000000000000000ull

#define MOD1 1000000007LL

#define mpr make_pair

typedef long long LL;

typedef unsigned long long ULL;

typedef unsigned long UL;

typedef unsigned short US;

typedef pair < int , int > pii;

clock_t __stt;

inline void TStart(){__stt=clock();}

inline void TReport(){printf("\nTaken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}

template < typename T > T MIN(T a,T b){return a<b?a:b;}

template < typename T > T MAX(T a,T b){return a>b?a:b;}

template < typename T > T ABS(T a){return a>0?a:(-a);}

template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}

template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}

int n,g[505][505],s[505][505],mx[505];

bool e[505][505];

LL res;

int readchar(){

	char c=getchar();

	while(c==' ' || c=='\n') c=getchar();

	if(c=='#') return 0;

	return c-'0';

}

void add(int x,int y){

	e[x][y]=1;

	if(x<n-1 && g[x+1][y] && !e[x+1][y]) add(x+1,y);

	if(y<n-1 && g[x][y+1] && !e[x][y+1]) add(x,y+1);

}

int getlower(int x,int y){

	int cx=x,cy=y,ret=(y?s[x][y-1]:0);

	mx[y]=x;

	while(1){

		while(1){

			if(cx+1<n && e[cx+1][cy]){

				++cx;

				mx[y]=cx;

				ret+=(cy?s[cx][cy-1]:0);

			}

			else if(cy+1<n && e[cx][cy+1]){

				++cy;

			}

			else break;

		}

		bool found=0;

		while(cy+1<n){

			++cy;

			if(e[cx][cy]){

				found=1;

				break;

			}

		}

		if(!found) break;

	}

	return ret;

}

int getupper(int x,int y){

	int cx=x,cy=y,ret=0;

	while(1){

		while(1){

			if(cy+1<n && e[cx][cy+1]){

				++cy;

			}

			else if(cx+1<n && e[cx+1][cy]){

				ret+=s[cx][cy];

				++cx;

			}

			else break;

		}

		bool found=0;

		while(cx<n-1){

			ret+=s[cx][cy];

			++cx;

			if(cx>mx[y]) break;

			if(e[cx][cy]){

				found=1;

				break;

			}

		}

		if(!found || cx>mx[y]) break;

	}

	if(cx<=mx[y]) ret+=s[cx][cy];

	return ret;

}

void solveline(int x){

	int i,j,k;

	memcpy(s,g,sizeof(g));

	for(i=0;i<n;++i){

		for(j=1;j<n;++j){

			s[i][j]+=s[i][j-1];

		}

	}

	for(i=x;i<n;++i) memset(e[i],0,sizeof(e[i]));

	for(i=0;i<n;++i){

		if(!g[x][i]) continue;

		add(x,i);

		res-=(LL)g[x][i]*(LL)getlower(x,i);

	}

	for(i=x;i<n;++i) memset(e[i],0,sizeof(e[i]));

	for(i=n-1;i>=0;--i){

		if(!g[x][i]) continue;

		add(x,i);

		res+=(LL)g[x][i]*(LL)(getupper(x,i)-g[x][i]);

	}

}

void del(int x,int y){

	if((!x || !g[x-1][y]) && (!y || !g[x][y-1])){

		g[x][y]=0;

		if(x<n-1 && g[x+1][y]) del(x+1,y);

		if(y<n-1 && g[x][y+1]) del(x,y+1);

	}

}

int main(){

    // inputting start

    // 数据结构记得初始化！ n，m别写反！

    int i,j,k;

	scanf("%d",&n);

	for(i=0;i<n;++i){

		for(j=0;j<n;++j){

			g[i][j]=readchar();

		}

	}

    #ifdef LOCAL

        TStart();

    #endif

    // calculation start

    // 数据结构记得初始化！ n，m别写反！

	for(i=0;i<n;++i){

		for(j=0;j<n;++j){

			e[i][j]=(!!g[i][j]);

		}

	}

    for(i=n-1;i>=0;--i){

		solveline(i);

		for(j=0;j<n;++j){

			if(g[i][j]) del(i,j);

		}

	}

	printf("%lld\n",res);

    #ifdef LOCAL

        TReport();

    #endif

    return 0;

}

巴特西

AtCoder AGC028-F：Reachable Cells

题意：

思路：

第一步

第二步

第三步

代码：

最新文章

热门文章