26杭电多校7

H

给定一个位运算方程 x1op1x2op2x3op3⋯xn−1opn−1xn=wx1​op1​x2​op2​x3​op3​⋯xn−1​opn−1​xn​=w，其中：

• x1,x2,x3,⋯,xnx1​,x2​,x3​,⋯,xn​ 是 $n$ 个独立的未知数；
• op1,op2,op3,⋯,opn−1op1​,op2​,op3​,⋯,opn−1​ 是 $n-1$ 个给定的运算符，每个运算符都是 $\mathrm{and},\mathrm{xor},\mathrm{or}$ 中的一个，三个运算符的优先级是 $\mathrm{and}$ 先于 $\mathrm{xor}$ 先于 $\mathrm{or}$；
• $w$ 是给定的参数。

你需要为该方程找到一组非负整数解，满足 0≤x1,x2,⋯xn<2310≤x1​,x2​,⋯xn​<231，若无法找到任何一组解则报告无解。

位运算。发现第一个数填 w，之后遇到 & 就填全集，其他填 $0$。

---

---

B

选取 01 字符串 s 的一个子序列并将其拼成字符串 ssub使其表达的信息与 s 一致。计算子序列长度的最小可能值。

易知答案不超过6，枚举即可。

---

---

L

给定一棵以顶点 1 为根、包含 n 个顶点的有根树。输入中的顶点称为原始顶点。根的深度为 0，其他顶点的深度为其到根的边数；树的高度为所有顶点深度的最大值。

你可以执行任意次操作，使最终树中的每个顶点至多有两个儿子：在顶点 u 与两个不同儿子 v,w之间插入一个点r，其余点关系保持不变

分别求出 最终树的高度 以及 所有 n 个原始顶点在最终树中的深度之和（新建顶点的深度不计入这个和）的最小值

两个最小值互相独立，可以由两种不同的操作方案取得。

定义路径长度为边数，则深度为某顶点到根的路径长度，而高度为深度最大的顶点深度。

对于最小高度：

对每个原顶点 u，它的若干棵儿子子树需要通过新增节点组成一棵二叉树。最后一次“合并”可以理解为直接挂到 u 的两个儿子上。设儿子 v 的子树最小高度为 h_v。

如果把高度为 a,b 的两个簇合并，新簇的高度为：max⁡(a,b)+1。为了最小化最终高度，每次取当前高度最小的两个簇合并，类似哈夫曼树：a,b→max⁡(a,b)+1

对于最小原顶点深度和：

设子树 v 中包含 sz_v​个原始顶点。

如果给整个子树 v 增加一层深度，深度和会增加 sz_v​​。因此每棵儿子子树的权值就是 sz_v​。
合并权值为 a,b 的两个簇：

• 新簇权值为 a+b；
• 深度和增加 a+b。

即可倒序 DP。

---

---

F

有若干个区间，需要放置两个断点，满足每个区间内有恰好一个断点。

 

设输入的每一对 CP 为 a_i , b_i，那就是 [ a_i , b_i ) 内须有一个断点。枚举右断点，则要求该断点右边不能有完整区间。维护所有包含当前断点 i 的区间并，设为 [ l_i , r_i ]，那么另一个断点则必须在 [1, l_i ) 当中。再维护所有 r< i 的区间的区间交，记为 [ x_i , y_i ]，就只需要判断 [ x_i , y_i ] 内部是否有  [ l_i , r_i ] 之外的点。显然，只需要观察 x_i 是否在 l_i 左边即可

---

---

K

白井黑子有 n 个电脑配件，质量分别为 x₁,x₂ ...... x_n（可能是负实数）。

题目会进行 m 次在线询问，每次给定三个参数经过加密的变量 a, b, d，解密后会得到一个方程 x_i + x_j  = 2c。

你需要判断当前方程是否与之前所有被认为是正确的方程冲突：

• 如果不冲突，则认为该测量结果正确，输出 Yes，并将正确询问计数器 k 加 1（用于后续解密）。

• 如果冲突，则认为该测量结果错误，输出 No，此结果作废，计数器 k 不变。

由于方程形式为 x_i + x_j  = 2c，我们可以将其转化为某个节点与其根节点的关系。 设 p[u] 为 u 的父节点，我们可以维护两个数组 s (符号) 和 v (权值)，使得每个节点与其根节点的关系始终满足：

x_u = s[u] * x_root + v[u]

其中 s[u]∈{1, -1}。

当节点 x 的父节点 p[x] 指向更高层的根节点时，推导得，路径压缩时更新公式为： v[x]=s[x]*v[p[x]]+v[x]  s[x]=s[x]*s[p[x]]

我们找到x_i + x_j  = 2c的根root_i 和root_j，分类讨论两者是否为同一点的情况，化简方程即可求解

---

---