首页 > 代码库 > BZOJ 2754 SCOI 2012 喵星球上的点名 后缀数组
BZOJ 2754 SCOI 2012 喵星球上的点名 后缀数组
题目大意:在喵星球上有一些喵~,每个喵都有一个姓和一个名字。点名的时候如果一个喵中姓或者名中有这个串的话他就会喵。问每次点名有几个喵喵了,和每个喵喵了几次。
思路:好萌的题喵~
AC自动机构造fail树是可以做的,但是和SA乱搞的时间差不多,我就是SA乱搞的w
把所有的串(姓名,询问)用$连接成一个串,然后做后缀数组,height数组。过程中记录一下每一个后缀数属于哪个喵,还有询问在串中的起始位置。在处理询问的时候,可以同过sa,rank数组快速的访问height数组,对于每一个询问向两边拓展,知道height数组小于询问串的长度。记录答案的时候要弄一个时间戳来盼重(真不知道为什么网上那么多用set的,真把常数不当干粮啊。。三倍的时间啊。。
当然这就是个暴力,时间复杂度是非常大的,想卡住也看好卡。想到了卡不住的方法,但是实现起来就比较困难了。将height数组用ST处理一下,然后对于每一个询问就可以向两边二分了,而不是暴力扫。得到了一整个区间之后,用主席树,直接看这个区间中有多少不同的喵。关于第二问就不太好处理了,我还没太想好QAQ
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 300010 using namespace std; int cats,asks,len; int s[MAX],from[MAX]; int ask[MAX],length[MAX]; int val[MAX],sa[MAX]; int rank[MAX],height[MAX]; int ans[MAX],v[MAX],T; inline bool Same(int x,int y,int l) { return val[x] == val[y] && ((x + l >= len && y + l >= len) || (x + l < len && y + l < len && val[x + l] == val[y + l])); } void GetSuffixArray() { static int _val[MAX],q[MAX],cnt[MAX],lim = 10010; for(int i = 0; i < len; ++i) ++cnt[val[i] = s[i]]; for(int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1]; for(int i = len - 1; ~i; --i) sa[--cnt[val[i]]] = i; for(int d = 1;; ++d) { int top = 0,l = 1 << (d - 1); for(int i = 0; i < len; ++i) if(sa[i] + l >= len) q[top++] = sa[i]; for(int i = 0; i < len; ++i) if(sa[i] >= l) q[top++] = sa[i] - l; for(int i = 0; i < lim; ++i) cnt[i] = 0; for(int i = 0; i < len; ++i) ++cnt[val[q[i]]]; for(int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1]; for(int i = len - 1; ~i; --i) sa[--cnt[val[q[i]]]] = q[i]; lim = 0; for(int i = 0,j; i < len; ++lim) { for(j = i; j < len - 1 && Same(sa[j],sa[j + 1],l); ++j); for(; i <= j; ++i) _val[sa[i]] = lim; } for(int i = 0; i < len; ++i) val[i] = _val[i]; if(lim == len) break; } return ; } void GetHeight() { for(int i = 0; i < len; ++i) rank[sa[i]] = i; for(int i = 0,k = 0; i < len; ++i) { if(k) --k; int j = sa[rank[i] - 1]; while(s[i + k] == s[j + k]) ++k; height[rank[i]] = k; } } int main() { cin >> cats >> asks; len = -1; for(int num,i = 1; i <= cats; ++i) { scanf("%d",&num); for(int j = 1; j <= num; ++j) scanf("%d",&s[++len]),from[len] = i; s[++len] = 10001; scanf("%d",&num); for(int j = 1; j <= num; ++j) scanf("%d",&s[++len]),from[len] = i; s[++len] = 10001; } for(int i = 1; i <= asks; ++i) { scanf("%d",&length[i]); ask[i] = len + 1; for(int j = 1; j <= length[i]; ++j) scanf("%d",&s[++len]); s[++len] = 10001; } ++len; GetSuffixArray(); GetHeight(); for(int i = 1; i <= asks; ++i) { int p = rank[ask[i]],temp = 0; ++T; while(height[p] >= length[i]) { if(from[sa[p - 1]]) if(v[from[sa[p - 1]]] != T) { v[from[sa[p - 1]]] = T; ++ans[from[sa[p - 1]]]; ++temp; } --p; if(!p) break; } p = rank[ask[i]]; while(height[p + 1] >= length[i]) { if(from[sa[p + 1]]) if(v[from[sa[p + 1]]] != T) { v[from[sa[p + 1]]] = T; ++ans[from[sa[p + 1]]]; ++temp; } ++p; if(p == len) break; } printf("%d\n",temp); } for(int i = 1; i <= cats; ++i) printf("%d%c",ans[i]," \n"[i == cats]); return 0; }
BZOJ 2754 SCOI 2012 喵星球上的点名 后缀数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。