loj 随机做题
玩一下随机做题好了。
看大火都有难度标识,我也整个好了,打分类似贴吧的,五分制。( 主要不了解 CF 的评分,而且我评判肯定是相当不准确的
不是自己写出来的会打颗星。
[loj2250]
Tag & Difficulty
Tag: 仙人掌、dp | Difficulty: 三
solution
做法:一般仙人掌的题都是先考虑树上咋做,再不济也能转个圆方树,所以先看看树。
容易想到题意可以转换成选出若干条边不相交链的方案数。这东西直接 dp,即设
更进一步,我们可以发现考不考虑父亲边的意义都不大。因为对于一个点而言,它考虑父亲边也要拿去匹配,不考虑也可以隐性地放置而不去理睬。也就是说,我们可以大胆地考虑直接匹配儿子,因为如果实质上我们并没有选取这个儿子的父亲边,也可以隐性地认为与它匹配的也没有选取,如果选取了,那对应地也选取了。即设
而仙人掌情况在转换完题意就结束了。环上的边都不能使用,于是去掉所有环上的边,剩下来的连通块都是树,各做一遍就好了。时间复杂度
1 | //2022.2.5 by ljz |
[loj545]
Tag & Difficulty
Tag: 贪心、STL | Difficulty: 思维二,代码实现三
solution
做法:说下我的思路历程。
开始我并没有注意到两个相等的数异或这件事,我先是注意到一定要是
再想了一下,发现两个相等的数的异或可以更小。于是不加证明地,我猜想每次选择这两种情况中最大的那个一定是最优的,事实证明是这样的,证明也并不复杂。
实现时,不知道为什么 deque
的空间会爆,把其改成 vector
就空间绰绰有余,这是为啥啊。
时间复杂度
坑:把所有零先行去掉。
1 | //2022.2.7 by ljz |
[loj6073]
Tag & Difficulty
Tag: 可持久化线段树、重链剖分 | Difficulty: 三
solution
做法:太久没写数据结构了,这种题都差点不会了。
首先可以注意到信息是可加减的,即题目所求的可以改成
而对每个点而言,它的
实现时,可持久化下传标记确实有点麻烦,还是写了标记永久化。( 主要担心爆空间哦 )
1 | //2022.2.7 by ljz |
[loj2655]
Tag & Difficulty
Tag: 结论 | Difficulty: 二
solution
做法:可以猜一个结论,所有点一定是在
但这并不一定是最优的最小花费,但由于边长已经固定了,那么一共只有
1 | //2022.2.8 by ljz |
[loj3082*]
Tag & Difficulty
Tag: 线段树、二分 | Difficulty: 五
solution
做法:呃呃,要捋清楚再写出来有点累哦。
首先我们能判断出水流的方向,只要看开孔的两侧谁的水比较高就谁从哪一边流过去( 当然首先得判断孔高度是否大于水 ),不失一般性地,我们假设水从左往右流。
模拟一下水流的过程,大致可以分为三步。设开孔处为
最开始,左边和
然后,把所有右边与
最后,把还剩下的水继续推平。
为了方便,我们将这三个步骤抽象成比较合理的形式语言。
设
接下来将三个步骤表示下。
第一步则是找到
第二步则是找到最大的
第三步我们除了推平,同时要修正第一步的错误,因为
形式化之后,我们要做的就是维护这三个操作了,
根据
看起来没啥用,毕竟直接递归这还是寄完了的。但是,通过观察,可以发现一个非常好的性质。
当
当
于是递归永远只用递归一边,那么复杂度就是
修改就直接打标记即可。为了每次都算
最后考虑找这个
呃呃,代码还在路上,这几天事情比较多,估计要一会儿写。
1 |
[loj2829]
Tag & Difficulty
Tag: 贪心 | Difficulty: 二
solution
做法:可以注意到与
再注意到
1 | //2022.2.11 by ljz |
[loj2000]
Tag & Difficulty
Tag: 莫比乌斯反演、整除分块 | Difficulty: 二
solution
做法:呃呃,一上来就把乘积看成加法了,虽然差不多。
直接推式子就行了,远古题还是比较容易推的。
其中
1 | //2022.2.13 by ljz |
[loj6182]
Tag & Difficulty
Tag: LCP、动态规划 | Difficulty: 三
solution
做法:先讲点正常的做法。
枚举两串后,设
这样复杂度是
注意到
然后一看其他人代码,会立刻发现有不少求
1 | //2022.2.13 by ljz |
[loj3025]
Tag & Difficulty
Tag: 模拟、STL | Difficulty: 一
solution
做法:直接模拟就行了,将已经发出信号按楼层高低排序,往下会不会碰到直接判就行了。这些动态排序都可以用各种 STL 维护。时间复杂度
1 | //2022.2.13 by ljz |
[loj2320]
Tag & Difficulty
Tag: 多项式各种操作、prufer 序列 | Difficulty: 三点五
solution
做法:看到生成树计数,不是矩阵树就是 prufer 序列。我是先考虑的矩阵树定理,然后发现确实不太难构造出边权,所以就遗憾放弃了。于是就考虑 prufer 序列,推一推式子就出来了。
首先可以把连通块看成点,
推到这一步可以说是结束了,把前者看成一个多项式,后者看成一个多项式,那么
那么答案就是
后者取
已知
这个东西也比较经典了,直接提取系数,即求
于是总复杂度
不要问我为什么代码这么怪,主要还是之前的多项式板子有点问题,导致边写边改,希望以后能写个正常的板子出来。
1 | //2022.2.13 by ljz |
[loj2861]
Tag & Difficulty
Tag: 类虚树 | Difficulty: 二
solution
做法:这题唯一的难点就是转化题意,仔细思考下题意到底可以改成什么。由于是凸多边形,于是切割实际上只是选择某一条边,然后分开来,而一条边最多会被两个三角形共用。那么我们将共用一条边的三角形连边后,这一定会是棵树。于是题意转化成了,给一棵树,每个点有颜色,问最多有多少个连通块,使得相同颜色的点一定在一个连通块里。对每一种颜色分别考虑,那么这种颜色构成的虚树一定在同一个连通块里。于是类似地建出虚树,树上差分维护下就好了。时间复杂度
1 | //2022.2.14 by ljz |
[loj2601]
Tag & Difficulty
Tag: 贪心 | Difficulty: 二
solution
做法:设每个景点车要离开的时间为
其中
于是,我们可以发现
虽然这样已经可以做了,但显然是有点麻烦,我们再改写一下前面的式子。注意到
于是再接着改写下最终答案,即
另一方面,注意到答案已经与起点无关了,所以再度改写,即
于是,此时对某个
1 | //2022.2.15 by ljz |
[loj3083]
Tag & Difficulty
Tag: 拆位算贡献、单调栈 | Difficulty: 一点五
solution
做法:容易注意到直接算比较困难,于是考虑每一位来算。于是题意等价于找全
单调栈算子矩阵贡献时为了不算重,我们对于一个将要弹出栈的点只算它到两边点之间的高度,这样就不会算重了。
1 | //2022.2.9 by ljz |
[loj6104*]
Tag & Difficulty
Tag: 贪心 | Difficulty: 三
solution
做法:都转化模型了却分析不出怎么贪心啊。
首先可以注意到每一列至少要消掉最高的好点以下的所有点,那么题意转化成有序列
于是就看了他人做法。注意到除了减到零的部分外,有些要减更多,减到负数部分。于是我们考虑除了减到零之后,还要多减少有几个。从左往右考虑,假设当前列最多还要操作
时间复杂度
1 | //2022.2.18 by ljz |
[loj6432]
Tag & Difficulty
Tag: 组合数学 | Difficulty: 二
solution
做法:怎么以前 PKUSC 还有这么简单的题啊。
对每个人分别考虑,分类讨论这个人是否在那翻倍的人之中,然后剩下的组合数都非常简单,二分找一下数量就好了。时间复杂度
坑:注意特判分数为
1 | //2022.2.20 by ljz |
[loj3274*]
Tag & Difficulty
Tag: 二分图、二分 | Difficulty: 四 ( 这可能只是因为我不会 )
solution
做法:呃呃,我完全不会。第一步转成二分图我都没想到。
我们将可能颜色会变成一样的( 原色相同、舔狗、有舔狗 )的连边,那么一个点的度数要么是
那么问题就在于找这个二分图。考虑每次找一个最大点独立集,然后暴力三次二分找到独立集外与它相连的边,然后递归地找那些不在点独立集的边。由于点度不过
1 | //2022.2.25 by ljz |
[loj3561]
Tag & Difficulty
Tag: 贪心 | Difficulty: 三点五
solution
做法:先考虑对一个
相离的可以独立考虑,那么我们要处理的就是包含关系,然后贪心处理答案。包含关系诈一看前面的选择会影响后面导致没有贪心性,实际上前后若都选,则答案不变。所以我们可以去贪心前面的选择,让前面的选择尽量大即可。从后往前考虑每个区间,隔断处一定是某个区间的起点,此时可以贪心考虑哪处隔断影响答案最大,然后更改其它隔断处的答案。注意到区间是包含关系,所以每个隔断处最多被修改一遍,利用单调栈总复杂度就是
1 | //2022.2.27 by ljz |
[loj3545]
Tag & Difficulty
Tag: 平面图对偶、区间 dp | Difficulty: 四
solution
做法:不能说是我想出来的,纯纯是因为之前看过题解了。
1 | //2022.2.28 by ljz |
[loj6086]
Tag & Difficulty
Tag: 拆式子算贡献 | Difficulty: 三
solution
做法:可以先考虑二维,然后就会发现三维是差差不多的。
我们假设当前
注意到上面两个不等式一加,左边就是它们的贡献。于是我们就可以把一个数对的贡献拆成
坑:注意要除以
1 | //2022.3.1 by ljz |
[loj3028]
Tag & Difficulty
Tag: 贪心、树的直径 | Difficulty: 零点五
solution
做法:直径一定是两个叶子的路径,所以答案就是最深的点重复然后加上原来的直径即可。时间复杂度
1 | //2022.3.2 by ljz |
[loj3239*]
Tag & Difficulty
Tag: 倍增、结论题 | Difficulty: 三
solution
做法:这种题似乎我都不会。
有一个非常重要的性质就是,若某个点在两条对边所夹出的另外一端时,则一定无解。这可以考虑反证法,然后利用凸包的斜率性质得证。有了这个结论,这题就可以宣告结束了。我们随意地找一组对边来判一下,那么最坏情况就是这个点在两条边的同侧,这说明有一条边已经满足夹住这个点的性质。剩余的那条边我们直接倍增,找找看中途有没有满足,因为凸包的斜率性质,所以这是对的。时间复杂度
1 | //2022.3.3 by ljz |
[loj6297]
Tag & Difficulty
Tag: 排序 | Difficulty: 零
solution
做法:排序就做完了,零分。
1 | //2022.3.17 by ljz |
[loj3684]
Tag & Difficulty
Tag: 性质分析、贪心构造 | Difficulty: 三
solution
做法:首先分析答案是什么,容易发现是强连通分量个数,于是就是给边定向使得强连通分量个数最少。不妨让左边一列边都往下,右边一列边都往上,这样会直观一点。
容易分析出一个性质,我们总想让右边上面的点连向左边上面的点,左边下面的点连向右边下面的点。可以发现,这样两边的最高点和最低点之间就形成了一个强联通分量。于是贪心地在左边自上而下地定向,如果当前连的右边的点在之前所有点的上面,那就从右往左连,否则从左往右连。证明是容易的,因为后者一定更劣,而前者一定更不劣。建完图再跑个 tarjan 求强连通分量即可。时间复杂度
1 | //2022.3.18 by ljz |
[loj3683]
Tag & Difficulty
Tag: 线段树、数论复杂度分析 | Difficulty: 三
solution
做法:考虑每个数在线段树上维护与它不互质的前驱,然后查询就是线段树上的区间
1 | //2022.3.21 by ljz |
[loj3671]
Tag & Difficulty
Tag: Bitset、四毛子 | Difficulty: 三点五
solution
做法:容易注意到这题是个大拼凑题。考虑询问的答案是如何得出的,容易贪心地发现是对 bitset
,然后排序那一维再套个四毛子,这样复杂度是
为啥我这个跑得这么慢啊。
1 | //2022.4.2 by ljz |
[loj2037]
Tag & Difficulty
Tag: 线段树二分 | Difficulty: 二
solution
做法:发现三个操作都异常简单,询问操作是个类似最大子段和的东西,操作一是个区间覆盖,操作二我们可以二分出修改的右端点,然后也是个区间覆盖。注意到这个二分是可以放在线段树上,同时更加注意到这个二分和修改可以放在一起写,所以就很容易了。时间复杂度
1 | //2022.4.2 by ljz |
[loj3672]
Tag & Difficulty
Tag: 单调性分析 | Difficulty: 二
solution
做法:这真的是 CTT 的题吗,这难度是不是有点。
uoj 有个简化题意,一看就懂了。考虑一个合法