题解：CF1393D Rarity and New Dress

· · 题解

观察发现题解区都是大佬，写的题解十分简略，对萌新十分不友好，于是本蒟蒻来写一篇超详细的题解。

思路

显然求出以每个点为最下端点的最大大小菱形的大小 f_{i,j}，然后答案就是：

\sum_{i = 1}^n \sum_{j = 1}^m f_{i,j}

但是显然 f_{i,j} 是不能直接求的，就算使用二分加矩阵转置加预处理也只能做到最坏 \mathcal{O}(nm \sqrt{nm} \log \sqrt{nm})。显然是不足以通过的。

所以肯定得进行一些小小的转化。

对于一个菱形，假设最下端点是 (i,j)，大小为 r，那么对于 d \in \{0,1,2,\dots,r-1\}，第 i-d 行需要选择的列区间是 [j-d,j+d]；而对于 d' \in \{r,r+1,\dots,2r-2\}，第 i-d' 行需要选择的列区间是 [j-(2r-2-d'),j+(2r-2-d')]。

比较显然的一点是，大菱形一定是由小菱形推出的，所以不妨大胆尝试推一下。

设 D(i,j,r) 表示以 (i,j) 为下端点且大小为 r 的菱形的格子集合。

那么根据刚刚对于菱形的分析可以得到：

D(i,j,r) = \{(x,y) \ : |x-(i-r+1)|+|y-j| \le r-1\}

于是可得：

D(i,j,r) \setminus (D(i-1,j-1,r-1) \cup D(i-1,j+1,r-1)) = \{(i,j),(i-1,j),(i-2r+2,j),(i-3r+3,j)\}

于是我们想要判断 D(i,j,r) 是否同色，只需要判断 D(i-1,j-1,r-1) 和 D(i-1,j+1,r-1) 是否同色且都为 a_{i,j}，最后就是那四个格子是否也均为 a_{i,j}。

但是这是一件很麻烦的事情，麻烦在四个格子上。

由于本身 D(i-1,j-1,r-1) \cup D(i-1,j+1,r-1) 包含了第 j 列除了那四个格子之外的所有格子，所以那些格子一定是 a_{i,j}，于是判断四个格子可以改为 up_{i,j} \ge 2r-1。

其中 up_{i,j} 表示 (i,j) 往上只看第 j 列的连续同色格子数。

于是我们就可以列状态转移方程了：

f_{i,j} = \max_{r = 1}^n ([(a_{i-1,j-1} = a_{i-1,j+1} = a_{i,j}) \land (\min(f_{i-1,j-1},f_{i-1,j+1}) \ge r-1) \land (up_{i,j} \ge 2r-1)] \times r)

显然，这等价于：

f_{i,j} = \begin{cases} \min\left(\min(f_{i-1,j-1},f_{i-1,j+1})+1,\left\lfloor\dfrac{up_{i,j}+1}{2}\right\rfloor\right), & a_{i-1,j-1} = a_{i-1,j+1} = a_{i,j} \\ 1, & \text{otherwise} \end{cases}

直接转移就行了，时间复杂度 \mathcal{O}(nm)，轻松通过。 :::success[Code]

#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
char s[N][N];
int f[N][N];
int up[N][N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;++i)
    {
        cin >> s[i]+1;
    }
    for(int i = 1;i<=m;++i)
    {
        for(int j = 1;j<=n;++j)
        {
            int jj = j-1;
            if(s[j][i] == s[jj][i])
            {
                up[j][i] = up[j-1][i]+1;
            }
            else
            {
                up[j][i] = 1;
            }
        }
    }
    long long sum = 0;
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=m;++j)
        {
            int ii = i-1,jj = j-1,j_ = j+1;
            if(s[ii][jj] == s[ii][j_]&&s[ii][j_] == s[i][j])
            {
                f[i][j] = min(min(f[ii][jj],f[ii][j_])+1,up[i][j]+1>>1);
            }
            else
            {
                f[i][j] = 1;
            }
            sum+=f[i][j];
        }
    }
    cout << sum;
    return 0;
}

:::

总结

没想到这种类型的计数题竟然能用 DP，强强！？

尾声

如果你也想让这篇题解被更多萌新看到，请你点一个小小的赞，助力我的文章造福更多萌新，谢谢你们！