poj-3349

#include <stdio.h>  #include <stdlib.h>  #include <string.h>  const int MAX_LENGTH = 100000;  struct snowFlakeInfo{      int armLength[6];      char used;      int hashValue;  };  typedef struct snowFlakeInfo snowFlakeInfo;  const int ARM_NUM = 6;  const int BIG_PRIME = 1000003;  snowFlakeInfo hashArray[1000010];  unsigned int hash(int * input) {      unsigned long long powSum = 0;      int i;      for (i = 0; i < ARM_NUM; i++) {          if (input[i]) {              powSum += input[i]*input[i];          }      }      return powSum % BIG_PRIME;  }  int comp(const void *a,const void *b)  {      return *(int*)a - *(int*)b;  }  char equal(int * sf1, int * sf2) {      int i;      qsort(sf1, ARM_NUM, sizeof(int), comp);      qsort(sf2, ARM_NUM, sizeof(int), comp);      for (i = 0; i < ARM_NUM; i++) {          if (sf1[i] != sf2[i]) {              return 0;          }      }      return 1;  }  const int sfSize = 24;  char fill(int * input) {      unsigned int hashValue = hash(input);      unsigned int insertPos = hashValue;      while(1) {          if (!hashArray[insertPos].used) {              // memcpy(&(hashArray[insertPos].armLength), input, sfSize);              int i = 0;              for (; i< ARM_NUM; i++) {                  hashArray[insertPos].armLength[i] = input[i];              }              hashArray[insertPos].used = 1;              hashArray[insertPos].hashValue = hashValue;              return 0;          } else {              if (hashArray[insertPos].hashValue == hashValue) {                  if (equal(input, hashArray[insertPos].armLength)) {                      return 1;                  }              }              insertPos++;              if (insertPos >= BIG_PRIME+1) {                  insertPos = 0;              }          }      }  }  char check(int * input) {      return fill(input);  }  int main() {      int num;      // while(scanf("%d", &num) > 0) {          int i = 0;          char hasSame = 0;          scanf("%d", &num);          memset(hashArray, 0, sizeof(hashArray));          for (; i < num; i++) {              int tmp[6] = {0};              int j = 0;              for (; j <= 5; j++) {                  scanf("%d", tmp+j);              }              if (!hasSame && check(tmp)) {                 // printf("%d\n", hash(tmp));                  hasSame = 1;              }          }          if (hasSame) {              printf("Twin snowflakes found.\n");          } else {              printf("No two snowflakes are alike.");          }                // } }

C 31484K　2438MS

第一次干hash， 以前用STL的hashmap， 这一次，我亲自卷了一把， 感觉不一样。

多谢discuss有好心人列举了hash的方法：

1. 直接相加, 把(总和%大质数)作为key.2. 平方和相加， 把(总和%大质数)作为key.3. 从小到大的顺序， 对v[i]<<(i*3)依次异或， 然后作为key模一个大质量数.(by hust07p434. 六个数中非零数的积累乘上一个大质数，然后模一个100w上下的数。最好用随机数据测量110w左右。随机数据量为10w时，hash值相同的情况只有6k以上，几乎可以忽略不计。(by killertom)5. key依次将每个数异或收入的数量作为key. (by archerstarlee)6. (a[0] + a[2] + a[4])&(a[1] + a[3] + a[5]), 再模一个大质数. 中间的&也可以改成‘|’ 或者'^'.非常巧妙! 我用‘^’得到最快的719ms. (只适用于本题目的hash方法)其实最重要的是开放式寻址来解决hash冲突， 不要认为hash可以解决问题。最后，使用getchar和gets进行输入转换更快. G++比GCC快一点。欢迎您添加更快的Hash方法.

我在这里用的是第二个hash法，　注意平方和最好的long(我直接做long) long), 不然RE, 唉，一个小问题耽误了很长时间.

大质数我用的是1000003，　以下几种方法有时间也可以尝试.

处理hash冲突，　因为最熟悉的是拉链法，　相反，我想尝试一种开放式寻址方法，它不需要动态的应用空间，而且在遍历时，　在某些情况下，效率也很高.

步骤描述也很简单，就是在寻找snowflake的hash值后，　在之前打开的hash数组中找到相应的位置是否已经填满了东西，

如果填写，比较这里存储的hash值是否与当前值相同。如果是一样的话，那么真正比较arms的值(这个问题的arm值很棒，我先排序，然后比较顺序，　找不到更好的)。若hash不等或arm不等，　然后继续往后看，到最后再从0开始，直到找到一个没有填满的位置(一定能找到，　按照这个做法)， 假如找到了完全一样的，　可以认为same snowflake， 还需要注意的是，一般都是为了效率，　边输入边开始保存hash作出判断，有了same snowflake之后， 不用再hash了 和　比较了，　但还是要继续接收输入. 做一个标志位，最后输入全部处理，然后根据其值输出结果.