HDU3973 线段树 + 字符哈希
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3973 , 线段树 + 字符哈希，好题。
又学了一种新的哈希方法，hhhh~
解法：
想法是用P进制的数来表示一个字符串，由于可能数太大，所以就将转换成是十进制后的数模long long的最大值，这样虽然也有可能冲突，但是概率会非常小。这里的P可以随意取一个素数(我取的是31)。
先用上面提到的哈希方法将W集合中的字符串都转成十进制数存在数组中，然后进行排序；每一次询问时候，将询问区间的子串转成十进制后二分查找是否在W集合中即可。
思路虽然简单，但是实现起来还是比较麻烦，尤其是有很多细节需要注意。
#include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <vector> #include <string> #include <string.h> #include <algorithm> using namespace std; #define LL __int64 #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 100000 + 20; const int p = 31; char str[2000020]; LL Hash[maxn << 2] , P[maxn]; LL W[10000 + 5]; void init() { P[0] = 1; for(int i = 1 ; i <= maxn ; i++) P[i] = P[i - 1] * p; } LL calhash(char str[]) { LL sum = 0; for(int i = 0 ; str[i] != '\0' ; i++) { sum = sum * p + str[i] - 'a' + 1; } return sum; } int binary_search(int l , int r , LL a[] , LL x) { int m = (l + r) >> 1; while(l <= r) { if(a[m] == x) return m; if(a[m] > x) r = m - 1; if(a[m] < x) l = m + 1; m = (l + r) >> 1; } return -1; } void PushUp(int l , int r , int rt) { int m = (l + r) >> 1; Hash[rt] = Hash[rt << 1] * P[r - m] + Hash[rt << 1 | 1]; } void build(int l , int r , int rt) { if(l == r) { Hash[rt] = str[r] - 'a' + 1; return; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(l , r , rt); } void update(int x , int l , int r , int rt) { if(l == r) { Hash[rt] = str[x] - 'a' + 1; return; } int m = (l + r) >> 1; if(x > m) update(x , rson); else update(x , lson); PushUp(l , r , rt); } LL query(int L , int R , int l , int r , int rt) { if(L <= l && R >= r) { return Hash[rt]; } int m = (l + r) >> 1; if(m < L) return query(L , R , rson); else if(m >= R) return query(L , R , lson); else return query(L , m , lson) * P[R - m] + query(m + 1 , R , rson); } int main() { int n , m , T; char ch[10] , s[10]; init(); cin >> T; for(int k = 1 ; k <= T ; k++) { scanf("%d" , &n); for(int i = 1 ; i <= n ; i++) { scanf("%s" , str); W[i] = calhash(str); } sort(W + 1 , W + n + 1); scanf("%s" , str); int len = strlen(str); build(0 , len - 1 , 1); printf("Case #%d:\n" , k); scanf("%d" , &m); while(m--) { scanf("%s" , ch); if(ch[0] == 'Q') { int L , R; scanf("%d %d" , &L , &R); LL tmp = query(L , R , 0 , len - 1 , 1); if(binary_search(1 , n , W , tmp) != -1) puts("Yes"); else puts("No"); } else { int x; scanf("%d" , &x); scanf("%s" , s); str[x] = s[0]; update(x , 0 , len - 1 , 1); } } } return 0; }优质内容筛选与推荐>>
1、《计算机科学概论》读书笔记
2、C#上位机制作之串口接受数据（利用接受事件）
3、redis简单总结
4、5.13(n)个人围成一圈，1、2、3、1、2、3 报数，报到3的出圈，请问最后一个出圈的人是原来的几号？留下的是原来的几号？
5、CSS学习笔记