又幻想了

· · 个人记录

你说得对但是又幻想了

虽然D1已经尽可能打到最高了，但是D2和联赛一样是无法挽救的。

但是接下来是幻想时间！

2024-11-31

今天是联赛，但是昨晚睡得非常不好。

开考前看了一眼样例，发现两个取模一个字符串一个DS？

优势有一半在我啊

首先开完所有题，想了一会，感觉T4会了64pts，T3题面有点鬼畜后边再看，T1T2都是简单题，可以冲的。此时是 9:00。

首先写T1，直接分段贪心匹配即可，但是实现起来有点麻烦，写完已经9:30了。

然后火速开T2，先写了 O(n) 的暴力，然后发现可以矩阵快速幂优化，火速写了 O(m\log n)，此时是 10:00。

还有3h！优势在我！

迅速去写了T4的暴力32pts，然后写B性质的时候发现了一点问题啊，这个玩意是 O(\frac{nq}{len}) 的假做法啊。

？？？我请问呢？

这个时候已经10：40了

哦哦哦按照dottle教的分块写就对了。

于是写写写，细节多的一批，写到了12：20才调出来。

但是这个时候发现 O(n\log^2n) 似乎只能跑 10^5？

然后火速写了个快读，又给二分上下界剪了点枝，这才勉强能跑进时限。

然后又把之前的 O(\frac{nq}{len}) 做法拿过来阈值分治了一下，现在就跑得飞快了。

此时只有20min了！

赶紧开T3，发现AB性质是好做的，想了10min，写出来了。然后赶紧去测了所有题的语法，交了所有题。

于是结束了？

结束了

出来发现那头和xht都打了304，高二的好多都是300+ 虽然不是最好的，但是也不错了？ 但是T4的关键trick是区间lca可以转化成区间两两点对lca的deep的min啊啊啊，那我这个做法直接搬过去不就是能冲过去的吗？ ## Day ?? 查分了，没挂。 但是xht挂到了260，有点可惜。 直接继续停课了，不用考期末了！ ## Day ? 欸我宣布 Dovish 没有在2025年参加任何wc。 ## Day ??? 省选D1 头天晚上还是睡得非常不好，迷迷糊糊像睡了又像没有。 但是精神状态还算不错？ 进场之前听了几遍 Cyberangel，非常上头啊！ 开题！ 题面上T2这个6s2g直接给我吓到了，这不是DS这是什么？ 开完所有题，感觉T1不难，T2只会是在bitset上做文章了。T3完全不会一点。 然后倒序开题先把暴力拼满，T3拼了暴力之后发现自己似乎会了树的性质？然后写了棵 fhq 上去，但是甲烷了。哦子树之间的包含关系还有点复杂嘞？然后又想想想还是不会一点。欸这个性质似乎是在说一棵树内的子树合并是只能并列不能相交的？哦哦哦这么会，然后写写写。森林的合并就没有限制不能包含了，于是直接按照之前的那种做法做即可。 此时已经是 10:40 了，赶紧测了语法就交了。 然后开T1，先把对于每个数的判定写了，然后发现本质不同的数只有 $O(n)$ 个。于是直接离散化一下就好了。 此时是11：20，优势不在我！ 开T2，有点激动，是不是自己能打上200了？ 首先把整个图以及 b 映射到 a 数组上，于是我们此时就是对于bitset上的一段区间查询。 交换a似乎是很难做的，那就先考虑A性质。 区间询问满足条件的 b 的最大值？ 那我能不能二分 b 然后让将 $\le mid$ 的 b 标记为 1，再&上这个这个点可达性的bitset就可以check了？ 但是直接这么做就没法交换 b 了，并且空间也是 $2\times\frac{n^2}{\omega}$ 的，开不下一点。 欸容易想到分块！ 我们直接对b的值域分块，对于每个块，把大于等于其左边界的值丢到bitset上，这样修改复杂度就是 $O(T)$ 的了（T是块的数量），查询复杂度是 $O(\frac{n\log T}{\omega}+\frac nT)$。 但是此时只有1h了！ 冲冲冲！ 首先交换a的操作对这个重映射是非常不友好的，所以暴力和特殊性质分开写，暴力是写得很快的，只要10min不到。 然后写A性质的时候发现映射关系还是有点混乱。于是又写了一份暴力，用来调试映射关系。 最后5min极限调出来了！来不及测语法就直接交上去了。交完了才开虚拟机测语法 谢天谢地没有什么问题 最后是 $100+52+52=204

小赢那头一手，出来发现大家似乎都只有130左右？forest写了180+，wht有172，那头把T2冲出来了

卧槽我是不是能翻盘了！？！

然后D1下午去打原神了，平静一下浮躁的心情。

D2加油！

Day？？？？

在T3下边写了点小作文

欸卧槽这个题好像一道都不会啊？

先冲T1？我只怕是要遭起，还是先写暴力吧

T2暴力不难写，直接枚举有图的形态再枚举生成树即可。B性质直接枚举树边的状态看整张图的连通性直接24pts入手。欸能不能直接对这个东西上容斥啊？想了好久发现不会一点，直接弘文了，丢了不管。

T3感觉单调递增是有点性质的，但是也是想了会发现没有一点前途，赶紧写了个裸的复杂度位置的暴力就跑路了。

卧槽怎么就过去10：20了？？？？？

于是来决战T1。

这个题感觉有点眼熟啊？是不是迪茵集训最后一天T2的序列上版本？

但是切记不要先入为主意淫题目难度以及题目方向！

所以还是老老实实观察题目本身的性质吧

感觉一眼看上去不会，先想了一下AB性质怎么做。

然后写了个暴力拍了一下发现存在一种贪心策略。（lim为第一关键字，len 为第二关键字）

欸那是不是就是直接把路径上挡住的直接往后推？

或许是对的吧？感觉有点道理的，但是这个yes/no的判断让我非常不敢相信大样例的强度啊，于是还是写了份暴力的。可以证明的是显然不会推一个箱子推到一半去推别的，除非是挡道了，且挡道了也只会恰好推到能放下的位置上去，不会多推一步的。

于是做法就很明显了，每次找到能操作的最优的那个点，然后直接二分出第一个阻碍的位置，把区间赋值为等差数列即可。

欸但是这个玩意有点诡异啊，怎么找到lim最小且len最小的？此时，过去乱冲DS的不好回忆又一次显现在我脑海中于是我决定考虑一下是否有必要这么做。

欸，仔细一想，似乎第二维这个限制就是没有必要的了啊。

那lim是不会改变的，直接排序一个个做就是对的了！

但是想到这里已经是12：00了，火速开写！

写写写，调调调，最后压哨写完了交了上去。

欸出场才想起来这个鬼玩意大样例一组只有一个极限数据？

那搞屁啊卧槽

这下不知道要挂多少分了。

[60,100]+24+8=[92,132]

这下D2被翻了。

Day ？￥#%……&%

出分了:

但是联赛没有队线啊，不知道能不能翻进去。 upd:翻进去了/oh forest差一点队长，有点可惜了 ## Day #%#$%# 用给核桃投垃圾题的钱给女朋友买了个礼物 欸等等，我啥时候有女朋友了？ 原来只是一场梦啊