20241223 作业

too hard for me!(4)

QOJ6660. 택시 여행

题意

给定一棵 个点的树，边有边权。

每一个点上有一个出租车，起步价是 ，每走一单位需要多付 的代价。

你现在在 ，需要求出走到每一个点的最小代价。

。

题解

考虑什么时候会在一个点换车坐，发现新换的车 一定更小。

也就是说，所有坐过的车， 一定是递降的。

设 表示只乘坐 的车，到达点 的最小代价。

那么 。

直接做就能 了。

点分树套李超树优化一下，复杂度 。

提交记录。

QOJ6661. 야유회

题意

现在有 个人站成一个圆，第 个人有一个数字 ， 是一个 的排列。

现在要进行三轮游戏，分别是早上、下午、晚上。

早上的时候，每个人能看见自己和右边一个人的数字，然后所有人会同时更改自己的数字。

下午和晚上的时候，每个人能看见自己和左右各一个人的数字，然后所有人会同时更改自己的数字。

构造一种策略，使得三轮游戏过后任意相邻两个人数字不同。

，满分需要使得最后所有人的数字都在 之间。

具体的，需要构造三个确定性函数，分别为早上、中午、晚上每一个人的策略。

如果交互库调用函数时发现相同传入返回了不同的结果，将会直接判错。

每一组数据包含多测，但你不知道有几组数据也不知道 是多少，保证三个函数调用次数分别不超过 。

题解

首先可以发现，下午和晚上其实可以分别拆成 轮游戏。

考虑让每一次游戏过程之后，相邻两个人的数字都不相同（否则肯定不好搞）。

对于早上，也就是说我们要构造一个函数 ，满足对于 ，有 。并且 值域尽可能小。

一个可能的思路是使用二进制位相关的东西进行构造：

令 表示数字 二进制下的第 位是 还是 。

设 为最小的 满足 ，那么 。

可以发现若 且 则 一定成立，且 。

那么此时我们能做到的数字种类为 。也就是说最后会剩下 种数字。似乎有 分。

我们现在的值域要在 前面带一个 的常数，这是很不牛的！

考虑为什么一定要带上一个 ，因为如果直接令 可能会出现 的情况。

这样就可能会导致 ，这是不合法的。

那么考虑能不能令 为最小的 使得 且 呢？

显然也是不行的，因为有 在二进制下完全包含 的情况，这样就找不到满足条件的 了。

这个时候就有一个神仙优化，考虑 。

那么我们先将一开始所有人身上的数字映射到，二进制下恰好有 个 的整数上（显然映射完有每一个人的数字 ）。

那么这个时候 二进制下 的个数相等，并且 ，那么就一定能找到一个 使得 且 。

那么我们直接令 ，此时显然有 。

考虑当前数字种类为 。能拿到 分，离目标的 种数字还剩一种。

但是此时后两轮没有对局面造成任何改变，也就是说，我们还有整个晚上没有用！

考虑单独对晚上进行操作，设晚上的时候，相邻三个数分别为 。

若 ，考虑直接让 不变。

若 则 都不是 。且此时 里必然有一个和 都不相等，我们直接令 变成剩下这个数。

这样我们就能在晚上能让数字种类数从 变成 ，这实在是太牛了！

提交记录。

QOJ6662. 기지 간소화

题意

现在有 个点构成了一棵树。

定义 为选出若干条边使得 中的所有点连通，取出边权和的最小值。

求 。

。

题解

就是 所有点的虚树边权和。

线段树合并一下，计算每条边会被计算多少遍。

提交记录。

QOJ6664. 학생들

题意

现在有 个学生和 个补习团队，你知道每一个补习团队包含哪些人，但是学生只知道自己所在的补习团队有哪些人。

学生们只知道补习团队个数 ，但不知道补习团队总数。保证每一个补习团队的人为 挖掉一个区间 。

现在过去了若干天，每一天早上，若一个人推断出，存在一个补习团队，使得自己不在这个团队里，那么他会选择进行举报。

如果学生进行举报，之后所有补习活动立刻停止。若下一天补习活动照常进行，则学生们都会知道上一天没有人进行举报。

问举报发生在第几天，有哪些学生进行了举报。

。

题解

先推一下什么时候会发生举报。

如果存在一个人 ，他不在任何补习团队里面。

初始时 知道补习团队个数 ，所以 会在第一天就选择举报。

如果存在两个人 ，满足没有一个团队同时包含这两个人。

那么在 的眼里， 没有被任何团队包含，那么 应该选择在第一天举报。

那么如果 没有在第一天举报，就说明存在一个团队，包含 但不包含 。

所以 会在第二天选择举报，同理 也会在第二天进行举报。

那么我们可以推出，在第 天发生了举报，当且仅当存在 个不同的人 。

满足不存在一个补习团队，同时包含这 个人。这容易使用数学归纳法证明。

---

那么首先来考虑第一次举报在第几天，这相当于问找出最少的人，使得没有一个集合包含他们。

题目中给的条件相当于是在说，一个补习团队的补集是一个区间。

那么这相当于选出最少的人，满足每一个区间都包含了至少一个选中的人。

如果只是求出最小的人数的话，可以看出来最后这步是一个普及组贪心。

直接把所有区间按照右端点从小到大的顺序排序，然后直接贪就好了。

考虑现在还需要判断每一个人是否会去投诉，那就考虑设 表示只考虑右端点 的区间，最少需要选出多少个人。

同理令 表示只考虑左端点 的区间，至少需要选出多少人。两个数组都容易算出来。

那么如果固定第 个人被选，一共就需要选 个人。

所以哪些人会去举报也是容易计算的。

复杂度 。

提交记录。

QOJ6663. 회의실 2

题意

现在有 场会议，第 场会议是一个区间 。

称两个会议有关，当且仅当，这两个会议时间段有交，或者存在另外一场会议，和这两场会议都有关。

在一次开会的过程中，所有有关的会议可以在一个会议室中进行，一次开会的代价是需要的最小的会议室个数。

现在要开 次会，每一次开完会之后，都会选出一个会议，永久的将他删掉。

求让总代价和最小的，删除会议的顺序方案数。

。

题解

首先可以发现两个会议有关相当于是两个会议在一个连通块里面。

先考虑如果初始的时候，所有会议在同一个连通块里面，怎么做。

不难发现此时一定存在一个方案，使得，每一次开会的时候代价都是 。

也就是说，我们现在需要计算的是，每一次删除区间之后，代价都是 的方案数。

正着不好想，考虑倒着做，考虑计算每一次加一个区间，使得代价一直保持 的方案数。

考虑加入一个区间之后，区间并变化的时刻。假设并一共变化了 次。

考虑其他的区间可以在什么时候插入。

令 表示区间 最早可以在第几次区间并变化后插入， 表示 的 数量。

同时令 。

那么方案数可以表示为 。

这个时候就好做了，设 表示当前所有区间的并是 ，所有方案的权值和是多少。

dp 的时候只对并变化的过程进行转移即可。这样就做好了。

最后考虑初始的时候不是所有连通块都有关的情况，可以发现一定是每一次盯着最小的连通块删。

提交记录。

QOJ6665. 팀 만들기

题意

现在有 个男生和 个女生。

每一个人均有一个代码能力和思维能力，男生的代码能力和思维能力分别用 表示，女生的分别用 。

已知对于任意 都满足 与 。

一个男生 和一个女生 的能力值是 。

现在有 次询问，每一次给定两个区间 ，从 选一个男生， 选一个女生的最佳能力值。

。时限 。

题解

后续分析中默认 同阶。

设现在有两个男生 ，和两个女生 。

考虑 。

因式分解一下，。

所以可以知道 。

也就是说，这个矩阵是满足四边形不等式，这是一个完全单调矩阵。

这样如果是单组询问，就可以直接分治去做了，可以做到 ，并且此时还可以求出每一行的最大值在哪个位置。

但是现在有多组询问，考虑分块去做。

散块对散块，直接把散块薅出来暴力跑分治，复杂度 。

整块对散块，预处理男生的每一块，和每一个女生的最优取值。复杂度 。

询问的时候，男生这边的整块有 个，女生的散块也只有 个。

那么直接把这当成一个 的矩阵，再跑分治即可。

散块对整块，和上面一样。

整块对整块，先预处理出男生每一个整块，和女生每一个整块的最优解，这部分可以和上面一起预处理。

还是和上面一样，男生女生整块数量都是 ，再把这个矩阵跑分治即可。

（其实这里也可以用 st 表）

所有最终复杂度是 。

若使用 SMAWK 算法代替分治，则可以做到 。

分治提交记录。（怎么喜提最劣解）