题解:给定一串字符串,按杨辉三角一次从上到下,从左到右摆放,每个字符最多出现3次。问那些字符构成了一个等边三角形。将其输出之,如没有输出loser。
题解:暴力根据杨辉三角的性质,将每个字符赋予一个坐标(根据数学公式,下面给出),然后从a到z判断是否有三点,有就判断是否等边。输出答案即可。
数学公式:
将第一个点设置成(10000,10000)
其后的点是没下降一层 y 要减去3,x减去根号3。这是根据等边三角形的性质,要使得这些坐标构成的杨辉三角满足等边三角形的性质。
然后对于y这一层的字符,从左到右,一次赋值坐标,赋值之后x加两倍根号3。
直到处理全部字符。
然后暴力求解。
代码:
//#include <iostream> #include <cstdio> //#include <cstring> //#include <algorithm> #include <cmath> //using namespace std; #define INF 0x7ffffff #define MAXN 110 #define eps 1e-7 #define ghs 1.7320508075 struct line{ int num; double x[3],y[3]; }p[27]; bool judge(line & q){ double ans = (q.x[0] - q.x[1]) * (q.x[0] - q.x[1]) + (q.y[0] - q.y[1]) * (q.y[0] - q.y[1]); for(int i = 1; i < 3; i++){ if(fabs(ans - ((q.x[i] - q.x[(i+1)%3]) * (q.x[i] - q.x[(i+1)%3]) + (q.y[i] - q.y[(i+1)%3]) * (q.y[i] - q.y[(i+1)%3]))) > eps)return 0; } return 1; } int main(){ int n,i,j; double t, a, b; char c; while(scanf("%d",&n),n){ for(i = 0; i < 27; i++){ p[i].num = 0; } a = 10000.0; b = 10000.0; getchar(); for(i = 1; i <= n; i++){ t = a ; for(j = 1; j <= i; j++){ c = getchar(); p[c - 'a'].x[p[c-'a'].num] = t; p[c - 'a'].y[p[c-'a'].num] = b; p[c - 'a'].num ++; t = t + 2*ghs; } a = a - ghs; b = b - 3.0; } int flag = 0; for(i = 0; i < 26; i++){ if(p[i].num != 3)continue; if(judge(p[i])){printf("%c",'a'+i);flag = 1;} } if(!flag){ printf("LOOOOOOOOSER!"); } putchar('\n'); } return 0; }