CF1181C

背景

今天课上遇到了这道题，在思考了一会后同学发现了一个神奇的思路，机房其他同学hack无果，假了私信删除

思路

Part 1

先观察样例二

CPP

6 1
a
a
b
b
c
c

可以得出一个看似很对的贪心，就是对于单个列的任意一面旗帜，中间段必然只能是一整段的相同颜色。也就是说下面的分割是不行的

CPP

……
a
a
a
a
------
a
a
a
a
……

所以对于每一列我们可以用双指针，枚举每一个连续的相同字符段，然后遍历上下的相同长度段，判断是否可行，时间复杂度是

O(n)

，~~常数略大，但这题应该不卡常~~。

Part 2

考虑把单列扩展到矩阵。
继续观察样例，发现样例1的子矩阵

CPP

aa
bb
cc

实际上整体也是一个国旗，所以我们对于每个区间（上的任意点）记录下前面与这个区间相同的数量，统计答案也要加上这个值，然后更新。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define F(i,x,y) for(i=x;i<=y;i++)
#define rF(i,x,y) for(i=x;i>=y;i--)
int n,m,dis[1005][1005];
char g[1005][1005];
signed main()
{
	int i,j,l=1,r,k,ans=0;
	cin>>n>>m;
	F(i,1,n) F(j,1,m) cin>>g[j][i];
	F(i,1,m)
	{
		l=1;
		F(r,1,n)
		{
			if(g[i][r]!=g[i][r+1])
			{
				int len=r-l+1;
				if(l-len<1||r+len>n) 
				{
					l=r+1;
					continue;
				}
				rF(j,l-2,l-len) if(g[i][j]!=g[i][j+1]) break;
				F(k,r+2,r+len) if(g[i][k]!=g[i][k-1]) break;
				if(j>=l-len||k<=r+len) 
				{
					l=r+1;
					continue;
				}
				F(j,l-len,r+len) if(g[i-1][j]!=g[i][j]) break;
				if(j>r+len) dis[i][l]=dis[i-1][l]+1;
				else dis[i][l]=1;
				ans+=dis[i][l];
				l=r+1;
			}
		}
	}
	cout<<ans;
	return 0;
}

其实这题不需要预处理。。。

Wang_H_Y帮我完成了TJ的一部分

题解：CF1181C Flag

文章操作