针对2011 ACM/ICPC 上海赛区9月10日网络赛，本日志汇总网上ACMer们发布的解题报告，方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告，和大家分享知识的各位神牛。
A 24 Puzzle (HDU 4021)
http://zhyu.me/acm/hdu-4021.html
http://www.cppblog.com/wiza/archive/2011/09/10/155534.html
B Bombing (HDU 4022)
http://blog.csdn.net/iaccepted/article/details/6766209
http://www.blogjava.net/sweetsc/archive/2011/09/10/358426.html
http://www.cppblog.com/aswmtjdsj/archive/2011/09/10/155518.aspx
C Game (HDU 4023)
http://www.cnblogs.com/staginner/archive/2011/09/10/2173317.html
http://blog.csdn.net/jxy859/article/details/6766427
D Dwarven Sniper’s hunting (HDU 4024)
http://www.cppblog.com/aswmtjdsj/archive/2011/09/10/155528.html
http://acm.nbu.edu.cn/SwordHoly/?p=260
E Equation of XOR (HDU 4025)
http://blog.csdn.net/moorage/article/details/6767057
F Unlock the Cell Phone (HDU 4026)
http://hi.baidu.com/nyroro/blog/item/2972d1f5a25ae175dcc47472.html
http://blog.csdn.net/xymscau/article/details/6766700 （感谢xym提供）
G Can you answer these queries? (HDU 4027)
http://www.blogjava.net/sweetsc/archive/2011/09/10/358427.html
http://blog.csdn.net/ggggiqnypgjg/article/details/6766203
H The time of a day (HDU 4028)
http://www.shuizilong.com/house/archives/3196
http://www.cnblogs.com/Fatedayt/archive/2011/09/10/2173352.html （感谢zxy提供）
I Distinct Sub-matrix (HDU 4029)
ftiasch大神提供的解题思路和相应代码如下：
枚举长度width。然后令h[i][j] = Hash(a[i][j], a[i][j + 1], a[i][j + 2], …, a[i][j + width – 1])。按列构造一个新串h[1][1], h[2][1], …, h[n][1], #1, h[1][2], h[2][2], …, h[n][2], #2, …, h[1][m], h[2][m], …, h[n][m] #m。其中#1, #2, …, #m是分隔符。然后求这个新串有多少个不同的子串。
一个字符串的不同子串数量，实际上就是len * (len + 1) / 2减去后缀排序后相邻两个后缀LCP的长度。证明显然。
整个复杂度是O(N^3 log N)。
本题参考代码，点击可展开。
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 222;
const int M = N * N;
const int MOD = 1000000007;
const int BASE = 117;
typedef pair<int, unsigned long long> Hash;
int n, m, strCnt;
char mat[N][N];
Hash hash[N][N], str[M];
int ord[M], arr[M], tmpArr[M], rnk[M], rnk1[M], rnk2[M], cnt[M];
int cmp(int i, int j){
return str[i] < str[j];
}
int main(){
int testCnt;
scanf("%d", &testCnt);
for(int t = 1; t <= testCnt; ++ t){
scanf("%d%d", &n, &m);
char space[N];
fgets(space, N, stdin);
for(int i = 0; i < n; ++ i){
fgets(mat[i], N, stdin);
}
long long res = 0;
for(int width = 1; width <= m; ++ width){
int tmpTime1 = 1;
unsigned long long tmpTime2 = 1;
for(int i = 1; i < width; ++ i){
tmpTime1 = ((long long)tmpTime1 * BASE) % MOD;
tmpTime2 = tmpTime2 * BASE;
}
for(int i = 0; i < n; ++ i){
int tmpHash1 = 0;
unsigned long long tmpHash2 = 0;
for(int j = m - 1; j > -1; -- j){
tmpHash1 = ((long long)tmpHash1 * BASE + mat[i][j]) % MOD;
tmpHash2 = tmpHash2 * BASE + mat[i][j];
if(j <= m - width){
hash[i][j] = make_pair(tmpHash1, tmpHash2);
tmpHash1 = (tmpHash1 - (long long)tmpTime1 * mat[i][j + width - 1]) % MOD;
if(tmpHash1 < 0){
tmpHash1 += MOD;
}
tmpHash2 = tmpHash2 - tmpTime2 * mat[i][j + width - 1];
}
}
}
strCnt = 0;
for(int j = 0; j <= m - width; ++ j){
for(int i = 0; i < n; ++ i){
str[++ strCnt] = hash[i][j];
}
str[++ strCnt] = make_pair(- (j + 1), 0);
}
for(int i = 0; i < strCnt; ++ i){
ord[i] = i + 1;
}
sort(ord, ord + strCnt, cmp);
rnk[ord[0]] = 1;
for(int i = 1; i < strCnt; ++ i){
rnk[ord[i]] = rnk[ord[i - 1]] + (str[ord[i - 1]] != str[ord[i]]);
}
int len = 1;
while(len < strCnt){
for(int i = 1; i <= strCnt; ++ i){
rnk1[i] = rnk[i];
rnk2[i] = i + len <= strCnt? rnk[i + len]: 0;
}
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= strCnt; ++ i){
cnt[rnk2[i]] += 1;
}
for(int i = 1; i <= strCnt; ++ i){
cnt[i] += cnt[i - 1];
}
for(int i = 1; i <= strCnt; ++ i){
tmpArr[cnt[rnk2[i]] --] = i;
}
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= strCnt; ++ i){
cnt[rnk1[i]] += 1;
}
for(int i = 1; i <= strCnt; ++ i){
cnt[i] += cnt[i - 1];
}
for(int i = strCnt; i >= 1; -- i){
arr[cnt[rnk1[tmpArr[i]]] --] = tmpArr[i];
}
rnk[arr[1]] = 1;
for(int i = 2; i <= strCnt; ++ i){
rnk[arr[i]] = rnk[arr[i - 1]] + (rnk1[arr[i - 1]] != rnk1[arr[i]] or rnk2[arr[i - 1]] != rnk2[arr[i]]);
}
len <<= 1;
}
long long tmpRes = (1 + n) * n / 2 * (m - width + 1);
//printf("-- \n");
//for(int i = 1; i <= strCnt; ++ i){
// for(int j = arr[i]; j <= strCnt; ++ j){
// printf("%d ", str[j].first);
// }
// printf("\n");
//}
//printf("\n");
int lcp = 0;
for(int i = 1; i <= strCnt; ++ i){
if(rnk[i] > 1){
int j = arr[rnk[i] - 1];
while(i + lcp <= strCnt and j + lcp <= strCnt and str[i + lcp] == str[j + lcp]){
lcp += 1;
}
}
//printf("%d ", lcp);
tmpRes -= lcp;
if(lcp > 0){
lcp -= 1;
}
}
//printf("\n");
res += tmpRes;
}
printf("Case #%d: ", t);
cout << res << endl;
}
return 0;
}
J Tank (HDU 4030)
http://hi.baidu.com/%E5%B0%8F%E6%AD%A6rj/blog/item/e98bbd0ef47d9b316159f30d.html （感谢zxy提供）
You can follow any responses to this entry through the RSS 2.0 You can leave a response, or trackback.
10 tank
http://hi.baidu.com/%E5%B0%8F%E6%AD%A6rj/blog/item/e98bbd0ef47d9b316159f30d.html
3 game
http://www.cnblogs.com/staginner/archive/2011/09/10/2173317.html
1 24 puzzle
http://archive.cnblogs.com/a/2173365/
4 Dwarven Sniper’s hunting
http://www.cppblog.com/aswmtjdsj/archive/2011/09/10/155528.aspx
8 The time of a day
http://archive.cnblogs.com/a/2173352/
7 Can you answer these queries?
http://www.blogjava.net/sweetsc/archive/2011/09/10/358427.html
全都有
http://user.qzone.qq.com/122155302/blog/1315682296
sssstO 。。
06 Unlock the Cell Phone http://blog.csdn.net/xymscau/article/details/6766700
– – 1009就是枚举长度width。然后令h[i][j] = Hash(a[i][j], a[i][j + 1], a[i][j + 2], …, a[i][j + width – 1])。按列构造一个新串h[1][1], h[2][1], …, h[n][1], #1, h[1][2], h[2][2], …, h[n][2], #2, …, h[1][m], h[2][m], …, h[n][m] #m。其中#1, #2, …, #m是分隔符。然后求这个新串有多少个不同的子串。
一个字符串的不同子串数量，实际上就是len * (len + 1) / 2减去后缀排序后相邻两个后缀LCP的长度。证明显然。
整个复杂度是O(N^3 log N)。
膜拜那个hash过程
04 Dwarven Sniper’s hunting http://acm.nbu.edu.cn/SwordHoly/?p=260