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