题解：CF1181C Flag

· · 题解

CF1181C

背景

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

思路

Part 1

先观察样例二

6 1
a
a
b
b
c
c

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

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

所以对于每一列我们可以用双指针，枚举每一个连续的相同字符段，然后遍历上下的相同长度段，判断是否可行，时间复杂度是 O(n)，常数略大，但这题应该不卡常。

Part 2

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

aa
bb
cc

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

Code

#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的一部分