0%

20241216 作业

too hard for me!

QOJ8807. Infiltration

题意

现在有一棵 个点的树,Alice 和 Bob 初始在 两个点, 未知。

在奇数时刻,Alice 可以选择走一步或者原地不动,偶数时刻 Bob 可以选择走一步或原地不动。

构造一组策略,令 表示 两个点的距离, 表示此策略下两人第一次相遇的时间。

构造的方案需要满足对于任意

输出策略的方式为,对于一个人和一个起点,输出所有时刻,这个人应该在哪个点。

题解

先考虑,如果两个人初始在一个数轴上,如何使他们相遇。

可以发现,先让 Alice 往右走 步,再让 Bob 往右走 步,然后 Alice 往右走 步……依次类推。

那么对于一条链的情况,相当于限制两人初始坐标在 内(且不能走出这个范围),最劣比值为

考虑一个很无语的优化,我们取这条链的中点当作根,算出来恰好取得

那么放到树上,找到树直径的终点,然后以这个点为根,两个人轮流往上跳就好了。

由于未知的原因,输出策略时每一行后面都需要多输出一遍根,不然会挂。

提交记录

题意

现在有一个 个点 条边的图,每一个点有一个点权,点权只可能是

称一个 串是好的,当且仅当存在一条图上的路径(可以不是简单路径),满足这条路径上的点权正好与 串一一对应。

判断是否存在不好的串,有的话输出最小长度。

题解

可以发现,最小的串一定是 的子串。

使用反证法,假设当前最小的不好的串为

那么长度 的子串一定都是好的。

可以发现,一个串 一定可以在一个长度比他小的 串上被表示出来。

也就是说,在上面这个图中,只需要 能被表示出来,这个 肯定也能被表示出来。

这与我们的假设冲突,所以最小的串一定是 的子串。

那么这样就好办了,令 表示从点 开始,最短的无法表示的第 种串,长度是多少。

那么 。跑一个拓扑排序就能跑出来。

提交记录

QOJ8581. 섬

题意

给定一个正 边形的三角剖分。

现在可以进行若干次操作,每一次操作为选择一个三角形 ,然后在这个三角形中间加入点 与三条边

进行最少次数操作,使得可以选出两个边不交的生成树(新加入的点也要连通)。

题解

先考虑不使用操作,此时有 个点和 条边,一定选不出来。

如果使用一次操作,此时有 个点和 条边,边数足够了,考虑此时是否有解。

这个正 边形被分成了 个小三角形,不难发现这些小三角形可以形成一个树形结构。

考虑以 这条边所在的三角形为根,建一棵树出来。

一个三角形,除了他和父亲连的那条边以外还有两条边。

那么把左右两条边分别分给第一个边集和第二个边集。

那么此时可以发现,红色边集除了 以外全部连通,蓝色边集除了 以外全部连通。

那么先把最上面一条边分给红色边集,这样红色边集就全部连通。

此时只有蓝色边集还存在两个连通块。

那么给 所在的这个三角形用一次操作,并按上图方式连边。

这样就成功搞出了两棵生成树。

提交记录

QOJ9870. Items

题意

现在有 种物品,第 种重量为 ,每一种物品有无限个。

给一个 ,判断是否能拿出 个物品,总重恰好为

题解

,并令

可以发现,此时问题答案不变,但是 现在都是 级别的。

考虑对于一个合法方案,若前 个物品的重量前缀和为

那么若 ,则后 个物品一定有重量 的。

,则后 个物品一定有重量 的。

这说明一定存在一个重量前缀和始终在 的方案。

只保留 内位置,多项式快速幂解决。复杂度

提交记录(不知道为啥保留 也过了,也许是对的)。

QOJ8577. 평균 최대화

题意

定义一个序列 是封闭的当且仅当

一个序列 的权值 为进行若干操作后,能得到最大的,序列平均值。

一次操作是选择一个封闭的连续子序列 ,然后删除

给定一个长度为 的序列 次询问 ,保证 封闭的

。序列中可能有相同元素。

题解

考虑哪些区间是封闭的。考虑建出整个序列的小根笛卡尔树。

可发现,若 是封闭的,那么必然 在树上是一棵完整的子树。

如果满足这个条件可以发现,一定有

那么此时只需要额外要求 的根 即可。

