又是一道明明很明晰却困了我一个上午的题。完了我刷蓝书的进度要被吊打了
解一 字符串Hash结合二分
$\mathrm{O}(n+m)$预处理出两个字符串的前缀哈希。对于每一个$S$的后缀$suf(i)$，设其与$T$的最大匹配长度为$maxl(i)$。容易发现二者前缀哈希是否相等具有单调性。$\mathrm{O}(\log n)$二分每个后缀的答案，最后统计每种$maxl$的计数即可。代码实现略。
其实昨晚扫一眼题就想到了这个做法。要不是愣是要研究KMP，也不至于沦落到如此地步（
分类： OI
-
AcWing 160 匹配统计 – 题解与思路重现
-
模板 – 支持单点修改与删除操作的二叉堆
昨天考试完成T4时，明明想出了正解，但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现，发现完全没有技术上的问题。
具体来讲，通过同时保存指向每个元素在堆中当前位置的指针，可以$\mathrm{O}(\log n)$地修改和删除特定节点，以及常规的$\mathrm{O}(\log n)$的弹出栈顶、插入等操作，$\mathrm{O}(1)$地查询堆顶元素。
下面就以动态修改无向图中每个点的度并查询最小度的点为例实现一个这样的二叉堆。
-
转载 – 数论小白都能看懂的数学期望讲解 – ShineEternal
说来惭愧。从国庆到现在，至少有3个人试图把我讲懂期望，但我还是只明白最基本的定义，根本不会做题。
今天发现一篇入门级别的数学期望讲解，在此转载。
-
Educational Codeforces Round 115 解题报告
Educational Codeforces Round 115
A – Computer Game
由题意可知这是一个八连通的$2 \times n$网格。故我们扫描一遍，发现某列的两个格子均无法通过则失败。复杂度$\mathrm{O}(n)$。
-
三道排列组合好题
或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。
AtCoder ABC226 F – Score of Permutations
题意参见原题面。
很自然地想到，对于一个排列$P = (p_1, p_2, \dots, p_n)$，有$n$条$i \rightarrow p_i$的连边。因为排列中正整数$1, 2, \dots, n$恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即$p_i = i$的情况）。例如排列$P = (1, 3, 4, 2)$代表由$1 \rightarrow 1$和$2 \rightarrow 3 \rightarrow 4 \rightarrow 2$两个环组成的图。
-
牛客网 货物分组 – 题解
是的，又是一道考试时想出正解没有打出来的题目根据题意，我们很容易想到一个朴素的类区间DP——令$dp(i, j)$表示现在将第$i$件货物划分到第$j$箱中，且作为箱内的最后一件货物，所需最小花费。容易写出转移：$$dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\}$$，初值有$dp(0, 0) = 0$，应求得$\min\limits_{j \in [1, n]} dp(n, j)$。
-
CF201D Brand New Problem 简略题解
Problem D – Codeforces Round #127 (Div. 1)
多模式串匹配，是不是又是AC自动机啊？显然，每个文本串中，模式串的排列构成的子序列的逆序对数量只和模式串有关。所以我们可以对模式串建立Trie树，每扫入一个文本串的单词就进行匹配。可以做到$\mathrm{O}(K)$，K为文本串总长（
虽然单个字符串的长度极小可以$\mathrm{O}(NK)暴跳$）。这样就构建出一个由$1$到$n$构建的数列。枚举$15!$的全排列然后暴搜显然不可行。我们注意到，如果钦定一个数$x$，只要知晓当前的排列中前$j$位分别是哪些数，就可以立刻算出$x$加入排列后新增的逆序对数量。则我们考虑状压DP。 （更多…）
-
洛谷题库 P2414 [NOI2011] 阿狸的打字机 简略题解
根据题意，这是一道多模式串多文本串匹配问题。容易想到AC自动机。易知第一行的输入可以用递归/栈的形式模拟并且构建一棵Trie，可以在$\mathrm{O}(|S_0|)$的时间内完成。可以同时构建Fail失配树，时间复杂度$\mathrm{O}(P)$，$P$为Trie的节点总数。