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

考虑把单列扩展到矩阵。
继续观察样例，发现当这一列的这一段与上一列的这一段相等且这一段可行，那么这一段与上一段也可以合成新的一段合法旗帜。
于是，我们可以把每一个段的答案记录下来，遍历到上述情况时就把新的答案变为旧的答案加一，而答案就是

\sum_{i=1}^m\sum_{l=1}^ndis_{i,l }

用这个思路建议把列和行反过来输入。。。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#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()
{
//	ios::sync_with_stdio(0);
//	cin.tie();
//	cout.tie();
	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];
//				cout<<i<<' '<<l<<' '<<r<<' '<<dis[i][l]<<endl;
				l=r+1;
			}
		}
	}
	cout<<ans;
	return 0;
}

代码来自同机房同学 weisongze，感谢他的贡献，但他用我的半个TJ写了一个新的交了

题解：CF1181C Flag

文章操作

CF1181C

背景

思路

Part 1

Part 2

代码

相关推荐

评论

题解：CF1181C Flag