题解 CF253D【Table with Letters - 2】

rui_er · 2022-05-23 20:28:01 · 题解

发现数据范围只够 \mathcal O(n^3) 的，因此考虑枚举上下左边界。发现“包含不超过 k 个 a”是有单调性的，因此可以处理出字母 a 的二维前缀和，使用双指针维护左右边界。

具体地，我们枚举上下边界 u,d，在移动 l,r 指针的时候记录数组 buc，buc_i 表示有多少个 l\le j\le r 满足 s_{u,j}=s_{d,j}=i。然后在满足“长宽大于一”且左上、左下字母相等的情况下利用 buc 数组即可统计答案。

注意本题需要文件读写，文件名是 input.txt 和 output.txt。

// Problem: CF253D Table with Letters - 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF253D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug prllf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 405;

ll n, m, k, sum[N][N], buc[26], ans;
char s[N][N];
template<typename T> void chkmin(T &x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T &x, T y) {if(x < y) x = y;}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%lld%lld%lld", &n, &m, &k);
    rep(i, 1, n) scanf("%s", s[i]+1);
    rep(i, 1, n) rep(j, 1, m) sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (s[i][j] == 'a');
    rep(u, 1, n) {
        rep(d, u+1, n) {
            memset(buc, 0, sizeof(buc));
            ll l = 1, r = 1, now = 0;
            while(l < m) {
                while(r <= m && sum[d][r] - sum[u-1][r] - sum[d][l-1] + sum[u-1][l-1] <= k) {
                    if(s[u][r] == s[d][r]) ++buc[s[u][r]-'a'];
                    ++r;
                }
                if(l < r && s[u][l] == s[d][l]) {
                    --buc[s[u][l]-'a'];
                    now += buc[s[u][l]-'a'];
                }
                ++l;
            }
            ans += now;
        }
    }
    printf("%lld\n", ans);
    return 0;
}