T1.简单树（easy.cpp） 题目描述 给定一棵 $n$ 个点的树，你需要给每条边赋值 $0$ 或 $1$，求树上所有点对之间的简单路径权值总和的最大值，并输出方案。 一条路径的权值定义为这条路径上所有边权的异或和。 题解 引理 可以知道， $ans(x,y) = ans(x, root) \oplus ans(y, root)$。将树想象成一…

题目链接 长度为 $m$ 的栅栏上，有 $n$ 头牛需要坐车前往别的地方，起点和终点分别为 $a_i$ 和$b_i$ 。现在一辆出租车从最左端 $0$ 出发，要运送完所有牛，最后到达最右端$m$ ，求最小路程。出租车只能一次载一只牛。 题解 超级无敌大水题思维题 首先，出租车要将每个牛都从出发点送到目的地，那么必须经过所有牛的路程。我们先将这个路程…

题目描述 给定一个长度为 $n$ 的数字串 $a$，和一个长度为 $m$ 的数字串 $b$，保证 $b$ 中出现的元素在 $a$ 中都出现过，且 $b$ 中任一元素只出现过一次。现求一个 $a$ 的长度尽可能短，且尽可能靠左的子串，使 $b$ 成为其子序列。 数据范围 多测 $1≤T≤1000$ $1≤m≤n≤10^6$ $1≤∑n≤5×10^6$…

题目描述 在 $xy-$ 直角坐标平面的天空中，有 $n$ 片四边平行于坐标轴的矩形云朵。每一片云由一个五元组 $(xi,yi,wi,hi,di)$ 表示，其中 $(xi,yi)$ 为云左下角顶点的坐标，$w_i$ 表示云在 $x$ 轴方向的宽度，$h_i$ 表示云在 $y$ 轴方向的长度，$di∈lbrace 0,1rbrace $ 为云的移动方…

题目描述 给定 $n$ 和 $k$ 棵有 $n$ 个点的树。对于每个点对 $(i,j)$ ，求出其在每棵树上的路径经过的点（含端点）的交集大小。 数据范围: $1 \leq n, k \leq 500$ 时间限制: $2.000s$ 题解 首先明白一个性质：对于某一棵树，考虑 $x$ 在 $(u, v)$ 路径上的充要条件：$dis(u,x) + …

问题描述 给定一个 $n$ 行 $m$ 列的网格图，每个格子的颜色是蓝色、白色中的一种。白色的格子是障碍点。对于 $2$ 个有公共边的蓝色格子，它们之间是连通的。保证任意 $2$ 个蓝色格子间最多只有 $1$ 条不经过白色格子的路径。现给出 $Q$ 个矩形区域，对每个矩形区域求出对蓝色格子来说的连通块个数（不能经过白色格子和矩形区域外的格子）。 数…

题目大意 在一条数轴上有 $n$ 人 $k$ 把钥匙，每个人能拿且仅能拿一把钥匙，办公室坐标为 $p$ ，所有人同时开始去拿钥匙，然后去办公室。求所有人消耗的最大时长。 每人的坐标在 $a_i$ ，每个钥匙的坐标在 $b_i$ 。 题解 我们先将每个人的坐标和钥匙先排序，然后可以证明： $$\forall a_i\leq a_j\ …

[题目链接] 题目描述 Bessie喜欢在手机上下游戏玩（……），然而她蹄子太大，很难在小小的手机屏幕上面操作。 她被她最近玩的一款游戏迷住了，游戏一开始有$n$个正整数，$(2\leq n\leq262144)$，范围在$1-40$。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个$7$合并成一个$8$)，目标是使…

[题目链接] Lomsat gelral [原题链接] E. Lomsat gelral Lomsat gelral 题面翻译 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子…

期望值（Expectation）是概率论和统计学中的一个重要概念，它表示在一个随机事件或随机变量的多次重复实验中，某个特定数值的平均或期望表现。通常用符号 "$E(X)$" 表示，其中 "$X$" 是随机变量。期望值提供了一个概率分布的数值特征，它可以帮助我们了解随机事件的中心趋势。 在离散随机变量的情况下，期望值的计算可以使用下面的公式： $$&…