糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 3188 Cellphones 枚举+hash

思路:

这题是暴力枚举,哈哈。
枚举每一种可能的字母分配情况。
然后再对每个单词求出按键序列以后,对按键序列进行 hash,用普通的字串hash函数即可。
最后就可以统计具有唯一按键序列的单词个数了。

这种做法还是相当快的,代码跑到了450ms 。是第一哦!

#include <stdio.h>
#include 
<string.h>

#define MAX_D 1024
#define HASH_SIZE 65536

struct node {
    
struct node *next;
    
int val, cnt;
}
;

int B, L, D;
int map[256], ans[256], best;
char dict[MAX_D][16];
struct node nodes[MAX_D], *hash[HASH_SIZE];
int nodes_cnt;
int vis[HASH_SIZE], tm;

inline 
void calc()
{
    
int i, h, val, uni;
    
char *s;
    
struct node *t;

    tm
++;
    nodes_cnt 
= 0;
    
for (i = 0; i < D; i++{
        val 
= 0;
        
for (s = dict[i]; *s; s++
            val 
= val*31 + map[*s] + 'a';
        h 
= val & (HASH_SIZE - 1);
        
if (vis[h] != tm) {
            vis[h] 
= tm;
            hash[h] 
= NULL;
        }

        
for (t = hash[h]; t; t = t->next)
            
if (t->val == val)
                
break;
        
if (!t) {
            t 
= &nodes[nodes_cnt++];
            t
->val = val;
            t
->cnt = 0;
            t
->next = hash[h];
            hash[h] 
= t;
        }

        t
->cnt++;
    }


    uni 
= 0;
    
for (i = 0; i < nodes_cnt; i++)
        
if (nodes[i].cnt == 1)
            uni
++;

    
if (uni > best) {
        best 
= uni;
        memcpy(ans, map, 
sizeof(map));
    }

}


void dfs(int b, int l)
{
    
int i, cnt;

    cnt 
= L - l - (B - b) + 1;
    
for (i = 0; i < cnt; i++)
        map[l 
+ 'A' + i] = b;
    
    
if (b == B - 1{
        calc();
        
return ;
    }


    
for (i = cnt; i >= 1; i--)
        dfs(b 
+ 1, l + i);
}


int main()
{
    
int i;

    freopen(
"e:\\test\\in.txt""r", stdin);

    scanf(
"%d%d%d"&B, &L, &D);
    
for (i = 0; i < D; i++)
        scanf(
"%s", dict[i]);
    dfs(
00);
    printf(
"%d\n", best);
    
for (i = 'A'; i < 'A' + L; i++{
        
if (ans[i] != ans[i - 1])
            putchar(
'\n');
        putchar(i);
    }

    putchar(
'\n');

    
return 0;
}

posted on 2010-04-26 19:28 糯米 阅读(615) 评论(1)  编辑 收藏 引用 所属分类: POJ

评论

# re: POJ 3188 Cellphones 枚举+hash  回复  更多评论   

稍加优化即可刷到344Ms,我现在是第一了,呵呵。
2011-07-06 18:19 | fanhqme

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理