【题解】[清华集训 2016] 你的生命已如风中残烛 – Sora1336
这道题很谔谔。就一阅读理解呗。 本来是想状压 DP 的，结果懒了。事实上这就是一道组合数学。 题面人话翻译：有和为 $0$ 的 $m$ 个数 $a_i\sim a_m$，求 $i$ 有多少种排列使得任意一个前缀和都大于等于 $0$ 。 不能这样直接算，给序列末尾加上一个 $-1$ 然后求前 $m$ 阅读更多…
【题解】薇尔莉特的打字机
update：题目地址：here 首先，这题需要处理字符串，我们用 $trie$分析 先忽略删除操作 拿样例 1 举个例子： 首先把最开始的字符串插入到树中 然后薇尔莉特打了一个字符 $A$ 此时可以插入或者是不插入，就会有这样的情况： 不插入时，之前插入进去的字符均可以作为字符串的结尾 假设之前插 阅读更多…
【算法】类欧几里得算法浅谈
类欧几里得算法，简称类欧，因为计算过程中有类似辗转相除的算法故叫类欧几里得算法。 前置知识 欧拉定理 / 欧拉函数 取模 限制转换 简单的不等式知识 放缩 平方化简公式（具体见化简 $f_2$ 那个模块）模板题：P5170【模板】类欧几里得算法 基础 给定一个函数 $$f(n,a,b,c)=\su 阅读更多…
【题解】数列分块入门 8 ODT 解法 – Sora1336
题面： 给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间询问等于一个数 $c$ 的元素，并将这个区间的所有元素改为 $c$。 这道题我一看到区间推平就想到了 ODT，完全不管这是一道分块题。实际上，分块可以做的题， ODT 也基本可以胜任。 问题是网上的博客基本没有讲到 ODT 的查 阅读更多…
【算法】浅谈数列分块问题 – Sora1336
写这篇博文呢，主要还是为了准备信息队员交流，毕竟分块是我最喜欢的数据结构，所以我就试着写了一篇博文。 基本介绍： 分块是维护较为复杂的信息的，尤其是不满足区间可加性可减性的信息的重要工具。如果运用树状数组或线段树，代码也非常的麻烦和不直观，Debug 可以 Debug 一天。而分块是以一种 “暴力” 阅读更多…
【题解】字符串题目记录
字符串杂题记录 字符串刚刚入门。 考的少就贼亏。 Aho-Corasick AutoMaton 需要谨记的一点就是，$\rm{ACM}$ 跳的是 最长公共后缀，而不是 最长公共前后缀 。 不要和 $kmp$ 搞混了，千万不要相信什么 $\rm{ACM}$ 就是 $kmp$ 上树，千万不要。 Suff 阅读更多…
【系列】数据结构一百题
「洛谷题单界面」，如果有帮助可以 archive 一下。「洛谷博客界面」在 mina.moe 上可能更新比较延后，因为我要同时维护多个地方，懒得很…… 这里是由 @BoringHacker 以及 @Lautisticyc 维护的数据结构 100 题，简称 DS100P。 难度主要在提高组及以上。 阅读更多…
【题解】[JSOI2019] 节日庆典 扩展 kmp luoguP5334
传送门 题面 题意 给定一个字符串 $s$ (起始位置为 $1$), 对 $s$ 的每个前缀求出最小循环表示的起始位置. 输入样例 abaacaba 输出样例 1 1 3 3 3 6 3 8 数据范围 $|s| \le 3 \times 10^6$. 思路 假设先从前往后扫一遍, 则对于每个前缀, 阅读更多…
【算法】关于二维二项式反演的正确性 -永无岛
前言 我第一次看到这个 idea 是神 $Fuyuki$ 去年 6 月份的时候出了一套题目，里面用到了这个东西，不过他当时没有给出证明。后来看到了 $boshi$ 在 $Mina$ 上发的计数合集，里面证明了这玩意儿的正确性，我个人认为还是一个非常妙的东西，所以专门开个坑记录一下。 柿子 $$ \t 阅读更多…
【题解】[十二省联考 2019] 字符串问题 后缀数组+拓扑+可持久化线段树优化建图 Loj3049 —Qiuly
暴力连边的话，对于原图中的 $(x,y)$ ，将 $A_x\rightarrow B_y$ 给连上，然后如果 $B_i$ 是 $A_j$ 的前缀的话，将 $B_i\rightarrow A_j$ 连上。定义点 $A$ 的权值为其长度，点 $B$ 权值为 $0$ ，显然答案就是图上的最长路，当然如果出 阅读更多…