题库编号：hdu 4331~4339
好累的一个假期...今天中午没睡觉，下午比赛的时候还是很困的，不过不知道为什么没能睡着，所以回到宿舍写着写着这东西的时候就睡着了- -
八月的第一场组队赛~
今天的结果还是不错的，能做出3题，但是这还是远远不够的，因为做出的三题几乎所有校队的队伍都能做出来。赛后粗略看了一下题解，几题不会做的题涵盖的 数论，概率统计，树状数组，扩展KMP....... 好多东西要学啊！
今天三题都是我过的，小有成就感~
首先过的是1009，又是线段树！今天的线段树是要求出从某一点开始的最长相同子串的长度。刚开始的时候，因为以前没有解决过这样的问题，于是就当场和队友合作想解决这样的问题的线段树的一种更新方法。我当时首先想到的是每个结点标记该段内的串是否完全相同，这个的pushup是很容易就可以实现的。然后，就是query的时候是要如何统计。因为更新是单点更新，所以多个线段树的模板函数中，pushdown是不需要的，update也是很容易实现的。 好了，现在就是着重于query了。其实我们在每一种线段树的写法中，query都是要求进行一个区间的合并，然后在根的位置获得答案。现在我们记录了每段的覆盖情况，因此，在query合并区间时需要判断两段是否相连。这里有一个办法，就是用左儿子的末值(m)来减去k-1（或者当 k<=l 时的该段的长度）从而判断出左儿子相同的区间是否到左段的结尾，如果是就加上右儿子左边最长的相同区间的长度。
这样的方法是没问题的，可是数据卡优化了，超时了。不过多得队友的提醒，所以我添加了一个标记变量，来记录每个段中从左边开始最长的相同区间的长度。添加了记忆化以后，效率优化了不少，然后当然就过了~
代码如下：
View Code
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <vector> 5 #include <map> 6 #include <queue> 7 #include <list> 8 #include <set> 9 #include <cstring> 10 #include <string> 11 12 using namespace std; 13 14 #define INF 0x7fffffff; 15 #define max4(a, b, c, d) (max2(a, b) > max2(c, d) ? max2(a, b) : max2(c, d)) 16 #define min4(a, b, c, d) (min2(a, b) < min2(c, d) ? min2(a, b) : min2(c, d)) 17 #define feq(a, b) fabs((a) - (b)) < eps 18 #define flq(a, b) (feq(a, b) || (a) < (b)) 19 #define reset(a) memset(a, 0, sizeof(a)) 20 #define fileout freopen("test.out", "w", stdout) 21 #define filein freopen("test.in", "r", stdin) 22 //segment tree 23 #define lson l, m, rt << 1 24 #define rson m + 1, r, rt << 1 | 1 25 #define root 0, len - 1, 1 26 27 #define debug 0 28 29 const double eps = 1e-6; 30 const int maxn = 1000005; 31 32 int cov[maxn << 2], len[maxn << 2]; 33 char s[3][maxn]; 34 35 int max2(int a, int b){return a > b ? a : b;} 36 int min2(int a, int b){return a < b ? a : b;} 37 38 void up(int rt){ 39 if (cov[rt << 1]){ 40 len[rt] = len[rt << 1] + len[rt << 1 | 1]; 41 } 42 else { 43 len[rt] = len[rt << 1]; 44 } 45 cov[rt] = (cov[rt << 1] && cov[rt << 1 | 1]) ? 1 : 0; 46 } 47 48 void build(int l, int r, int rt){ 49 if (l == r){ 50 if (s[1][l] == s[2][l]){ 51 cov[rt] = 1; 52 len[rt] = 1; 53 } 54 else { 55 cov[rt] = 0; 56 len[rt] = 0; 57 } 58 return ; 59 } 60 int m = (l + r) >> 1; 61 62 build(lson); 63 build(rson); 64 65 up(rt); 66 } 67 68 void update(int k, int l, int r, int rt){ 69 if (l == r){ 70 if (s[1][l] == s[2][l]){ 71 cov[rt] = 1; 72 len[rt] = 1; 73 } 74 else { 75 cov[rt] = 0; 76 len[rt] = 0; 77 } 78 return ; 79 } 80 int m = (l + r) >> 1; 81 82 if (k <= m){ 83 update(k, lson); 84 } 85 if (m < k){ 86 update(k, rson); 87 } 88 up(rt); 89 } 90 91 int query(int k, int l, int r, int rt){ 92 if (k <= l){ 93 return len[rt]; 94 } 95 if (l == r){ 96 return len[rt]; 97 } 98 int m = (l + r) >> 1; 99 100 int tmp; 101 if (k <= m){ 102 tmp = query(k, lson); 103 #if debug 104 printf("rtl %d %d\n", rt, tmp); 105 #endif 106 int t = max2(k, l); 107 if (tmp == m - t + 1){ 108 tmp += query(k, rson); 109 #if debug 110 printf("rtr %d %d\n", rt, tmp); 111 #endif 112 } 113 } 114 else { 115 tmp = query(k, rson); 116 } 117 118 #if debug 119 printf("rt %d %d\n", rt, tmp); 120 #endif 121 return tmp; 122 } 123 124 void deal(){ 125 int m, op, a, b; 126 int len; 127 128 scanf("%s%s", s[1], s[2]); 129 len = min2(strlen(s[1]), strlen(s[2])); 130 build(root); 131 #if debug 132 for (int j = 0; j < 15; j++){ 133 printf("%d", cov[j]); 134 } 135 puts(""); 136 #endif 137 138 scanf("%d", &m); 139 while (m--){ 140 scanf("%d", &op); 141 if (op == 1){ 142 scanf("%d%d%s", &a, &b, s[0]); 143 s[a][b] = s[0][0]; 144 update(b, root); 145 } 146 else if (op == 2){ 147 scanf("%d", &a); 148 printf("%d\n", query(a, root)); 149 } 150 } 151 } 152 153 int main() 154 { 155 int T; 156 157 scanf("%d", &T); 158 for (int i = 1; i <= T; i++){ 159 printf("Case %d:\n", i); 160 deal(); 161 #if debug 162 for (int j = 0; j < 15; j++){ 163 printf("%d", cov[j]); 164 } 165 puts(""); 166 #endif 167 168 } 169 170 return 0; 171 }
然后就是1004，一个简单的hash。刚开始，队友在我debug线段树那题的时候尝试打trie树上去，但是我现在算了一下，用这个数据结构应该是会超时的，因为大数据可以达到10^15，也就是树的深度可能达到depth=16的状况。哈希平均常数接近1，这样都要用掉1984ms了，如果是要trie树，那恐怕是要超时了。 当时我很快就打出了hash的函数，做过hash经典题目的话都可以看出这题就是数据变大了的那道经典hash（题意大概是给出一堆数，找出4个和为零的数）。不过我一开始hash开小了，才勉强大于要储存的个数40000，所以tle了一次。然后，简单的增大数组就轻松通过了。 对于hash参数的设置还是不熟，以后还得多练！
代码如下：
View Code
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <vector> 5 #include <map> 6 #include <queue> 7 #include <list> 8 #include <set> 9 #include <cstring> 10 #include <string> 11 12 using namespace std; 13 14 #define INF 0x7fffffff; 15 #define max4(a, b, c, d) (max2(a, b) > max2(c, d) ? max2(a, b) : max2(c, d)) 16 #define min4(a, b, c, d) (min2(a, b) < min2(c, d) ? min2(a, b) : min2(c, d)) 17 #define feq(a, b) fabs((a) - (b)) < eps 18 #define flq(a, b) (feq(a, b) || (a) < (b)) 19 #define reset(a) memset(a, 0, sizeof(a)) 20 #define fileout freopen("test.out", "w", stdout) 21 #define filein freopen("test.in", "r", stdin) 22 //segment tree 23 #define lson l, m, rt << 1 24 #define rson m + 1, r, rt << 1 | 1 25 #define root 1, n, 1 26 27 #define debug 0 28 29 const double eps = 1e-6; 30 const int maxn = 100001; 31 32 int max2(int a, int b) 33 { 34 return a > b ? a : b; 35 } 36 37 int min2(int a, int b) 38 { 39 return a < b ? a : b; 40 } 41 const int size = 1000007; 42 __int64 hash[size]; 43 bool ex[size]; 44 45 __int64 loc(__int64 s){ 46 __int64 h = (s << 2) % size; 47 48 while (h < 0) h += size; 49 while (h >= size) h -= size; 50 while (ex[h] && hash[h] != s){ 51 h = (h + 1) % size; 52 } 53 54 return h; 55 } 56 57 void insert(__int64 s){ 58 __int64 pos = loc(s); 59 60 hash[pos] = s; 61 ex[pos] = true; 62 } 63 64 __int64 tmp[3][201]; 65 //__int64 sum[201 * 201]; 66 67 bool deal(){ 68 int n; 69 70 memset(ex, 0, sizeof(ex)); 71 scanf("%d", &n); 72 for (int i = 0; i < n; i++){ 73 scanf("%I64d", &tmp[0][i]); 74 } 75 for (int i = 0; i < n; i++){ 76 scanf("%I64d", &tmp[1][0]); 77 for (int j = 0; j < n; j++){ 78 insert(tmp[1][0] + tmp[0][j]); 79 } 80 } 81 #if debug 82 puts(""); 83 for (int i = 0; i < size; i++){ 84 if (ex[i]) printf("%I64d\n", hash[i]); 85 } 86 puts(""); 87 #endif 88 for (int i = 0; i < 3; i++){ 89 for (int j = 0; j < n; j++) 90 scanf("%I64d", &tmp[i][j]); 91 } 92 for (int i = 0; i < n; i++){ 93 for (int j = 0; j < n; j++){ 94 for (int k = 0; k < n; k++){ 95 if (ex[loc(-(tmp[0][i] + tmp[1][j] + tmp[2][k]))]) return true; 96 } 97 } 98 } 99 return false; 100 } 101 102 int main(){ 103 int T; 104 105 scanf("%d", &T); 106 for (int i = 1; i <= T; i++){ 107 if (deal()){ 108 printf("Yes\n"); 109 } 110 else { 111 printf("No\n"); 112 } 113 } 114 return 0; 115 }
最后的1007就不详细说了，因为我是借一位大牛的模板基本一样的套上去哈密顿(hamilton)函数过的。
代码如下：
View Code
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <vector> 5 #include <map> 6 #include <queue> 7 #include <list> 8 #include <set> 9 #include <cstring> 10 #include <string> 11 12 using namespace std; 13 14 #define INF 0x7fffffff; 15 #define max4(a, b, c, d) (max2(a, b) > max2(c, d) ? max2(a, b) : max2(c, d)) 16 #define min4(a, b, c, d) (min2(a, b) < min2(c, d) ? min2(a, b) : min2(c, d)) 17 #define feq(a, b) fabs((a) - (b)) < eps 18 #define flq(a, b) (feq(a, b) || (a) < (b)) 19 #define reset(a) memset(a, 0, sizeof(a)) 20 #define fileout freopen("test.out", "w", stdout) 21 #define filein freopen("test.in", "r", stdin) 22 //segment tree 23 #define lson l, m, rt << 1 24 #define rson m + 1, r, rt << 1 | 1 25 #define root 1, n, 1 26 27 #define debug 1 28 29 const double eps = 1e-6; 30 31 32 int max2(int a, int b) 33 { 34 return a > b ? a : b; 35 } 36 37 int min2(int a, int b) 38 { 39 return a < b ? a : b; 40 } 41 42 const int maxn = 155; 43 bool maz[maxn][maxn], vis[maxn]; 44 int s, t, len, tot, p, n; 45 int ans[2][maxn]; 46 47 void expand(int x){ 48 bool flag; 49 50 do{ 51 flag = false; 52 if (!vis[x]) ans[p][tot++] = x; 53 vis[x] = true; 54 for (int i = 0; i < n; i++){ 55 if (maz[x][i] && !vis[i]){ 56 x = i; 57 flag = true; 58 break; 59 } 60 } 61 }while (flag); 62 } 63 64 void init (){ 65 memset(vis, 0, sizeof(vis)); 66 s = t = len = tot = p = 0; 67 expand(s); 68 reverse(ans[p], ans[p] + tot); 69 expand(t); 70 len = tot; 71 s = ans[p][0]; 72 t = ans[p][len - 1]; 73 } 74 75 void hamilton(){ 76 init(); 77 int i, j; 78 79 while (len < n || !maz[s][t]){ 80 if (maz[s][t]){ 81 int u = -1, v = -1; 82 83 for (i = 0; u == -1 && i < len; i++){ 84 for (j = 0; j < n; j++){ 85 if (!vis[j] && maz[ans[p][i]][j]){ 86 u = i; 87 v = j; 88 break; 89 } 90 } 91 } 92 p = !p; 93 tot = 0; 94 for (i = u + 1; i < len; i++){ 95 ans[p][tot++] = ans[!p][i]; 96 } 97 for (i = 0; i <= u; i++){ 98 ans[p][tot++] = ans[!p][i]; 99 } 100 ans[p][tot++] =v; 101 vis[v] = true; 102 len++; 103 104 } 105 else{ 106 for (i = 1; i < len; i++){ 107 if (maz[s][ans[p][i]] && maz[t][ans[p][i - 1]]) break; 108 } 109 reverse(ans[p] + i, ans[p] + len); 110 } 111 s = ans[p][0], t = ans[p][len - 1]; 112 } 113 } 114 115 116 int main() 117 { 118 int a, b, m; 119 while (~scanf("%d%d", &n, &m)){ 120 //n *= 2; 121 memset(maz, false, sizeof(maz)); 122 for (int i = 0; i < m; i++){ 123 scanf("%d%d", &a, &b); 124 --a, --b; 125 maz[a][b] = maz[b][a] = true; 126 } 127 for (int i = 0; i < n; i++)maz[i][i] = false; 128 hamilton(); 129 if (len < n)printf("no solution\n"); 130 else{ 131 for (int i = 0; i < len - 1; i++){ 132 printf("%d ", ans[p][i] + 1); 133 } 134 printf("%d\n", ans[p][len - 1] + 1); 135 } 136 } 137 138 return 0; 139 }
不过这题过的挺惊险的，队友一开始想到用网络流增广路来找到连接成环的边，不过我随便出了个小数据就卡死了他.......汗啊！其实我没出数据就能想到算法的问题，不过解释了队友没有accept我的意见。然后就唯有找模板，不过我的模板没有圆桌问题的模板，而刚开始我又忘记了“哈密顿回路”这个词了 - - 结果在最后25min的时候我终于想到这个名了，这时队友告诉我他的模板里有哈密顿回路的模板，于是我们就从debug直接转变成打新代码了。 一个以前没试用的模板，还真怕模板不能用，不过我们师兄，秋教，他的模板真好，看上去应该是每个模板都能正确的，不像网上那些乱来的代码模板 = =，搞到我最近不断的在试。当然，顺便学各种算法。 最后匆匆忙忙的十来分钟打完函数，套进数据输入模式后测试了几组数据都正确，立马就提交了！最后在剩6分钟的时候Accepted了~~Yeah！~最后赶上了大队，因为这次大家都是三题四题的！
好了，后面的路还长着，要练的还有很多！今天还有一个就是，我们三个人讨论好算法的分配了，希望这样的组织可以有效对付剩下的组队赛。
当然，过了暑假以后还是要增强大家的个人综合能力的，这才是关键！一枝独秀，队里一人独强，这不是我喜欢的模式。因为纵观历史，合作是很重要的，合作成功与否的关键就是大家的水平必须要接近。这仅是我的观点。
——written by Lyon
2012-8-2