做题笔记 2024 NFLS NOI 模拟赛
2024.5.21 展开目录
树数术展开目录
给一颗
假设
前缀信息可以用兔队线段树维护。使用
查询前缀信息在不强制在线时可以离线之后用扫描线 + 二分解决。本题用这种方式容易做到
Perotation 展开目录
给一个
一个序列是满足条件的当且仅当每个数后面比他小的数的个数均为偶数。于是我们试图维护
考虑分块。不妨设
一个重要的观察是,本题在询问时我们只关心一个块内是否存在 std::lower_bound
,会多一个 std::lower_bound
常数很小,没必要将其替换掉。总复杂度视为
术数树展开目录
定义
给一张无向图,边有边权。一条路径的权值为路径上所有边的边权的
2024.5.24 展开目录
棋盘展开目录
有一个
Alice 希望权值尽可能小,Bob 希望权值尽可能大,在这样的目标下,我们可以首先二分答案
感性理解,限制格子被移到的次数小于
我们称权值
另外需要注意到本题中双方都可以在轮到自己操作时选择结束游戏,所以如果
二分图博弈的结论是,先手必胜当且仅当起点被包含在二分图的所有最大匹配中,证明并不困难。
于是就有了一个暴力的做法,建出
考虑直接在原来的网格图上做最大匹配,不过匹配这个形式并不方便描述,可以将其转化为最大独立集。一个点向同行同列的异色点连边,所以最大独立集相当于选取一些行和列,选取同时落在这些行和列内的白点,以及同时落在其余行和列内的黑点,最大化所选点的个数。
如果我们将
2024.5.25 展开目录
树的镜像 / LG4672 [BalticOI 2011 Day2] Tree Mirroring 展开目录
做法很多,关键在于定位到一个叶子或者一组对应点。
叶子总是二度点,但二度点未必是叶子。我们考虑广义串并联图方法,不断缩二度点。特判掉链和环的情况,不难发现,若图合法,则我们总是能缩出重边,那么一个叶子就是其中一条边对应的原图上路径的中点。更简便的方法是,若
据此我们就可以定位出所有的叶子。分别以
我们可以用所有叶子将图分成两部分,用树哈希判断以
注意细节的处理。
2024.5.27 展开目录
排序幻觉展开目录
给一个长度为
小于等于这个限制实际上是非常强的,这个条件满足当且仅当两数相同,或在两数最高的不同的二进制位上,较小数为
图展开目录
给一张
保证无向图中的每条边
由于有
我们需要利用答案对
为了让式子更好看一点,我们将贡献改为
这样就可以 dp 了。设
复杂度
分身术展开目录
从
对每个
事实上
这样容易做到
另一个符合直觉的事实是若一个区间在
这样若我们已经有了
2024.5.28 展开目录
语言学展开目录
给
我们容易求解的是这样的问题:每有一个
现在问题是如何去重。
若一个模式串
现在只需要考虑间隔不是最小周期倍数的情况,根据 border 理论,所有周期可以被划分成
注意这部分统计中有可能重复统计最小周期的倍数,最后要将这部分贡献去掉。一个例子是
总复杂度为
航行展开目录
有
这个人的初始速度总是为
速度每次只会加减
基于此,有效状态
状态间会循环转移的原因在于速度可正可负,但是速度的正负性改变时总会经过
最后我们对
2024.6.1 展开目录
小班课展开目录
有
如果不考虑优先度的问题,单纯的让尽可能多的学生去匹配一个优先度序列中的课程,这就是二分图匹配,可以用 Dinic 解决。但是网络流无法处理优先级问题。
为了处理优先级,我们想到了匈牙利算法,因为匈牙利算法对于每一个左部点的匹配策略恰好就是,按顺序枚举出边,找到第一个可以匹配的右部点并匹配上。用匈牙利求出匹配后,我们需要确定一个排列使得按此顺序选课恰好能取到我们跑出的最大匹配。
对于第
可以结合匈牙利的流程感性理解图中一定不会连出环。对 DAG 跑拓扑排序即可。
复杂度为
密码展开目录
给一张
这个询问次数看起来就是
很自然的考虑二分一个点的出边,这样我们需要支持查询
我的考场思路是考虑到
注意到我们可以用
2024.6.3 展开目录
FCT 展开目录
给长度为
求
一个经典结论是
模
一种做法是,考虑一共有多少对
也可以考虑分治,将序列
B 展开目录
有两个点集
两个点集内部的点都完全等价,所以随机选择起点和终点的过程不重要。
为了求两点间距离的期望,我们考虑用 dp 维护一个类似 bfs 的过程。
朴素的想法是设
但是容易发现这个
总复杂度
篮球大师展开目录
给一个二次函数集合,每个二次函数有定义域
我们熟知的维护函数最值的数据结构是李超线段树,其可以支持插入一次函数和查询
但是处理一次函数的方法并不能推广至二次函数,原因是两个二次函数可能有多于一个交点,在线段树上插入时中点处优的函数可能在两侧都劣,从而之前的复杂度分析不再适用。
EI 的集训队论文中介绍了一种高效的维护函数最值的方法。
首先介绍 DS 序列:记一个长为
很容易发现 DS 序列与函数最值之间的联系。考虑对所有函数取最大值得到的分段函数,考察每一段最大值是从哪个函数上取到,这就是一个 DS 序列。而
本题中,两个二次函数最多有两个交点,同时由于对定义域左边界有限制,所以
记
所以,如果希望维护函数最值,只要两函数间至多有
如果只需要支持查询,可以分治求出最大值的分段函数,合并两个分段函数是容易的。本题由于需要支持插入,使用二进制分组即可,总复杂度
2024.6.7 展开目录
图上删边 / CF1368E Ski Accidents 展开目录
我们只能删
启发是,构造题若不需要最优化操作次数,则可以考虑在可以接受的范围内通过更多的操作使整体有更优的性质。
2024.6.8 展开目录
想不出展开目录
在平面上给定
若将无界区域也算进答案,那么由欧拉公式或直接观察可得,区域数应当为所有射线的交点个数
一种符合直觉的射线定向方案是,若点左上方的点比右下方的点多,则连向上的射线,否则取向下的射线。考场上我只是证明了在这样的定向方案下,每个点连出的射线上的交点一定超过左上方点与右下方点数量总和的一半,但是这个证明不够严谨。
一个关键结论是,若一个点
于是回到之前猜测的基于贪心的定向方案。不妨设点
于是我们可以用二维数点统计答案。复杂度
题解还有一种人类智慧的答案统计方法。对于所有射线向上的点
2024.6.11 展开目录
虚无展开目录
给定长度为
01 序列上的不下降子序列形如前面一部分是 0,剩余部分是 1。所以对于
可以将特殊的段一分为二,将问题改为划分
可以将
费用流模型参考:


