2017 ICPC网络赛(西安)--- Xor
程序员文章站
2023-09-09 18:18:31
题目连接 Problem There is a tree with n nodes. For each node, there is an integer value ai, (1≤ai≤1,000,000,000 for 1≤i≤n). There is q queries which are ......
problem
there is a tree with n nodes. for each node, there is an integer value ai, (1≤ai≤1,000,000,000 for 1≤i≤n). there is q queries which are described as follow:
assume the value on the path from node a to node b is t0,t1,⋯tm. you are supposed to calculate t0 xor tk xor t2k xor ... xor tpk (pk≤m).
input format
there are multi datasets. (∑n≤50,000,∑q≤500,000).
for each dataset: in the first n−1 lines, there are two integers u,v, indicates there is an edge connect node uand node v.
in the next nn lines, there is an integer ai (1≤ai≤1,000,000,000).
in the next q lines, there is three integers a,b and k. (1≤a,b,k≤n).
output format
for each query, output an integer in one line, without any additional space.
样例输入
5 6
1 5 4 1 2 1 3 2 19 26 0 8 17 5 5 1 1 3 2 3 2 1 5 4 2 3 4 4 1 4 5
样例输出
17
19 26 25 0 19
题意: 有一棵n个节点的树,每个节点上有个权值vi,现在q次询问:节点a到节点b的路径上,从a开始每k个节点跳一次所经过的所有节点的异或值为(a0,ak,a2k,a3k...)?
思路: 建树,倍增算法记录每个节点的深度和2^i的祖先,处理并记录每个节点i到根节点间隔为k(1,2,3……100)的异或值dp[i][k]。当k<=100时,使用记录的异或值dp计算a到b间隔为k的异或值;当k>100时,直接从a走到b,每次跳动使用倍增的信息(快速跳动)。
注:这道题是2017年打西安网络赛时没过的题,当时其实代码写的很接近了,测数据都没问题,一直检查不出来,我也一直惦记着这道题。本科毕业后读研,又看过一次还是没找出原因,今天五一放假,没啥事儿,我又看了一遍当时写的代码,突然发现没初始化fa数组,心想难道是计蒜客网站编译器不是默认未初始化的值为0?加上fa的初始化后提交了一把,过了!!!
my god! 心心念念的这道题竟然是这个原因没过,气呀。不过,今天总算是找到原因了,哈哈~ 又一次想起来西安正式赛的时候,一道铜牌题没过“lol bp”导致没拿到银牌,可惜的是当时的银牌题都过了,唉~ 与银失之交臂。现在是研究生了,很少刷题了,以后要少看剧,多看看相关的图形学的专业书,充实自己,找个好工作。
代码如下:
1 //https://nanti.jisuanke.com/t/a1273 《xor》 2 #include <iostream> 3 #include <algorithm> 4 #include <cstdio> 5 #include <cstring> 6 using namespace std; 7 const int n = 5e4 + 5; 8 int fa[n][20], deep[n], head[n]; 9 int v[n], cnt; 10 bool vis[n]; 11 int dp[n][105]; 12 struct data 13 { 14 int to, next; 15 }e[2 * n]; 16 17 void insert(int u, int v) 18 { 19 e[++cnt].to = v; 20 e[cnt].next = head[u]; 21 head[u] = cnt; 22 e[++cnt].to = u; 23 e[cnt].next = head[v]; 24 head[v] = cnt; 25 } 26 int cal(int x, int t) 27 { 28 for (int i = 0; i <= 19; i++) 29 if (t&(1 << i)) x = fa[x][i]; 30 return x; 31 } 32 void dfs(int x) 33 { 34 vis[x] = 1; 35 for (int i = 1; i <= 19; i++) 36 { 37 if (deep[x]<(1 << i))break; 38 fa[x][i] = fa[fa[x][i - 1]][i - 1];///倍增处理祖先信息 39 } 40 for (int k = 1; k <= 100; k++) 41 { 42 dp[x][k] = v[x]; 43 if (deep[x]<k) continue; 44 int p = cal(x, k); 45 dp[x][k] ^= dp[p][k]; 46 } 47 for (int i = head[x]; i; i = e[i].next) 48 { 49 if (vis[e[i].to]) continue; 50 deep[e[i].to] = deep[x] + 1; 51 fa[e[i].to][0] = x; 52 dfs(e[i].to); 53 } 54 } 55 int lca(int x, int y)///求lca 56 { 57 if (deep[x]<deep[y]) swap(x, y); 58 x = cal(x, deep[x] - deep[y]); 59 for (int i = 19; i >= 0; i--) 60 if (fa[x][i] != fa[y][i]) 61 { 62 x = fa[x][i]; 63 y = fa[y][i]; 64 } 65 if (x == y)return x; 66 else return fa[x][0]; 67 } 68 69 void init() 70 { 71 cnt = 0; 72 memset(head, 0, sizeof(head)); 73 memset(vis, 0, sizeof(vis)); 74 memset(dp, 0, sizeof(dp)); 75 memset(deep, 0, sizeof(deep)); 76 memset(fa,0,sizeof(fa)); 77 } 78 79 int main() 80 { 81 int n, q; 82 while (scanf("%d%d", &n, &q) != eof) 83 { 84 init(); 85 for (int i = 1; i<n; i++) 86 { 87 int x, y; scanf("%d%d", &x, &y); 88 insert(x, y); 89 } 90 for (int i = 1; i <= n; i++) scanf("%d", &v[i]); 91 dfs(1); 92 while (q--) 93 { 94 int x, y, k; scanf("%d%d%d", &x, &y, &k); 95 int pa = lca(x, y); 96 if (k <= 100) 97 { 98 int ans = dp[x][k]; 99 int h = (deep[x] - deep[pa]) % k; 100 int t = k - h; 101 if (deep[pa] >= t) 102 { 103 int l = cal(pa, t); 104 ans ^= dp[l][k]; 105 } 106 int r = k - h; 107 t = deep[y] - deep[pa] - r; 108 if (t<0) goto endw2; 109 t %= k; 110 y = cal(y, t);/// 111 ans ^= dp[y][k]; 112 t = k - r; 113 if (deep[pa] >= t) 114 { 115 int l = cal(pa, t); 116 ans ^= dp[l][k]; 117 } 118 endw2:; 119 printf("%d\n", ans); 120 } 121 else 122 { 123 int ans = 0; 124 while (1) 125 { 126 ans ^= v[x]; 127 if (deep[x] - k<deep[pa]) break; 128 x = cal(x, k); 129 } 130 int l = k - (deep[x] - deep[pa]); 131 int t = deep[y] - deep[pa] - l; 132 if (t<0) goto endw; 133 t %= k; 134 y = cal(y, t); 135 while (1) 136 { 137 ans ^= v[y]; 138 if (deep[y] - k <= deep[pa]) break; 139 y = cal(y, k); 140 } 141 endw:; 142 printf("%d\n", ans); 143 } 144 } 145 } 146 return 0; 147 } 148 /** 149 8 11 150 1 2 151 2 3 152 2 4 153 1 5 154 5 6 155 5 7 156 4 8 157 3 5 6 2 7 0 1 10 158 1 8 1 159 answer=14 160 */
推荐阅读
-
2017 ICPC网络赛(西安)--- Xor
-
【计蒜客】2018ICPC徐州赛区网络赛H Ryuji doesn't want to study(树状数组)
-
ICPC网络赛 Ryuji doesn't want to study (线段树/树状数组)
-
计蒜客 Trace(2018 ICPC亚洲区域赛网络赛 徐州 G)(线段树)
-
2020ICPC·小米 网络选拔赛热身赛-A.ABBA
-
2017 ACM-ICPC 亚洲区(西安赛区)网络赛 E. Maximum Flow(最大流/规律)
-
2020ICPC·小米网络选拔赛第一场 J.Matrix Subtraction
-
2020ICPC·小米 网络选拔赛第一场 D - Router Mesh(求删掉割点后的连通块数)
-
2020ICPC·小米 网络选拔赛第一场 A Intelligent Warehouse
-
2020ICPC·小米 网络选拔赛热身赛