针对2011 ACM/ICPC 成都赛区11月6日现场赛，本日志汇总网上ACMer们发布的解题报告，方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告，和大家分享知识的各位神牛。
A Alice and Bob (SPOJ 9934, HDU 4111)
http://blog.csdn.net/ahero_happy/article/details/6955595
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)
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;
}
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)
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;
}
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
You can follow any responses to this entry through the RSS 2.0 You can leave a response, or trackback.
成都现场赛E 2-sat http://blog.sina.com.cn/s/blog_68629c7701010c6h.html