洛谷-算法2-4-字符串2

P4551 最长异或路径题目描述给定一棵 n 个点的带权树结点下标从 1 开始到 n。求树中所有异或路径的最大值。异或路径指树上两个结点之间唯一路径上的所有边权的异或值。输入格式第一行一个整数 n表示结点数。接下来 n−1 行给出 u,v,w 分别表示树上的 u 点和 v 点有连边边的权值是 w。输出格式一行一个整数表示答案。输入输出样例输入 #1复制4 1 2 3 2 3 4 2 4 6输出 #1复制7说明/提示当两个结点分别是 1,3 时答案是 73⊕4取最大值。数据范围1≤n≤105;0u,v≤n;0≤w231。实现代码#includebits/stdc.h using namespace std; struct qwq{ int v; int w; int nxt; }edge[2000001]; int head[2000001]; int cnt-1; void add(int u,int v,int w){ edge[cnt].nxthead[u]; edge[cnt].vv; edge[cnt].ww; head[u]cnt; } int sum[2000001]; void dfs(int x,int fa){ for(int ihead[x];~i;iedge[i].nxt){ int vedge[i].v; int wedge[i].w; if(v!fa){ sum[v]sum[x]^w; dfs(v,x); } } } struct trie{ int ch[2]; }t[2000001]; int tot; void build(int val,int x){ for(int i(130);i;i1){ bool cvali; if(!t[x].ch[c]){ t[x].ch[c]tot; } xt[x].ch[c]; } } int query(int val,int x){ int ans0; for(int i(130);i;i1){ bool cvali; if(t[x].ch[!c]){ ansi; xt[x].ch[!c]; } else xt[x].ch[c]; } return ans; } int main(){ memset(head,-1,sizeof(head)); int n; scanf(%d,n); for(int i1;in;i){ int u,v,w; scanf(%d%d%d,u,v,w); add(u,v,w); add(v,u,w); } dfs(1,-1); for(int i1;in;i)build(sum[i],0); int ans0; for(int i1;in;i){ ansmax(ans,query(sum[i],0)); } printf(%d\n,ans); }P5283 [十二省联考 2019] 异或粽子题目描述小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。小粽面前有 n 种互不相同的粽子馅儿小粽将它们摆放为了一排并从左至右编号为 1 到 n。第 i 种馅儿具有一个非负整数的属性值 ai​。每种馅儿的数量都足够多即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 k 个粽子。小粽的做法是选两个整数数 l, r满足 1⩽l⩽r⩽n将编号在 [l,r] 范围内的所有馅儿混合做成一个粽子所得的粽子的美味度为这些粽子馅儿的属性值的异或和。异或就是我们常说的 xor 运算即 C/C 中的ˆ运算符或 Pascal 中的xor运算符小粽想品尝不同口味的粽子因此她不希望用同样的馅儿的集合做出一个以上的粽子。小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧输入格式第一行两个正整数 n, k表示馅儿的数量以及小粽打算做出的粽子的数量。接下来一行为 n 个非负整数第 i 个数为 ai​表示第 i 个粽子的属性值。 对于所有的输入数据都满足1⩽n⩽5×105, 1⩽k⩽min{2n(n−1)​,2×105}, 0⩽ai​⩽4294967295。输出格式输出一行一个整数表示小粽可以做出的粽子的美味度之和的最大值。输入输出样例输入 #1复制3 2 1 2 3输出 #1复制6说明/提示测试点nk1, 2, 3, 4, 5, 6, 7, 8⩽103⩽1039, 10, 11, 12⩽5×105⩽10313, 14, 15, 16⩽103⩽2×10517, 18, 19, 20⩽5×105⩽2×105实现代码#includeiostream #includecstdio #includecstring #includequeue using namespace std; const int N2000000010; struct Node{int id,rk;long long w;bool operator (const Node a)const{return wa.w;}}; priority_queueNodeq; long long ans1,x,s[N]; int a[N][2],size[N],n,m,tot; void ins(long long x) { int u0; for(int i31;i0;i--) { int ch(xi)1;size[u]; if(!a[u][ch])a[u][ch]tot; ua[u][ch]; } size[u]; } long long query(long long x,int rk) { int u0;long long ans0; for(int i31;i0;i--) { int ch(xi)1; if(!a[u][ch^1])ua[u][ch]; else if(rksize[a[u][ch^1]])ua[u][ch^1],ans|1LLi; else rk-size[a[u][ch^1]],ua[u][ch]; } return ans; } long long getin() { long long x0;char chgetchar(); while(ch0||ch9)chgetchar(); while(ch0ch9)xx*10ch-48,chgetchar(); return x; } int main() { ngetin(),mgetin();m1; for(int i1;in;i)xgetin(),s[i]s[i-1]^x; for(int i0;in;i)ins(s[i]); for(int i0;in;i)q.push((Node){i,1,query(s[i],1)}); for(int i1;im;i) { Node tq.top();anst.w;q.pop(); if(t.rkn)q.push((Node){t.id,t.rk1,query(s[t.id],t.rk1)}); } cout(ans1)endl; }P1470 [IOI 1996 / USACO2.3] 最长前缀 Longest Prefix题目描述在生物学中一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列即元素很感兴趣。如果一个集合 P 中的元素可以串起来元素可以重复使用组成一个序列 S那么我们认为序列 S 可以分解为 P 中的元素。元素不一定要全部出现如下例中BBC就没有出现。举个例子序列ABABACABAAB可以分解为下面集合中的元素{A,AB,BA,CA,BBC}。序列 S 的前面 k 个字符称作 S 中长度为 k 的前缀。设计一个程序输入一个元素集合以及一个大写字母序列设 S′ 是序列 S 的前缀使其可以分解为给出的集合 P 中的元素求 S′ 的长度 k 的最大值。输入格式输入数据的开头包括若干个元素组成的集合 P用连续的以空格分开的字符串表示。字母全部是大写数据可能不止一行。元素集合结束的标志是一个只包含一个.的行集合中的元素没有重复。接着是大写字母序列 S用字符串表示每 76 个字符换一行。输出格式只有一行输出一个整数表示 S 符合条件的前缀的最大长度。输入输出样例输入 #1复制A AB BA CA BBC . ABABACABAABC输出 #1复制11说明/提示【数据范围】对于 100% 的数据1≤card(P)≤2001≤∣S∣≤2×105P 中的元素长度均不超过 10。翻译来自 NOCOW。实现代码#include iostream #include set #include cstring using namespace std; int dp[200005],m; setstring s[20]; int main(){ string tp; while (cintp){ if (tp.) break; s[tp.size()].insert(tp); mmax(m,int(tp.size())); } int i,ans0; dp[0]1; string n; n ; while (cintp){ nntp; } for (i1;in.size();i){ for (int jmin(i,m);j1;j--){ string ttn.substr(i-j1,j); if (s[tt.size()].count(tt)1dp[i-j]1){ ansi; dp[i]1; break; } } } coutans; }CF25E Test题目描述给定 3 个字符串 s1​,s2​,s3​试求一个字符串使 s1​,s2​,s3​ 都是这个字符串的子串并使这个字符串最短。输出最短字符串的长度 l。输入格式第一行输入一个字符串表示 s1​。第二行输入一个字符串表示 s2​。第三行输入一个字符串表示 s3​。输出格式第一行输出一个正整数表示答案 l。显示翻译题意翻译输入输出样例输入 #1复制ab bc cd输出 #1复制4输入 #2复制abacaba abaaba x输出 #2复制11说明/提示1≤∣s1​∣,∣s2​∣,∣s3​∣≤105。实现代码#include cstdio #include cstring #define min(a,b) ((a)(b))?(a):(b) using namespace std; const int INF2147483646; int nxt[4][100050],l[4]; char s[4][100050]; inline void Pre(){ for(int f1;f4;f){ int p0,lenl[f]; for(int i2;ilen;i){ while(ps[f][i]!s[f][p1]) pnxt[f][p]; if(s[f][i]s[f][p1]) p; nxt[f][i]p; } } return ; } int f(int a,int b,int c){ int ansINF,p10; int all[a],bll[b],cll[c]; for(int i1;ial;i){ while(p1s[b][p11]!s[a][i]) p1nxt[b][p1]; if(s[b][p11]s[a][i]) p1; if(p1bl){ p1-1; break; } } if(p1-1){ int p0; for(int i1;ial;i){ while(ps[c][p1]!s[a][i]) pnxt[c][p]; if(s[c][p1]s[a][i]) p; if(pcl){ p-1; break; } } if(p-1) ansal; else ansalcl-p; } else{ int p0; for(int i1;ial;i){ while(ps[c][p1]!s[a][i]) pnxt[c][p]; if(s[c][p1]s[a][i]) p; if(pcl){ p-1; break; } } if(p!-1){ int p2p; for(int ip11;ibl;i){ while(p2s[c][p21]!s[b][i]) p2nxt[c][p2]; if(s[c][p21]s[b][i]) p2; if(p2cl){ p2-1; break; } } if(p2-1) ansalbl-p1; else ansalbl-p1 cl -p2; } else ansalbl-p1; } return ans; } int main(){ scanf(%s%s%s,s[1]1,s[2]1,s[3]1); int ansINF; l[1]strlen(s[1]1);l[2]strlen(s[2]1);l[3]strlen(s[3]1); Pre(); ansmin(ans,f(1,2,3));ansmin(ans,f(1,3,2)); ansmin(ans,f(2,1,3));ansmin(ans,f(2,3,1)); ansmin(ans,f(3,2,1));ansmin(ans,f(3,1,2)); printf(%d,ans); return 0; }