考虑一个询问 ,此时 一定是不可能被删除的,所以需要在 这棵子树上计算答案。

表示对 这个区间进行若干操作,使得剩下了 个数,这些数和的最大值是多少。

那么有 。直接暴力做就可以

考虑用这个 dp 如何计算答案,显然求得是最大的

将所有的 看作一个点放在平面上,那么可能成为答案的点一定在凸壳上。

考虑维护每一个区间对应的凸壳。

观察 dp 转移式,发现后面是一个 卷积,可以用闵可夫斯基和合并(对斜率跑归并排序)。

但是前面还有一个 ,加入新的点之后可能会(其实是一定会)破坏整个凸包。

所以需要一个手写的平衡树维护凸包上的点,加入新点的时候需要将前面若干个点进行合并。

询问时的 肯定是一个完整的区间,直接预处理出所有区间的答案即可。

时间复杂度

提交记录

(这题 spj 是唐诗,我怎么看别人直接返回 就过了)

QOJ9863. Brackets

题意

给定一个长度为 的括号序列,里面有 四种括号。

额外给定 个区间,第 个是

现在要求从 个区间中选择尽可能多的“区间对”。

满足每一对的两个区间拼起来之后是合法括号串,且一个区间至多出现一次。

题解

考虑一个对 什么情况是合法的。

第一种情况是 是两个合法的括号串。

第二种情况是 左边匹配了一段,右边没匹配的一段全是左括号。

并且 右边匹配了一段,左边没匹配的一段全是右括号,并且恰好能和 剩下的部分匹配上。

分别统计这三类括号串的数量。

考虑什么括号串,可能在左右分别加入一些其他括号后变得合法。

可以发现,这种字符串,如果消掉中间已经匹配成功的部分,剩下的部分,一定是左边一段右括号,剩下的右边全是左括号。

那么一对合法的区间,在内部各自消完之前,应该大概长成 这个样子。

考虑分治来统计,以统计哪些字符串消完之后只剩下左括号举例。

尝试想象一下,在分治中心左右两侧,这个字符串可能长什么样子。

可以发现,可能大概长成这个样子,

中心的左侧一定没有右括号,并且中心右侧的右括号可以被左边的左括号全部消掉。

此时左侧剩余的左括号+右侧的左括号就是需要统计的部分。

提交记录

QOJ9189. Make them Meet

题意

给定一个 个点 条边的图,初始有两个人在两个不同点,但你不知道他们在哪两个点。

现在可以进行若干轮操作,一轮操作是给每一个点染一个 之间的颜色。

然后两个人会走向一个,与当前点相邻,且颜色相同的点。没有这样的点则在原地不动,有多个则随机选一个走。

若某轮操作后两个人在同一个点,或者两个人经过了同一条边,则称两个人相遇了。

构造操作,使得无论两个人起点在哪里,中间过程选择了哪条边行走,他们中间都相遇过。

,满分需要满足操作轮数

题解

首先从树看起,容易发现此时相当于是每一轮选择一些边激活。

但是树的情况仍然不好做,所以先来考虑链怎么做。

考虑奇数轮的时候让深度为奇数的边激活,偶数的时候让深度为偶数的边激活。

这样,一个人行走的路径,就是在从起点走到一个链头,然后在两个链头中间不断往返。

可以发现,走 轮之后,无论起点在哪里,两个人一定相遇了。


再来考虑菊花怎么做。

考虑第一轮先让所有边激活,这样如果两个人初始在两个叶子,这一轮直接就相遇了。

否则,两人初始一个在叶子一个在根,一次操作之后肯定还是一个在叶子一个在根。

那么第二轮我们随便激活一条边,剩余的边关掉。

这样在根上的那个人就会走到那个叶子去,如果另一个人恰好在那个叶子上,两个人直接就相遇了。

否则,另一个人不会动,那么现在两个人就都在叶子上,直接再来一轮,激活所有边就好了。

这样可以在 轮的时间让他们两个相遇。


最后考虑一个普通的树怎么做。

先来想能不能直接把链的做法套上来。

可以发现,这样是不行的,此时两个人的路径是在根和某个叶子直接晃,并且这个晃的叶子可能会更换。

此时可能会出现两个人一直晃但就不相遇的情况。

考虑再套一点点菊花的做法上来。

