【记录】「SCOI2016」三道模拟赛/26.7.12

pMath女士，中考后玩固然开心，但你的训练怎么办呢？

P3294 [SCOI2016] 背单词 - 洛谷 (luogu.com.cn)

看错题，但我觉得可能不是我的问题。

教练使用了原版题意，意义不明，导致我卡了一个小时。

字典树 + 一点点小贪心。

赛后 1h 重新读题+重构 ac 了：

#include<bits/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; } vector<int> 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 的，不然不在路径上。

详见注释代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e4 + 10; const int D = 63; LL a[N]; vector<int> 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)

#include<bits/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) 且 (x+2^(k-1), k-1) == (y+2^(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; }