针对2011 ACM/ICPC 成都赛区11月6日现场赛，本日志汇总网上ACMer们发布的解题报告，方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告，和大家分享知识的各位神牛。

题目链接SPOJ 9934-9944题
题目链接HDU

出题报告

A Alice and Bob (SPOJ 9934, HDU 4111)
http://blog.csdn.net/ahero_happy/article/details/6955595
http://blog.sina.com.cn/s/blog_91a062f50100uk8f.html

B Break the Chocolate (SPOJ 9935, HDU 4112)
http://blog.csdn.net/xieshimao/article/details/6950823
http://blog.sina.com.cn/s/blog_71fda4350100zbl3.html

C Construct the Great Wall (SPOJ 9936, HDU 4113)
http://boleyn.su.blog.163.com/blog/static/64514320111136441690/

D Disney Fastpass (SPOJ 9938, HDU 4114)
ftiasch提供代码，点击可展开

// 9938. Disney Fastpass
// Problem code: DISNEY
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;
const int K = 8;
const int INF = 1000000000;

int n, m, k, g[N][N], hasAttr[N], hasPass[N], slow[N], fast[N], dp[1 << K][1 << K][N], queue[N];
bool visit[N];

void checkMin (int &x, int a) {
    x = min(x, a);
}

int main () {
    int testCnt;
    scanf("%d", &testCnt);
    for (int t = 1; t <= testCnt; ++ t) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < n; ++ j) {
                g[i][j] = INF;
            }
        }
        for (int i = 0; i < m; ++ i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            a --;
            b --;
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        for (int i = 0; i < n; ++ i) {
            g[i][i] = INF;
        }
        memset(hasAttr, 0, sizeof(hasAttr));
        memset(hasPass, 0, sizeof(hasPass));
        for (int i = 0; i < k; ++ i) {
            int p, ni;
            scanf("%d%d%d%d", &p, slow + i, fast + i, &ni);
            hasAttr[p - 1] |= 1 << i;
            while (ni --) {
                int q;
                scanf("%d", &q);
                hasPass[q - 1] |= 1 << i;
            }
        }
        for (int attrMask = 0; attrMask < (1 << k); ++ attrMask) {
            for (int passMask = 0; passMask < (1 << k); ++ passMask) {
                if (!(attrMask & passMask)) {
                    for (int i = 0; i < n; ++ i) {
                        dp[attrMask][passMask][i] = INF;
                    }
                }
            }
        }
        dp[0][0][0] = 0;
        for (int attrMask = 0; attrMask < (1 << k); ++ attrMask) {
            for (int passMask = 0; passMask < (1 << k); ++ passMask) {             
                if (!(attrMask & passMask)) { 
                    int *dist = dp[attrMask][passMask],
                        head = 0,
                        tail = 0;
                    for (int i = 0; i < n; ++ i) {
                        visit[i] = true;
                        queue[tail ++] = i;
                    }
                    while (head != tail) {
                        int i = queue[head ++];                       
                        if (head == N) {
                            head = 0;
                        }
                        visit[i] = false;
                        for (int j = 0; j < n; ++ j) {
                            if (dist[i] + g[i][j] < dist[j]) {
                                dist[j] = dist[i] + g[i][j];
                                if (!visit[j]) {
                                    visit[j] = true;
                                    queue[tail ++] = j;
                                    if (tail == N) {
                                        tail = 0;
                                    }
                                }
                            }
                        }
                    }
                    for (int i = 0; i < n; ++ i) {
                        int tmp = dp[attrMask][passMask][i];
                        checkMin(dp[attrMask][(passMask | hasPass[i]) & ~(attrMask)][i], tmp);
                        for (int j = 0; j < k; ++ j) {
                            if (!((attrMask >> j) & 1) && ((hasAttr[i] >> j) & 1)) {
                                tmp += ((passMask >> j) & 1)? fast[j]: slow[j];
                            }
                        }
                        checkMin(dp[attrMask | hasAttr[i]][passMask & ~(attrMask | hasAttr[i])][i], tmp);
                    }
                }
            }
        }
        printf("Case #%d: %d\n", t, dp[(1 << k) - 1][0][0]);
    }
    return 0;
}

http://www.cppblog.com/hanfei19910905/archive/2012/04/24/172647.aspx

E Eliminate the Conflict (SPOJ 9939, HDU 4115)
http://www.ctzsm.tk/?p=293
http://www.cnblogs.com/ambition/archive/2011/11/09/Eliminate_the_Conflict.html
http://blog.csdn.net/wsniyufang/article/details/6955738
http://blog.sina.com.cn/s/blog_68629c7701010c6h.html

F Fruit Ninja (SPOJ 9940, HDU 4116)
http://www.cppblog.com/hanfei19910905/archive/2012/08/06/186457.html

