当前位置: 首页 > 图灵资讯 > 技术篇> poj-3349

poj-3349

来源:图灵教育
时间:2023-05-24 09:26:53

#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了 和 比较了, 但还是要继续接收输入. 做一个标志位,最后输入全部处理,然后根据其值输出结果.

上一篇:

poj-2260

下一篇:

poj-2151