[LibreOJ 2033][SDOI2016]生成魔咒
转载请注明出处：http://danihao123.is-programmer.com/
辣鸡爆炸OJ又被卡了说好的修bug呢说好的新OJ呢哼我去loj交了
本题的正解是SA，但很显然可以用SAM搞过去（逃
首先字符集过大？我们可以考虑开map解决转移的问题。
然后思考一个点加入后对答案会有什么影响。一个点的对答案的贡献，就是他自己的最大表示范围减去他父亲的。因为更小的长度在之前都已经被表示过了。即使之后这个点被拆成了两个，那这两个点对答案的总贡献是不会变的。所以每次加完点，把贡献加到答案里即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <map>typedef long long ll;#define REP(i, l, r) for(int i = (l); i <= (r); i ++)struct Node { Node *fa; std::map<int, Node*> *ch; int len; Node() { fa = NULL; ch = new std::map<int, Node*>(); } Node(int l) { fa = NULL; ch = new std::map<int, Node*>(); len = l; } ~Node() { delete ch; }};Node *rt, *last;void init() { rt = new Node(0); // rt -> tl = 1; last = rt;}ll ans = 0;void insert(int c) { static int clk = 1; Node *np = new Node(); np -> len = last -> len + 1; Node *p = last; while(p != NULL && p -> ch -> count(c) == 0) { p -> ch -> insert(std::make_pair(c, np)); p = p -> fa; } if(p == NULL) { np -> fa = rt; } else { Node *q = (*(p -> ch -> find(c))).second; if(q -> len == p -> len + 1) { np -> fa = q; } else { Node *nq = new Node(p -> len + 1); nq -> fa = q -> fa; nq -> ch -> insert(q -> ch -> begin(), q -> ch -> end()); // nq -> ch -> insert(std::make_pair(c, np)); np -> fa = q -> fa = nq; while(p != NULL && ((*(p -> ch -> find(c))).second) == q) { p -> ch -> erase(p -> ch -> find(c)); p -> ch -> insert(std::make_pair(c, nq)); p = p -> fa; } } } last = np; ans += np -> len - np -> fa -> len;} int main() { int n; scanf("%d", &n); init(); REP(i, 1, n) { int c; scanf("%d", &c); insert(c); printf("%lld\n", ans); } return 0;} |
评论 (0)
