BZOJ 2119: 股市的预测 (Hash / 后缀数组 + st表)

转博客大法好

自己画一画看一看,就会体会到这个设置关键点的强大之处了.

CODE(sa)

$O(nlogn)\to 1436ms$

#include 
using namespace std;
typedef long long LL;
template<class T>inline void read(T &num) {register char ch; register int flg = 1;while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar());num *= flg;
}
const int MAXN = 5e4+5;int x[MAXN], y[MAXN], c[MAXN], Log[MAXN];int n, s[MAXN], b[MAXN], tot;
struct SA {int sa[MAXN], rk[MAXN], h[MAXN], f[MAXN][16];inline void Get_Sa(int m) {for(int i = 1; i <= m; ++i) c[i] = 0;for(int i = 1; i <= n; ++i) ++c[x[i]=s[i]];for(int i = 2; i <= m; ++i) c[i] += c[i-1];for(int i = n; i >= 1; --i) sa[c[x[i]]--] = i;for(int k = 1; k <= n; k<<=1) {int p = 0;for(int i = n-k+1; i <= n; ++i) y[++p] = i;for(int i = 1; i <= n; ++i) if(sa[i]>k) y[++p] = sa[i]-k;for(int i = 1; i <= m; ++i) c[i] = 0;for(int i = 1; i <= n; ++i) ++c[x[i]];for(int i = 2; i <= m; ++i) c[i] += c[i-1];for(int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];swap(x, y);x[sa[1]] = 1; p = 1;for(int i = 2; i <= n; ++i)x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] ==y[sa[i-1]+k]) ? p : ++p;if((m=p) == n) break;}}inline void Get_Height() {int k = 0;for(int i = 1; i <= n; ++i) rk[sa[i]] = i;for(int i = 1; i <= n; ++i) {if(rk[i] == 1) continue;if(k) --k;int j = sa[rk[i]-1];while(i+k <= n && j+k <= n && s[i+k] == s[j+k]) ++k;h[rk[i]] = k;}}inline void rev() {reverse(rk + 1, rk + n + 1);for(int i = 1; i <= n; ++i) sa[i] = n-i+1;}inline void init() {Get_Sa(n);Get_Height();}inline void initST() {for(int i = 1; i <= n; ++i) f[i][0] = h[i];for(int j = 1; j <= Log[n]; ++j)for(int i = 1; i <= n-(1<<j)+1; ++i)f[i][j] = min(f[i][j-1], f[i+(1<<j-1)][j-1]);}inline int query(int l, int r) {l = rk[l], r = rk[r];if(l > r) swap(l, r);++l;int k = Log[r-l+1];return min(f[l][k], f[r-(1<<k)+1][k]);}
}sa1, sa2;
int m;
int main() {read(n), read(m);for(int i = 1; i <= n; ++i) read(s[i]);--n;for(int i = 1; i <= n; ++i) b[++tot] = (s[i]=s[i+1]-s[i]);s[n+1] = 0;sort(b + 1, b + tot + 1); tot = unique(b + 1, b + tot + 1) - b - 1;for(int i = 1; i <= n; ++i) s[i] = lower_bound(b + 1, b + tot + 1, s[i]) - b;for(int i = 2; i <= n; ++i) Log[i] = Log[i>>1] + 1;sa1.init(), sa1.initST();reverse(s + 1, s + n + 1);sa2.init(), sa2.rev(), sa2.initST();LL ans = 0;for(int len = 1; (len<<1)+m <= n; ++len)for(int i = 1, j; (j=i+len+m) <= n; i += len) {int l = min(sa2.query(i, j), len), r = min(sa1.query(i, j), len);if(l + r > len) ans += l + r - len;}printf("%lld\n", ans);
}

CODE(hash)

O ( n l o g 2 n ) → 688 m s O(nlog^2n)\to 688ms O(nlog2n)→688ms

实测hash速度是sa的2.5倍…
常数的幽怨…

市面上貌似找不到hash的代码的说…

#include 
using namespace std;
typedef long long LL;
template<class T>inline void read(T &num) {register char ch; register int flg = 1;while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar());num *= flg;
}
const int MAXN = 5e4+5;
const int p = 137;
int n, m, s[MAXN], h[MAXN], mul[MAXN];
inline int hsh(int l, int r) {return h[r] - h[l-1]*mul[r-l+1];
}
inline int querypre(int i, int j, int up) {int l = 0, r = min(min(i, j), up), mid;while(l < r) {mid = (l + r + 1) >> 1;if(hsh(i-mid+1, i) == hsh(j-mid+1, j)) l = mid;else r = mid-1;}return l;
}
inline int querysuf(int i, int j, int up) {int l = 0, r = min(min(n-i+1, n-j+1), up), mid;while(l < r) {mid = (l + r + 1) >> 1;if(hsh(i, i+mid-1) == hsh(j, j+mid-1)) l = mid;else r = mid-1;}return l;
}
int main() {read(n), read(m); mul[0] = 1;for(int i = 1; i <= n; ++i) read(s[i]);for(int i = 1; i < n; ++i) {h[i] = h[i-1] * p + s[i+1]-s[i];mul[i] = mul[i-1] * p;}s[n] =  0; --n;LL ans = 0;for(int len = 1; (len<<1)+m <= n; ++len)for(int i = 1, j; (j=i+len+m) <= n; i += len) {int l = querypre(i, j, len), r = querysuf(i, j, len);if(l + r > len) ans += l + r - len;}printf("%lld\n", ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！