第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛 B题 跳一跳,很简单的(字符串Hash + 树上路径倍增)
2024-08-29 00:56:20
考虑到每条边的权值变化$26$个时刻之后一定会回到原来的状态。
那么预处理出前$26$个时刻每棵树的形态,对每棵树做一遍字符串哈希。
查询的时候找到满足$x$往上爬$k$步和$y$往上爬$k$步之后面对的边的边权不一样的时候的$k$的最小值。
那么比较这条不一样的边的权值就好了。这个过程用倍增实现即可。
时间复杂度$O(nlogn)$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef unsigned long long LL; const int N = 1e5 + 10;
const int A = 20;
const LL base = 233; int T;
int n, q;
int a[N], c[N], deep[N], f[N][A], g[26][N];
LL val[30];
LL bin[N], h[29][N];
LL seed = 87378051;
vector <int> v[N]; inline LL rnd(){ return seed = seed * 17 + 23;} void dfs(int x, int dep){
deep[x] = dep; for (auto u : v[x]){
int w = a[u];
rep(i, 0, 25){
int z = (w + i * c[u]) % 26;
g[i][u] = z;
h[i][u] = h[i][x] * base + val[z];
}
dfs(u, dep + 1);
}
} int main(){ rep(i, 0, 26) val[i] = rnd() * rnd() * rnd();
bin[0] = 1;
rep(i, 1, 1e5 + 1) bin[i] = bin[i - 1] * base; scanf("%d", &T);
while (T--){
memset(f, 0, sizeof f);
memset(h, 0, sizeof h);
memset(g, 0, sizeof g);
scanf("%d", &n);
rep(i, 0, n + 1) v[i].clear();
rep(i, 2, n){
int x, k;
char ch[2];
scanf("%d%s%d", &x, ch, &k);
a[i] = ch[0] - 'a';
c[i] = k;
f[i][0] = x;
v[x].push_back(i);
} rep(i, 0, 25) g[i][1] = -1;
dfs(1, 0); rep(i, 1, n) rep(j, 0, 18) f[i][j + 1] = f[f[i][j]][j]; scanf("%d", &q);
while (q--){
int x, y, t;
scanf("%d%d%d", &x, &y, &t);
t %= 26; int dep = min(deep[x], deep[y]);
int z = 1, m = 0;
for (; (z << 1) <= dep; z <<= 1) ++m; dec(i, m, 0){
int fx = f[x][i], fy = f[y][i];
int now = 1 << i;
LL hx = h[t][x] - h[t][fx] * bin[now];
LL hy = h[t][y] - h[t][fy] * bin[now];
if (hx == hy){
x = fx;
y = fy;
}
} if (g[t][x] < g[t][y]) puts("<");
else if (g[t][x] > g[t][y]) puts(">");
else puts("=");
}
} return 0; }
最新文章
- IBM X3850 Windows 无法安装到这个磁盘。选中的磁盘具有MBR分区表。在 EFI 系统上,Windows 只能安装到 GPT 磁盘
- 最简实例说明wait、notify、notifyAll的使用方法
- vs 2012 智能提示后为何不能 直接按enter键把提示的内容输入
- 【img】 图片是怎么存储的
- IOS版UC我的视频地址
- POJ2689 - Prime Distance(素数筛选)
- C#实现发送邮件
- Spring事务隔离级别与传播机制详解,spring+mybatis+atomikos实现分布式事务管理
- [转载] ZooKeeper原理及使用
- RecyclerView 实现gallery画廊效果
- Ubuntu版本linux系统安装git
- h5-audio/video标签
- css背景色半透明的最佳实践
- LA 2218 Triathlon(半平面交)
- 用命令bat打开某个文件或文件夹
- 解决git中文乱码问题
- 8.4 正睿暑期集训营 Day1
- 解决appcompat中各种奇葩的错误
- Mock 模拟测试简介及 Mockito 使用入门
- 使用webbench做压力测试