首页 > Xor Path

lifehappy

发表于 2020-07-29 15:22:04

Xor Path 思路先是看错题目，以为是所有的路径异或值的和，然后好像用了个假的print函数，一直wa，，，既然是异或，那么当一个点出现的次数是偶数次的时候它会被自己异或成零，也就是队整体的答案没有贡献度，所以我们只要统计有多少条路经过了这个点就行了。我们得到一个节点的每一个儿子的节点数量，展开全文

998244353

发表于 2020-07-29 21:05:04

题意：给定一棵个点的树，每个点有点权，问树上所有两点之间的最短路径异或和为多少，即求树上所有两点的路径所经过的点的点权的异惑和。题解：既然是考虑异或和，那么就要考虑一个点是否对答案有贡献。考虑一个点在所有路径中出现的次数，由异或的性质，可以知道当一个点在所有路径中出现总次数为偶数时，则对答案无贡献展开全文

zzugzx

发表于 2020-07-29 12:40:33

题目链接题意：题解： AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; 展开全文

程序蒟蒻

发表于 2020-08-14 21:23:17

https://ac.nowcoder.com/acm/problem/20857?&headNav=acm 思路： #include<iostream> #include<string> #include<math.h 展开全文

CoolGuang!

发表于 2020-07-29 14:06:40

介绍两种思路，一种被卡掉了注意一下这个异或和是指所有path(i,j)的异或首先从一个根出发，算出跟到点x的路径异或为b[x] 那么对于两点的path(i,j)的答案即为：b[x]^b[y]^a[lca] 由于最终答案又是异或也就是说path(i,j)表示为三个数异或然后在异或显然对于每一个展开全文

sunrise__sunrise

发表于 2020-07-29 16:34:23

题目意思 Solution #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include &l 展开全文

hnust_yangyanjun

发表于 2020-08-08 22:29:30

题意：有一棵n个节点的树，树的每一个节点有一个权值，定义path(i,j)表示 i 到 j 的最短路径上，所有点的点权异或和。求所有path(i,j)的异或和。思路：我们可以统计一个点被计算了多少次来求解，一个节点x，以x为终点的path有（n-1）条，然后包括它的路径与它的子树有关，一棵子树的节展开全文

blowhail

发表于 2020-08-03 17:03:47

因为要求所有路径的异或和，而异或又有个特殊性质a xor a =0因此只需要求每个点在最短路径上的出现次数可以通过计算与点相连的边的经过次数来计算点的次数 #include <cstdio> #include <iostream> #include <algorithm 展开全文

Severus.

发表于 2020-07-29 23:57:58

题目描述给定一棵n个点的树，每个点有权值。定义表示到的最短路径上，所有点的点权异或和。对于，求所有的异或和。输入描述: 第一行一个整数n。接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。第n+1行有n个整数，表示每个点的权值。输出描述: 输出一个整数，表示所有的异展开全文

昵称很长很长真是太好了

发表于 2020-07-31 23:10:35

题解：首先我们知道，一个点肯定不可能只出现一次的，他会出现好多次，但是根据二进制a xor a =0a xor a xor a =a所以我们发现当某个点出现的次数为偶数次时，这个点相当于没有出现过，奇数次时，答案异或一下这个点的权值即可。没有见过这种题的建议先看求树上任意两点之间距离之和的平均值这个展开全文

查看本题

查看本题讨论

等你来战

查看全部

衡阳师范学院第二十五届程序设计竞赛（同步赛）

报名截止时间：2025-06-08 18:00
2025牛客暑期多校训练营1

报名截止时间：2025-07-15 17:00

相关比赛

等你来战