3月每日总结

Tue Mar 04 2025

47 分钟

life 日记

11458 字

3 月 4 日#

考试。

T1#

神秘小结论 + 神秘小 dp。具体就是来算每条边对于答案的贡献，但是因为先看 T1 没甚思路，所以便去把 T2 写了。欲知写完 T2 如何，请听下回分解。

T2#

首先看到题目，一眼大模拟。于是口胡了一个做法。但是，准备开写的时候，发现有问题：怎么判断每条边哪边是里，哪边是外。然后又口胡了 10 min，就真正的开写了。写完了，已经做好心理准备和 bug 大战 300 回合了，但是居然过了大样例？！~~意外之喜~~

T3#

依然是先口胡了一个做法，发现 $f(x)$ 就是 $x = ac + bd$ 的正整数解个数。想到枚举 $[L,R]$ 内的每个 $x$ ，再枚举 $[1,x-1]$ 的每个 $i$ ，这样我们就只用统计 $ac = i$ 的正整数解的个数了，显然是因数个数。 $O(n^{1.5})$ 预处理， $O(n^2)$ 查询。赛时就想到这里。赛后听 hrl 说可以用 FFT 优化到 $O(n \log n)$ ，于是去学了 FFT 一个一知半解。但是又听说不用 FFT 可以有 $O(n^{1.5})$ ，于是兴致勃勃的放弃 FFT。但是 $O(n^{1.5})$ 的神秘小做法还是没搞懂，听说有数论分块做法，明天问问。

T4#

听 zcy 讲了，也懂了，但是改好题推荐去了，于是没补。好像这个做法和大模拟一样，~~不想写啊~~。明天写了。

总结：今天的策略有进步，但不多。码力似乎有所提升？也许是幻觉。机房 rating 有进步， $17.7 \rightarrow 20.0$ ，慢慢来咯。

3 月 5 日#

不是考试就是综合训练。

Game on Tree (Hard)#

首先看的不是这题，但是首先 A 的是这题。

先口胡了一个神秘小 dp，果不其然连样例都过不了。经过一番严密推理发现 dp 状态设的有点漏洞，于是把漏洞补起了，内心浅浅的博弈了一下便开始写了。令人震惊的是居然过了样例。更令人震惊的是竟然就这么水灵灵的过了。上洛谷一搜： $\textcolor{3498DB}蓝$ 的？！我能切蓝题，真的假的？

当然是假的。

Minimizing the Sum #

其实最先看的是这道题。先口胡了一个假做法：把每个 $|a_i - a_{i - 1}|$ 都扔到一个 multiset 里面，每次取最大的用来更改答案。但是很显然这个是一个错的。因为有些时候，两个 $i$ 所对应的 $|a_i - a_{i - 1}|$ 是一样的，但是他们俩并不一样优，要判断的话需要 $O(n)$ ，显然不可取。

我见过好多这种“两种决策看起来一样但是实际上不一样，要决定哪个更优需要再考虑好多麻烦的东西”这样的题。这种无一例外都是 dp。看到 $k \le 10$ ，就想到把它塞到状态里。然后就搓了一个 $O(nk^2)$ ，过了。

说句闲话：本来以为是 $O(n^2 k)$ 的，AC 的时候吓死我了，我还以为 CF 神机一秒能跑 $3 \times 10^{11}$ 呢。

Infinite Sequence (Easy Version)#

首先就想到 $a_m = \bigoplus\limits_{1}^{\lfloor \frac{m}{2} \rfloor} a_i = a_{m - 2} \oplus a_{\lfloor \frac{m}{2} \rfloor}$ ，但是如果递归求解的话，因为有 $m - 2$ ，所以是 $O(n)$ 起步的。显然不可取。下午看了题解才知道如何变成 $O(\log n)$ 。

还是太菜了。

Nene and the Mex Operator #

这道是蓝的，但是没有切出来。赛时只想到了要操作的区间必须出现 $[0,len - 1]$ 的每个数才最优，实际上可以通过神秘小操作给他操作到这个区间内每个数都是 $len - 1$ 。先用区间 dp 求解答案，再使用神秘小构造求解操作方法。

总结：实力有增长，但不多。去看了一眼 2023 的 S 组，T2 一眼能想到 50%，多看几眼应该就能做出来。

3 月 6 日#

考逝。

totscore： $\huge \color{red}{40}$ 。

究其原因是 T2 的暴力爆炸了。

T1#

没看。

正解是这样的：对于每条边，有 $\frac{1}{2x + 1}$ 的概率使得连通块的数量 $+1$ ，剩下的会使同色的对数 $-1$ 。直接算就行。

T2#

爆炸了

不然不会只有 $40$ 分的呜呜呜。

