pMath女士中考后玩固然开心但你的训练怎么办呢P3294 [SCOI2016] 背单词 - 洛谷 (luogu.com.cn)看错题但我觉得可能不是我的问题。教练使用了原版题意意义不明导致我卡了一个小时。字典树 一点点小贪心。赛后 1h 重新读题重构 ac 了#includebits/stdc.h using namespace std; typedef long long LL; const int N 5e5 10; int ch[N][30]; int id; string s[N]; int ed[N], ped[N], led[N]; int rd[N]; void ins(string ss, int x) { int p 0; for (int i 0; ss[i]; i ) { int j ss[i] - a; if (ch[p][j] 0) { id ; ch[p][j] id; } p ch[p][j]; } ed[p] x; } vectorint G[N]; void dfs(int p, int fa) { if(ed[p]) { G[fa].push_back(p); // 只连接到最近的后缀 fa p; } for(int i 0; i 26; i) { if(ch[p][i]) dfs(ch[p][i], fa); } } int dfn[N]; int siz[N]; int tsp; LL ans; void dfsa(int x) { siz[x] 1; for (int y : G[x]) { dfsa(y); siz[x] siz[y]; } } bool cmp(int na, int nb) { return siz[na] siz[nb]; } void dfsb(int x, int fa) { dfn[x] tsp; ans dfn[x] - dfn[fa]; sort(G[x].begin(), G[x].end(), cmp); for (int y : G[x]) { dfsb(y, x); } } signed main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; id 0; memset(ch, 0, sizeof(ch)); memset(ed, 0, sizeof(ed)); for (int i 1; i n; i ) { cin s[i]; reverse(s[i].begin(), s[i].end()); ins(s[i], i); } dfs(0, 0); memset(siz, 0, sizeof(siz)); dfsa(0); memset(dfn, 0, sizeof(dfn)); tsp 0; ans 0; dfsb(0, 0); cout ans \n; return 0; }P3292 [SCOI2016] 幸运数字 - 洛谷 (luogu.com.cn)忘了线性基赛时打了个差不多的没调出来最好是差不多。【模版】线性基相关贪心模板和高斯消元第 K 小-CSDN博客知道线性基后就很简单了。1.题目里图是棵树树上两点间路径唯一且由两点的 LCA 到两点的直接距离构成。2.要求路径上所有点构成的线性基从而求出最大异或和。3.将一个集合分开成两部分单独求线性基再合并和整个集合求线性基两者求出的结果相同不影响异或和运算。4.将从根节点到节点 x 路径上所有点的线性基存在 p[x][] 里将线性基对应的点编号存在 pos[x][]。5.当有两个点都能构成节点 x 二进制第 i 位的线性基时优先选 dep 大的深层的点。为什么这样贪心因为合并线性基时只有 dep LCA dep 的才可以被纳入即在路径上所以我们选择尽量深的基dep 更大更容易被选6.合并根节点到 x 和根节点到 y 的基时只能选择 dep LCA dep 的不然不在路径上。详见注释代码#includebits/stdc.h using namespace std; typedef long long LL; const int N 2e4 10; const int D 63; LL a[N]; vectorint G[N]; int dep[N]; int pos[N][D]; LL p[N][D]; int f[N][D]; void insert(int x, int fa) { for (int i 0; i 60; i ) { p[x][i] p[fa][i]; pos[x][i] pos[fa][i]; } LL X a[x]; int P x; for (int i 60; i 0; i --) if (X (1ll i)) { if (!p[x][i]) { p[x][i] X; pos[x][i] P; return ; } if (dep[pos[x][i]] dep[P]) { swap(pos[x][i], P); swap(p[x][i], X); } X ^ p[x][i]; } } void dfs(int x, int fa) { dep[x] dep[fa] 1; f[x][0] fa; for (int i 1; i 15; i ) { f[x][i] f[f[x][i - 1]][i - 1]; } insert(x, fa); for (int y : G[x]) if (y ! fa) { dfs(y, x); } } int LCA(int x, int y) { if (dep[x] dep[y]) { swap(x, y); } for (int i 15; i 0; i --) { if (dep[f[x][i]] dep[y]) { x f[x][i]; } } if (x y) { return x; } for (int i 15; i 0; i --) { if (f[x][i] ! f[y][i]) { x f[x][i]; y f[y][i]; } } return f[x][0]; } LL b[D]; LL query(int x, int y) { memset(b, 0, sizeof(b)); int lca LCA(x, y); for (int i 60; i 0; i --) { // 先将 p[x] 里符合条件插到 b 数组里 if (dep[pos[x][i]] dep[lca]) { b[i] p[x][i]; } } for (int i 60; i 0; i --) { // 合并 p[y] 里的线性基 if (dep[pos[y][i]] dep[lca]) { LL X p[y][i]; for (int j i; j 0; j --) if (X (1ll j)) { if (!b[j]) { b[j] X; break; } X ^ b[j]; } } } LL ans 0; for (int i 60; i 0; i --) if ((ans ^ b[i]) ans) { ans ^ b[i]; } return ans; } int main () { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin n q; for (int i 1; i n; i ) { cin a[i]; } for (int i 1; i n; i ) { int x, y; cin x y; G[x].push_back(y); G[y].push_back(x); } dep[0] 0; memset(p, 0, sizeof(p)); memset(f, 0, sizeof(f)); dfs(1, 0); for (int i 1; i q; i ) { int x, y; cin x y; cout query(x, y) \n; } return 0; }P3295 [SCOI2016] 萌萌哒 - 洛谷 (luogu.com.cn)#includebits/stdc.h using namespace std; typedef long long LL; const int N 100005; const LL P 1e9 7; int fa[N][20]; // fa[i][k] 表示从位置 i 开始长度为 2^k 的区间块的代表元 // 18 是因为 2^17 131072 1e5所以够用 int findfa(int x, int k) { if (fa[x][k] x) { return fa[x][k]; } return fa[x][k] findfa(fa[x][k], k); } // 并查集合并,将两个长度为 2^k 的块合并到同一个集合 void merge(int x, int y, int k) { x findfa(x, k); y findfa(y, k); if(x ! y) { fa[x][k] y; // 将 x 的根指向 y 的根 } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; int D floor(log2(n)); // 最大的块大小 // 初始化每个块单独成一个集合 for (int i 1; i n; i ) { for (int k 0; k D; k ) { fa[i][k] i; } } /* 对于每个条件[l1, r1] [l2, r2] 用二进制拆分的方法将区间拆成若干个长度为 2 的幂次的块 并合并对应的块 */ for (int i 1; i m; i ) { int la, ra, lb, rb; cin la ra lb rb; // 从大到小枚举 k贪心地拆分区间 for (int k D; k 0; k --) { // 如果当前区间还能分出一个长度为 2^k 的块 if (la (1 k) - 1 ra) { merge(la, lb, k); // 合并这两个长度为 2^k 的块 la 1 k; // 移动指针到下一个未处理的位置 lb 1 k; } } } /* 将高层的相等关系传递到低层 如果两个长度为 2^k 的块相等那么它们的前半段和后半段也分别相等 即(x, k) (y, k) (x, k-1) (y, k-1) 且 (x2^(k-1), k-1) (y2^(k-1), k-1) */ for (int k D; k 1; k --) { // 从最高层向低层递推 for (int i 1; i (1 k) - 1 n; i) { int pos findfa(i, k); // 找到 i 所在长度为 2^k 块的根 // 实际上是将根所在块的信息下推给所有成员 // 注意这里是把 i 和 pos 的前半段合并后半段也合并 merge(i, pos, k - 1); merge(i (1 (k - 1)), pos (1 (k - 1)), k - 1); } } /* 统计答案 现在所有的相等关系已经传递到第 0 层即单个字符层 fa[i][0] 就表示位置 i 最终属于哪个等价类 */ LL ans 0; for (int i 1; i n; i ) { if (fa[i][0] i) { // 找到一个新的等价类根节点 // 第一个位置最高位不能为 0所以第一个等价类有 9 种选择 // 其他等价类有 10 种选择0-9 if (ans 0) { ans 9; } else { ans ans * 10ll % P; } } } cout ans \n; return 0; }