Tsinghua Bootcamp 2024 预选赛部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

A. A + B

题意

交互题，有两个未知的数 $a,b$，你一次可以询问 $x$，交互库返回 $(a|b|x) + (a\&b\&x) + (a\oplus b\oplus x)$。用不超过 $5$ 个询问，求 $a+b$。

题解

设 $M=2^{35}-1$，查询 $0$ 得到 $(a|b) + 0 + (a\oplus b)$，查询 $M$ 得到 $M + (a\&b) + (M-(a\oplus b))$。两次答案相加减 $2M$ 得到 $a+b$。

C. Historic Memories

题意

有一棵树，每个点有点权。有的点点权处于不变的状态，有的点点权每年减一，这个状态可能改变。中间穿插有询问：如果在某时刻从某点出发，（假设之后状态不变），能到达的点权最大的点是多少。每次询问和修改都带有时间戳，时间戳不降。$n,q\leq 10^5$，5s。

题解

点权不变的点好维护，考虑点权变化的点。对点权变化的点，记录其点权外推到 $0$ 时刻时的点权；从询问点出发到某点时的点权为 (0 时的权值 - 距离) - 询问时刻。使用点分树，把点权减（到分治中心的）距离记录到分治中心上；询问时同样跳每个分治中心，求每个中心【存的最大值减去询问点到分治中心的距离】的最大值。可以改写为点分治，将每个分治中心各个时段的答案用线段树维护。

E. Secure Prison

题意

有 $n$ 个矩形，各自有横向和纵向的长度。可以把一个矩形的任意一条边延长任意长度，代价为长度变化量。现在对于每个 $i$ 求，要让另外某个矩形（可以经过改造）的两条边都不短于第 $i$ 个矩形的对应边，求最小的代价。$n\leq 2 times 10^5$。

题解

二维数点，考虑要把哪个矩形改造成比当前矩形大，那个改造的矩形与当前矩形的边长关系有四种情况，就是四个二维数点（如何简单实现没细想）。

G. Crazy Arrangements

题意

有一棵 $n$ 个点的树。依次给出若干条链。问有多少给边赋 0/1 权值的方案，使得这些链的权值和模 $2$ 之后单调不降。$n,m\leq 2.5 \times 10^5$。

题解

先考虑树上前缀和，那么每个点的前缀和可以任意安排（根除外），一个链的权值和就对应某两个前缀和相等/不等。因此若确定了链的权值和，用链建图，则答案为 $2^{\text{连通块个数}-1}$（没有奇环的话）。考虑权值是 0/1 的段各有多长不确定，使用线段树分治+可撤销权值并查集来求每种情况下的连通块个数和奇环存在性。

I. Delivery Robot

题意

构造题。你位于平面上一个整点，希望到达另一个整点；你可以做四种操作：围绕 $(0,0)/(1,0)$ 顺/逆时针旋转 $90$ 度。构造一种 $10^6$ 步以内的方案，或报告无解。坐标范围 $\pm 10^5$。

题解

记 1/2 分别为绕 $(0,0)$ 顺/逆时针旋转 $90$ 度。3/4 分别为绕 $(1,0)$ 顺/逆时针旋转 $90$ 度。

整个过程 $x+y$ 的奇偶性不变。如果前后 $x+y$ 奇偶性相同则有解：

• 用 1 来把点旋转到合适的象限。
• 用 14 来同时改变 $x,y$ 的奇偶性。
• 用 1133 让 $x$ 加 $2$，用 3311 让 $x$ 减 $2$。
• 用 1...2 对 $y$ 进行操作。

J. Pizza

题意

有 $n$ 种配料，$m$ 个人。每个人有一些要求，形如要有/不能有某种配料。问有多少种配料方案，每个人的要求都至少满足一个。$n\leq 1000, m\leq 20$。

题解

容斥，钦定一些人的要求完全不满足；然后要判断这些不满足的要求是否矛盾、涉及多少配料，使用 bitset 即可。

K. String Mutation

题意

给定一小写字母组成的字符串 $s$，三种操作：

• 单点修改
• 全局将一种字母替换为另一种字母
• 求两个区间（子串）是否相等 $n,q\leq 2 \times 10^5$。4s。

题解

使用线段树维护区间的哈希值，用启发式合并维护全局替换操作，需要一个数组记录字符与哈希值的映射。

L. Magical Clock

题意

一个 $720 t$ 个刻度的钟表，每一 tick，分针走 $12$ 格，时针走 $1$ 格；如果分针即将追上/超过时针，则分针下一 tick 会回到 $0$（而不是向前走）。问从一个状态（时针和分针的位置）出发，最少需要多少 tick 才能到达另一个状态，或输出无解。$t\leq 1500,q\leq 5 \times 10^5$。

题解

只考虑那些分针位于 $0$ 的状态（我们可以求出给定状态走多少步到达这样的状态），这样的状态只有 $720 t$（记为 $n$）个，同时可以快速计算一个状态的后继状态（与相应所需步数），这得到一棵基环树。通过基环树的类 DFN 序状物，可以快速判断两个状态是否有祖孙关系，从而判断是否有解；有解的话，可以通过点的深度和在环上的位置来计算步数。