首页 > 代码库 > BZOJ 2754: [SCOI2012]喵星球上的点名
BZOJ 2754: [SCOI2012]喵星球上的点名
二次联通门 : BZOJ 2754: [SCOI2012]喵星球上的点名
/* BZOJ 2754: [SCOI2012]喵星球上的点名 此题有N种做法。。。 见到众dalao用各种奇怪的姿势AC此题。。 具体有 后缀数组 + 莫队 后缀数组 + 优化暴力 AC自动机 抽离Fail树 AC自动机 乱搞。。 AC自动机 + hash。。。 最神的是一个 AC自动机 建fail树 树链剖分维护子树与查询lca + 树状数组 跪烂。。 bakabaka 我当然是开心的写了AC自动机 + 暴力转移啦。。 每次沿着fail指针跳,然后计算, 注意判断是否计算过 输入太恶心。。用map存Trie树的儿子节点即可 */ #include <cstdio> #include <map> #include <vector> #include <queue> #define Max 80090 void read (int &now) { now = 0; register char word = getchar (); while (word < ‘0‘ || word > ‘9‘) word = getchar (); while (word >= ‘0‘ && word <= ‘9‘) { now = now * 10 + word - ‘0‘; word = getchar (); } } int N, M; struct T_D { int Flandre; int Id; T_D *Fail; std :: map <int, T_D *> child; T_D () { child.clear (); Flandre = 0; Id = 0; Fail = NULL; } }; std :: map <int, bool> visit; std :: vector <int> name[Max]; std :: vector <int> count[Max * 3]; int Answer_1[Max]; int Answer_2[Max]; class AC_Type { private : T_D *Root ; int Count; int Insert_Count; public : AC_Type () { Count = 0; Root = new T_D ; Root->Id = ++ Count; Insert_Count = 0; } void Insert (int Len) { T_D *now = Root; int Id; for (int i = 1; i <= Len; i ++) { read (Id); if (now->child[Id] == NULL) { now->child[Id] = new T_D; now->child[Id]->Id = ++ Count; } now = now->child[Id]; } now->Flandre ++; count[now->Id].push_back (++ Insert_Count); } void Build_AC () { std :: queue <T_D *> Queue; Queue.push (Root); T_D *now, *pos; while (!Queue.empty ()) { now = Queue.front (); Queue.pop (); pos = NULL; for (std :: map <int, T_D *> :: iterator i = now->child.begin (); i != now->child.end (); i ++) { if (now == Root) i->second->Fail = Root; else { for (pos = now->Fail; pos; pos = pos->Fail) if (pos->child[i->first]) { i->second->Fail = pos->child[i->first]; break; } if (pos == NULL) i->second->Fail = Root; } Queue.push (i->second); } } } T_D *Get_Root () { return Root; } }; AC_Type Make; void Calculate (T_D *now, int i) { if (now->Flandre) { Answer_2[i] += now->Flandre; for (int k = 0; k < count[now->Id].size (); k ++) Answer_1[count[now->Id][k]] ++; } } int main (int argc, char *argv[]) { read (N); read (M); for (int i = 1, x, y; i <= N; i ++) { read (x); for (int j = 1; j <= x; j ++) { read (y); name[i].push_back (y); } name[i].push_back (-1); read (x); for (int j = 1; j <= x; j ++) { read (y); name[i].push_back (y); } name[i].push_back (-2); } for (int i = 1, x; i <= M; i ++) { read (x); Make.Insert (x); } Make.Build_AC (); int Len; T_D *now , *pos; for (int i = 1; i <= N; i ++) { Len = name[i].size (); visit.clear (); now = Make.Get_Root (); pos = NULL; for (int j = 0; j < Len; j ++) { if (!visit[now->Id]) { visit[now->Id] = true; Calculate (now, i); for (pos = now->Fail; pos; pos = pos->Fail) if (!visit[pos->Id]) { visit[pos->Id] = true; Calculate (pos, i); } } if (now->child[name[i][j]]) now = now->child[name[i][j]]; else { for (pos = now->Fail; pos; pos = pos->Fail) { if (!visit[pos->Id]) { visit[pos->Id] = true; Calculate (pos, i); } if (pos->child[name[i][j]]) { now = pos->child[name[i][j]]; for (T_D *Saber = pos->Fail; Saber; Saber = Saber->Fail) if (!visit[Saber->Id]) { visit[Saber->Id] = true; Calculate (Saber, i); } break; } } if (pos == NULL) now = Make.Get_Root (); } } } for (int i = 1; i <= M; i ++) printf ("%d\n", Answer_1[i]); printf ("%d", Answer_2[1]); for (int i = 2; i <= N; i ++) printf (" %d", Answer_2[i]); return 0; }
BZOJ 2754: [SCOI2012]喵星球上的点名
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。