退役XCPCer|いまの僕は、やがてその過去の「俺」に憑かれる
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
嗨害嗨，复活赛打赢喽！ 前排推歌：クライヤ——すこっぷ 今天不搞字符串了，来说说博弈论。 先从 Nim 游戏说起： 有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个。两个玩家轮流行动，每次选择一堆石子，最少拿走一个，最多拿掉一堆的所有石子，不能操作者输。 至于为什么要从这里开始，为了引出叫做“公平组合游戏”，以…
今天比较没精神，再加上晚上发生了一些事情闭幕雷击，因此复习一下以前的东西。 前排推歌：こころに響く恋ほたる——橋本みゆき 继续昨天 AC 自动机的内容。 [NOI2011 阿狸的打字机](https://www.luogu.com.cn/problem/P2414) 首先转化一下题意：以一种基于公共前缀对末尾字符进行增…
补题。 前排推歌：少女レイ——みきとP [洛谷 P4824](https://www.luogu.com/article/lwo814h6) 我们充分发扬数据结构智慧，用字符串哈希搞匹配，当一个位置配上之后直接给这段删掉，接着暴力往后配即可，删子串直接考虑用线段树维护字符串哈希，区间打标记，暴力删也可以，因为显然每个位…
孩子们，我回来了。 前排推歌：ナツノヒ——Nina77 进入正题，今天主要是补题。 [洛谷 P8112](https://www.luogu.com.cn/problem/P8112) 很难想象我当时是以什么精神状态被这题卡的。 直接考虑 DP,设 $f_i$ 为文本串的 $i$ 前缀最小划分次数，转移的话对于当前的前…
悲报：今天（2025.5.9）凌晨熬夜出题干了半天。 为什么干了半天？因为两个人没凑出一份对的 std。 具体地，他锅，我也锅。 那就今天补个题吧。 2025.5.10 的内容共用此文章，虽然但是，10 号的安排是单挑 VP，等战后总结吧。 前排推歌也是加倍的： 1. scrape——keeno 2. decide——…
前排推歌：ヒバナ——DECO*27 继续字符串的一些基础算法。 哈希可能明后天上，毕竟能干的事情挺多的。 **manacher 算法** 一个十分甚至九分简单的用于求字符串所有位置回文半径的算法。 首先我们在每个字符中间加入一个字符串中没出现过的分隔符，给整个串长度干成奇数。 然后，对于若干回文中心： 我们维护下标 $…
前排推歌：インタビュア————原唱的和鹿乃版本都建议听听。 今天睡眠有点不够，来点基础的。 KMP 算法： 定义一个字符串的 Border 为：其相等的非空真前缀与真后缀。 由 Border，我们定义一个字符串的前缀函数 $pi_{i}$ 为：该字符串的前缀 $i$ 的最长 Border 长度。 考虑这个东西怎么求：…
今日推歌：不完全という証明——Nina77 废话少说，终于把（中原雅言）论文搞完了。 直接切入。 昨天我们讲了一堆后缀数组的基础的东西，今天看题。 - 给定一个字符串，设其 $k-$ 循环移位为：将其长度为 $k$ 的前缀剪切到串尾构成的新字符串。对其所有循环移位找出字典序最小的。 循环移位显然是有个套路的：直接把原串…
前排推歌：ラストタイム——夢乃ゆき 北泽社长的歌确实顶，不出意外下一次推歌就是 Nina77 的了。 虽然也可能是标题歌词来源这首歌吧。keeno，神，词写的更神。 今天主要是后缀数组简单杂谈。 以下说明如果没有特例，都是 $1-index$，也就是下标自1开始。 首先简单介绍一下这是啥东西：对于一个字符串 $s$，我…
标题来自:ラストタイム--夢乃ゆき 回头有时间了把 golden hour 也给推了，虽然大概率要等到退役后然后无限咕咕咕了。 正题的话，NOI 2016 优秀的差分，洛谷站内 P1117，三年前做过的题了，复习一下。 前排推歌：evergreen——鹿乃，可以搭配下文前半部分食用。 首先考虑一个套路：给串拆成前半截…
**一些组合恒等式与证明：** $\binom{n}{0}=\binom{n}{n}=1$：考虑组合意义，都是 $1$。 $\sum_{i=0}^{n}\binom{n}{i}=2^{n}$：考虑组合意义，左边可以解释为：钦定子集大小，求出这个大小的子集数量之后求和，这个结果就是集合的全部子集数量之和，考虑每个元素存在…
在讨论《如果你96pt WA #6》回复：
确实（悲）
提供一个基于 DFS 生成树的不一样的思路。 通过瞪样例我们可以猜想：对于原图为树的情况，选取的两条边必须相邻。 为什么？考虑对树 DFS,删掉两条边将树拆成三部分，两个子树可以直接从根 DFS 一遍，显然每条边经过两次；直接先 DFS 一个子树，回到根后走两条边到达另一个根，之后对剩下的子树 DFS 即可构造，容易证…
正好学概率论了，看个题。 给定一棵有根树，每次等概率选取一个结点把它的子树都给删了，问期望意义下多少次操作删掉整颗树。 首先一个套路：对于一个事件搞一个指示器一样的东西，$X_i={0,1}$ 表示结点 $i$ 是否进行操作，那么设 $P_i$ 为结点 $i$ 进行操作的概率，每个结点进行操作的期望 $E_i=P_iX…
前情提要：这把这题交互库锅了，打的 div2。 交互库修好之后重测了。 其中，赛时过了此题，赛后重测 FST，且下分的人，本场不计分。 我：赛时过了此题，赛后没 FST，下分。 问就是被 BC 创似了（没写出来），最后这题一个小地方调了好几遍（没看出来），+5。 回到正题。这题不难，大概 1600-1700？ 注意到如…
注意到本题的限制为 $m\le n+2$ 且为无重边自环的连通图，我们先考虑一些特殊情况： 首先，如果原图是树，那么边的颜色并不会影响答案：把图复制，选一个边集加到其中一个图，剩下的边加到另一个图，显然两者都是加一条边少一个连通块，至于是谁无所谓，答案显然是 $2\times n-m$。 由于继续加边可能成环，我们考虑…
在文章《关于KMP的一些理解》发表评论：
不好意思，border的定义我前两天说错了，不要求不重叠，但一般要求是真前缀。
在文章《关于KMP的一些理解》发表评论：
严谨地讲，KMP中的前缀函数(你这里说的p数组)是指每个前缀的最长border(即不重叠的相同前后缀)，可以通过反证法证明一个前缀的次长border一定是最长border的最长border(充分性显然，必要性考虑反证法)，只要记住这一点很好理解。
简单总结一下前几天做到的这一类题。 标题的话，对，就是来自 scrape。 注：如果没有特殊说明，下面研究的序列均为排列或离散化后为排列，且下面所说的“一轮冒泡排序”实现均为： ```cpp for(int i=1;i A[i+1]) swap(A[i],A[i+1]); ``` 这个实现等价于：每次从第一个数开始，把…
在文章《序列范围分治信息维护的一些胡扯》发表评论：
考完离散数学了，感觉双半群模型某些情况下是环，或者说如果H=T那么这个所谓”双半群“就是环？
在文章《日有所思》发表评论：
起来，补题了。
复习时想起这个，想不起来怎么推的，随手翻了一篇博客结果写的狗屁不通，后在 [@Rnfmabj](https://www.luogu.com.cn/user/93707) 帮助下得出式子，遂打算专门写一篇。 首先，此处的“树拓扑序”指：对一颗有根树 $T$ 的所有结点的排列，满足每个结点都出现在其父亲结点之后。 设 $f…
在文章《NOIP2024 游记》发表评论：
胜败乃兵家常事。
在讨论《【集中处理】升学/换校快速处理》回复：
456724 新疆维吾尔自治区特派员
在讨论《qwq, about第一问》回复：
@[jinxiu6_hehe](luogu://user/1054952) 题目中说明了，如果出现车还未走到终点速度就降为0，直接视为离开路。
在文章《CSP2024全国迷惑行为大赏合集：》发表评论：
蹲一个XJ的
在讨论《机房里有极端利己主义者怎么办》回复：
还好是赛博空间，要是现实中有这种给帽子叔叔瞎添工作量的破事叫我碰上我非得展示一下素质地板。
在讨论《机房里有极端利己主义者怎么办》回复：
@[HEPwP](/user/664651) 跟我没骂过他似的，他之前犯唐的时候也挨过不少人喷，你肯定更了解，但我现在说的是你。 反正开个地图炮，都挺搞的。
在讨论《机房里有极端利己主义者怎么办》回复：
@[HEPwP](/user/664651) 我建议保留你所有言论到十年后自阅。 这句同样适用所有你谷小朋友。时间会证明你们的可笑程度的。
在讨论《求今年河南的S2一等和二等线，以及全国二等线》回复：
@[xingshuyan000](/user/1101744) 我猜1=线可能要大于120，到130-140这样。 按照去年 NOIP 估计的，难度比较接近(这把前面比后者简单，后面更难，总体要简单一些)，但考虑不是所有CSP-S选手都能去打NOIP，分母大一点的话可能要乐观一点。 其他问题不清楚，早就不在HA了。