这几天是NOI，对于我而言的最后一个赛季进入了其真正的结尾。尽管我已经提前立场，然而依旧牵挂着它。而在我退役后的漫长时间里，我有时想提笔写下一些回忆性质的文字，然而又不知道从哪里开头，什么时候开头。现在，不妨借NOI的机会，写下一个比较完整的回忆录吧。 离开OI已经4月有余了，但它依旧让我魂牵梦萦，心神不宁。它早已完全…

考虑你的矩形 $S$ 的左端为 $L$，下端为 $D$，则右端为 $L+W$，上端为 $D+H$。类似的小矩形的四边坐标记作 $l_i,d_i,r_i,u_i$。 那么覆盖则须满足 $$ L \max l_i\\ D+H> \max u_i $$ 我们将 $W,H$ 各减去 $1$，然后挪到右边去，同时考虑将 $L,D…

你如果多手模几个例子，你会发现，似乎答案的形式都为 $2^k-1$。 细细思考，你会发现这容易理解。对于两个元素 $x,y$，如果它们所出现的集合位置是相同的话，那么这两个元素可以看作同一类。因此对于每一类元素，其在一个集合中要么出现要么不出现，而且由于一个集合和它的补集都存在。所以集合数量就是 $2^k-1$，其中…

我们无需考虑左右儿子的问题，因为我们只需要求出每个节点的父亲。 考虑递归处理。 每次处理一个子树时，花费子树大小次询问找到其一条链，强制其为左链，将其存储在 vector 中，而后按顺序处理每个点的右子树，设询问次数为 $f(n)$，则 $f(n)\le n-1+\sum_{i=1}^{\log n} f(\frac{…

在讨论《PA Mashup #2 赛后总结》回复：

话说FHC和CJR为啥标粗体。

对于 $N \le 20$，直接 $O({N \choose K})$ 枚举每个点是否取即可。 对于 $N \le 500$，可以设计一个 $O(N^3)$ 的 dp，设 $f_{i,j}$ 表示在 $i$ 个点中选出 $j$ 个点的最大面积。我们将点划分为上半部分和下半部分，将极左极右点各分到一个部分中，分别从左到右…

提交通道：[IP over Avian Carrier - Problem - QOJ.ac](https://qoj.ac/contest/293/problem/503) 我一开始的想法是，将连续 $C$ 个字符拼起来，变成一个 $[0,2^C)$ 内的数，记 $[0,2^K)$ 内 $\mathrm{popcou…

学了一下有限域，感觉找既约（不可约）多项式是最难的地方啊。主要的知识可以查看 oiwiki。其他题解都没有怎么讲如何找这个既约多项式。 对于质数是简单的，使用整数加法乘法，并对 $n$ 取模即可。 对于 $GF(p^n)$，我们构造的加法和乘法都应该是多项式的形式，也即 $$ a_{n-1}x^{n-1}+a_{n-2…

在讨论《LACPT-Open 题单征集》回复：

出题人投稿 P8915 [DMOI-R2] 回到过去，考察数学推导能力与分类讨论能力，对AI的细节实现是极大的考验。

考虑先 $O(nm)$ 处理出二维前缀和。 以下默认 $n \le m$。 如果对每次询问都二分答案，然后 $O(nm)$ 检查正确性，那么时间复杂度会来到 $O(nmq\log n)$，可以获得 40pts。 然后考虑我们可以先预处理出来每个点对应的答案，而不是每次查询时在询问。我们可以先 $O(\log n)$ 的…

在讨论《LGR-212 赛时答疑帖》回复：

@[07kzs](luogu://user/222609) 题意清晰，请自行计算。

在讨论《评级建议》回复：

@[Starrykiller](https://www.luogu.com.cn/user/235125) 建议评级：蓝。虽然通信题默认难度较高，但是这个题的 dfs 序思路并不难想，代码实现也较为简单。

观察数据范围，我们发现如果要取得满分，就必须要使 $l \le 20$。 而考虑到 $n \le 1000$，我们发现 $l=2 \log n$ 是恰好的。 自然地，我们可以想到将点的编号压缩成二进制存到 01 串中，那么一个点上恰好可以存两个点的编号。 一般来说我们遍历一棵树会使用 dfs，因此我们可以自然地想到节点…

在讨论《本题数据已加强》回复：

@[Hoks](luogu://user/551100) 考虑我们要找的类似于 `AABB` 段。我们需要找到以 $i$ 结尾的最长 `AA` 段长度与以 $i+1$ 开头的最长 `BB` 段长度。考虑两个相同的字串的结尾/开头必然为相同的字符，因此对于 `AA` 段，我们只需要从前往后枚举每个与 $s_i$ 相等的位…

首先可以考虑区间 dp。 设 $f_{l,r,0/1}$ 表示考虑第 $l$ 堆到第 $r$ 堆，由 A/B 先手能拿到的青草。设 $ans_x$ 表示 A 提前操作了 $n-x$ 次，**留下**了 $x$ 堆草的答案。 $$ f_{l,r,0}=\max(f_{l+1,r,1},f_{l,r-1,1})\\ f_{…

amylase 伯爵来到了某条街。这条街由 $n$ 个路口和连接这些路口的 $m$ 条道路构成。 每个路口都有一个红绿灯，每个红绿灯有红色和绿色两种状态。时间 $t=0,1,2,\dots$ 的十字路口 $i$ 的信号状态，根据如下参数 $a_i,b_i,c_i$ 决定： - 最开始的 $c_i$ 秒，即 $t=0,1…

在讨论《建议评黄》回复：

验题人题解，是不是证明了这个（

在讨论《【作弊名单】洛谷入门赛 #27 赛后总结》回复：

出题人歌单似乎与我很相像，特别在李荣浩上/xyx。看着歌词边哼边做的/tiao。

分块过了，甚至于是有问题的分块都能过。 我的做法是分三个块，第一个块是位置块，第二三个块是权值块。对三个块分别块内排序，位置块块内按照数的大小排序。我的错误是：对于询问 $[l,r]$，若 $[l,r]$ 在同一个位置块或者在**相邻位置块**，直接块内找到第 $k$ 小。而由于我仅进行了块内排序，所以不能对**相邻位…

在讨论《洛谷 Dataset 代码征集公告》回复：

支持喵

test 2 最后一个询问的答案是 `918957089641524701`，我的答案是 `918957089641524619`。 我的思路就是每个靶子的左右端点分开讨论，归类到负斜率和正斜率。假设有 $posc$ 个正斜率，$negc$ 个负斜率。右上端点对应负斜率，右下端点对应正斜率，各自恰好有 $n$ 个点。左…

在讨论《一点思路的不理解》回复：

我是倒着dp的，分两个 dp 数组 $f_0,f_1$ 这样的话 $f_0$ 就只需要对 $a_{i,j}$ 的和取 $\max$，$f_1$ 只需要对 $-b_{i,j}$ 的和取 $\min$，那么我们有 $$ f_{0,new\_state}=\max(a_{i,j}+f_{1,state})\\ f_{1,ne…

是按区间分块的思路，时间复杂度和高维莫队一样是 $O(n^{\frac{7}{4}})$，但是常数比较大，第11个点就T了。空间复杂度为 $O(n^{\frac{5}{4}})$。设分的块长为 $B$。则具体时间复杂度为 $O(qB+\frac{n^4}{B^3})$，空间复杂度为 $O((\frac{n}{B})^4…

在讨论《LGR-157 赛时答疑帖》回复：

T4的样例3好像没有满足 保证在进行第二种操作前队列内元素个数不小于 $y$ 的条件？ 我加了判断语句之后能够输出正确答案，没有加保证队列元素不少于0之前会错误。

在讨论《永久封禁公告》回复：

发现我好像在 GAOI 时和 lOIAKME 这个账号直接接触过，有点忘了当时他做了什么了（不过反正没给我留下任何好印象就是了）。然后当时因为 JEOI 和 GAOI 的比赛靠的比较近，我也关注了一下那个搬题。没想到这条线原来这么长。 希望以后 OI 社区不要再出现类似情况。感谢洛谷社区对自己的审查，支持洛谷以后的类似…

在文章《wqs二分&闵可夫斯基和学习笔记》发表评论：

orz

在讨论《【LGR-141】洛谷 6 月月赛 I 赛后总结帖》回复：

感觉 gap 比较合理

在讨论《等级分功能已经上线》回复：

惊奇地发现从2022年11月26日至今，elo rating 一直在1800 到 2000. 没有进步了

在讨论《关于偏数学向问题的证明》回复：

@[NaCly_Fish](/user/115864) 谢谢！

在讨论《关于偏数学向问题的证明》回复：

@[NaCly_Fish](/user/115864) 您可以帮忙看看下面这个推导过程有没有什么错误吗？