题解：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

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

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

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

代码

#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写了一个新的交了