题目链接
分类:combinatorics
1.题意概述 给你一个 n×m 的字符串矩阵(由.和*组成),问你有多少个与矩阵边平行的直角三角形? 2.解题思路 对于|_和_|形的三角形,我们只需要在底边_上方看有多少个*即可,所以公式就是 (x[i]−1)×(y[i]−1) ,对每一次累加求和即为答案。 3.AC代码 char g[N][N];int a[N], b[N];int main() { int n, m; scanf("%d%d", &n, &m); rep(i, 0, n) scanf("%s", g[i]); rep(i, 0, n) { rep(j, 0, m) { if (g[i][j] == '*') { a[i]++; b[j]++; } } } ll ans = 0; rep(i, 0, n) { rep(j, 0, m) { if (g[i][j] == '*') ans += (a[i] - 1) * (b[j] - 1); } } printf("%I64dn", ans); return 0;}