首页 > 代码库 > bzoj4896 [Thu Summer Camp2016]补退选
bzoj4896 [Thu Summer Camp2016]补退选
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4896
【题解】
隔壁thusc画风怎么这么正常啊。。
三个操作:插入字符串,删除字符串,询问以某字符串为前缀,最早什么时候超过了d个。
用trie插入然后拿个vector维护第一次超过x个的时间。
vector中总的元素为60*10w=600w个。所以可以承受。
然后我们发现非常坑。。
我们只能用指针写省空间。。然后开了600w的trienode还是MLE了。。
改成400w就过了(?)看来没去卡。。
# include <map> # include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 4e6 + 10, N = 310; const int mod = 1e9+7; # define RG register # define ST static char str[N]; struct trienode { trienode *ch[26]; int w; vector<int> v; }T[M]; int cnt = 1; int nQ; inline void add(char *str, int d) { trienode *p = &T[1], *q; for (int i=0, c; str[i]; ++i) { c = str[i] - ‘a‘; if(p->ch[c] == 0) { ++cnt; q = &T[cnt]; p->ch[c] = q; } p = p->ch[c]; p->w += d; if((p->v).size() < p->w) p->v.push_back(nQ); } } inline int query(int d) { // printf("d = %d\n", d); trienode *p = &T[1], *q; for (int i=0, c; str[i]; ++i) { c = str[i] - ‘a‘; if(p->ch[c] == 0) return -1; p = p->ch[c]; // printf("%d\n", p->v.size()); } if(p->v.size() > d) return p->v[d]; else return -1; } int main() { int q, opt, a, b, c; cin >> q; int ans = 0; for (nQ = 1; nQ <= q; ++nQ) { scanf("%d", &opt); scanf("%s", str); if(opt == 1) add(str, 1); else if(opt == 2) add(str, -1); else { scanf("%d%d%d", &a, &b, &c); ans = query(((ll)a*abs(ans)+b)%c); printf("%d\n", ans); } } return 0; }
后来看了看popoqqq的博客发现有很多ch[..]是没有用的。
那么拿map存有用的和没用的。。每个节点开个map即可。
这样理论多个log还更快?
# include <map> # include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 6e6 + 10, N = 310; const int mod = 1e9+7; # define RG register # define ST static char str[N]; struct trienode { map<int, trienode*> ch; int w; vector<int> v; }T[M]; int cnt = 1; int nQ; inline void add(char *str, int d) { trienode *p = &T[1], *q; for (int i=0, c; str[i]; ++i) { c = str[i] - ‘a‘; if(p->ch[c] == 0) { ++cnt; q = &T[cnt]; p->ch[c] = q; } p = p->ch[c]; p->w += d; if((p->v).size() < p->w) p->v.push_back(nQ); } } inline int query(int d) { // printf("d = %d\n", d); trienode *p = &T[1], *q; for (int i=0, c; str[i]; ++i) { c = str[i] - ‘a‘; if(p->ch[c] == 0) return -1; p = p->ch[c]; // printf("%d\n", p->v.size()); } if(p->v.size() > d) return p->v[d]; else return -1; } int main() { int q, opt, a, b, c; cin >> q; int ans = 0; for (nQ = 1; nQ <= q; ++nQ) { scanf("%d", &opt); scanf("%s", str); if(opt == 1) add(str, 1); else if(opt == 2) add(str, -1); else { scanf("%d%d%d", &a, &b, &c); ans = query(((ll)a*abs(ans)+b)%c); printf("%d\n", ans); } } return 0; }
(下一个是用map,上一个是直接400w个trienode开26个ch)
bzoj4896 [Thu Summer Camp2016]补退选
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。