HLG 1963 Diary （哈希 + set或map）

链接： http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1963
Description：

SunShine喜欢写日记，她把她的日记用TXT文件都保存在电脑里。每月一号和十六号，她都会新建一个TXT文件，然后接下来半个月，她都会在这个日记本里写。（为了方便，我们假设每个月都是30天）。今天是元旦，SunShine又像往常一样打开电脑，可是当她打开写日记的文件夹之后，她发现她的日记文件名称被改成了“ShineCheng-is-a-cool-boy(#).txt”(#表示数字)。原来昨天ShineCheng在SunShine的电脑上捣乱了。SunShine仔细一看，发现ShineCheng留下了个小程序。一运行，小程序说：“我要考考你的记忆力，我会给你看几篇日记，你需要回答这是不是你写的。如果你都答对了，我就帮你恢复原来的文件名。”
为了简化问题，也为了保护SunShine的隐私，每天的日记简化成 天气 + 心情。天气有三种：晴天（S)、阴天（C）、雨天（R）。心情也有三种：开心（H)、一般(N)、伤心（B)。每行显示一个日记文件的内容，如果当天没有写日记，则显示为OO。例如某个日记文件的内容如：“SHCNCHRBCBRBRHSHCNRBSNCNRHOOSH”。小程序的提问也被简化成如上形式。
Input：

第一行一个数 T，表示一共有T组测试数据。
对于每组测试数据，第一行一个整数 n 表示有n个日记文件。
接下来有n行，每行一个日记文件。
再接下来有一个整数 q ，表示有q组询问。
接下来有q行，每行一个日记文件。
每组数据之后会有一个空行。
(0 < n < 106,0 < q < 1000)
Output：

对于每组询问，如果存在，输出"YES"，否则，输出"NO"（不包括引号）。
Sample Input：

2
2
SHCNCHRBCBRBRHSHCNRBSNCNRHOOSH
SHCNRBSNCNRHOOSHSHCNCHRBCBRBRH
2
SHCNRBSNCNRHOOSHSHCNCHRBCBRBRH
SHCNRBSNCNRHOOSHSHCNCHRBCBOORH

2
SHCNCHRBCBRBRHSHCNRBSNCNRHOOSH
SHCNRBSNCNRHOOSHSHCNCHRBCBRBRH
2
SHCNRBSNCNRHOOSHSHCNCHRBCBRBRH
SHCNRBSNCNRHOOSHSHCNCHRBCBOORH
Sample Output：

YES
NO
YES
NO

解析：

这道题用传统的set、map来做的话，挺耗内存，也挺耗时，这道题就是卡时间和卡内存，时间的话用set或map容器检索搞定，内存的话刚刚都说了用传统的任何方法都会超内存，所以不可能把所有的字符串都存储到容器里，只能通过一种转换，把字符串转换成数字进行存储，这样，内存就会大大降低；

这个代码肯定超时：

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
using namespace std;

int main()
{
    map <string, int> mp;
    string s;
    char str[35];
    int n, m, t;
    scanf("%d", &t);

    while(t--) {
        scanf("%d", &n);
        getchar();
        for(int i=0; i<n; i++) {
            scanf("%s", str);
            s = str;
            mp[s] = i;
        }
        scanf("%d", &m);
        char ss[35];
        map <string, int> ::iterator it;
        for(int i=0; i<m; i++) {
            scanf("%s", ss);
            s = ss;
            it = mp.find(s);
            if(it != mp.end()) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

#define ULL unsigned long long
#define LL long long
const LL MOD = 1e9 + 7;

using namespace std;

int t[30];
char s[105];
set<ULL> ds;

int main(){
    int cas, n, q;
    scanf("%d", &cas);

    while (cas--) {
        scanf("%d", &n);
        ds.clear();
        while (n--) {
            scanf("%s", s);
            ULL me = 0;
            for (int i=0; s[i]; i+=2) {
                if (s[i]==‘S‘) {
                    if (s[i+1]==‘H‘) t[i/2]=1;
                    else if (s[i+1]==‘N‘) t[i/2]=2;
                    else if (s[i+1]==‘B‘) t[i/2]=3;
                } else if (s[i]==‘C‘) {
                    if (s[i+1]==‘H‘) t[i/2]=4;
                    else if (s[i+1]==‘N‘) t[i/2]=5;
                    else if (s[i+1]==‘B‘) t[i/2]=6;
                } else if (s[i]==‘R‘) {
                    if (s[i+1]==‘H‘) t[i/2]=7;
                    else if (s[i+1]==‘N‘) t[i/2]=8;
                    else if (s[i+1]==‘B‘) t[i/2]=9;
                } else if (s[i]==‘O‘) t[i/2]=10;
                me = me * MOD + t[i / 2];
            }
            ds.insert(me);
        }
        scanf("%d", &q);
        while (q--) {
            scanf("%s", s);
            ULL me = 0;
            for (int i=0; s[i]; i+=2) {
                if (s[i]==‘S‘) {
                    if (s[i+1]==‘H‘) t[i/2]=1;
                    else if (s[i+1]==‘N‘) t[i/2]=2;
                    else if (s[i+1]==‘B‘) t[i/2]=3;
                } else if (s[i]==‘C‘) {
                    if (s[i+1]==‘H‘) t[i/2]=4;
                    else if (s[i+1]==‘N‘) t[i/2]=5;
                    else if (s[i+1]==‘B‘) t[i/2]=6;
                } else if (s[i]==‘R‘) {
                    if (s[i+1]==‘H‘) t[i/2]=7;
                    else if (s[i+1]==‘N‘) t[i/2]=8;
                    else if (s[i+1]==‘B‘) t[i/2]=9;
                } else if (s[i]==‘O‘) t[i/2]=10;
                me = me * MOD + t[i / 2];
            }
            if (ds.find(me) != ds.end()) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0；
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <cstdlib>
#include <algorithm>
#define MAXN 10005
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

typedef long long LL;

int num[256], cas, n;

LL encode(char *s) {
    LL ret = 0;
    for (int i = 0; i < 30; i++) {
        ret = ret * 3 + num[s[i]];
    }
    return ret;
}

int main() 
{
    num[‘S‘] = num[‘H‘] = 0;
    num[‘C‘] = num[‘N‘] = 1;
    num[‘R‘] = num[‘B‘] = 2;
    scanf("%d", &cas);

    while (cas--) {
        scanf("%d", &n);
        map <LL, bool> ma;
        char s[60];
        
        for(int i=0; i<n; i++) {
            scanf("%s", s);
            LL k = encode(s);
            ma[k] = true;
        }
        int q;
        scanf("%d", &q);

        while (q--) {
            scanf("%s", s);
            LL k = encode(s);
            puts( ma[k] ? "YES" : "NO");
        }
    }
    return 0;
}

HLG 1963 Diary （哈希 + set或map）,布布扣,bubuko.com

HLG 1963 Diary （哈希 + set或map）

原文：http://blog.csdn.net/keshacookie/article/details/25644165