- 1动态规划课堂6-----回文串问题_java 算法:给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符
- 2InstructionGPT
- 3Android6.0 图像合成过程详解（一） setUpHWComposer函数_android dotransaction
- 4基于hadoop的社交网络的分析_基于hadoop的社交网络分析
- 5Xilinx Virtex-5 FPGA CLB资源学习笔记_v5 fgpa
- 6opencv-python 视频流光去抖、实时去抖_python opencv 防抖
- 7YOLOv5独家原创改进：图像去噪 |一种新颖的双分支残差注意，助力低光照、红外小目标检测 | 2024年最新发表（全网独家首发）_yolov5 双分支
- 8使用 .NET Upgrade Assistant 将 ASP.NET Framework 现代化为 ASP.NET Core
- 9Spring Boot整合WebSocket和Redis实现直播间在线人数统计功能_redis 记录 websocket 在线人数, 服务重启
- 10模拟行程编码（C语言）_行程编码是一种统计编码,适用于经常出现具有相同值的连 续符号时的数据压缩,假设
Trie字典树题集_给定 n 个长度不超过 1 0 10 的数字串,问其中是否存在两个数字串 ,
赞
踩
Phone List
原题来自：POJ 3630
给定 n 个长度不超过 10 的数字串，问其中是否存在两个数字串 S,T，使得 S 是 T 的前缀，多组数据。
解题思路
Trie的经典应用，可以作为模板题练手。
代码示例
#include<bits/stdc++.h> using namespace std; const int SZ = 1e5+10; int trie[SZ][30], tot; int End[SZ]; int n,t; const int N = 1e4+10; char str[N][20]; void Insert(char *s){ /* 将字串s插入trie树 */ int len = strlen(s) ,p = 1; for(int i = 0;i < len;i++){ int ch = s[i]-'0'; if(trie[p][ch] == 0) trie[p][ch] = ++tot; p = trie[p][ch]; } End[p]++; } bool search(char *s){ /* 字串s是否有前缀 */ int len = strlen(s), p = 1; for(int i = 0;i < len;i++){ int ch = s[i]-'0'; if(End[p]) return true; p = trie[p][ch]; } return false; } bool solve(){ for(int i = 1;i <= n;i++) Insert(str[i]); for(int i = 1;i <= n;i++) if(search(str[i])) return true; return false; } int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); /* 初始化trie相关变量 */ memset(End,0,sizeof End); tot = 1; memset(trie,0,sizeof trie); for(int i = 1;i <= n;i++) scanf("%s",str[i]); if(solve()) puts("NO"); else puts("YES"); } return 0; }
- 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
The XOR Largest Pair
题意简述
在给定的 N 个整数 A1,A2,…,AN 中选出两个进行异或运算，得到的结果最大是多少？
解题思路
就是将每个整数看作31位的01字符串，然后全部插入到Trie上，再分别对每个整数从高位到低位优先在Trie上走和该位相反的节点。01字典树。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; const int SZ = 5e6+10;//大小要合理！！！ int trie[SZ][3], End[SZ], tot = 1; int n,a[N],ans = 0; void Insert(int x){ int p = 1; for(int i = 31;i >= 0;i--){ int ch = (x>>i)&1; if(trie[p][ch] == 0) trie[p][ch] = ++tot; p = trie[p][ch]; } End[p]++; } void calc(int x){ int res = 0, p = 1; for(int i = 31;i >= 0;i--){ int ch = (x>>i)&1; if(trie[p][!ch]) p = trie[p][!ch], res |= 1<<i; else p = trie[p][ch]; } ans = max(ans,res); } void solve(){ for(int i = 1;i <= n;i++) Insert(a[i]); for(int i = 1;i <= n;i++) calc(a[i]); printf("%d\n",ans); } int main(){ //freopen("123.txt","r",stdin); scanf("%d",&n); for(int i = 1;i <= n;i++) scanf("%d",a+i); solve(); return 0; }
- 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
Codechef REBXOR*
题意简述
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-csdLTzCO-1569857847410)(en-resource://database/4704:1)]
解题思路
这题用的是 “Trie维护异或前缀和”，根据异或的特性，我们从左到右依次将元素插入后，再利用 xyx = y 这个特性在常数时间利用 Trie 找最大区间异或和。本题还是很有参考意义的，尤其是异或前缀和这一技巧。
当然由于OJ上给定的空间过小，本代码没过，待解决。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 4e5+10; const int SZ = 20*N; int trie[SZ][3], tot = 1; int n,a[N],lmx[N],rmx[N]; void Insert(int x){ int p = 1; for(int i = 32;i >= 0;i--){ int ch = (x>>i)&1; if(!trie[p][ch]) trie[p][ch] = ++tot; p = trie[p][ch]; } } int search(int x){ int p = 1, res = 0; for(int i = 32;i >= 0;i--){ int ch = (x>>i)&1; if(trie[p][!ch]) p = trie[p][!ch],res |= 1<<i; else p = trie[p][ch]; } return res; } void solve(){ int x = 0;Insert(0); /* x 用于累计异或前缀和,Trie用于求最大异或区间*/ for(int i = 1;i <= n;i++){ x ^= a[i]; Insert(x); lmx[i] = max(search(x),lmx[i-1]); //包含x的最大区间异或和 与 不包含x的区间的最大异或和 } memset(trie,0,sizeof trie); tot = 1; Insert(0); x = 0; for(int i = n;i > 0;i--){ x ^= a[i]; Insert(x); rmx[i] = max(search(x),rmx[i+1]); } int ans = 0; for(int i = 0;i <= n;i++) ans = max(ans,lmx[i]+rmx[i+1]); printf("%d\n",ans); } int getInt() { int ans = 0; bool neg = false; char c = getchar(); while (c!='-' && (c<'0' || c>'9')) c = getchar(); if (c == '-') neg = true, c = getchar(); while (c>='0' && c<='9') ans = ans*10 + c-'0', c = getchar(); return neg ? -ans : ans; } int main(){ // freopen("123.txt","r",stdin); n = getInt(); for(int i = 1;i <= n;i++) a[i] = getInt(); solve(); return 0; }
- 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
Immediate Decodability
题意简述
原题来自：ACM Pacific NW Region 1998
给出一些数字串，判断是否有一个数字串是另一个串的前缀。
解题思路
和第1题一样，模板题。
代码示例
#include<bits/stdc++.h> using namespace std; const int SZ = 1e5+10; int trie[SZ][30], tot = 1; int End[SZ]; int n,t,cnt = 0; const int N = 1e4+10; char str[N][20]; void Insert(char *s){ /* 将字串s插入trie树 */ int len = strlen(s) ,p = 1; for(int i = 0;i < len;i++){ int ch = s[i]-'0'; if(trie[p][ch] == 0) trie[p][ch] = ++tot; p = trie[p][ch]; } End[p]++; } bool search(char *s){ /* 字串s是否有前缀 */ int len = strlen(s), p = 1; for(int i = 0;i < len;i++){ int ch = s[i]-'0'; if(End[p]) return true; p = trie[p][ch]; } return false; } bool solve(){ for(int i = 1;i <= n;i++) Insert(str[i]); for(int i = 1;i <= n;i++) if(search(str[i])) return true; return false; } int main(){ while(scanf("%s",str[++n]) != EOF){ /* 初始化trie相关变量 */ if(strlen(str[n]) == 1 && str[n][0] == '9'){ if(!solve()) printf("Set %d is immediately decodable\n",++cnt); else printf("Set %d is not immediately decodable\n",++cnt); memset(End,0,sizeof End); tot = 1; memset(trie,0,sizeof trie); n = 0; } } return 0; }
- 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
L语言*
题意简述
原题来自：HNOI 2004
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。
一段文章 T 是由若干小写字母构成。一个单词 W 也是由若干小写字母构成。一个字典 D 是若干个单词的集合。
我们称一段文章 T 在某个字典 D 下是可以被理解的，是指如果文章 T 可以被分成若干部分，且每一个部分都是字典 D 中的单词。例如字典 D 中包括单词 is , your , what , name ，则文章 whatisyourname 是在字典 D 下可以被理解的，因为它可以分成 4 个单词： what , is , your , name ，且每个单词都属于字典 D，而文章 whatisyouname 在字典 D 下不能被理解，但可以在字典 D′=D+you 下被理解。这段文章的一个前缀 whatis ，也可以在字典 D 下被理解 而且是在字典 D 下能够被理解的最长的前缀。
给定一个字典 D ，你的程序需要判断若干段文章在字典 D 下是否能够被理解。 并给出其在字典 D 下能够被理解的最长前缀的位置。
解题思路
这题有点难的地方是 文章中某个前缀可能由多个单词组合出来，于是我们需要对每个可能是单词末尾的位置再进行下一次匹配，检查其后是否有字典D中的单词。
我们首先将所有单词插入字典树，由于单词长度小于10，所以对于每个单词，我们最多比较10次就能知道该字串是否为字典D中的单词。每次匹配都要从字典树的根开始匹配。
我们设f[i]表示 “文章中第 i 位是否为可以被D理解的某个前缀的末尾”；如果 f[i] 为 1 ，那么说明[1, i]都可以被D理解，接下来只要再从 i+1 位开始尝试在字典树匹配单词即可。
这是存在性DP，状态转移很简单，在字典树查找单词时，若当前位置是某个单词的末尾，即End[ p ] = 1，那么f[ pos ] = 1（pos为当前字符位置），时间复杂度为O(10N)。
优化
在 查找/匹配 单词时，我习惯将其封装为一个函数search(char * s)，但是最差情况我们会调用1e6次该函数，虽然该函数内最多只比较10次，但是函数传参以及保护现场以及恢复等步骤还是会大大增加花费的时间。经过测试，写成函数调用形式在1e6数据下大概会比直接展开慢几十秒，当然还是可以通过一些步骤优化函数调用的。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 2e6+10; const int SZ = 1e4+10; int trie[SZ][30],End[SZ], tot = 1; int n,m; char str[N],s[30]; bool f[N]; void Insert(char *s){ int len = strlen(s), p = 1; for(int i = 0;i < len;i++){ int ch = s[i]-'a'; if(!trie[p][ch]) trie[p][ch] = ++tot; p = trie[p][ch]; } End[p] = 1; } void solve(){ int len = strlen(str)-1, ans; memset(f,0,sizeof f); f[0] = 1; //printf("%d\n",len); for(int i = 0;i <= len;i++){ if(!f[i]) continue; ans = i; for(int j = i+1,p = 1;j <= len;j++){ int ch = str[j]-'a'; p = trie[p][ch]; if(!p) break; if(End[p]) f[j] = 1; } } printf("%d\n",ans); } int main(){ //freopen("123.txt","r",stdin); scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++){ scanf("%s",s); Insert(s); } for(int i = 1;i <= m;i++){ scanf("%s",str+1); str[0] = '#'; solve(); } return 0; }
- 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
Secret Message 秘密信息
题意描述
原题来自：USACO 2008 Dec. Gold
贝茜正在领导奶牛们逃跑。为了联络，奶牛们互相发送秘密信息。信息是二进制的，共有 M 条。反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 i 条二进制信息的前 bi 位。
他同时知道，奶牛使用 N 条密码。但是，他仅仅了解第 j 条密码的前 cj位。对于每条密码 j ，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条密码有着相同的前缀。当然，这个前缀长度必须等于密码和那条信息长度的较小者。
解题思路
根据所给样例呢，可以更加明确题意。首先我们将M条信息看作01字符串，同理N条密码也看作01字符串，题意问的就是对于每个密码，有多少条信息可能和该密码匹配，如果一条信息 A 和密码 B 匹配，那么有 A 是 B 的前缀或 B 是 A 的前缀。
于是我们就只需要先把01数组转化为01字符串，再用trie统计即可，当然由于同一信息可能会重复出现，所以 End[p] 记录的是以 p 结尾的字串个数。
在本机与洛谷上都是可以AC的，复杂度大概O(5e5)，但是在一本通OJ就过不去，猜测可能是不支持关闭 scanf 同步流？待修改。
代码示例
#include<bits/stdc++.h> using namespace std; int n,m; const int N = 5e4+10; const int SZ = 5e5+10; string str[N],s[N]; int trie[SZ][2],End[SZ],tot = 1,tc[SZ]; void Insert(const string& s){ int len = s.length(), p = 1; for(int i = 0;i < len;i++){ int ch = s[i]-'0'; if(!trie[p][ch]) trie[p][ch] = ++tot; p = trie[p][ch]; tc[p]++; } End[p]++; } int search(const string& s){ //cout << s << "-" << endl; int len = s.length(), p = 1,res = 0; for(int i = 0;i < len;i++){ int ch = s[i]-'0'; p = trie[p][ch]; if(!p) break; if(End[p] && i != len-1) res += End[p]; } return res + tc[p]; } void solve(){ for(int i = 1;i <= n;i++) Insert(str[i]); for(int i = 1;i <= m;i++) cout << search(s[i]) << endl; } int main(){ ios::sync_with_stdio(false); // freopen("123.txt","r",stdin); // freopen("222.txt","w",stdout); cin >> n >> m; for(int i = 1,k;i <= n;i++){ cin >> k; for(int j = 1,x;j <= k;j++) cin >> x, str[i] += x+'0'; //cout << str[i] << endl; } for(int i = 1,k;i <= m;i++){ cin >> k; for(int j = 1,x;j <= k;j++) cin >> x, s[i] += x+'0'; //cout << s[i] << endl; } solve(); return 0; }
- 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
【SCOI2016】背单词*
题意简述
Lweb 面对如山的英语单词，陷入了深深的沉思，「我怎么样才能快点学完，然后去玩三国杀呢？」。
这时候睿智的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x 的单词（序号 1…x−1 都已经被填入）：
- 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n×n 颗泡椒才能学会；
- 当它的所有后缀都被填入表内的情况下，如果在 1…x−1 的位置上的单词都不是它的后缀，那么他吃 x 颗泡椒就能记住它；
- 当它的所有后缀都被填入表内的情况下，如果 1…x−1 的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y，那么你只要吃 x−y 颗泡椒就能把它记住。
Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb，寻找一种最优的填写单词方案，使得他记住这 n 个单词的情况下，吃最少的泡椒。
解题思路
首先把所有字符串反转，那么后缀就变成前缀了，就可以用trie维护。
刚开始我是想记录每个字符串的前缀个数，然后根据个数从小到大分配编号，但显然不行。
正解是将所有字符串构成一棵树，一个节点的父亲就是它的前缀，而没有前缀的字符串父亲为 0 号节点。我们可以利用 trie中的 search 时填边建树。
这样我们就有一棵有向树了，假设我们给节点 x 分配的序号是 f[x] ，那么显然 ans += f[x] - f[par[x] ]，其中 par[x] 代表 x 的父亲节点。所以我们需要让每个节点和它父亲节点的编号相差尽量小，那么自然是优先给节点数少的子树分配编号咯，所以对于每个节点 x ，我们选择节点最小的一棵子树，为它们分配编号。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; const int SZ = 6e5+10; int tc[N];//记录后缀个数 int trie[SZ][30],End[SZ], tot = 1; int par[N], head[N], ver[N], nex[N],tot2 = 1; void addEdge(int x,int y){ ver[++tot2] = y, nex[tot2] = head[x], head[x] = tot2; } void Insert(const string& s,int id){ //cout << s << endl; int len = s.length(), p = 1; for(int i = 0;i < len;i++){ int ch = s[i]-'a'; if(!trie[p][ch]) trie[p][ch] = ++tot; p = trie[p][ch]; } End[p] = id; } void search(const string& s,int id){ //cout << s << endl; int len = s.length(), p = 1 ,res = 0; for(int i = 0;i < len;i++){ int ch = s[i]-'a'; p = trie[p][ch]; if(End[p] && i != len-1) par[id] = End[p]; } addEdge(par[id],id);//顺便建树啦 } int n; string str[N]; typedef long long ll; int num[N];//记录子树x的节点个数 int dfs(int x){ for(int i = head[x];i != -1;i = nex[i]){ int y = ver[i]; num[x] += dfs(y); } return num[x]+1; } ll ans = 0, cnt = 0; priority_queue< pair<int,int> > q; int f[N]; //记录x编号 void calc(int x){ ans += cnt - f[par[x]]; f[x] = cnt; for(int i = head[x];i != -1;i = nex[i]){ int y = ver[i]; q.push(make_pair(-num[y],y)); } int nnex[q.size()],tt = 0; while(!q.empty()){ int y = q.top().second;q.pop(); nnex[tt++] = y; } for(int i = 0;i < tt;i++) cnt++, calc(nnex[i]); } void solve(){ memset(head,-1,sizeof head); for(int i = 1;i <= n;i++) Insert(str[i],i); for(int i = 1;i <= n;i++) search(str[i],i); num[0] = dfs(0); calc(0); cout << ans << endl; } int main(){ //freopen("123.txt","r",stdin); ios::sync_with_stdio(false); cin >> n; for(int i = 1;i <= n;i++) cin >> str[i]; for(int i = 1;i <= n;i++) reverse(str[i].begin(),str[i].end()); solve(); return 0; }
- 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
- 74
- 75
- 76
- 77
The xor-longest Path*
题意简述
原题来自：POJ 3764
给定一棵 n 个点的带权树，求树上最长的异或和路径。
解题思路
设 d[x] 表示 x 到根节点的路径异或和，那么显然由于异或的特性，xyx = y，我们任选两个点 x 和 y ，那么d[x] ^ d[y]就是 x 和 y 之间的路径异或和，因为从LCA(x , y)到根节点的路径都被抵消了。
所以原问题就成了从 d[1,n] 中选两个数，使它们的异或和最大。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 2e5+10; int head[N],ver[N],nex[N],edge[N],tot = 1; int n,d[N];//d[x]:x到根节点的路径异或和 bool vis[N]; void addEdge(int x,int y,int z){ ver[++tot] = y, nex[tot] = head[x]; edge[tot] = z, head[x] = tot; } int getInt() { int ans = 0; bool neg = false; char c = getchar(); while (c!='-' && (c<'0' || c>'9')) c = getchar(); if (c == '-') neg = true, c = getchar(); while (c>='0' && c<='9') ans = ans*10 + c-'0', c = getchar(); return neg ? -ans : ans; } void dfs(int x){ vis[x] = true; for(int i = head[x];i ;i = nex[i]){ int y = ver[i], z = edge[i]; if(vis[y]) continue; // printf("%d %d %d\n",x,y,z); d[y] = d[x]^z; dfs(y); } } const int SZ = 32*N; int trie[SZ][2], tot2 = 1; void Insert(int x){ for(int i = 31,p = 1;i >= 0;i--){ int ch = (x>>i)&1; if(!trie[p][ch]) trie[p][ch] = ++tot2; p = trie[p][ch]; } } int search(int x){ /*返回x与集合中异或和最大的 结果*/ int res = 0,p = 1; for(int i = 31;i >= 0;i--){ int ch = (x>>i)&1; if(trie[p][!ch]) p = trie[p][!ch],res |= 1<<i; else p = trie[p][ch]; } return res; } void solve(){ /* 计算并输出答案 */ dfs(1); int ans = 0; for(int i = 1;i <= n;i++) Insert(d[i]); for(int i = 1;i <= n;i++) ans = max(ans,search(d[i])); printf("%d\n",ans); } int main(){ //freopen("123.txt","r",stdin); n = getInt(); for(int i = 1,x,y,z;i < n;i++){ x = getInt(); y = getInt(); z = getInt(); addEdge(x,y,z); addEdge(y,x,z); } solve(); }
- 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
