第十四届蓝桥杯省赛 Python B 组 I 题——异或和（AC）

🕗 发布于 2024-01-16 11:59 蓝桥杯 python 数据结构 c++ java

1. 异或和

前置知识点：树状数组，线段树，DFS 序。

1. 问题描述

给一棵含有 $n$ 个结点的有根树，根结点为 $1$ ，编号为 $i$ 的点有点权 $a_i$ （ $\in [1,n]$ ）。现在有两种操作，格式如下：

$1\ x\ y$ ：该操作表示将点 $x$ 的点权改为 $y$ 。
$2\ x$ ：该操作表示查询以结点 $x$ 为根的子树内的所有点的点权的异或和。

现有长度为 $m$ 的操作序列，请对于每个第二类操作给出正确的结果。

2 .输入格式

输入的第一行包含两个正整数 $n, m$ ，用一个空格分隔。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ，相邻整数之间使用一个空格分隔。

接下来 $n - 1$ 行，每行包含两个正整数 $u_i,v_i$ ，表示结点 $u_i$ 和 $v_i$ 之间有一条边。

接下来 $m$ 行，每行包含一个操作。

3. 输出格式

输出若干行，每行对应一个查询操作的答案。

4. 样例输入

5. 样例输出

4
5
6

6. 评测用例规模与约定

对于 $30$ % 的评测用例， $\leq 1000$ ；

对于所有评测用例， $\leq n,m \leq 100000$ ， $\leq a_i,y \leq 100000$ ， $\leq u_i,v_i,x \leq n$ 。

7. 原题链接

异或和

2. 解题思路

考虑第二个操作，查询以节点 $x$ 为根的子树内的所有点的点权的异或和。

类似这种子树查询问题，我们通常使用 DFS 序对树进行预处理。具体地说，在 DFS 遍历中，我们从根节点开始，依次遍历它的每个子节点。对于每个子节点，我们首先遍历它的子树，然后回溯到该子节点，继续遍历它的兄弟节点。在遍历的过程中，我们可以记录每个节点在 DFS 序中的遍历顺序，即第一次遍历到该节点的时间戳和最后一次遍历到该节点的时间戳。这里的时间戳可以使用一个计数器来实现，每次遍历到一个新节点时，计数器加 $1$ ，表示当前节点的时间戳。当回溯到该节点时，表示当前节点的最后一次遍历时间戳。

这样操作有什么作用呢？假设我们有一个长度大于 $n$ 的数组 $a$ ，我们记进入每个点 $i$ 的时间戳为 $\text{in}[i]$ ，回溯到点 $i$ 的时间戳为 $\text{out}[i]$ ，同时将每个点的点权赋值到 $a[\text{in}[i]]$ 上。这样对于一个根为 $x$ 的子树内所有点的点权异或和就等价于 $a$ 数组区间 $[\text{in}[x],\text{out}[x]]$ 的异或和。这样我们就将复杂的树上询问，转化为我们熟悉的数组区间查询问题。

接下来考虑操作 $1$ ，将点 $x$ 的点权改为 $y$ 。

结合上述分析，该操作即是将 $a[\text{in}[x]]$ 改为 $y$ 。

综上所述，我们需要对 $a$ 数组进行一个单点修改和区间查询的操作，这个经典操作我们可以使用树状数组或者线段树来维护，代码中使用的是树状数组。具体地说，我们使用一个树状数组 $a$ 来维护树的 DFS 序的前缀异或序列， $a_i$ 表示区间 $[1, i]$ 的异或和。

操作 $1$ ：将 $a[\text{in}[x]]$ 修改为 $y$ 。
操作 $2$ ：求解 $[\text{in}[x],\text{out}[x]]$ 的异或和，根据异或性质 $\oplus[1,l-1]=[l,r]$ ，我们只需要求解 $a_{\text{in}[x]-1} \oplus a_r$ 即可求得答案。

时间复杂度为 $\log n)$ 。

3. AC_Code

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

template <typename T>
struct Fenwick {
int n;
std::vector<T> a;

Fenwick(int n = 0) {
init(n);
}

void init(int n) {
this->n = n;
a.assign(n + 1, T());
}

void add(int x, T v) {
for (; x <= n; x += x & (-x)) {
a[x] ^= v;
}
}

T sum(int x) {
auto ans = T();
for (; x; x -= x & (-x)) {
ans ^= a[x];
}
return ans;
}

T rangeSum(int l, int r) {
return sum(r) ^ sum(l);
}
};
int n, m, tot;
int a[N], in[N], out[N];
std::vector<int> e[N];
void dfs(int u, int fa) {
in[u] = ++tot;
for (auto v : e[u]) {
if (v == fa) continue;
dfs(v, u);
}
out[u] = tot;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
Fenwick<int> tr(n);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; ++i) tr.add(in[i], a[i]);
int op, x, y;
for (int i = 0; i < m; ++i) {
cin >> op >> x;
if (op == 1) {
cin >> y;
int v = tr.rangeSum(in[x] - 1, in[x]);
tr.add(in[x], y ^ v);
} else {
cout << tr.rangeSum(in[x] - 1, out[x]) << '\n';
}
}
return 0;
}

Java

import java.util.*;
import java.io.*;
 
public class Main {
    static int N = 100010;
    static int n, m, tot;
    static int[] a = new int[N], in = new int[N], out = new int[N], b = new int[N];
    static List<Integer>[] e = new List[N];
 
