task17

[TOC]
1. MX-X12H - 地铁 [E]
题面
给定 LRUD
中两种垂直的方向
你需要使得每个点都被至少一条折线覆盖,求最小的
对于仅求最小
对于要求构造的数据:
题解
Sol
每条折线要么是左上到右下,要么是左下到右上,不难发现我们可以将其延长到四个角上
设
那么最多覆盖的点数有一个上界:左上角和右下角边长为
减去一个
可以猜测一下这个就是充要条件,写一下可以发现这是对的,注意到
接下来考虑构造。
经过充分长时间的手模,可以发现如下事情:
不妨假设
我们可以通过上面的操作把
带入判别式求值发现
2. AGC020F - Arcs on a Circle [E]
题面
一个长为
求每个点都被弧覆盖的概率,输出浮点数
题解
Sol
首先我们可以把最大的
如果我们已经确定每个弧放的位置的整数部分,那么这个弧一定会覆盖一段
因此,只要我们能够提前得知小数部分的大小关系,我们就可以转化成整数上的问题,而小数部分的大小关系可以提前枚举
枚举大小关系之后我们列一个 dp 状态:
复杂度
3. 集训队互测 2023 - 森林游戏 [E]
题面
给定一棵
两个人在上面博弈,每次每人选择一个没有父亲的点,将其删除,得分为自己删除的所有点的点权之和
两个人都要最大化自己的得分,求最优策略下先手的得分
题解
Sol
不会做,所以考虑大胆一点。首先把点权变成先手减去后手。
我们直接仿照树上打怪兽的贪心,每次选点权最大的点出来,认为它一定是紧跟着它父亲后面操作的。
但是有一点问题:我们合并完的点可能有两种,一种是选完会改变先后手,另一种是不会改变的
如果选完不会改变先后手,且它的点权还是正的,那么不管是谁操作,都一定会取这个点,这个看起来就很对,所以可以考虑直接和上面合并。
否则如果选完不会改变先后手,且它的点权是负的,那么这个东西就很没用,我们把这种东西放到最后合并
如果选完会改变先后手,那么我们就按点权从大到小合并
具体地,我们按照如下规则给点安排顺序:
- 首先是点权非负,且不会改变先后手的点,这些点按照权值从大到小排序
- 然后是会改变先后手的点,这些点按照权值从大到小排序
- 首先是点权为负,且不会改变先后手的点,这些点按照权值从大到小排序
每次选出最优先的点和父亲合并即可,正确性不知道
复杂度
4. QOJ4212 - Brackets [E]
题面
给定一个长为
请构造一个字典序最小的长为
题解
Sol
贪心:我们从前往后扫,如果将当前这个填成 (
后存在后缀和 )
,否则就填 (
如果构造出来解了,那么显然这个解是最大的,否则我们可以说明原问题即无解
证明:令
如果我们没有构造出来解,我们找到任意一组合法解,从左到右扫每一组相等位置的取值,找到第一个不同的位置,这个位置只能是我们的解构造了 (
,而合法解构造了 )
此时我们要说明:我们可以调整合法解使得这个位置取了 )
设这个位置为
不难发现我们可以调整
此时我们找到贪心解中
因此上面的贪心就是正确的,复杂度
5. ARC138F - KD Tree [E]
题面
给定一个
你会给一个集合
- 如果
,那么只有一种安排顺序的方式,直接返回 - 否则,你可以选择一个
,将所有横坐标 的放在前面递归安排顺序,剩下的东西放在后面递归安排顺序,或者选择一个 ,将所有纵坐标 的放在前面递归安排顺序,剩下的东西放在后面递归安顺序
题解
Sol
对第一步操作进行容斥。
我们选择一个操作的集合
那么可以发现,我们对点的要求就是如果我们把有点的小区域染成黑色,黑色应该是从左下不断向右上移动的
对这个跑 dp,我们强制一个路径是从左下出发,走到右上角,然后在两个黑色之间必须向上再向右
定义两个状态,一个
总复杂度
6. CF1710D - Recover the Tree [E] ⭐
题面
对于一棵
请构造一棵树,使得其满足条件,数据保证有解
题解
TBA
7. 集训队互测 2023 - 雷同 [E] ⭐
题面
给定
你每次可以指定两个物品
求将所有物品合并到一起的最小代价
多组数据,
题解
Sol
合并过程是一棵二叉树,最后的贡献上是
不难发现如果将
那么我们只要能够对于一个固定的
容易发现这是一个
最优的匹配方式就是按照优先深度大的互相匹配,因为可以注意到我们留到后面的子树一定
在这种情况下,我们可以列出 dp 状态:
复杂度
8. 集训队互测 2023 - Permutation Counting 2 [E]
题面
给定
对所有
题解
Sol
对两个限制同时容斥,那么相当于序列被分为了
从小到大加入数,相当于我们有
方案数也即:
可以用范德蒙德卷积发现这就是
但是这样会有些段是空的,那么再做一遍二项式反演即可
最后代码写出来就是
复杂度
9. 集训队互测 2023 - 没有创意的题目名称 [E]
题面
给定一个正整数
- 对于所有
, - 对于任意
,都有 (我们认为 的位置都满足 )
答案对
题解
Sol
放弃思考,相信打表。
当
- 如果
,循环节为 - 否则循环节为
循环节
之后只要统计不超过
10. 集训队互测 2023 - 挑战积和式 [K] ⭐
题面
给定一个长为
题解
Sol
设最优解的和为
而
但是这个还是太高了。
最后复杂度里不能带
引理:对于任意非负实数集合
证明:
- 如果
,那么我们直接选 为这个最大的元素即可 - 否则我们将
的大小补到偶数,然后从小到大排序,取所有排名为偶数的数作为 的元素,此时 显然 ,而我们将 去掉之后可以说明其一定 ,即
那么我们的值域只用保留到
注意到我们上面的说明中只用到了
那么总复杂度就是
11. CF1707E - Replace [E] ⭐
题面
给定长为
题解
Sol
注意到如果两个区间
证明是容易的。
那么我们就可以选择一些关键区间,然后倍增处理出这些关键区间经过若干步之后的结果,最后合并起来
具体地,我们预处理
总复杂度
12. CF793E - Problem of offices [S]
题面
给定一棵
现在取一个欧拉序将其循环无穷多遍,是否可能满足:
- 任意两次相邻的
出现之间间隔的其它叶子个数相等 - 任意两次相邻的
出现之间间隔的其它叶子个数相等
题解
Sol
设两个变量
可以发现每个子树是否要对
复杂度
13. UNR6 - 小火车 [K] ⭐
题面
给定
保证
题解
Sol
我们的问题实际上就是要找两个子集和相等,而
在值域上二分。时刻维护一个区间
求子集和在一个区间内的数量可以折半+双指针
复杂度
14. CF1483E - Vabank [E]
题面
你想从银行里贪钱。
你每次操作可以指定一个正整数
银行有一个阈值
你初始有一块钱,请在不被警察抓走的前提下,
题解
Sol
首先依次询问
然后我们在这个区间内二分,假设我们现在知道了
这样分析一下次数可以发现是
改变一下我们的策略,可以发现我们最劣的情况是
由于我们是倍增二分,我们可以假设
这时候我们的钱一定是
也就是说,我们将
令
翻转一下状态和值,可以得到一个
每次按照 dp 告诉你的最优转移点去询问即可,实际数据里跑出来是
15. KTSC2025 - evolution2 [E]
题面
给定一棵
你可以向交互库提出询问,每次给定两个整数
设树结构一共有
题解
green:Sol
考虑一些极端的情况:
如果整棵树是一条链,那么
如果整棵树是一条链,再拼上一个点,那么
进一步地,如果整棵树是两条链,长为
而我们发现,如果我们能在
归并两个序列我写的是,设
注意到这种策略比较劣的情况是
把
16. ARC199D - Limestone [K] ⭐
题面
给定
题解
Sol
考虑最后一行的状态,为了唯一计数,不妨假设我们是把第一段极长的
即,我们枚举一个
注意到可以不枚举
17. ARC199A - Flip Row or Col 2 [K]
题面
给定一个大小为
给出构造或判断无解
题解
Sol
注意到我们可以 ban 掉第一行的操作,不改变答案。
将第一行消为
那么现在我们就没有行操作了,每一列
复杂度
18. EC Final 2018 - Exotic … Ancient City [E/K] ✔️
题面
定义一个
对每个
题解
Sol
注意到
首先外层枚举一个
如果暴力的话,我们就只需要用并查集不断维护出上一行的连通性,然后加上这一层的边,就知道有多少边是有用的,进而能够推算出连通块数
进行优化。
首先考虑如何从上一行的连通性推算出下一行的连通性,可以发现两个点
考虑从第一行逐次扩展联通性的过程,第一行到第二行时,我们需要将
而加的这些边,在第二行扩展到第三行的时候,就相当于我们需要把边端点的两个集合合并,从而又会新加一些边,这样不断扩展下去即可
而一共只会加
接下来考虑求出每一轮加的边有哪些是有用的,这个我们可以再维护一个并查集,有
总复杂度
19. AGC049F - Happy Sequence [K] ✨
题面
给定三个长为
将
加强版:
题解
Sol
太魔法了。
将
可以观察到最后的序列需要满足
可以猜出一个性质:题目条件等价于
虽然不用这个性质也能做,但是用了会方便一点,称
证明:
我们可以证明,
首先证明
然后证明
最后可以验证当
接下来我们都用
分析操作的性质,由于代价函数是凸的,所以我们可以直接将操作拆成代价为
如果存在
也就是说我们的操作一定满足存在一个分界点
此时可以发现,考察所有操作对每个位置的
进一步地,考虑最靠右的向右点
而被增大最多却还是
而对于单向的子问题,考虑固定一个代价
总复杂度为
20. QOJ9080 - Item Exchange [K] ⭐
题面
有
你需要进行若干次如下操作,使得第
- 选择两个相邻的人
,满足这两个人都更喜欢对方手上的物品,然后交换他们的物品
求是否可能达成,
题解
Sol
注意到,每个人手上的物品一定是越变越喜欢的。
注意到,每个物品一定要么向右要么向左。
假设
此时我们就有
继续观察:对于任意一个
以向左的情况举例,那么
假设
对于向右的情况同理。
现在我们知道每个
考虑加哪些限制。
注意到选出来的方向一定满足
这之后,我们只要让每次交换都合法即可。
最后观察一个性质:对于
这是因为我们知道
那么我们对每对
可以发现这样如果有解,跑出来的解一定
对每个
21. QOJ10042 - Scheduling [E/K] ✔️
题面
有
题解
Sol
如果没有不能相邻的限制,那么这个是容易的:我们只要从左到右扫,每次取出右端点最小的位置将其匹配掉
考虑强行改一下上面的做法,我们维护两个集合
但是尝试一下可以发现,我们按照任何一种看起来比较有道理的方式比较两个集合,最后都对了
具体地,我们可以证明如下结论:
- 对于任意一个状态
,如果其存在合法状态,那么一定有一个集合能够全维偏序同状态的其它所有集合 - 对于
都存在合法状态的情况, 一定能全维偏序
Proof 好像有点问题。 称可以取到状态 我们证明如下事情:如果 对于任意 如果 现在 因此匹配 而一开始的两个结论也就可以归纳证明了,相当于是已知 ~~Proof~~
这之后如果我们删除掉
这个直接写就是
- Title: task17
- Author: Flamire
- Created at : 2025-05-06 00:00:00
- Updated at : 2025-06-06 16:49:35
- Link: https://flamire.github.io/2025/05/06/task17/
- License: This work is licensed under CC BY-NC-SA 4.0.