Topcoder SRM 639 Div2 T3 BoardFoldingDiv2 题解

Topcoder Single Round Match 639 DIv2 T3 BoardFoldingDiv2 题解

这是我博客的第 66 篇文章，庆祝一下 :tada:

Translation

有一个 n 行 m 列的矩阵，每个元素都是 0 或 1；现在你可以沿着平行于矩阵边缘的直线“翻折”，必须保证翻折后重合的两个面上的对应元素相同。问你经过一系列翻折操作后，可能产生多少不同的矩阵。如果两个矩阵大小、元素相同，但��对于最初大矩阵左上角坐标不同，则这两个矩阵不同。 数据范围 $1\leqslant n,m \leqslant 50$。

• paper will contain between 1 and 50 elements, inclusive.
• Each element of paper will contain between 1 and 50 elements, inclusive.
• All elements of paper will have the same length.
• paper will contain only characters '0' and '1'.
• Time limit (s): 2.000
• Memory limit (MB): 256
• Stack limit (MB): 256

Examples

样例零：

{"10",
 "11"}

Returns: 1

这张纸根本没法折。

There is no valid way to fold this paper, so there is just one possible outcome.

样例一：

{"1111111",
 "1111111"}

Returns: 84

这张纸可以随便折。一共有 84 种方案。

We can fold it into any of the 84 possible subrectangles of the original rectangle.

样例三：

{"0110",
 "1001",
 "1001",
 "0110"}

Returns: 9

横着、竖着都可以沿中线对折，共 9 种方案。

Original

Little Petya likes puzzles a lot. Recently he has received one as a gift from his mother. The puzzle has the form of a rectangular sheet of paper that is divided into N rows by M columns of unit square cells. Rows are numbered 0 through N-1 from top to bottom, and columns 0 through M-1 from left to right. Each cell is colored either black or white. You are given a description of the paper, the exact format is specified at the end of this problem statement. The goal of the puzzle is to fold the paper. This has to be done in a sequence of turns. In each turn, Petya has to fold the paper according to the rules below. He can end the process after any number of turns (including zero), even if there are still valid ways to fold the paper. In each turn, Petya must follow these steps: To start folding, he must choose a line that is parallel to one of the sides of the paper and passes between two rows/columns of cells. He can then take the smaller part of the paper and fold it on top of the larger part. (If the line divides the current paper in half, he can fold either half on top of the other.) There is one additional restriction: Petya may only perform the fold if all cells of the part that is being folded land on equally-colored cells of the part that remains in place. For example, consider the following paper (with 0 and 1 representing white and black): 10010101 11110100 00000000 01101110 Here, Petya could choose the vertical line that goes between the two leftmost columns and the rest of the paper. Note that this is a valid choice: as he makes the fold, the cells from the leftmost two columns will all match their counterparts in the right part of the paper. This is how the paper looks like after the fold (with periods representing empty spaces): ..010101 ..110100 ..000000 ..101110 Clearly, even after multiple folds the paper will always look like a subrectangle of the original paper. Two states of the game are considered the same if that rectangle has the same dimensions and the same offset with respect to the original top left corner of the paper. (Note that folding order does not matter. Two different sequences of folding may produce the same final state.) You are given a description of the original state of the paper as a vector paper. Here N is the number of elements in paper and M is the length of its each element. For each i and j, the character paper[i][j] is either '0' (meaning that the cell (i,j) is white) or '1' (the cell is black). Compute and return the number of possible final states of the game.

Analysis

首先必须想明白一个很重要的结论（其实原题题目里都提示你了）：横向翻折与纵向翻折是独立的。也就是说我们可以先处理横向翻折的情况，得出方案数，再处理纵向翻折，最后两者相乘就是答案。 有了这个结论，问题就很简单了。我们直接做一次区间 DP 就可以方便地得出翻折方案数，累计即可。

Code

代码实现起来有点复杂，但是只要思路清晰其实并不难。