G GRE Words (SPOJ 9941, HDU 4117)
ftiasch提供代码，点击可展开

// 9941. GRE Words
// Problem code: GRE
#include <ctime>
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 300000;

int n, w[N], len[N], begin[N], 
    trieCnt, fail[N], queue[N],
    firstEdge[N], nextEdge[N], 
    dfsCnt, pos[N], size[N],
    delta[N << 2], dp[N];
char str[N];
map <char, int> childs[N];

void dfs (int u) {
    pos[u] = dfsCnt ++;
    size[u] = 1;
    for (int iter = firstEdge[u]; iter != -1; iter = nextEdge[iter]) {
        dfs(iter);
        size[u] += size[iter];
    }
}

void updateMax (int &x, int a) {
    x = max(x, a);
}

void cover (int t, int l, int r, int a, int b, int v) {
    if (b < l or r < a) {
        return;
    }
    if (a <= l and r <= b) {
        updateMax(delta[t], v);
    } else {
        int m = (l + r) >> 1;
        cover(t + t, l, m, a, b, v);
        cover(t + t + 1, m + 1, r, a, b, v);
    }
}

int query (int t, int l, int r, int a) {
    if (a < l or r < a) {
        return 0;
    }    
    if (l == a and a == r) {
        return delta[t];
    }
    int m = (l + r) >> 1;
    return max(delta[t], 
            max(query(t + t, l, m, a), query(t + t + 1, m + 1, r, a)));
}

int main () { 
    int testCnt;
    scanf("%d", &testCnt);
    for (int t = 1; t <= testCnt; ++ t) {
        scanf("%d", &n);
        begin[0] = 0;
        for (int i = 0; i < n; ++ i) {
            scanf("%s", str + begin[i]);
            // w[i] = 1
            scanf("%d", w + i);
            len[i] = strlen(str + begin[i]);
            begin[i + 1] = begin[i] + len[i];
        }
        trieCnt = 1;
        for (int i = 0; i < n; ++ i) {
            int cur = 0;
            for (int j = begin[i]; j < begin[i] + len[i]; ++ j) {
                if (not childs[cur].count(str[j])) {
                    childs[trieCnt].clear();
                    childs[cur][str[j]] = trieCnt ++;
                }
                cur = childs[cur][str[j]];
            }
        }
        int head = 0, tail = 0;
        for (map <char, int> :: iterator iter = childs[0].begin(); 
                iter != childs[0].end(); ++ iter) {
            fail[iter->second] = 0;
            queue[tail ++] = iter->second;
        }
        while (head != tail) {
            for (map <char, int> :: iterator iter = childs[queue[head]].begin(); 
                    iter != childs[queue[head]].end(); ++ iter) {
                fail[iter->second] = 0;
                int tmp = queue[head];
                while (tmp != 0) {
                    tmp = fail[tmp];
                    if (childs[tmp].count(iter->first)) {
                        fail[iter->second] = childs[tmp][iter->first];
                        break;
                    }
                }
                queue[tail ++] = iter->second;
            }
            head += 1;
        }
        memset(firstEdge, -1, sizeof(firstEdge));
        for (int i = 1; i < trieCnt; ++ i) {
            nextEdge[i] = firstEdge[fail[i]];
            firstEdge[fail[i]] = i;
        }        
        dfsCnt = 0;
        dfs(0);        
        memset(delta, 0, sizeof(delta));
        int result = 0;
        for (int i = 0; i < n; ++ i) {
            dp[i] = 0;
            int cur = 0;
            for (int j = begin[i]; j < begin[i] + len[i]; ++ j) {
                cur = childs[cur][str[j]];
                updateMax(dp[i], 
                        query(1, 0, trieCnt - 1, pos[cur]));
            }
            dp[i] += w[i];
            cover(1, 0, trieCnt - 1, pos[cur], pos[cur] + size[cur] - 1, dp[i]);
            updateMax(result, dp[i]);
        }
        printf("Case #%d: %d\n", t, result);
        for (int i = 0; i < N; i++)
            childs[i].clear();
    }
    return 0;
}

http://www.cppblog.com/hanfei19910905/archive/2012/07/23/184715.aspx

H Holiday Accommodation (SPOJ 9942, HDU 4118)
http://hi.baidu.com/jiantaodongshe/blog/item/6a0dfefffece7c59d7887dcb.html
http://blog.csdn.net/lencle/article/details/6957702

I Isabella Message (SPOJ 9943, HDU 4119)
http://ideone.com/ClR1e
http://blog.sina.com.cn/s/blog_91a062f50100ujkz.html

J Ji-Tu Problem (SPOJ 9944, HDU 4120)
http://www.cnblogs.com/yaoz10051538/archive/2011/11/10/2244836.html