    static void add(int x, int v) {
        for (; x <= n; x += x & (-x)) {
            b[x] ^= v;
        }
    }
 
    static int sum(int x) {
        int ans = 0;
        if (x == 0) return 0;
        for (; x > 0; x -= x & (-x)) {
            ans ^= b[x];
        }
        return ans;
    }
 
    static int rangeSum(int l, int r) {
        return sum(r) ^ sum(l);
    }
 
    static void dfs(int u, int fa) {
        in[u] = ++tot;
        for (int v : e[u]) {
            if (v == fa) continue;
            dfs(v, u);
        }
        out[u] = tot;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = reader.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        temp = reader.readLine().split(" ");
        for (int i = 1; i <= n; ++i) {
            a[i] = Integer.parseInt(temp[i - 1]);
            e[i]=new ArrayList<>();
        }
        for (int i = 0; i < n - 1; ++i) {
            temp = reader.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);
            e[u].add(v);
            e[v].add(u);
        }
        dfs(1, 0);
        for (int i = 1; i <= n; ++i) {
            add(in[i], a[i]);
        }
        for (int i = 0; i < m; ++i) {
            temp = reader.readLine().split(" ");
            int op = Integer.parseInt(temp[0]);
            int x = Integer.parseInt(temp[1]);
            if (op == 1) {
                int y = Integer.parseInt(temp[2]);
                int v = rangeSum(in[x] - 1, in[x]);
                add(in[x], y ^ v);
            } else {
                writer.write(rangeSum(in[x] - 1, out[x]) + "\n");
            }
        }
        reader.close();
        writer.flush();
        writer.close();
    }
}

Python

import sys

N = 100010
n, m, tot = 0, 0, 0
a = [0]*N
in_ = [0]*N
out = [0]*N
b = [0]*N
e = [[] for _ in range(N)]

def add(x, v):
    while x <= n:
        b[x] ^= v
        x += x & (-x)

def sum_(x):
    ans = 0
    if x == 0:
        return ans
    while x > 0:
        ans ^= b[x]
        x -= x & (-x)
    return ans

def rangeSum(l, r):
    return sum_(r) ^ sum_(l)

def dfs(u, fa):
    global tot
    in_[u] = tot = tot + 1
    for v in e[u]:
        if v == fa:
            continue
        dfs(v, u)
    out[u] = tot

def main():
    global n, m, tot
    n, m = map(int, sys.stdin.readline().split())
    a[1:n+1] = map(int, sys.stdin.readline().split())
    for _ in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        e[u].append(v)
        e[v].append(u)
    dfs(1, 0)
    for i in range(1, n+1):
        add(in_[i], a[i])
    for _ in range(m):
        op, x, *extra = map(int, sys.stdin.readline().split())
        if op == 1:
            y = extra[0]
            v = rangeSum(in_[x] - 1, in_[x])
            add(in_[x], y ^ v)
        else:
            print(rangeSum(in_[x] - 1, out[x]))

if __name__ == "__main__":
    main()

原文地址：https://blog.csdn.net/m0_57487901/article/details/135619052

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：复旦、交大、清华等公布2023届本科生毕业数据
下一篇：精心挑选免费好用的api，推荐给大家

大数据机器学习算法与计算机视觉应用02：线性规划
在零和博弈中，是概率和对应收益乘积的总和（收益给定），在最大流问题中，是通往终点所有流量的总和。卡马卡方法又被称作内部点方法，它寻找最优解的方法并非从可行域边界的一个顶点出发，而是从可行域内部的一个点
阅读更多2024-11-15
Python学习------第八天
num = int (input("请输入您想存入多少钱：请输入："))print(f"{name},你好，你的余额剩余:{money}元")num = in
阅读更多2024-11-15
【qt】控件
frameGeometry是开始从红圈开始算，Geometry从黑圈算程序证明：使用一个按键，当按键按下,qdebug打印各自左上角的坐标（相当于屏幕左上角），以及窗口大小视频演示：frameGeom
阅读更多2024-11-15
Jupyter notebook如何加载torch环境
Jupyter notebook如何加载torch环境
阅读更多2024-11-15
「QT」文件类之 QDataStream 数据流类
QDataStream是Qt框架中的一个类，它提供了基于Qt数据类型的二进制流接口。通过QDataStream，可以方便地将Qt的基本数据类型（如整型、浮点型、字符串等）以及自定义的Qt对象序列化（即
阅读更多2024-11-15
在vue项目中使用SM4加密登录
在 utils 文件夹中创建 sm4Util.js 文件。
阅读更多2024-11-15
力扣654：最大二叉树
力扣654：最大二叉树。C语言
阅读更多2024-11-15
Linux各种解压命令汇总
最常用的是.tar.gz，原因：linux各种版本标准压缩方式，几乎各大版本可以直接用；【注意】：.tar不是压缩的格式，tar只是按照一定的格式将所有的文件打包在一起。压缩目录tar cf - te
阅读更多2024-11-15
命令行打包Java工程
表示跳过测试可用于指定本地maven仓库路径。
阅读更多2024-11-15
web服务器
web 服务器提供的这些数据大部分都是文件，那么我们需要在服务器端先将数据文件写好，并且放置在某个特殊的目录下面，这个目录就是我们整个网站的首页，在nginx 中，这个目录默认在浏览器是通过你在地址栏
阅读更多2024-11-15