我们选择一个根的儿子,然后让根和这个儿子中间的边,一直被激活。

考虑这个时候一个人会怎么走。

对于大部分情况,一个人会(先向下走到某一个叶子,然后往上走,然后)一路走到根,然后持续在根和选择的儿子两个点中间一直晃。

但是还有特殊情况,可能会出现一个人初始在根和儿子中间来回晃,然后在某个时间突然逃逸,然后走到某个儿子再上来晃。

可以发现其实特殊情况不是很影响这个做法的正确性。考虑多少轮之后两个人会相遇。

最极限的情况应该是一个人初始在根和某个儿子中间晃,另一个人先走到一个叶子再往上走。

此时经过了 步,考虑一开始就在根的那个点,如果在 轮才逃逸,那么两个人肯定在之前就逃逸了。

所以第二个人肯定在前 步会逃逸,逃逸之后经过 步还是会回到根。

所以直接分析就会发现两个人肯定可以在 步相遇。

仔细思考还能得出,其实两人经过 步就会相遇了。

懒得证了自己看图吧。

这样我们就得到了树的做法。


再来考虑普通图怎么做。

一个很自然的想法是,能不能找出这个图的随便一棵生成树,然后套用树的做法。

思考可以发现,找到的生成树需要满足如下两个条件:

  1. 父亲相同的两个点,中间不能有边;
  2. 若在树的做法中,选出的根的儿子为 ,则根和 的儿子之间不能有边。

首先第一个条件非常好满足,我们只需要找一棵 dfs 树即可,因为 dfs 树上没有横叉边。

那是否所有的图都能找到一个合适的根和 满足条件二呢,显然不是,例如一个完全图。

但是这个时候可以发现,完全图的 dfs 树是一条链,而这个时候是可以直接套用链的做法做的。

那么我们先找到这个图的随便一棵 dfs 树,用调整法搞出一个符合条件的图。

首先,如果这棵 dfs 树直接是一条链,那么直接套用链的做法。

否则这棵树一定存在“分叉点”,设最深的一个分叉点为 的父亲为

的儿子分别为 ,若此时存在一个 满足 没有边,那么我们能找到一个合法的构造。

首先先把 下面的点(即 及以下的部分)都先删掉。

然后以 为根开始跑 dfs,要求在 dfs 到 的时候先走 ,dfs 的时候优先走剩余的 以及点

考虑这样有什么好处,可以发现,如果 先走 的话,此时 在 dfs 树上就不会有其他的儿子。

(需要注意的是, 优先走 ,意思并不是,将所有 都当作 在 dfs 树上的儿子。例如若图中存在紫色边,那么在搜到 的时候直接将 当作 的儿子就可以了)

那么令 当根, 为选中的儿子,这棵树目前是满足条件的。

然后我们将 以及下面的部分挂回原树。但是此时可能会出现 这条边,这就破坏了性质。

(虽然还可能存在一些别的横叉边,但是这些边都不影响)。

考虑更改一下我们的操作,原来操作是一轮奇数边,一轮偶数边,一直反复。

现在加入一类操作,称为特殊边,在这一轮操作中,我们只让 两个点颜色相同,这样就只激活了 这条边。

现在我们让三种操作,奇数边,偶数边,特殊边一直反复。

(注意一下,这里奇数和偶数的操作由于深度定义不同,可能出现差异,所以正确的操作也可以能是先偶数边再奇数边)

如果这样操作的话,在原树上的人,行走路径不会改变。

在链上的人,会(先弹到底部,然后)走到 ,然后在 之间晃,然后某一时刻逃逸,走到一个叶子之后,再回来持续在 之间晃。

分析此时轮数,可以发现 轮就足够了。


此时还有一种情况,就是 与每一个 中间都有边。

考虑直接拿 当作根,还是先把 下面的链删掉。

然后从 开始 dfs,并且在访问到 的时候优先访问其他的

因为其他的 也都有边,所以此时 一定不会是 的儿子。

然后我们就构造出了和上面一种情况完全相同的生成树,和上面一样构造即可。

最终只需 步即可。时间复杂度

我感觉这是对的啊不知道为什么 过不去,但是 过了

提交记录

QOJ8578. 과일 게임

题意

现在有 个卡牌,第 张等级为

