口胡一个不需要数据随机的做法，代码之后补（不是）。 假设我们已经转化到了 [[HNOI2010] 弹飞绵羊](https://www.luogu.com.cn/problem/P3203) ，也就是说我们只需要能快速查询对于 $t$ 的某一个区间的子串是不是给定的模式串的子串即可（更确切的说法是最长的能和某一个子串匹配…

真逆天了

书接上回，我们构造了一个对偶问题，但是仅仅是给出了构造方法，并不能说明为什么是正确的。 不过考虑到线性规划问题本质上就是最优化一个带约束多元函数，因此不难将其与拉格朗日乘子法联系在一起。 ### （广义）拉格朗日函数 对于一个线性规划问题： $$ \begin{align} \min f_0(\boldsymbol{x…

斗网络流的时候遇到了这个神秘东西，写一下。 在信息学竞赛中，很多时候遇到的线性规划问题并不是标准形式的线性规划，没办法直接斗成矩阵然后转置，况且转置后的组合意义也可能是不明确的（绝大多数信息学竞赛中的线性规划问题中，约束矩阵都是一个稀疏矩阵，而其转置后的组合意义可能并不明显）。 而最近看到了一个简单的构造对偶问题的方法…

没参加第19届。

一个不用动脑子的笨b做法。 考虑先做静态的这个问题。套路的对于每一个 $a_i$ 求出以它为最大值的区间（方便起见这里钦定对于大小相同的 $a_i$，下标更小的 $a_i$ 更小）。 以 $a_i$ 为最大值的区间 $[l,r]$ 一定形如 $L_i \leq l \leq i \leq r \leq R_i$，而对于…

在讨论《关于网络流》回复：

直接做是 $O(n^4)$，但可以先原始对偶再用fib堆优化dij可以做 $O(nm+n(n \log n + m))$ 也就是 $O(n^3)$。

在讨论《瞎想的题目不会做，求助。》回复：

放到前缀和上直接跑差分约束

一天，信友队给我打来电话他说：“你敢不敢跟我举行联考大战”，我豪爽的答应了：“我当然敢”， 周日上午在 xx 机房 xx 电脑举行，谁不来谁就是怂货。 我原本以为我恐吓了信友队，信友队应该躲在学军中学，不敢找我，可正当这是，我听见了音乐 声，原来是我手机响了，一看，竟然是信友队打来的电话，他还真有勇气，我接通了电话，听…

难蚌题目。 考虑如果最终答案的方向向量是 $(x,y)$，那么把所有向量转到 $(x,y)$ 的投影上，显然对应的答案是使得这个投影最大的答案。 所以对于 $2,3$ 问，随机 $30000$ 个方向将所有向量转化到投影上，即可变为一维上的问题，对向量大小排序即可。 ```cpp #include using name…

RT,会UKE,答案其实可以超过int范围。 https://www.luogu.com.cn/record/212351663

### 前言 唐氏数据结构，支持均摊 $O(1)$ 插入，合并，decreaseKey(默认小根堆)，$O(\log n)$ 删除任意元素。 插入常数其实并不大，不过删除常数非常大。 Bonus:如果不改变 $\min$，也可以均摊 $O(1)$ 的做 increaseKey。 ### 基本思想 斐波那契堆降低时间复杂…

被szzjz骗去做这道题，给我赤石赤饱了。 给定一个长度为 $n$ 的序列，$q$ 次询问 $l,r,k$，表示在区间 $l,r$ 中取出 $k$ 个不相交的非空子段的元素和最大值。 首先答案对 $k$ 是凸的，可以用费用流模型简单证明。只有一次询问时可以维护凸函数的 $(\max,+)$ 卷积，每次合并两个复杂度为…

在文章《OI 生活回忆录》发表评论：

byd我想肝原神了

在文章《OI 生活回忆录》发表评论：

其实OI好不好都无所谓，不要太消极

在文章《OI 生活回忆录》发表评论：

祝你高考不坠机

题意：给你一个带容量与费用的有原汇图，求费用最小的最小容量割。 做法1(感谢@JLGxy): 先跑一边最小割，将残量网络缩点后任意一个割为原图最小割，按照费用在跑一边即可。 做法2： 将每条边权值定位 $Ac_i+w_i$，则新图最小割为 $cut$，原图最小割为 $\lfloor \frac{cut}{A} \rfl…

在文章《[洛谷日报#271]Testlib——最强出题辅助工具库》发表评论：

某OJ使用testlib出题需要1000+行代码

在讨论《看洛谷这题解区还不如日文能理解》回复：

审题解的人不一定看过这题，怎么保证质量？

如题，也可能是我笨了，希望不要嘲讽我（也可以嘲讽我）。

在讨论《ABC 模拟赛 | A Passing Contest 001 赛时答疑帖》回复：

@[tbdsh](/user/752485) 那你玩原神吗？

在讨论《【求助】校建模队作业》回复：

是不是可以先斗成一个二元函数然后退火？

在文章《NOI 2024》发表评论：

不许你说咒术回战！！！

在讨论《100，Unaccepted》回复：

所以？

在讨论《强烈谴责CF！！》回复：

这种东西发学术版干吗

在讨论《建议撤下以下题解》回复：

前排

写了一个很唐的交互库，可能有锅，但是标程至少能过样例（ 交互库:https://www.luogu.com.cn/paste/szwhlpjq 另外此题翻译的不是很清楚，其实那个组成的图形在高度上只会有一个方块。

在讨论《如何判断别人是否喜欢你？》回复：

让他帮你做[好题](https://atcoder.jp/contests/agc066/tasks/agc066_e)

在讨论《求有意愿的7+钩gks合伙人》回复：

我没钱

原本为了取消二次剩余的log而使用小质数，但是加了hack数据后带log反而能过了。 所以加这个hack是不是没太大价值？ 不过这题原时限也确实能被卡就是了。