CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== Codeforces Round #662 (Div. 2) ======

[[https://codeforces.com/contest/1393|比赛链接]]

===== D. Rarity and New Dress =====

==== 题意 ====

给定一个 $n\times m$ 的网格，每个网格中有一个字母，问有多少个由同一字母构成的菱形。

下面给出边长为 $1,2,3$ 的菱形示例。

<code cpp>
						  a
			 a			 aaa
a			aaa			aaaaa
			 a			 aaa
						  a
</code>

==== 题解 ====

考虑以每个网格为中心的菱形个数，发现答案等于以该网格为中心的最大菱形的边长，于是题目等价于求以每个网格为中心得最大菱形的边长的和。

可以将每个菱形划分为左半三角形和右半三角形，再将三角形划分为列，发现每列长度为等差数列。

考虑 $\text{dp}$ 求出每个网格所在列能向上拓展的最大长度和向下拓展的最大长度，于是可以得到以每个网格为中心的三角形的列的最大长度。

然后再考虑 $\text{dp}$，根据等差数列的约束即可求出左右三角形的最大边长，最终每个点答案为左右三角形的最大边长的较小值。

<hidden 查看代码>
<code cpp>
const int MAXN=2005;
char s[MAXN][MAXN];
int dir[MAXN][MAXN][4],len[MAXN][MAXN];
int main()
{
	int n=read_int(),m=read_int();
	LL ans=0;
	_rep(i,1,n)
	fgets(s[i]+1,MAXN,stdin);
	_rep(i,1,n)
	_rep(j,1,m){
		if(s[i][j]==s[i-1][j])
		dir[i][j][0]=dir[i-1][j][0]+1;
	}
	for(int i=n;i;i--)
	_rep(j,1,m){
		if(s[i][j]==s[i+1][j])
		dir[i][j][1]=dir[i+1][j][1]+1;
		len[i][j]=min(dir[i][j][0],dir[i][j][1]);
	}
	_rep(i,1,n)
	_rep(j,1,m){
		if(s[i][j]==s[i][j-1])
		dir[i][j][2]=min(len[i][j],dir[i][j-1][2]+1);
	}
	_rep(i,1,n)
	for(int j=m;j;j--){
		if(s[i][j]==s[i][j+1])
		dir[i][j][3]=min(len[i][j],dir[i][j+1][3]+1);
		ans+=1+min(dir[i][j][2],dir[i][j][3]);
	}
	enter(ans);
	return 0;
}
</code>
</hidden>
CVBB ACM Team

用户工具

站点工具

页面工具
