Description
小花梨现在有一个n层三角形图(参考下图)，第 i 层有2i − 1个边长为1的等边三角形。
每个交点处存在一个字符，总共有n + 1层字符，第 i 层有 i 个字符。
小花梨用等边三角形三个顶点上的字符来表示这个三角形，两个等边三角形如果它们的三个
顶点字符相同(不区分顺序)则视为同一类等边三角形。小花梨想知道总共存在多少种不同类
别的等边三角形。
Input
第一行为正整数n，表示三角形层数(1 ≤ n ≤ 100)。
接下来n + 1行，第 i 行输入 i 个字符，表示第 i 层的字符。(字符只包含小写字母"a − z")
Output
输出一个整数表示存在多少种不同类别的三角形
Note
样例一：只存在顶点为(a,b,c)的三角形
样例二：存在顶点为(a,b,b) 、 (a,c,c) 、 (a,b,c)的3类不同的三角形
样例三：只存在顶点为(a,a,a)的三角形
分析
题目给出的范围比较小，为n<=100，直接找等边三角形就可以，那么怎么找呢？我的方法是这样的：先找正着的三角形，再找倒着的三角形。例如样例二，（a,b,b）就是正着的三角形，（b,b,a）就是倒着的三角形。在查找时要注意，可能有多个三角形拼凑出来的大三角形也满足条件。找到每个三角形以后，用map来记录相应的三个顶点的组合是否出现过，因为不区分顺序，所以每次都要排一下序。
代码
#include<iostream>#include<cstdio>#include<string.h>#include<algorithm>#include<map>#include<vector>using namespace std;int main(){int n,ans=0;char tu[105][105];scanf("%d",&n);for(int i=0;i<=n;i++){scanf("%s",tu[i]);}map<string,int> M;for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){int d=1;while(1){if(i+d<=n)//不能超过n层 {string t="";t+=tu[i][j];t+=tu[i+d][j];t+=tu[i+d][j+d];sort(t.begin(),t.end());if(M[t]==0){M[t]=1;ans++;}}elsebreak;d++;}}}for(int i=n;i>=0;i--){for(int j=0;j<=i;j++){int d=1;while(1){if(i-d>=0&&j-d>=0&&j<=i-d)//注意与查找正着的三角形判断条件不一样 {string t="";t+=tu[i][j];t+=tu[i-d][j];t+=tu[i-d][j-d];sort(t.begin(),t.end());if(M[t]==0){M[t]=1;ans++;}}elsebreak;d++;}}}cout<<ans<<endl;return 0;}
如果觉得《小花梨的三角形--美登杯》对你有帮助，请点赞、收藏，并留下你的观点哦！
