CF567(Div2)Flag-飞外

1、题目链接：https://www.luogu.org/problem/CF1181C

2、题意：有个人想要卖国旗。

3、一面国旗可以抽象为一个n×m的矩形，每一个位置有一个颜色。这个矩形由自上而下三条横向的颜色带组成，每一条颜色带宽度相等，而且相邻两个颜色带颜色不能相同。

4、现在你有一个n×m的矩形，你需要计算其中能够称为国旗的子矩形数量。

5、题意：我们可以先用一个pre数组预处理，存储的是以点(i,j)之后又多少行和它颜色是相同的(包括自身)

6、我们便可以一列一列的开始找矩形。

7、具体看代码

8、#include bits/stdc++.h using namespace std;typedef long long ll;const int maxn=1007;const int inf=0x3f3f3f3f;const int N=1e7;const ll mod=1e9+7;#define meminf(a) memset(a,0x3f,sizeof(a))#define mem0(a) memset(a,0,sizeof(a));char g[1007][1007];int pre[1007][1007];int main(){ int n,m;scanf("%d%d", n, m); for(int i=1;i i++)scanf("%s",g[i]+1); for(int i=n;i 0;i--){ for(int j=m;j 0;j--) pre[i][j]=g[i+1][j]==g[i][j]?pre[i+1][j]+1:1; //预处理，pre数组代表点（i,j）下面的点和它相同的长度（包括它自身） ll ans=0; for(int i=1;i i++){ ll cnt=0; int pa=-1,pb=-1,pc=-1,pd=-1;//pa,pb,pc,pd代表上一个以四条分界线坐标 for(int j=1;j j++){ //a,b,c,d是一个国旗（如果能构成的话）的三个颜色带的分界线 int a=i,b=a+pre[a][j],c=b+pre[b][j],d=c+pre[c][j]; if(c =n b-a==c-b b-a =d-c){ //当前这一列满足能构成一个国旗 if(pc =n pa==a pb==b pc==c pd-pc =pb-pa g[a][j]==g[a][j-1] g[b][j]==g[b][j-1] g[c][j]==g[c][j-1]){ //如果新成的一列的能够和前一列合并的话，就将宽度加一 cnt++; else{ //否则就加上前面那个矩形能够构成的国旗的个数，并且将cnt重新赋为1, ans+=(cnt*(cnt+1)) 1; cnt=1; pa=a,pb=b,pc=c,pd=d;//更新 ans+=(cnt*(cnt+1)) 1; //每一列遍历完后记得还要再加一遍 printf("%lld",ans); return 0;}

【#CF567(Div2)Flag-飞外#】到此分享完毕，希望对大家有所帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！