Codeforces Testing Round 1 B. Right Triangles 题解 组合数学

Right Triangles

题目描述

You are given a $n\times m$ field consisting only of periods (‘.’) and asterisks (‘*’). Your task is to count all right triangles with two sides parallel to the square sides, whose vertices are in the centers of ‘*’-cells. A right triangle is a triangle in which one angle is a right angle (that is, a 90 degree angle).

输入格式

The first line contains two positive integer numbers $n$ and $m$ ( $1<=n,m<=1000$ ). The following $n$ lines consist of $m$ characters each, describing the field. Only ‘.’ and ‘*’ are allowed.

输出格式

Output a single number — total number of square triangles in the field. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

样例 #1

样例输入 #1

2 2
**
*.

样例输出 #1

1

样例 #2

样例输入 #2

3 4
*..*
.**.
*.**

样例输出 #2

9

原题

Codeforces——传送门
洛谷——传送门

思路

题目要求是求图中三个顶点均为 ${}^{\prime }{\ast }^{\prime }$ 字符的直角三角形个数。我们发现，直角三角形有两条直角边和一个拐点，而两条直角边和一个拐点唯一确定了一个直角三角形。所以如果我们知道了以任意一点为拐点的行直角边个数和列直角边个数，便可以确定以该点为拐点的直角三角形个数，从而计算出答案。那么思路便是先存储每行的 ${}^{\prime }{\ast }^{\prime }$ 点个数和每列的 ${}^{\prime }{\ast }^{\prime }$ 点个数，再遍历图，找到所有能构成直角三角形的点，接着以其为拐点，计算行直角边个数与列直角边个数的组合数并统计进 $ans$ 中即可。

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;int main()
{ios::sync_with_stdio(0);cin.tie(0);int n, m;cin >> n >> m;vector<vector<char>> g(n, vector<char>(m)); // 存图vector<int> hor(n, 0), ver(m, 0);           // 统计每行的'*'点数和每列的'*'点数for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> g[i][j];if (g[i][j] == '*'){hor[i]++;ver[j]++;}}}i64 ans = 0; // 直角三角形个数// 遍历图，找到所有能构成直角三角形的点for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (g[i][j] == '*') // 让其成为拐点，则其与该行的其他'*'构成一条直角边，与该列的其他'*'构成另一条直角边{ans += (hor[i] - 1) * (ver[j] - 1); // 行上直角边与列上直角边的组合个数即为以该点为拐点的直角三角形个数}}}cout << ans << '\n';return 0;
}