【2023.07.16】清华&字节夏令营资格赛(Tsinghua University Bootcamp. Qualification Round)过题小记

发布时间 2023-07-17 23:25:23作者: hh2048

B - Performance(贪心、排序)

23分过题。打卡题,差分+排序。

A - Code Lock(图论、搜索)

37分由队友单人过题。打卡题,将序列转化为图上问题,随后维护每一个环上相同元素的距离。

D - Company Network(树论、倍增、数据结构)

2小时55分全队一起过题。中等难度,对于每一个节点,倍增向上搜索其最高处的上司。随后使用树链剖分+线段树维护其到上司路径上的答案。

C - Protective Field(几何、二分搜索)

题意:平面上 \(n\ (1\le n\le 400)\) 个点,绘制一个半径最小的圆使得其覆盖至少一半的点。

赛时推导出结论:答案圆上至少包含两个点。以此作为突破口,暴力枚举每一对点对,随后,二分圆的半径。注意,由于两点一半径可以确定两个圆,所以需要分别计算两个圆。官方说最终复杂度 \(\mathcal O(N^3\cdot \log(10^{15}))\) ,时限十秒,可以通过。

H - Garbage(数据结构、位运算)

题意:维护一个序列,使得满足 $[1]: $ 区间查询异或和、$[2]: $ 区间赋值成某个值、$[3]: $ 区间修改,使得每一个元素和(AND)、或(OR)、异或(XOR)上某个值。

首先,这么复杂的区间操作,基本确定是线段树了。

显然,我们可以按位建立 \(15\) 棵线段树,每一棵线段树维护一个位置。随后问题在于如何有序处理各种操作。

inf.

I - Collecting Artifacts(图论、暴力、搜索)

题意:有 \(k\ (1\le k\le 6)\) 个种类的宝藏,图中每一个点可能存在某一个种类的宝藏、也可以为空。你需要选取一条最短的路径(可以不是简单路径),使得可以获取到全部种类的宝藏;若不存在则输出 \(-1\)

inf.

F - Recombination(字符串)

题目比较难读。

inf.