https://codeforces.com/contest/1181/problem/C

题意:给一个n*m的格子(n,m<=1000),每个格子有个颜色,求可以条纹子矩阵的数量。

条纹矩阵就是如图

解法:

先预处理出每个点向下和它同字符能扩展到的位置down[i][j],然后暴力枚举顶点,检查即可。复杂度o(n*m)。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29); int n,m;
char s[1100][1100];
int down[1100][1100]; void init_down(){
for(int j=1;j<=m;j++){
int l=1,r=1;
for(;l<=n;){
while(r+1<=n && s[r+1][j]==s[l][j]) r++;
for(int i=l;i<=r;i++) down[i][j]=r-i+1;
l=r+1;r=l;
}
}
} bool check(int i,int j,int cnt,int k){
if(s[i][j]!=s[i][k] || s[i+cnt][j]!=s[i+cnt][k] || s[i+2*cnt][j]!=s[i+2*cnt][k]) return 0;
return down[i][k]==cnt && down[i+cnt][k]==cnt && down[i+2*cnt][k]>=cnt;
} void solve(){
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) down[i][j]=0;
init_down();
ll res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;){
int cnt=down[i][j];
if(i+3*cnt-1>n||!check(i,j,cnt,j)){
j++;continue;
}
int k=j;
while(k+1<=m&&check(i,j,cnt,k+1)) k++;
int w=k-j+1;
res+=1LL*w*(w+1)/2;
j=k+1;
}
}
cout<<res<<endl;
} int main(){
// freopen("in.txt","r",stdin);
while(cin>>n>>m) solve();
return 0;
}

最新文章

  1. disabled=&quot;true&quot; 的标签元素不可提交
  2. 中间人攻击(MITM)姿势总结
  3. MVC 4 用Nuget安装组件后的常见错误
  4. Java笔记2-数据类型,变量,Java运算符
  5. BOM与DOM
  6. java对xml文件做增删改查------摘录
  7. 模板 lucas
  8. Cretiria查询应用(二)
  9. HDU 3336 Count the string KMP
  10. 在windows下安装mysql5.6.24版本
  11. android 获取屏幕的宽和高
  12. Coursera, Big Data 4, Machine Learning With Big Data (week 1/2)
  13. Android学习之adb异常处理
  14. 原生JS实现瀑布流布局
  15. ios中scrollView基本用法
  16. springboot 设置 session 过期时间
  17. java-appium-527进阶-1 UiAutomator1&amp;2区别和封装
  18. Python3.6学习笔记(五)
  19. MVC框架中的值提供机制(一)
  20. ABAP CDS ON HANA-(7)CDSビューでの集約

热门文章

  1. select加下拉箭头
  2. javaSE学习四
  3. 06 RDD编程
  4. C# 连接SQLSERVER数据库常用操作类
  5. java--BigDecimal 类型介绍
  6. oracle收缩表和表空间
  7. antd-vue 框架的日期选择选年份
  8. kafak学习总结
  9. Containerd 安装及使用(yum及源码)
  10. Agilepoint中的JS Method 封装