#include <bits/stdc++.h>
using namespace std;
const int maxn=55;
int n,m,ans1,ans2;
bool vis[maxn][maxn]; // vis[i][j]: 第i个cell开始的一段长度为j的闭区间能否与i+j+1开始的一段等长的闭区间匹配
// 即[i,i+j]与[i+j+1,i+2*j+1]两段区间的cells是否对称
// 注意j是整个区间半长
bool f[maxn][maxn]; // F[i][j]: 能否折叠得只剩[i,j]区间
class BoardFoldingDiv2 {
public:
    int howMany( vector <string> paper );
};
inline bool Check(int x,int y,bool mode,vector <string> paper){ // 验证两行/两列是否相同的函数
	// mode: 竖向验证(true)(||)或横向验证(false)(=)
	if (mode){
		for (int i=0;i<n;i++) if (paper[i][x]!=paper[i][y]) return false;
		// printf("Check Succesful: %d %d\n",x,y);
		return true;
	} else {
		for (int i=0;i<m;i++) if (paper[x][i]!=paper[y][i]) return false;
		return true;
	}
	return false;
}
int BoardFoldingDiv2::howMany(vector <string> paper) {
    n=paper.size();
	if (n==0) return 0;
	m=paper[0].length();

	// Part 1: build ans1 -------------------------------

	memset(vis,0,sizeof(vis));
	for (int i=0;i<m-1;i++) vis[i][1]=Check(i,i+1,true,paper);
	for (int L=3;L<=m;L+=2)
	for (int i=0;i<m-L;i++){
		int j=i+L;
		if ((j>=m)||(!vis[i+1][L/2])) continue;
		vis[i][(L+1)/2]=Check(i,j,true,paper);
	}

	memset(f,0,sizeof(f));
	f[0][m-1]=true;
	for (int L=m-1;L>=0;L--)
	for (int i=0;i<m-L;i++){
		int j=i+L;
		if (j>=m) continue;
		for (int k=i;(k<=j)&&(!f[i][j]);k++){
			if ((j+(j-k+1)<m)&&(vis[k][j-k+1])){ // 先考虑右边一块向左边折叠情况
				f[i][j]|=f[i][j+(j-k+1)];
			}
			if ((i-(k-i+1)>=0)&&(vis[i-(k-i+1)][k-i+1])){ // 左边一块向右折叠
				f[i][j]|=f[i-(k-i+1)][j];
			}
		}
	}
	ans1=0;
	for (int i=0;i<m;i++)
	for (int j=i;j<m;j++) ans1+=f[i][j];
	if (m==1) ans1=1;

	// Part 2: build ans2 -------------------------------

	memset(vis,0,sizeof(vis));
	for (int i=0;i<n-1;i++) vis[i][1]=Check(i,i+1,false,paper);
	for (int L=3;L<=n;L+=2)
	for (int i=0;i<n-L;i++){
		int j=i+L;
		if ((j>=n)||(!vis[i+1][L/2])) continue;
		vis[i][(L+1)/2]=Check(i,j,false,paper);
	}

	memset(f,0,sizeof(f));
	f[0][n-1]=true;
	for (int L=n-1;L>=0;L--)
	for (int i=0;i<n-L;i++){
		int j=i+L;
		if (j>=n) continue;
		for (int k=i;(k<=j)&&(!f[i][j]);k++){
			if ((j+(j-k+1)<n)&&(vis[k][j-k+1])){ // 先考虑下面一块向上边折叠情况
				f[i][j]|=f[i][j+(j-k+1)];
			}
			if ((i-(k-i+1)>=0)&&(vis[i-(k-i+1)][k-i+1])){ // 上面一块向下折叠
				f[i][j]|=f[i-(k-i+1)][j];
			}
		}
	}
	ans2=0;
	for (int i=0;i<n;i++)
	for (int j=i;j<n;j++) ans2+=f[i][j];
	if (n==1) ans2=1;

	// printf("ANS1=%d  ANS2=%d\n",ans1,ans2);
	return ans1*ans2;
}