#include#include #define PRI 93961struct SF{ int e[6]; SF *next; SF(){ e[0] = -1; next = NULL; }};SF snow[PRI];bool exactsame(SF s1, SF s2){ for (int i = 0; i < 6; i++){ if (s1.e[i] != s2.e[i]) return false; } return true;}int mycmp(const void *a, const void *b){ return *(int *)a - *(int *)b;}int main(){ bool ok = false; int nos, key; SF *p, tmp; scanf("%d", &nos); for (int i = 0; i < nos; i++){ for (int j = 0; j < 6; j++) scanf("%d", &tmp.e[j]); if (!ok){ key = 0; qsort(tmp.e, 6, sizeof(tmp.e[0]), mycmp); for (int j = 0; j < 6; j++){ key += tmp.e[j]; key %= PRI; } if (snow[key].e[0] == -1) snow[key] = tmp; else if (exactsame(snow[key], tmp)) ok = true; else if (snow[key].next == NULL){ if (exactsame(snow[key], tmp)) ok = true; else{ SF *newsf = new SF; for (int k = 0; k < 6; k++) newsf->e[k] = tmp.e[k]; snow[key].next = newsf; } } else{ p = snow[key].next; if (exactsame(*p, tmp)) ok = true; while (p->next && !ok){ p = p->next; if (exactsame(*p, tmp)) ok = true; } if (!ok){ SF *newsf = new SF; for (int k = 0; k < 6; k++) newsf->e[k] = tmp.e[k]; p->next = newsf; } } } } if (ok) printf("Twin snowflakes found.\n"); else printf("No two snowflakes are alike.\n"); return 0;}
【开博第一篇(*^__^*) ……~】虽然是水题但是调了一下午TUT。坑点在神马clockwise,counterclockwise都是骗人的。。六条边correspond的匹配就好了~
嗯哼。来说思路,是每个雪花按arm从小到大用qsort排序好,然后用哈希开地址法比较,若比较时有相同则标记ok = true,否则将该雪花存入相应地址。关键码用的是加和取mod。判断部分写得稍微冗杂了些。><