2017 ICPC网络赛(西安)--- Xor
2019-05-04 09:39:17来源:博客园 阅读 ()
题目连接
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 */
原文链接:https://www.cnblogs.com/chen9510/p/10800247.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:c/c++ socket函数详解
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架:gevent 2020-06-05
- windows7 + Qt(MSVC2017) + VS2019安装配置 2020-04-25
- 2020年04月10日UCF Local Programming Contest 2017 2020-04-10
- 【新年呈献】高性能网络通信框架 HP-Socket v5.7.1 2020-01-07
- 最小割最大流定理&残量网络的性质 2019-12-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash