0%

20241223 作业

too hard for me!(4)

QOJ6660. 택시 여행

题意

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

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

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

题解

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

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

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

那么

直接做就能 了。

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

提交记录

QOJ6661. 야유회

题意

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

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

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

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

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

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

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

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

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

题解

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

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

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

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

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

为最小的 满足 ,那么

可以发现若 一定成立,且

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

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

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

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

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

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

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

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

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

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

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

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

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

,考虑直接让 不变。

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

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

提交记录

QOJ6662. 기지 간소화

题意

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

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

题解

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

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

提交记录

QOJ6664. 학생들

题意

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

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

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

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

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

题解

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

复杂度

提交记录

QOJ6663. 회의실 2

题意

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

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

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

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

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

题解

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

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

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

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

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

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

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

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

同时令

那么方案数可以表示为

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

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

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

提交记录

QOJ6665. 팀 만들기

题意

现在有 个男生和 个女生。

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

已知对于任意 都满足

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

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

。时限

题解

后续分析中默认 同阶。

设现在有两个男生 ,和两个女生

考虑

因式分解一下,

所以可以知道

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

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

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

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

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

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

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

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

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

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

(其实这里也可以用 st 表)

所有最终复杂度是

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

分治提交记录。(怎么喜提最劣解)