HDU6052 To my boyfriend

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6052

题目意思

给比个矩阵，矩阵中每个格子都有一个数字，同一数字代表同一种颜色，问你所有子矩阵种颜色个数总和。

解题思路

对于每个子矩阵含多多少颜色不好判断，所有判断没个颜色占子矩阵个数。而同种颜色判断从上到下，从左到右。没判断完一个位子上所占矩阵个数，就标记，防止下面同种颜色重复计算。

代码部分

#include<bits/stdc++.h> using namespace std; typedef long long LL; LL w[105][105];//保存原理图 int vis[105],m,n;//vis[j] = i 表示将第j列用i颜色标记 vector<int> y[105];//y[i]用来表示第i行有哪些列被标记过 vector<pair<int,int> > C[10005];//用来保存所有颜色出现的坐标 LL calc(int col) { memset(vis,0,sizeof(vis)); LL sum = 0; for(auto now:C[col]) { int ni = now.first,nj = now.second;//保存当前颜色的坐标 for(int i = 1; i <= m; i++)//对于每次找那些坐标被标记过之间都应该将此数组清零，防止以前数据对这次查找有影响 y[i].clear(); for(int i=1; i<=m; i++) if(vis[i]) y[vis[i]].push_back(i); int yl = 1,yr = m,flag = 0; for(int i = ni; i>=1; i--) { //枚举所有可能的上边界 vector<int>::iterator it; for(it = y[i].begin(); it!=y[i].end(); it++) { //如果第i行有被标记的，找出被标记的列数，并更新左右区间 int yy = *it; if(yy<nj) yl = max(yl,yy+1); else if(yy > nj) yr = min(yr,yy-1); else { //如果这个点的正上方有与它颜色相同的点结束循环 flag = 1; break; } } if(flag) break; sum += (n-ni+1)*(nj-yl+1)*(yr-nj+1);//计算已ii上上边界的方案数， } vis[nj] = ni;//将第nj列标记为ni方边利用y数组更新边界 } return sum; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); for(int i=0; i<=n*m; i++) C[i].clear(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { scanf("%lld",&w[i][j]); C[w[i][j]].push_back(make_pair(i,j));//记录每种颜色的坐标 } LL sum = 0;//记录不同颜色子矩阵的个数 for(int i=0; i<=n*m; i++) if(!C[i].empty()) { sort(C[i].begin(),C[i].end());//将每种颜色按坐标先行优先再列优先排序 sum += calc(i); } LL num = n*(n+1)*m*(m+1)/4;//子矩阵的个数 double ans = (sum*1.0)/num; printf("%.9lf\n",ans); } return 0; }