程序代码：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, j, k, p, q, r; // for循环使用
int n, m, c;
int t;
int s; // 求和
int cnt; // 子矩阵个数
int *a, *b, *x, **f; // 元素的个数有30000个, 所以都用动态分配内存
scanf("%d", &t);
while (t-- > 0) {
cnt = 0;
scanf("%d%d%d", &n, &m, &c);
a = (int *)malloc(n*sizeof(int));
b = (int *)malloc(m*sizeof(int));
x = (int *)malloc(m*sizeof(int));
f = (int **)malloc(n*sizeof(int *));
if (a == NULL || b == NULL || x == NULL || f == NULL)
exit(1);
for (i = 0; i < n; i++) {
f[i] = (int *)malloc(m*sizeof(int));
if (f[i] == NULL)
exit(1);
}
// 三个数组的值
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < m; i++)
scanf("%d", &b[i]);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
f[i][j] = a[i] * b[j];
for (r = 0; r < n; r++) {
for (i = 0; i < m; i++)
x[i] = 0;
for (i = r; i < n; i++) {
for (j = 0, k = 0; j < m; j++)
x[k++] += f[i][j];
for (p = 0; p < m; p++) {
s = x[p];
if (s%c == 0)
cnt++;
for (q = p + 1; q < m; q++) {
s += x[q];
if (s%c == 0)
cnt++;
}
}
}
}
printf("%d\n", cnt);
}
free(a);
free(b);
free(x);
for (i = 0; i < m; i++)
free(f[i]);
free(f);
return 0;
}
思路就是: 和冒泡排序的思路是一样的, 只是把排序变成求和.
把行和列分开考虑.
分别对行和列进行求和,
例如第一个:
1. 对第一行求和, 保存到x数组
2.对行求和, 结果与c求模
3.对第一行和第二行求和, 保存到x数组.
4. 重复2.
5. 对前三行求和..直到最后一行.
6. 最后一行之后, x数组重新初始化为0, 再从第二行开始. (冒泡排序的算法)
我感觉说得不是很清楚, 样例测试OK,
可以讨论....
[
本帖最后由 pangshch 于 2014-1-23 12:35 编辑 ]
2014-01-23 09:04