一次合并操作为选择相邻两张牌使得 ,然后删掉这两张牌,并插入一个等级高一级的牌。

称一次游戏的结果为,进行若干次合并操作,最后拥有的等级最大的牌的等级。

进行 次操作,每一次单调修改卡牌等级,或者询问一个区间的游戏结果。

,任意时刻初始卡牌等级 ,强制在线。

题解

先想静态的区间怎么做。

考虑按照等级从小到大的顺序,依次考虑每一个相同等级卡牌的连通块。

假设当前有一个等级为 ,长度为 的连通块。

因为我们是按照等级从小到大合成卡牌,所以这个块左右的卡牌都比这个块内要大。

也就是说块外怎么合并并不影响块内可以怎么合并。

考虑如果 为偶数,那么我们直接将这个块变为 个等级为 的卡牌。

否则 为奇数,可以发现无论如何,这个块内,是不可能所有卡牌都合成了,一定至少有一张卡牌,无法参与接下来任何一轮合成。

那么我们直接将这些牌变为, 等级的卡牌,一条分界线, 等级的卡牌。

这样一直合成下去,就能算出一个静态区间的答案了。

现在需要进行区间查询操作,优先考虑使用线段树进行维护。

但是直接维护显然是不行的,因为上述过程中我们要求卡牌按照等级从小到大进行合并,这肯定不能在线段树上做。

考虑一下为什么要求从小到大合并,原因是如果左右两边的卡牌都比他大,那么左右两侧不会影响中间的合并。

所以只需要某个块左右两边都比他大,就可以直接把这个块给合并,并不需要每一次找全局最小值合并。

这样的话,只要牌内部出现了凹下去的情况,我们就能把他合并掉。

所以合并完的结果,一定是一个凸起来的样子。

而卡牌最多就合成到 级,这个凸起来的序列整体块数也不会很多。

所以考虑,维护每一个区间合并成了什么样子。

两个区间合并的时候,直接暴力把两个子区间的结果拼一起然后暴力合并。

时间复杂度是

提交记录

QOJ9185. Garden Decorations

题意

个人住在 个房子里,每一个房子有一个状态

现在这些人想要搬家,原来住在 里的人将要搬到 去,但是每一个人住的房子状态不能变。

现在你可以进行若干次操作,对于第奇数次操作:

你将按照从 的顺序经过所有房子,并按照顺序选择更改或不更改每一个房子的状态(决策第 个房子的时候,无法得知第 房子的状态)。

对于第偶数次操作,将按照 的顺序经过房子并进行决策。

(输出策略时给定排列与当前的轮数,然后逐个给出经过的房子状态)

,满分需要在 轮以内操作完。

题解

考虑初始状态是一个向量 ,我们需要经过操作将其变成 。(注意我用的是行向量不是列向量,列向量应该要反一下)

那么相当于是给定了一个满秩的矩阵 ,要求我们构造出三个矩阵

满足 为上三角矩阵, 为下三角矩阵。容易知道首先这三个矩阵 都得是满秩的。

那么初始令

考虑跑一个类似于高斯消元的东西,保证 不变的前提下,把 消成下三角矩阵。

考虑如果 对矩阵的乘积造成了什么影响,容易发现 其实相当于是对乘积进行了若干的行变换。

由于 是上三角矩阵,所以通过更改 ,能够实现让 中编号大的行对编号小的行进行影响。

同理, 是对结果做列变换,能让 中编号小的列对编号大的列造成影响。

而现在我们需要利用这两种变换,把 弄成一个下三角矩阵。

考虑正常过程中我们怎么把一个矩阵消成下三角矩阵,流程如下:

  1. 对于 ,首先在前 行中找一个第 列为 的行,然后把这一行和第 行换一下。
  2. 对于前 行里面第 列为 的行,用第 行给他异或一下把 消掉。

可以发现我们的操作用 矩阵能做到第二步,但是不能做第一步。

考虑 矩阵有什么用,因为这个过程中每一个矩阵都是满秩的,所以若 ,那么 的第 行前 列必然至少有一个

那么直接用 矩阵把那一列的 异或到第 列即可。

这样就用消元的方法构造出了 ,答案随便输出。

提交记录

(不知道为啥这题不能用快读)

还有一个 QOJ8195 我做过不写了。