• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            no_rain

            hdoj1496(hash)

            這道題在a,b,c,d未知的情況下,是有200萬(wàn)的可能的結(jié)果,但是當(dāng)a,b,c,d給定則變成2萬(wàn)了,當(dāng)然這2萬(wàn)是不連續(xù)的,那么為了節(jié)省空間,可以用線性探測(cè),數(shù)組要開(kāi)的比2萬(wàn)大。
            無(wú)線性探測(cè)代碼
             1 #include<cstdio>
             2 #include<cstring>
             3 int hash[2000001] ;
             4 int hash_fun(int num){
             5   return num + 1000000;
             6 }
             7 int main(){
             8   int a,b,c,d;
             9   int sq[101={0};
            10   for(int i = 1; i <= 100; i++)
            11     sq[i] = i*i;
            12   while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
            13     if((a<0 && b<0 && c<0 && d<0|| 
            14        (a>0 && b>0 && c>0 && d>0) ){
            15       printf("0\n");
            16       continue;
            17     }
            18     memset(hash,0,sizeof(hash));
            19     for(int i = 1; i <= 100; i++)
            20       for(int j = 1; j <= 100; j++)
            21     hash[hash_fun(-sq[i]*- sq[j]*b)]++;
            22     int ans = 0;
            23     for(int i = 1; i <= 100; i++)
            24       for(int j = 1; j <= 100; j++)
            25     ans += hash[hash_fun(sq[i]*+ sq[j]*d)];
            26     printf("%d\n",ans*16);
            27   }
            28 }
            29       
            線性探測(cè):h(k)%S被占用,則用(h(k)+i)%S,直到找到?jīng)]有被占用的,因?yàn)槭褂镁€性探測(cè)就使h(k)存在不確定性,故在h(k)處必須保存k的值,即該數(shù)組是一結(jié)構(gòu)體的數(shù)組。
            先說(shuō)一下一段錯(cuò)誤的代碼
             1 #include<cstdio>
             2 #include<cstring>
             3 const int maxn = 21000;
             4 struct hashn{
             5   int k;
             6   int c;
             7 };
             8 hashn hash[100000] ;
             9 int hash_fun(int num){
            10   int t = num % maxn;
            11   if(t < 0)t += maxn;
            12   while(hash[t].k != 0 ){
            13     if(hash[t].k == num)return t;
            14     t = (t+1)%maxn;
            15     if(t<0) t+= maxn;
            16   }
            17   hash[t].k = num;
            18   return t;
            19 }
            20 int hash_fun2(int num){
            21   int t = num % maxn;
            22   if(t < 0)t += maxn;
            23   while(hash[t].k != 0 ){
            24     if(hash[t].k == num)return t;
            25     t = (t+1)%maxn;
            26     if(t<0) t+ maxn;
            27   }
            28   return t;
            29 }
            30 int main(){
            31   int a,b,c,d;
            32   int sq[101={0};
            33   for(int i = 1; i <= 100; i++)
            34     sq[i] = i*i;
            35   while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
            36     if((a<0 && b<0 && c<0 && d<0|| 
            37        (a>0 && b>0 && c>0 && d>0) ){
            38       printf("0\n");
            39       continue;
            40     }
            41     for(int i = 1; i <= 100000;i++)
            42       hash[i].c = hash[i].k = 0;
            43     for(int i = 1; i <= 100; i++)
            44       for(int j = 1; j <= 100; j++)
            45     hash[hash_fun(-sq[i]*- sq[j]*b)].c++;
            46     int ans = 0;
            47     for(int i = 1; i <= 100; i++)
            48       for(int j = 1; j <= 100; j++){
            49     int temp = hash_fun(sq[i]*+ sq[j]*d);
            50     ans += hash[temp].c;
            51       }
            52     printf("%d\n",ans*16);
            53   }
            54 }
            這段代碼有一個(gè)比較明顯的錯(cuò)誤,還有一個(gè)不明顯但是很容易錯(cuò)的地方。
            maxn定為21000過(guò)小了,即使數(shù)組足夠大,但是這也只用到了21000。
            另一個(gè)就是:初始化hash表的時(shí)候的值在所有可能的取值中出現(xiàn)了!(k初始化為0)
            改正后的代碼:
             1 #include<cstdio>
             2 #include<cstring>
             3 const int maxn = 51000;
             4 struct hashn{
             5   int k;
             6   int c;
             7 };
             8 hashn hash[100000] ;
             9 int hash_fun(int num){
            10   int t = num % maxn;
            11   if(t < 0)t += maxn;
            12   while(hash[t].k != -1){
            13     if(hash[t].k == num)return t;
            14     t = (t+1)%maxn;
            15   }
            16   hash[t].k = num;
            17   return t;
            18 }
            19 int main(){
            20   int a,b,c,d;
            21   int sq[101={0};
            22   for(int i = 1; i <= 100; i++)
            23     sq[i] = i*i;
            24   while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
            25     if((a<0 && b<0 && c<0 && d<0|| 
            26        (a>0 && b>0 && c>0 && d>0) ){
            27       printf("0\n");
            28       continue;
            29     }
            30     for(int i = 0; i <= 100000;i++){
            31       hash[i].c = 0;
            32       hash[i].k = -1;
            33     }
            34     for(int i = 1; i <= 100; i++)
            35       for(int j = 1; j <= 100; j++)
            36     hash[hash_fun(-sq[i]*- sq[j]*b)].c++;
            37     int ans = 0;
            38     for(int i = 1; i <= 100; i++)
            39       for(int j = 1; j <= 100; j++){
            40     int temp = hash_fun(sq[i]*+ sq[j]*d);
            41     ans += hash[temp].c;
            42       }
            43     printf("%d\n",ans*16);
            44   }
            45 }

            posted on 2011-11-16 18:10 is-programmer 閱讀(162) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法與數(shù)據(jù)結(jié)構(gòu)


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            導(dǎo)航

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計(jì)

            常用鏈接

            留言簿

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            99久久精品国产高清一区二区| 久久精品99无色码中文字幕| 久久99久久99精品免视看动漫| 热久久最新网站获取| 伊人久久大香线蕉综合Av| 久久ZYZ资源站无码中文动漫 | 久久久久亚洲av无码专区| 精品国产乱码久久久久久1区2区| 久久国产精品-久久精品| 久久99九九国产免费看小说| 国产精品美女久久久久久2018| 国产无套内射久久久国产| 伊人久久大香线蕉亚洲五月天| 伊人久久免费视频| 蜜臀av性久久久久蜜臀aⅴ麻豆| 国产精品美女久久久久av爽| 一本久久a久久精品亚洲| 国产福利电影一区二区三区久久久久成人精品综合| 国内精品欧美久久精品| 久久久久久无码Av成人影院| 91麻豆国产精品91久久久| 久久人人爽人人爽AV片| 夜夜亚洲天天久久| 人妻久久久一区二区三区| 久久免费看黄a级毛片| 久久亚洲国产精品123区| 久久99国产精品久久| 久久久亚洲欧洲日产国码aⅴ| 久久久受www免费人成| 成人精品一区二区久久久| 精品精品国产自在久久高清 | 久久亚洲国产中v天仙www | 久久久久一本毛久久久| 久久精品国产亚洲沈樵| 99久久精品午夜一区二区| 性高湖久久久久久久久| 欧美激情一区二区久久久| 久久久久亚洲精品日久生情| 亚洲一级Av无码毛片久久精品| 久久精品中文字幕一区| 亚洲精品乱码久久久久久不卡|