【记录】MX 11.17~11.23

· · 个人记录

11.17 ~ 11.23

11.17 限时训练

T1

P12016 [NOISG 2025 Finals] 震踏 - 洛谷

用到了曼哈顿距离和切比雪夫距离的转化，对于这种需要旋转坐标系的问题非常有帮助，然后就是发现相对位置是不变的，所以直接前缀加单点查，树状数组维护即可。

T2

P12194 [NOISG 2025 Prelim] Snacks - 洛谷

直接写了个大力线段树维护，每次操作区间赋值单点加，区间求和。

T3

P12017 [NOISG 2025 Finals] 可达性 - 洛谷

一个不错的树形 dp，考虑设 f_{i,j} 表示 i 子树内可达 j 个点是否合法，转移根据 l_u = l_v 分类讨论，然后按照每条边是否连通分类讨论即可。

T4

P12018 [NOISG 2025 Finals] 机器人 - 洛谷

发现对于最右边的每个点，能到达他的点是一段连续的区间，于是问题变成了给定 个区间 ， 次询问区间 ，询问覆盖区间 需要最少区间数量，可以直接倍增维护。具体的维护倍增从每个点出发，向后最远能到哪，然后跳倍增数组即可。

11.18 模拟赛

T1

Problems

发现一个性质是，最大值要么是 0，要么是 1，于是问题变成我们需要找到有多少个区间满足 mex = len + 1，也就是整个区间排序后是 0,1,2,3,4,\dots,len - 1。

发现必须经过 0，于是考虑按每个 0 分段处理，由于知道了区间最大值就可以知道区间长度，因此我们亲定最大值位于左边，右边的情况我们反转序列再做一遍即可。

之后我们考虑枚举左端点的位置，维护前后缀 \max，这样我们可以求出区间长度，也就求出了右端点位置，然后判断右端点的最大值是否合法，这样我们就只需要知道，这段区间是不是数字各不相同即可。

如何维护这个东西呢？其实可以直接对每个位置 i 维护 i 向后最远到哪能满足这段区间内每个数只出现一次，然后就做完了。

T2

Problems

考虑把变化维护到折线上，每次分治暴力枚举区间，时间复杂度 n \log n，还需要主席树维护一下前后缀信息，具体的可以去看官解，感觉口胡太麻烦了。

T3

反射容斥，还不会 \kk ~~。

11.19 限时训练

T1

P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2 - 洛谷

考虑贪心的从大到小做，然后变成了一个二维数点？实则发现合法转移式子两个是肯定同时满足的，于是维护两个值，一个排序，另一个维护单调栈即可。

T2

P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2 - 洛谷

很简单的一个 dp，考虑设 f_{i,0/1/2} 表示前 i 个灯合法，最后一个是 0/1/2 颜色的最小花费，转移是好写的，注意把 f_{i,2} 初始化成前缀全都熄灭的花费即可。

T3

P7405 [JOI 2021 Final] 雪球 / Snowball - 洛谷

很有难度的一个题。

首先你需要发现一个性质：每个雪球的贡献点是一段区间。

然后发现当两个雪球之间的区间端点确定了，就不会再变了，于是我们可以考虑暴力维护这个东西，复杂度 O(nq)。

考虑怎么优化呢？这一步非常困难，你发现这东西是具有可二分性的，二分最终确定端点的时间，就可以处理出每个端点，时间复杂度 O(n \log q)。

T4

P7804 [JOI Open 2021] 决算报告 / Financial Report - 洛谷

发现题目其实就是要让我们找一个上升子序列，我们发现对于 i 能转移过来的 j 是一段区间，我们可以用并查集维护这个东西，然后我们按照值从小到大去做，每次转移找到转移区间，线段树维护即可。

T5

P12196 [NOISG 2025 Prelim] Lasers 2 - 洛谷

哇好牛的一个题，考虑最大的这个块一定要被挡住，然后考虑 dp。

设 f_{i,j,0/1} 表示前 i 列，有 j 个位置是能照到的，有没有出现 mx 长度的照不到区间，不需要移动的贡献和最大值，发现转移实际上时对于右端点位于 i 的区间，覆盖到的范围加上一个它的权值，于是线段树维护即可。

P12196 [NOISG 2025 Prelim] Lasers 2 题解 - 洛谷专栏

T6

哇这题太难了，我们发现当我们使用 3 个数字一组，用 4 组凑一个人，那么我们需要满足任意 4 组组成的一个序列一定有一个人，否则我们可以先走这个东西，然后再走到某个位置，这样就确定不了一个必定赢的人了。

然后拿背包把这些合并起来即可，感觉代码太难写了，直接盒了。

11.20 模拟赛

T1

Problems

简单题，考虑排序后双指针指一下即可。

T2

Problems

发现排序后后面的是前面的倍数，类似一个进制形式的东西，同时发现这样的 v 只会有 \log 种，于是我们考虑对于 v = a_i 如果他没被选中，可以把 k 个合并成一个 v = a_{i + 1} 的物品，同一类按照性价比选即可。

T3

不会啊，反射容斥（刚刚那个 T3 好像不是反射容斥）。

T4

Problems

发现这东西一定是从小到大推平，我们推出式子，发现从两边先搞一定是更优的，然后就是要维护前后缀最小值，区间修改，线段树维护即可。

11.21 限时训练

P14333 [JOI2021 预选赛 R2] 安全检查 / Safety Inspection - 洛谷

考虑这东西可以二分，然后 check 考虑从后往前做，这样走到后面的人过来就不需要花费路程，只需要花费工时。

P14331 [JOI2021 预选赛 R2] 煎饼 / Pancake - 洛谷

数据范围很小，状态数可以搞得下，直接搜索就行了。

一些杂题

P14566 【MX-S12-T1】取模 - 洛谷

简单题，发现答案是 \max(x - y,z)，这里 x = \max(a_i),y = \min(a_i)，z 为严格次小。

P13520 [KOI 2025 #2] 存放箱子 - 洛谷

考虑相当于是给了一些区间，要求最少集合，使得同一集合内区间不相交，线段树维护即可。

P4317 花神的数论题 - 洛谷

考虑数位 dp，然后统计答案即可。

P2610 [ZJOI2012] 旅游 - 洛谷

将这棵树建出来之后，其实就是求树的直径。

T686591 「IDT41-D」旧影 - 洛谷

感觉这题没啥营养啊，就是直接 f_i 表示以 i 结尾的最大权值，然后动态开店权值线段树维护 dp 值即可。

P3116 [USACO15JAN] Meeting Time S - 洛谷

图上 dp 板子题，按照 topu 序 dp。

P10613 [PA 2008] Cliquers - 洛谷

整数拆分的模板，这个要好好看一下。

P5290 [十二省联考 2019] 春节十二响 - 洛谷

dsu on tree 好题，考虑两棵子树该如何合并，按照这种方式合并起来即可。

P2061 [USACO07OPEN] City Horizon S - 洛谷

考虑从前往后维护一下当前最大值，貌似还可以 ODT？直接维护一下最大值和贡献区间即可。

P7924 「EVOI-RD2」旅行家 - 洛谷

P1407 [国家集训队] 稳定婚姻 - 洛谷

几个简单的 tarjan。

ABC

感觉没什么好题，其中 E 是个大模拟，F 是组合数推式子，用组合恒等式优化一下就行了。