codeforces 253D. Table with Letters - 2

2024-09-04 23:18
文章标签 codeforces table letters 253d

本文主要是介绍codeforces 253D. Table with Letters - 2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

D. Table with Letters - 2

time limit per test

2 seconds

memory limit per test

256 megabytes

input

input.txt

output

output.txt

Vasya has recently started to learn English. Now he needs to remember how to write English letters. He isn't sure about some of them, so he decided to train a little.

He found a sheet of squared paper and began writing arbitrary English letters there. In the end Vasya wrote n lines containing m characters each. Thus, he got a rectangular n × m table, each cell of the table contained some English letter. Let's number the table rows from top to bottom with integers from 1 to n, and columns — from left to right with integers from 1 to m.

After that Vasya looked at the resulting rectangular table and wondered, how many subtables are there, that matches both following conditions:

  • the subtable contains at most k cells with "a" letter;
  • all letters, located in all four corner cells of the subtable, are equal.

Formally, a subtable's definition is as follows. It is defined by four integers x1, y1, x2, y2 such that 1 ≤ x1 < x2 ≤ n, 1 ≤ y1 < y2 ≤ m. Then the subtable contains all such cells (x, y) (x is the row number, y is the column number), for which the following inequality holds x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. The corner cells of the table are cells (x1, y1), (x1, y2), (x2, y1), (x2, y2).

Vasya is already too tired after he's been writing letters to a piece of paper. That's why he asks you to count the value he is interested in.

Input

The first line contains three integers n, m, k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m).

Next n lines contain m characters each — the given table. Each character of the table is a lowercase English letter.

Output

Print a single integer — the number of required subtables.

Examples

input

Copy

3 4 4
aabb
baab
baab

output

Copy

2

input

Copy

4 5 1
ababa
ccaca
ccacb
cbabc

output

Copy

1

Note

There are two suitable subtables in the first sample: the first one's upper left corner is cell (2, 2) and lower right corner is cell (3, 3), the second one's upper left corner is cell (2, 1) and lower right corner is cell (3, 4).

思路:先通过二维前缀和求出 每个点到左上角的矩形中一共有多少个a,然后判断任意一个矩形的时候类似容斥定理加加减减就好。关键是端点的枚举方式,首先固定上下的行然后固定左端点枚举右端点,很巧妙的是。用一个数组来记录上下这两行中取同一列的时候字母相同的列数用字母对应的acsii码做下标(先不管配对的问题只要符合同一列字母相同就给他计算上)每出现一对就给他加一。这样在右端点循环完之后左端点再变大的时候,之前已经计算好的矩形中的a的个数本来就小于K现在左端点还右移了肯定更加符合K,这样子r就可以保证最少遍历一遍也就是说区间左端点右移就不用在初始化右端点了。

需要注意的是开long long和在统计列数的时候不要忘记把自身减去。

#include <iostream>
#include <cmath>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
typedef  long long ll;
using namespace std;
int a[20000],sum[2000][2000];
char ha[1950][1950];
int main()
{freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);ll n,m,k,su=0;cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ha[i][j];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];if(ha[i][j]=='a')sum[i][j]++;// cout<<sum[i][j]<<endl;}}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int r=1;memset(a,0,sizeof(a));for(int l=1;l<=m;l++){if(ha[i][l]!=ha[j][l])continue;a[ha[i][l]]--;while(r<=m&&sum[j][r]-sum[j][l-1]-sum[i-1][r]+sum[i-1][l-1]<=k){if(ha[i][r]==ha[j][r])a[ha[i][r]]++;r++;//cout<<a[ha[i][r]]<<endl;}if(a[ha[i][l]]>0)su+=a[ha[i][l]];}}}cout<<su<<endl;
}

 

这篇关于codeforces 253D. Table with Letters - 2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137313

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

vue2实践:el-table实现由用户自己控制行数的动态表格

需求 项目中需要提供一个动态表单,如图: 当我点击添加时,便添加一行;点击右边的删除时,便删除这一行。 至少要有一行数据,但是没有上限。 思路 这种每一行的数据固定,但是不定行数的,很容易想到使用el-table来实现,它可以循环读取:data所绑定的数组,来生成行数据,不同的是: 1、table里面的每一个cell,需要放置一个input来支持用户编辑。 2、最后一列放置两个b

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

通过Ajax请求后台数据,返回JSONArray(JsonObject),页面(Jquery)以table的形式展示

点击“会商人员情况表”,弹出层,显示一个表格,如下图: 利用Ajax和Jquery和JSONArray和JsonObject来实现: 代码如下: 在hspersons.html中: <!DOCTYPE html><html><head><meta charset="UTF-8"><title>会商人员情况表</title><script type="text/javasc

UVa 10820 Send a Table (Farey数列欧拉函数求和)

这里先说一下欧拉函数的求法 先说一下筛选素数的方法 void Get_Prime(){ /*筛选素数法*/for(int i = 0; i < N; i++) vis[i] = 1;vis[0] = vis[1] = 0;for(int i = 2; i * i < N; i++)if(vis[i]){for(int j = i * i; j < N; j += i)vis[j] =

css-table

设置table的文字不换行:给th,td添加white-space: nowrap; 设置单元格内容及其边框的距离:使用html的cellpadding属性,还有一种方式设置padding。在CSS中,table, th, td{padding:0;}效果等同于cellpadding="0″。 设置table的单元格边距:border-spacing如果定义一个 length 参数,那么定义的是水