也可以直接观察出答案在
两种做法复杂度均为
2024.6.14 展开目录
装甲方阵 / CF1427G One Billion Shades of Grey 展开目录
直接处理绝对值通常是困难的,一种常见的处理方式是,如果我们要最大化某个绝对值,可以直接将绝对值拆开枚举符号。但是本题中这种方法显然无法使用。
本题中要对多个绝对值求和,我们考虑拆贡献。可以将
枚举
装甲会战 / TopCoder14379 RPSRobots 展开目录
刘一平老师在 WC 讲的题。
石头剪刀布可以用三进制减法刻画。然后有聪明人想到了用三次单位根来描述这个三进制除法,这样,我们还可以通过
我们希望两个机器人的策略序列无论如何循环移位,用对应位置进行游戏后,结果中的胜平负场次都相同。循环移位后用对应位置进行游戏可以用循环差卷积刻画,或者也就是将某个序列反转后做循环卷积,我们希望的就是卷积结果的每一位都相同。
做循环卷积是困难的。一个关键的事实是,做长度为
现在问题转化为,对一个「策略序列」和一个「策略序列的反转」做长度为
做多项式乘法我们会先做 DFT 再做 IDFT。考虑 IDFT 的实现方式仍然是求点值,卷积的结果每一位都相等也就意味着此时 IDFT 求出的点值全部相等,而只有常函数能做到这一点。这就要求原本的两个多项式 DFT 的结果在
可以计算发现,无论策略序列是否反转,DFT 结果中的非零位置并不会改变。
于是问题转化为,给一些集合,选取一些集合满足它们两辆不交,求方案数。这是容易完成的。
这个题,确实是太厉害了。
这篇博客烂尾了。
本作品采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可。