正解：题目里没写对于硝硼铀数量的限制，我们考虑钦定一个数量限制。设 $dp_{i,j}$ 表示到了第 $i$ 个字符，一共选了 $j$ 个硝硼铀。用 pair<string,string> 存。转移有：dp[i][j] = max(dp[i][j],{dp[i - 1][j - 1].first + s[i - 1],dp[i - 1][j - 1].second + t[i - 1]。s[i - 1] 是因为 $s$ 和 $t$ 是 0-index。

就这个“没限制就钦定一个限制”这操作给我整懵了，这谁想得到啊？

没逝，这次见过了没准下次就想得到了呢？

T3#

神秘小算法。

我们把每次删掉一个数扔掉，因为处于最优性考虑你不会去选同样的一个数。那么先掏一个样例：4 7 3 6 1 2 5，最先取的肯定是 6，其次是 3 或者 1。经过一番暴力，我们发现，对于 $\forall i \in [1,n]$ 的每个 $a_i$ 可选次数形如 1 2 3 4 3 2 1。我们考虑答案是在值域上的一个区间，那么我们把 $b_i$ 设为 $i$ 的可选次数。那么 $b$ 就是 3 2 3 1 1 4 2。考虑 $[2,4]$ ，我们看到 4 的出现次数最小，首先选它。选完， $b$ 在 $[2,4]$ 上变成了 1 2 0。以此类推。

考虑一个 $pre_i = \sum_{j = l}^{r}[b_j \le i]$ 。很明显要有 $\forall i \in [1,n],i - b_i \ge 0$ 。用线段树维护这个 $i - pre_i$ 区间最小值。区间合法即为区间最小值 $>0$ 用双指针解决。

感谢每一位愿意为我讲题的人。

T4#

没看，考场骗了 40。

总而言之：T1 看到是概率与期望就怕了，没写。T2 的暴力都打挂了我是真的。。。T3 一点思路都没有。就 T4 骗了 40。还是得多练。

T2 那个“没限制就钦定一个限制”是真的没绷住。

3 月 10 日#

这周只要考两次，今天不考。

Shuffling Songs #

一眼做法 + 一眼实现 + 亿眼优化。

第一眼就看出来是个转图论。对于有相同的建边，然后搜出来最长的路径。然后就打了一个暴力。不出所料，T 了。于是加上了神秘小剪枝。不出意外，T 的地方变晚了。但是优化不动了。考虑记搜。因为 $n \le 18$ ，所以 vis 可以塞进一个二进制数里面，时空复杂度都是 $O(n^2 \times 2^n)$ ，十分的劣。

Messenger in MAC #

两眼做法 + 两眼实现 + 调了 2h 的优化

第一道题的剪枝剪不动了就来看这题，但是写挂了，于是去把 T1 写出来就来写这道题了。

发现 $a_i$ 对于答案的贡献无关顺序，但是 $b_i$ 就有关，于是考虑把信息按照 $b_i$ 排序，然后做 dp， $dp_{i,j}$ 表示钦定 $i$ 一定被选， $[1,i]$ 里选了 $j$ 个的最小花费。答案就循环每个状态，找到最大的 $j$ 使得 $dp_{i,j} \le l$ 。

本来想的是单调栈优化的，但是好像不行，改成了前缀 $\min$ 优化就过了。

Vlad and Trouble at MIT #

一眼做法 + 一眼实现 + 不用优化

这道题总共就花了 20min。那我上午苦思冥想的 2h 和调洪文的 2h 算什么？

对于每个点 $u$ 有 $dp_{u,0}$ 表示这个钦定这个点为 $\texttt{S}$ 时的最小代价， $dp_{u,1}$ 表示钦定它为 $\texttt{P}$ 的最小代价。对于本来就是 $\texttt{S}$ 的点 $u$ ， $dp_{u,1}$ 显然为 $\inf$ ，不进行转移。反之亦然。转移方式显然。

剩下 $3$ 题都是看题解过的。还需要巩固。

后日谈#

然后下午就挺无所事事的，于是去把昨天 arc 的 b 改出来了。感谢 yzp 晚自习问我这道题，不然我绝对不会记得这道题。

改完了 arc194_b，去随便掏了两道 dp 写了，领悟 dp 小技能：状态存不下就把答案塞到状态里。

然后又去写了一道概期。起码是知道了怎么用高斯消元。

NOIp 是 11 月下旬，现在是 3 月中旬，我还有 8 个月的时间。

3 月 11 日#

今天不用考试，打昨天晚上 CF 的 VP

A，B 题太简单不说。

Breach of Faith #

反正赛时没做出来就是了。

Scammy Game Ad #

祝老的练习还真是卓有成效，1800 的题都做得出来 1400 的做不出来。。。

我们发现只有穿过每个闸门后加的是能动的，但是原本放着的不行，我们需要三思而后行。考虑两个同加或者两个同乘同一个数是与加的放在哪个位置无关的，考虑每个不满足上面条件的闸门。如果操作符不同， $\Delta$ 肯定是放在乘的地方。~~显而易见~~。对于相同，同加我们不考虑，同乘肯定是放在乘数大的那边。这个是真的显而易见。

~~感觉做法有点假但是它过了~~

Finding OR Sum #

赛时想到了正解，但是赛时没写出来。把做法告诉了 VP 还要 0.5h 的 yzp，他倒是写出来了。~~也算是某种意义上的 AC~~

考虑第一次查询 $\texttt{0101010101}... = (\texttt{2AAAAAAAA})_{16}$ ，将查询的答案减去二倍 $(\texttt{2AAAAAAAA})_{16}$ ，我们得到了 $x + y$ 的奇数位的信息。反之可以得到 $x + y$ 的偶数位信息。我们就可以得出答案了。

看来以后 VP 还是得晚点开。

3 月 12 日#

昨天晚上去打了 div.3，然后今天看到排名： $5$ 题能排到 $1000$ 名以内。我记得上一次 VP 的 div.3 $5$ 题都排到 $3000$ 多名去了。上 clist.by 瞅了一眼 T5 的难度：1700，而且做法基本上一眼。~~我真厉害~~

祝老的练习真是卓有成效。

Empty Triangle #

这就是昨天晚上的 T5。

赛时是这么想的：我先问随便问一个 1 2 3 吧。然后假设它返回的是 $i$ ，我们就再问一个 1 2 i。但是我们的出题人造数据肯定会想到有人会这么写于是就想把它卡掉。要不我 rand() 决定替换哪一个吧。好，开干！

然后就过了。。。

主打一个我估摸能过它就能过。但是题解用了神秘小方法证明出来这么询问在 $75$ 次以内问不出来的概率是 $1.2 \times 10^{-18}$ 以下。比买彩票还低。

[YNOI2019] 游戏 #

第一眼还以为是 Ynoi。。。

读完题先看一眼数据范围： $n \le 10$ 。应该要用高斯消元。然后苦思冥想 1h+。居然连状态怎么设都不知道。~~我好菜~~。于是去看题解。看到了状态的设法，于是就去推转移。也是成功的推出来了一半。于是又去看题解。于是便懂了。开始写代码。

该说不说这个系数的初始化是真的又臭又长。然后高斯消元还挂了，复制的之前的高斯消元代码。

[USACO24JAN] Merging Cells P #

其实老早以前就瞟过一眼题解，知道怎么设状态和转移。但是不知道怎么优化。于是又去看题解。

疑似有点题解过度依赖。

并非疑似。

于是去找了几道简单（吗？）的题练手。

Aeroplane chess #

简单是简单，但是我没读题。。。导致题意理解有误…

Maze #

并非简单题。

首先我们就设出来 $dp_u$ 表示当前在 $u$ 还要走几步才能出去。设 $t_i = 1 - k_i - e_i$ ，显然有 $dp_u = k_i \times dp_1 + t_i \times (dp_{fa} + 1 + \sum\limits_{v \in son_u}(dp_v + 1)$ 。但是这玩意有后效性。显然不能直接 dp。~~我们直接想到高斯消元~~。

消不了一点。 $O(n^3)$ 的复杂度直接让你飞起来。显然我们需要人工消元。于是题解直接把 dp 式子里的 $dp_u$ 之类的全部消完了？？！疑似有点消的太猛了。

然后我们的私人 HDU 评测机性能时好时坏。

3 月 13 日#

今天是考试 day。

我们初三 OIer 的日历已经没有周一还是周二的概念了，只有考试 day 和不考试 day。

T1#

没改。

细节：祝老的板书上都只写了 改第 2,3,4 题。

T2#

昨天，我们的祝老说：明天考概期 dp，好好复习。然后，他又说：没事，简单题。

但是一个人都没切。今天考试难度完全是反的，T4 该放 T1，T3 该放 T2…

于是我信了这道概期是简单题。于是兴致勃勃的推了 2h 的式子。不出意外的 WA 了。我刚开始还怀疑是我式子推错了，没想到我竟然难以置信的推对了。这样就只能是 dp 方程写错了。于是我的心态直接原地爆炸。

T3#

爆炸完了就去看 T3。也是想得到。写了一个 $O(n^2 \log n)$ 的做法。期望得分 $30 \sim 40$ 。实际得分 $20$ 。

正解实际上是和哈希。

T4#

真正的签到题

如果这套题按照难度排序的话，我说不定能拿一个 $130$ 。但是信了“没事，简单题。”这样的鬼话，导致策略出现大问题。

竞赛是自己的事情。不论是平时的练习，还是考试的策略，都得靠自己。不能信别人的“简单题”。不要在意别人的三言两语。

竞赛是自己的事情。

今天的 $3$ 到可做题都是理解起来很简单的。其中 T3，T4 也是想起来很简单的。半个下午就改完了。今天最主要的问题是策略问题。如果策略没有问题，那么期望得分应该是在 $130 \sim 150$ 之间。如果脑袋灵光，甚至可以打出 T3 正解。

竞赛是自己的事情

这篇日记在这里以上都是带点应付性质的。从这里开始就是为我自己写的了。想看我也不拦着。

[HNOI2015] 亚瑟王 #

这道题也是让我见识到了概期 dp 的多样性，于是我从今天晚上开始着手写我的概期 dp 学习笔记了。

考虑到每张牌对于答案的贡献是独立的，我们可以把答案拆成 $\sum_{i = 1}^{n}ans_i \times d_i$ 。其中 $ans_i$ 表示第 $i$ 张牌总的放出来的概率。于是这道题就转成了概率 dp 了。

我也是想得到。不过竞赛也要靠经验嘛。这次见过了下次就想得到咯。

对于第 $1$ 张牌，显然有发动概率有 $1 - (1 - p_1)^r$ 。对于第 $2$ 张牌，有两种：

当第 $1$ 张没放出来，那么发动概率就为 $1 - (1 - p_2)^r$ 。
当第 $1$ 张放出来了，那么第 $2$ 张在第 $1$ 张发动的那一轮显然发动不出来。那么发动概率就为 $1 - (1 - p_2)^{r - 1}$ 。

我们发现，对于一个牌发动的概率，和它排第几位有关，也和前面发动了几张牌有关。我们又发现数据范围不咋大。想到把这俩玩意放到状态里。

设 $dp_{i,j}$ 表示这是第 $i$ 张牌，在这 $r$ 轮里，排在 $i$ 前面的牌放了几张。于是我们有转移方程：

dp_{i,j} = dp_{i - 1,j - 1} \times (1 - (1 - p_i)^{r - (j - 1)}) + dp_{i - 1,j} \times (1 - (1 - p_i)^{r - j})

让我解释以下这个方程：

第一项表示第 $i$ 张发动的概率。因为如果第 $i$ 个能发动，前面有 $j - 1$ 张牌发动，那它就只有 $r - (j - 1)$ 轮能发动了。
第二项表示第 $i$ 张不发动的概率。和上面的一样。

我们就成功的做出了这道题。

总结：题做得不够多，没有见识过。

音乐真是治愈心神的良药啊。

3 月 14 日#

今天是个好日子啊。

那有人要问了：为啥是个好日子？

开心是没有理由的。

（我好中二）

Blocking Elements #

我的评价是：wqs 二分（輕量化）

首先，我们找到原题，发现带了一个 二分 的标签，于是我们就考虑二分。二分出一个 $x$ ，dp 出当分出来的每段和都不超过 $x$ ，分割的那几个数和的最小值。然后判断。

这个题居然还能评 $\textcolor{3498DB}蓝$ ，感觉不值蓝。

Programming Competition #

问啥设啥。

如上文所说，我们设 $dp_u$ 表示 $u$ 及其子树内最多能配多少对。考虑 $u$ 的重儿子 $son$ 。当 $siz_{son} \ge \lfloor \frac{siz_u}{2} \rfloor$ 时，一定有方案能凑够 $\lfloor \frac{siz_u}{2} \rfloor$ 。如果不满足，就进行转移： $dp_u \leftarrow dp_{son} + (siz_u - 1 - siz_{son})$ 。

Good Trip #

能不用 dp 就不用 dp。

初始有 $ans = 0,sum = \sum\limits_{i = 1}^{m}f_i$ ，对于每一次，都有 $\frac{2m}{n(n - 1)}$ 的概率取到暧昧的硝硼铀，所以对于每次， $ans \leftarrow ans + sum \times \frac{2m}{n(n - 1)}$ ，且 $sum \leftarrow sum + \frac{2m}{n(n - 1)}$ 。

Array Collapse #

做过，但是记不到。

Kim’s Quest #

也记不到。

[SHOI2011] 扫雷机器人 #

这题的题解是真的妙。

考虑对于每个蹦蹦炸弹分开算贡献。设能够引爆 $i$ 的有 $cnt_i$ 个，那么 $i$ 一定得在这 $cnt_i$ 个里面最先被引爆才行。引爆这 $cnt_i$ 个的顺序有 $cnt_i !$ 种，它在最前面的有 $(cnt_i - 1)!$ 种。那么它被最先引爆的概率就是 $\frac{(cnt_i - 1)!}{cnt_i !} = \frac{1}{cnt_i}$ 。我们对于每个炸弹，设它引爆能影响 $[lb_i,rb_i]$ 的范围， $O(n)$ 往两边扩张。最后统计答案的时候，看有多少 $j$ 满足 $x_i \in [lb_j,rb_j]$ 。 $j$ 的数量，最终答案就是 $\sum\limits_{i = 1}^{n}\frac{1}{cnt_i}$ 。

菜是原罪。

3 月 17 日#

在被世界狠狠打击后，从此知道了败北的意义。

这是鬼灭 OP 里的一句歌词。鬼灭很励志啊，但是由于太长了导致不想二刷。

Binary Subsequence Value Sum #

这道题是好题推荐里的题。我做好题推荐的逻辑就是：哪道题做的人多就去做。

但是思考良久，连突破口都找不到。

于是去看题解。题解给了个神秘小结论，于是去照着这个神秘小结论来写。

Floor or Ceil #

你聪明的，告诉我：为啥 div.2 的 B 会有 1500 以上的难度？

Math Division #

我们观察到：他是期望，我们考虑 dp。设 $dp_{i,j}$ 表示只剩下第 $n \sim i$ 位，且第 $i$ 位为 $j$ 的期望。

然后呢？

然后你以为我做得出来一道概期？你扯吧你。这是我的假解法。正解是这样的：

设 $dp_i$ 表示在第 $i$ 次操作中发生进位的概率。有转移：

dp_{i} = \begin{cases} \frac{dp_{i - 1}}{2} & x_i = 0 \\ \frac{1 + dp_{i - 1}}{2} & x_i = 1 \end{cases}

于是我们就得到了一个做法。

我什么时候才能自己做一道概期题呢？

MST in Modulo Graph #

这道题：一眼最小生成树。但是看到 $n \le 1 \times 10^5$ ，建完全图肯定是不行的。我们考虑优化建图。对于一个点 $u$ 有点权 $a_u$ 。考虑把在 $n$ 个点分成 $(1a_u,2a_u],[2a_u,3a_u]...$ 的块。那么每块内的都像当前块内点权最小的连边。这么做的最优性显然。

[USACO15JAN] Grass Cownoisseur G #

第一眼：先缩个点再说。

然后就说不出来了。

考虑 spfa， $dis1_i$ 表示 $1 \to i$ 的最长路， $dis2_i$ 表示 $i \to 1$ 的最长路。然后，遍历每个强联通分量 $u$ ，对于它在反图上相邻的点 $v$ ， $ans \leftarrow \max(ans,dis1_u + dis2_v - siz_{beL_1}$ ， $ans$ 初始为 $siz_{beL_1}$ 。

后日谈#

今天尝试驯服 ghidra 和 ida 这俩反编译软件，只驯服了一半。

今天还有点感冒，头晕乎乎的，晚上还要打 edu。这打什么？估计要掉分。

我拥有与我水平不相称的 CF rating。我的 CF rating 只比 wgc 低 $100$ 多。但是我的得分率却比他低 $15 \%$ 。为啥呢？是因为 CF 近似 IOI 赛制吗？

3 月 18 日#

补昨天晚上的 div.2。

Array Recoloring #

猜结论： $ans$ 为最大的 $k + 1$ 个数相加。

证明：很简单，不用写。

注意：特判 $k = 1$ 和 $k = n$ 。

昨天晚上就是没有特判导致挂了 B 题。

Equalization #

昨天晚上想的：想到了背包，但是因为有 $\sum_{i = 1}^{16} \approx 60 \times 2$ ，这个 $16$ ，我想到它可以放在指数上。于是就往状压上面想了。

正解：设 $dp_{i,j}$ 表示 $x$ 左移 $i$ ， $y$ 左移 $j$ 的最小代价。

[NOI2018] 归程 #

这里提供一个题解能过，我不能过的方法：

先 dijkstra 出 $1$ 开头的单源最短路，想到车在一个连通块内不用代价，考虑用并查集维护连痛块。如果不强制在线，我们可以通过海拔从大到小循环每个边，然后合并。但是这道题强制在线。并查集不能分离，考虑可持久化并查集。

但是可持久化并查集是 $O(m \log^2 n)$ 的。算了一下，大概是 $7.5 \times 10^7$ 。加上线段树的常数，跑不过。

[THUPC 2017] 天天爱射击 #

考虑击碎第 $i$ 块木板的子弹 $c_i$ 。那么 $c_i$ 一定是 $[l_i,r_i]$ 范围内第 $s_i$ 个出现的。这样就是一个静态区间 $k$ 小值。

后日谈#

考虑在期中的时候将得分率提高至至少 $30\%$ ，在期末提高至 $60\%$ 。

然而现在都开学第 $5$ 周了，我还没有长进。

3 月 19 日#

虽然排名没长进，但是分数有长进啊。

T1#

我都能一眼，当然不用说了。

T2#

经过一番推导，我们发现 $f(n,i) = (i + 1)^n$ ，从而有 $f(f(n,i)) = (i + 1)^{(i + 1)^n}$ 。直接欧拉定理 + 快速幂。

T3#

首先，我们有结论：如果线段 $L_1$ 包含了 $L_2$ ，那么 $L_1$ 要么单独成组，要么和 $L_2$ 分到一组。

证明：如果 $L_1$ 和 $L_3$ 分成了一组， $L_2$ 和 $L_4$ 分成了一组，那么我们可以把 $L_1$ 挪到 $L_2$ 那一组， $L_2$ 那组的贡献不会变，但是 $L_3$ 单独成组更优了。

于是我们把包含其他线段的先取出来，那么剩下的线段左右端点都是单增的。显然有结论：在剩下的线段里一定是连续的一段成一组。那么有 dp： $dp_{i,j}$ 表示分了 $i$ 段，第 $i$ 段结尾是 $j$ 的最大贡献。于是我们有转移：

dp_{i,j} = \max_{k = 0}^{j - 1}\{dp_{i - 1,k} + \max(0,r_{k + 1} - l_j)\}

用前缀和优化即可。

T4#

哈希。

最大异或和 #

尝试驯服可持久化字典树。

成功驯服，耗时 1h。

死因：root[maxn << 1] 写成了 root[maxn]

后日谈#

我爸曾经给我说过，他上高中的时候走路都在想题，专心的甚至能装到墙上去。

我现在懂了：只有没朋友的人才会那样，因为他们下课没事干只能思考。

3 月 20 日#

不考试 day。

本来想写可持久化学习笔记的，但是想了想，不想画可持久化线段树的图，于是放弃了。

[NOI2018] 归程 #

前天的可持久化并查集双 $\log$ 的做法爆炸了，于是只能去写单 $\log$ 的 Kruskal 重构树。

我们按照海拔建一个小根的重构树。那么倍增调到 $u$ 的最上面的祖先 $v$ ，满足它的点权大于查询的海拔。那么 $v$ 的子树内肯定都是 $u$ 开车能到达的。于是我们就能做了。

[TJOI2018] 异或 #

先剖了再说。

我们把树剖成链了，那么链上的区间异或不就好做了吗？直接可持久化 Trie。

[POI 2014] KUR-Couriers #

自己找了一道主席树的题来做。

我们看到“出现次数严格大于区间长度的一半”，如果对于整个的 $[1,n]$ 的区间，那么权值线段树肯定很好做，那么可持久化一下就可以做区间的了。

[FJOI2016] 神秘数 #

我们考虑对于一个区间来说怎么做：先从小到大排序，如果当前能表示出来的数集为 $[1,x]$ ，如果有 $a_i \le x$ ，那么区间变成 $[1,x + a_i]$ ，反之就表示不出来 $x + 1$ 。于是我们可以用主席树维护一段区间内小于 $x$ 的数的和。如果没有了，那么就是答案了。

3 月 23 日#

这下是真的离退役不远了。

吃多了 + 在运动的车上看手机，双重 debuff 加持，导致整个晚上都昏昏沉沉的。不是困而是晕。然后尝试补今天中午的 div.2，发现没有题解果断放弃。

然后祝老让我们打 arc。于是开始打。看到 A，第一眼没思路，去上了个厕所，直接茅厕炸开，想到了。于是开始写。

准备好和 bug 大战 300 回合了，但是他过了？？

后日谈#

考虑在期中的时候将得分率提高至至少 $30\%$ ，在期末提高至 $60\%$ 。

似乎可行。因为如果我磕 T1 磕他个 3h，最后 1h 再打点暴力分， $30\%$ 应该不成问题。 $60\%$ 等稳定在 $30\%$ 以上再说。

我爸曾经给我说过，他上高中的时候走路都在想题，专心的甚至能装到墙上去。
我现在懂了：只有没朋友的人才会那样，因为他们下课没事干只能思考。

然而当我问我妈，我爸高中是不是没朋友的时候，得到的回答却是：很多。甚至还很多女生追。

我爸这么有魅力的吗？不是说他高一才一米四吗？

3 月 24 日#

我刚上的青名啊！！！

Serval and Kaitenzushi Buffet #

这个喷不了这个是纯糖。

我们发现第 $i$ 盘寿司一定是在 $n - i \times (k + 1) + 1$ 分钟前吃掉，所以我们直接维护一个大根堆。如果当前的位置满足有一个整数 $i$ 使得 $n - i \times (k + 1) + 1$ 等于当前位置的下标，我们就把堆顶取出来。

这道题是个人都会去想 dp 吧？

Simple Permutation #

你说我怎么糖成这样，黄题都做不来。

一句话：从小往大取，取不到就往下找一个质数取。

我赛时还一个劲的猜结论。

Serval and Modulo #

我们发现，当一个 $k$ 成立，当且仅当 $a_i - b_i \equiv 0 \pmod k$ ，对于 $\sum a_i - \sum b_i$ 也一样。于是我们枚举 $\sum a_i - \sum b_i$ 的每个因子。然后 $O(n)$ check 它是否合法，总复杂度 $O(n \sqrt n)$

Uniform Sum #

泥硕德兑，但是 atcoder 的 rmj 为啥也挂了？

考虑 $\forall i \in [1,n],a_i + b_i = x$ 何时可行。当且仅当 $x \ge \max\limits_{i = 1}^{n}(\max(a_i,b_i))$ 且 $\sum\limits_{i = 1}^{n}[a_i + b_i = x] \ge n - cnta - cntb$ 。其中 $cnta$ 和 $cntb$ 分别表示 $a,b$ 中的 $-1$ 个数。我们可以用 map 记录对于每一个 $x$ 的 $\sum\limits_{i = 1}^{n}[a_i + b_i = x]$ ，然后看最大的是否大于等于 $n - cnta - cntb$ 。

CPP

#include<bits/extc++.h>
#define int long long
using namespace std;
int n,cnta,cntb,_max;
int a[2005],b[2005];
__gnu_pbds::gp_hash_table<int,int> mpa,mpb,tmp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        _max = max(_max,a[i]);
        if (~a[i])
            mpa[a[i]]++;
        else
            cnta++;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
        _max = max(_max,b[i]);
        if (~b[i])
            mpb[b[i]]++;
        else
            cntb++;
    }
    //重中之重
    for (auto [xa,ya] : mpa)
        for (auto [xb,yb] : mpb)
            if (xa + xb >= _max)
                tmp[xa + xb] += min(ya,yb);

    int ans = 0;
    for (auto [x,y] : tmp)
        ans = max(ans,y);
    if (ans >= n - cnta - cntb)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

[国家集训队] middle #

设中位数为 $x$ ，大于等于 $x$ 的置为 $1$ ，反之置为 $-1$ 。那么区间和大于等于 $0$ 的一定大于等于实际的中位数。我们就可以二分了。对于每个值维护一个线段树，线段树里存区间和，区间最大前缀和，区间最大后缀和。但是 $n$ 个线段树开不下，于是我们考虑可持久化。

后日谈#

NOIp 是 11 月下旬，现在是 3 月中旬，我还有 8 个月的时间。

然而 6 月就要决定能不能继续冲省选了，所以只有 3 个月了。

3 月 25 日#

昨天祝老问我 dp 要不要加难度，我说加。

Modular Sequence #

我们看到 $a_i$ 可以是 $a_{i - 1} \bmod y$ 也可以是 $a_{i - 1} + y$ 。那么肯定有 $a_1 \equiv a_2 \equiv a_3 \dots \pmod y$ ，于是我们判断无解首先就判断 $s \equiv (x \bmod y) \times n \pmod y$ 。然后我们设 $ans_i = a_i \times y + (x \bmod y)$ 。那么 $a$ 数组肯定形如 $\{st,st + 1,st + 2,\dots,st + k_0,0,1,2,3,\dots,k_1,0,1,2,3,\dots,k_2,\dots,0,1,2,3,\dots,k_?\}$ 。且 $\sum\limits_{i = 1}^{n}a_i = \frac{s - (x \bmod y) \times n}{y}$ 。

然后我尝试贪心构造 $a$ ，成功的 wrong answer Solution exists, but participant said No (test case 3970)。这个 3970 就很绝望。

正解是 dp，设 $dp_s$ 表示使得 $\sum\limits_{i = 1}^{n}a_i = s$ 的最小 $n$ 。我们可以通过枚举最后一段的长度来转移。枚举状态 $O(n)$ ，转移 $O(\sqrt{n})$ 。合起来 $O(n\sqrt{n})$ 。然后根据它来判断是否可行。构造合法序列就看它从哪里转移的就行了。

Distance to Different #

诶您猜怎么着？赛时我都想到 $80\%$ 了，然后放弃去看上面的那道了。

我们发现 $b$ 数组一定可以分成几段，最左边的一段单调递减，最右边的一段单调递增。中间的先递增再递减。于是我们设 $dp_{i,j}$ 表示分 $j$ 段，最后一段结尾为 $i$ 的方案数。我们发现，如果一段长度为 $2$ 的区间其实和两段长度为 $1$ 的区间形态一样，于是我们规定中间的段长度不能为 $2$ 。于是我们有转移： $dp_{i,j} = \sum\limits_{k = 0}^{i - 1}dp_{k,j - 1} - dp_{i - 2,j - 1}$ ，注意特判第一段和最后一段不需要减 $dp_{i - 2,j - 1}$ 。

GCD on a grid #

hrl：祝老特有的不识数，1600 ~ 2000 的题里面放 2100，2100 ~ 2400 的题里面放 1900。

我：你就偷着乐吧！

我们发现路径一定经过 $a_{1,1}$ 。于是我们考虑循环 $a_{1,1}$ 的每一个因数 $i$ 。看看是否有一条路径只经过模 $i$ 为 $0$ 的数。时间复杂度 $O(n^2)$ 。带一个 $240$ 左右的常数。因为 $1 \times 10^6$ 的数量级因数最多就 $240$ 多个。

Learning to Paint #

其实老早以前就看过这道题。但是没做。

我们发现，一个位置 $j$ 如果要转移 $i$ ，那么贡献一定是 $a_{j + 2,i}$ ，这是不变的。我们就可以设 $dp_i$ 为将前 $i$ 个数分段的最大的 $k$ 个数。转移就是这样：先从 $\forall j \in [-1,i),dp_{j}$ 里取出最大的放进备选里，然后执行 $k$ 次，每次从备选里去最大的一个，并把它接着的下一个放进备选。

还是放一下代码：

CPP

#include<bits/extc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
int n,m;
int a[1005][1005];
queue<int> tmp[1005];
priority_queue<pii> pend;
priority_queue<int> dp[1005];
template<typename typ>
void clear(priority_queue<typ> &q){while (!q.empty())q.pop();}
int get(int x){int res = dp[x].top();dp[x].pop();tmp[x].push(res);return res;}
void solve()
{
    scanf("%lld%lld",&n,&m);
    for (int i = 0; i <= n; i++)
        clear(dp[i]);
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            scanf("%lld",a[i] + j);
    dp[0].push(0);
    for (int i = 1; i <= n; i++)
    {
        clear(pend);
        pend.push({a[1][i],-1});// 放进备选
        for (int j = 0; j < i; j++)
            pend.push({get(j) + a[j + 2][i],j});// 放进备选
        for (int j = 1; j <= m && !pend.empty(); j++)
        {
            auto [val,id] = pend.top();// 取出最大值
            pend.pop();
            dp[i].push(val);// 转移
            if (~id && !dp[id].empty())
                pend.push({get(id) + a[id + 2][i],id});// 将它的下一个放进备选
        }
        for (int j = 0; j < i; j++)
        {
            while (!tmp[j].empty())
            {
                dp[j].push(tmp[j].front());
                tmp[j].pop();
                // 别忘了还原
            }
        }
    }
    while (m--)
    {
        printf("%lld%c",dp[n].top(),m ? ' ' : '\n');
        dp[n].pop();
    }
}
signed main()
{
    int t;
    scanf("%lld",&t);
    while (t--)
        solve();
    return 0;
}

这玩意的 clear 调了我 $30$ min。究其原因是没传引用。

这个喷不了这个是纯糖。

后日谈#

yzp 在做图论简单题。然而这些题我老早就做过了。

但是黄色的题啊，我一眼就看出来了，而且 $O(n^2)$ 都能过的题，他看不出来？？？

然后尝试理解线性基，只能感叹数学的神奇。

3 月 26 日#

这个喷不了，这个是纯糖。

T1#

题意：有一个长度为 $n$ 的数组 $a$ ，其中对于 $\forall i,j \in [1,n]$ ，如果 $i < j$ 且 $\gcd(a_i,a_j) > 1$ 那么就在 $i \to j$ 建一条单向边。有 $q$ 次查询，每次查询 $x,y$ 问 $x$ 能否到达 $y$ 。

你说我写个 dfs 不好吗非得写那个 Floyd！！！挂了 tmd $60$ 分。

正解：维护 $dp_{i,j}$ 表示从 $i$ 出发能走到的最靠前的有 $pr_j$ 这个质因子的位置。维护方法如下：

CPP

// f[j] 表示在 i 后面最靠前的有 pr[j] 这个质因子的位置
fill(f,f + pr.size(),n + 1);
for (int i = n; i >= 1; i--)
{
    if (!a[i])
    {
        fill(f,f + pr.size(),i);
        fill(dp[i],dp[i] + pr.size(),i);
    }
    else
    {
        fill(dp[i],dp[i] + pr.size(),n + 1);
        for (auto j : fac[i])
        {
            if (f[j] != n + 1)
                for (int k = 0; k < pr.size(); k++)
                    dp[i][k] = min(dp[i][k],dp[f[j]][k]);
            dp[i][j] = f[j] = i;
        }
    }
}

这就是代码的核心之处。查询时遍历 $a_y$ 的每个因子 $pr_j$ ，看看有没有 $dp_{x,j} \le y$ 。有就是 Shi，没有就是 Fou。

T2#

赛时思路正确，但是码力实在是太过于高强导致硬挂 $\huge\color{ff0000}80$ 分。

我也是个人物。

T3#

矩阵优化状压 dp。我们看到 $m \le 6$ ，直接想到状压。然后我们看到 $len \le 3000$ ，这只能矩阵优化。如果 $2^6$ 的状态直接上还带一个 $9000$ ，这不 T 才怪呢。我们发现真正合法的状态只有 $20$ 种， $20^3 \times 90000 = 7.2 \times 10^7$ ，有点极限但是问题不大，反正它跑过了。

后日谈#

写完了 T1，自信的没有打对拍，于是直接硬挂 $\huge\color{ff0000}60$ 分。T2 码力高超硬挂 $\huge\color{ff0000}80$ 。T3 如果打完 T2 不颓废似乎是可以想出来的。

其实 T2 并不算是全错，但是求最优解的地方有点问题。

总而言之，这次考试纯唐

~~考差了就得用下面的考试来补，这么简单（并非）的考试以后可不多见了啊~~

感觉心脏有点问题啊，要不要说一声呢？

\tiny \textcolor{ffffff}{我要进省队！}

3 月 27 日#

纯粹是被吓的。

Counting Binary Strings #

露头就秒。

我们看到一个“好的子串”有且仅有一个 1，于是我们想着把这个序列分成 $114514$ 段形如 00...001 的段，设 $dp_i$ 表示已经有了 $i$ 个好的子串。但我们发现，如果对于一个 1，想要算他对于子串个数的贡献，我们不但要知道它后面有多少个 0，我们还要知道它前面有多少个 0。我们又看到 $n,k \le 2500$ ，直接 $dp_{i,j}$ 表示已经有了 $i$ 个好的子串，这个 1 前面有 $j$ 个 0。转移很简单：

dp_{i,j} = \sum_{k = 0}^{\lfloor \frac{i}{j + 1} \rfloor - 1}dp_{i - (k + 1) \times (j + 1),k}

写代码的时候不用像式子里那么麻烦，只要判 (k + 1) * (j + 1) <= i 就行。

Array Collapse #

数组崩坏还在发力。

设 $dp1_i$ 表示 $i$ 被不取走有多少种， $dp2_i$ 表示 $i$ 被取走。设 $j$ 为第一个使得 $a_j \lt a_i$ 的。转移如下：

\begin{cases} dp1_i = dp1_j + dp2_j \\ dp2_i = dp1_j + \sum\limits_{k = j - 1}^{i - 1}dp2_k \end{cases}

$j$ 用单调栈维护， $\sum\limits_{k = j - 1}^{i - 1}dp2_k$ 用前缀和优化即可。最终答案为 $dp1_n + dp2_n$ 。

Transitive Graph #

这题能有 2100?

我们看到：

If there exists a triple of vertices $a$ , $b$ , $c$ of $H$ , such that there is an edge from $a$ to $b$ and an edge from $b$ to $c$ , but there is no edge from $a$ to $c$ , add an edge from $a$ to $c$ .

这就很缩点。我们又看到：

Among all the longest simple paths in H, find the one with the smallest value.

细说这个 longest，我们结合上面的，如果在一个强联通分量里，结合第一个条件，我们不用考虑从哪里进从哪里出，于是为了最长，我们肯定要把整个强联通分量走完再出来。那么这就是一个 tarjan 和拓扑排序板子题。

后日谈#

下午胸口疼的厉害，~~我才 14 岁我不想死~~，于是晚上出来看医生。得出结论：纯粹被吓的。~~我还能再熬。~~

但是却因此丢失了晚上回家 van you see 的机会，大悲~~~

3 月 28 日#

都半期了我怎么还那么菜！！！

Counting Rhyme #

我们设 $fl_i$ 表示 $a$ 里是否有 $i$ 的因子， $dp_i$ 表示有几组 $\gcd(a_x,a_y) = i$ 。显然这两个东西都可以在 $O(n \ln n)$ 的复杂度内求解，那么最终的复杂度就是 $O(n \ln n)$ 。~~甚至还比 $O(n \log_2 n)$ 优。~~

Non-Intersecting Subpermutations #

2024/5/14 做过。~~好臭的日期~~

我们设 $dp_{i,j}$ 表示在前 $i$ 个数里，第 $(i - j,i]$ 个数内没有重复的情况下的贡献。答案就是 $\sum\limits_{i = 1}^{n}dp_{i,k}$ 。

我们考虑如何转移。我们想两种情况：第 $i$ 位是否在 $dp_{i - 1,j - 1}$ 这不重复的 $j - 1$ 个里面。如果不在，那么就会增加 $dp_{i - 1,j - 1} \times (k - j + 1)$ 的贡献。如果在，我们考虑枚举这个数在哪里重复了，增加 $\sum\limits_{l = j}^{k - 1}dp_{i - 1,l}$ 的贡献。

放一下代码：

CPP

#include<bits/extc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n,k;
int dp[4005][4005],pw[4005];
signed main()
{
    cin >> n >> k;
    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = pw[i - 1] * k % mod;
    dp[1][1] = k;
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        int tmp = 0;
        dp[i - 1][0] = dp[i - 1][k];// 我不明白
        for (int j = k; j >= 1; j--)
        {
            if (j != k)
                tmp = (tmp + dp[i - 1][j]) % mod;
            dp[i][j] = (dp[i - 1][j - 1] * (k - j + 1) + tmp) % mod;
        }
        ans = (ans + dp[i][k] * pw[n - i]) % mod;
    }
    cout << ans;
    return 0;
}

我不明白：为啥要 dp[i - 1][0] = dp[i - 1][k]？

Another MEX Problem #

我们看到：异或？？！MEX？？！~~考虑不做~~。

这俩恶心扒拉的东西凑一起了，我们~~不做也得做~~。

看到异或，我们的最优性 dp 直接原地爆炸，考虑可行性 dp。我们发现， $5000$ 以下数再怎么也异或不出大于 $10000$ 的数，~~更适合可行性 dp 了~~。设 $dp_{i,j}$ 表示前 $i$ 个数能否异或出 $j$ 。考虑转移：枚举上一段的结尾 $k$ ，那么有 $dp_{i,j} \leftarrow dp_{k,j \oplus \operatorname{MEX}_{l = k + 1}^{i}a_l}$ 。但是这样有 $O(n^3)$ 的复杂度，显然不可行。

考虑优化：我们定义一种东西叫“好的区间”，其意义为：对于区间 $[l,r]$ ，不存在区间 $[l',r']$ 使得 $\operatorname{MEX}_{i = l}^{r}a_i = \operatorname{MEX}_{i = l'}^{r'}$ 。可以证明这种区间只有 $O(n)$ 个，~~然而我并不会~~。于是我们只用转移这些个好的区间，时间复杂度 $O(n^2)$ 。

后日谈#

即使注定失败，你也会坚持下去吗？

反正我会。

3 月 29 日#

谁说注定失败？

T1#

题意：对于 $[l,r]$ 区间内的每个数，输出它的最小质因子。 $l,r \le 10^{12},r - l + 1 \le 10^6$ 。

首先就想到欧拉筛筛出 $[2,10^6]$ 的质数，然后对于每个暴力判断。但是我还是小看了 $[999 \, 999 \times 10^6,10^{12}]$ 这个区间内的质数数量，不出意外的 T 了。

考虑预处理答案。枚举每个质数 $i$ ，然后枚举 $i$ 在 $[l,r]$ 内的每个倍数，将它的答案置为 $i$ ，时间复杂度 $O(n \ln n)$ ， $n$ 表示区间长度。

T2#

大模拟。

多大了还出大模拟？

T3#

我们有神秘小结论：我们将每个硝硼铀排序，我们称硝硼铀 $i$ 比硝硼铀 $j$ 小，当且仅当 $\min\{a_i,b_j\} < \min\{a_j,b_i\}$ 。按照这个排序就是了。

然而这个是错误的。cwoi 的数据是真的水。

用心扒题，用脚造数据。~~怎么和 CCF 一样~~

P哥破解密码 #

我们需要矩阵优化。

首先一眼 dp 方程：设 $dp_{i,j}$ 表示前 $i$ 个数已经填好，第 $[i - j + 1,i]$ 全是 $\texttt{A}$ 的方案数。有显然的转移：

\begin{aligned} 1 \times dp_{i - 1,0} + 1 \times dp_{i - 1,1} + 1 \times dp_{i - 1,2} & = dp_{i,0} \\ 1 \times dp_{i - 1,0} + 0 \times dp_{i - 1,1} + 0 \times dp_{i - 1,2} & = dp_{i,1} \\ 0 \times dp_{i - 1,0} + 1 \times dp_{i - 1,1} + 0 \times dp_{i - 1,2} & = dp_{i,1} \\ \end{aligned}

可以写成矩阵形式：

\begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \times \begin{bmatrix} dp_{i - 1,0} \\ dp_{i - 1,1} \\ dp_{i - 1,2} \end{bmatrix} = \begin{bmatrix} dp_{i,0} \\ dp_{i,1} \\ dp_{i,2} \end{bmatrix}

直接写矩阵快速幂优化即可。

后日谈#

没啥可谈的。现在似乎只有又臭又长的世界任务能够提起我的兴趣了。

3 月 30 日#

昨天晚上睡得实在是太晚了，然后中午玩爹 5 弘文过头了，直接睡了一下午。

Serval and Colorful Array (Easy Version)#

感觉这题不值 2600。~~虽然我还是没做出来~~

我们考虑一个字串怎么来。显然最优的情况是中间的一个数不动，然后两旁的挪过来。我们枚举每个可能的中间的数 $a_{pos}$ ，然后对于 $\forall i \in [1,k]$ ， $O(n)$ 处理 $l_i,r_i$ 分别表示左边离 $pos$ 最近的 $i$ 离 $pos$ 多远，右边离 $pos$ 最近的 $i$ 离 $pos$ 多远。现在的问题就是，如何选择使得 $\frac{k}{2}$ 个 $l_i$ 和 $\frac{k}{2}$ 个 $r_i$ 加起来最小。我们先钦定都选左边的，答案就是 $\sum\limits_{i = 1}^{k}l_i$ ，再记录一个 $c_i = r_i - l_i$ ，我们将 $c$ 从小到大排序，最终的答案就是 $\sum\limits_{i = 1}^{k}l_i + \sum\limits_{i = 1}^{\frac{k}{2}}c_i$ 。别忘了减掉多算的 $\sum\limits_{i = 1}^{k}|i - \lceil\frac{k}{2}\rceil|$ 。

后日谈#

做又臭又长的世界任务，刚刚被新地图震撼，一看锚点数量直接原地爆炸。

不管了，做什么世界任务，做题！

3 月 31 日#

神秘搜索综合训练。

剩下的等明天再写吧。

后日谈#

今天是 3 月的最后一天。马上就到半期了，希望我能趁早把得分率提到 $\ge 30 \%$ 。

我会成为新的王#

3月每日总结

https://nahida.cfd/blog/3月每日总结/