ACM模版
描述
题解
给定一个矩阵，求任选一个子矩阵的所拥有的不同颜色的期望个数。大致就是这么个意思。这里我们换位思考，可以考虑为求每一种颜色的贡献次数，也就是每一个颜色所出现的产生贡献的子矩阵个数。最后将所有颜色的贡献之和除以所有的子矩阵数目就是结果。
至于怎么求贡献，可以去参考一下 RJ28 大佬的这篇博客，感觉比官方题解的思路好一些，容易理解一些。这里单调栈的应用实在是不错，代码也更加简单一些。
感觉自己好蠢好蠢，想了好久也没有理清思路……多谢大佬的博客。
代码
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN =
111;
struct node
{
int x, n;
node() {};
node(
int a,
int b)
{
x = a;
n = b;
}
} stc[MAXN];
int n, m, tot;
ll ans;
int mat[MAXN][MAXN];
int pre[MAXN * MAXN][MAXN];
int tmp[MAXN * MAXN][MAXN];
int vis[MAXN * MAXN];
int get_cnt(
int l,
int r,
int i,
int j,
int col)
{
int sum =
0, t =
0, ret =
0;
for (
int k = l; k <= r; k++)
{
int d = (i == pre[col][k] && k >= j) ? i - tmp[col][k] : i - pre[col][k];
if (!d)
{
t = sum =
0;
}
else
{
node u = node(d,
1);
while (t && stc[t].x >= u.x)
{
sum -= stc[t].x * stc[t].n;
u.n += stc[t].n;
t--;
}
sum += u.x * u.n *
1ll;
stc[++t] = u;
ret += sum;
}
}
return ret;
}
template <
class T>
inline void scan_d(T &ret)
{
char c;
ret =
0;
while ((c = getchar()) <
'0' || c >
'9');
while (c >=
'0' && c <=
'9')
{
ret = ret *
10 + (c -
'0'), c = getchar();
}
}
int main()
{
int T;
scan_d(T);
while (T--)
{
memset(pre,
0,
sizeof(pre));
memset(vis,
0,
sizeof(vis));
tot =
0, ans =
0;
scan_d(n), scan_d(m);
for (
int i =
1; i <= n; i++)
{
for (
int j =
1; j <= m; j++)
{
scan_d(mat[i][j]);
if (!vis[mat[i][j]])
{
tot++;
vis[mat[i][j]] =
1;
}
}
}
for (
int i =
1; i <= n; i++)
{
for (
int j =
1; j <= m; j++)
{
tmp[mat[i][j]][j] = pre[mat[i][j]][j];
pre[mat[i][j]][j] = i;
}
for (
int j =
1; j <= m; j++)
{
int col = mat[i][j];
ans += (n - i +
1ll) *
(get_cnt(
1, m, i, j, col)
- get_cnt(
1, j -
1, i, j, col)
- get_cnt(j +
1, m, i, j, col));
}
}
printf(
"%.9f\n", ans *
4.0 / (n * (n +
1) * m * (m +
1)));
}
return 0;
}
