题目:戳这里
题意:给一个n*m的矩阵,里面由a~z及A~Z构成,问有多少个子矩阵满足任意一行或一列中都没有相同的字母。
解题思路:左上角和右下角两点可以确定一个矩阵。可以先预处理出来每个点作为一个矩阵的右下角,向左和向上的最长值。然后遍历每个点是右下角的情况,计算该点为右下角时,能构成多少个矩阵。计算方法为:
1.设右下角为(i,j),它向左的最长值为r[i][j],向上最长之为c[i][j],设左上角为(x,y)。
2.遍历j~j-r[i][j]+1,维护最小值minn[]。
3.根据minn[]数组和c[][]数组,找到符合条件的左上角,计入答案。
这三步操作的原因是,一个符合条件的左上角(x,y),要满足矩形底边上所有点的i-c[i][k]+1>=x,右边上所有点的j-r[k][j]+1>=y。
代码思路比较绕,写的时候得静下心。
附ac代码:
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include