分类： OI
-
洛谷题库 P4287 [SHOI2011]双倍回文 简略题解
唉，还是没有考虑清楚细节。
容易发现，一个双倍回文串必定是一个回文串，同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时，就可以同步更新答案。
但一开始我写出这样的判断：
// 完成第i个字符的最长回文的更新后 if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2) ans = max (ans, len[i]); -
洛谷题库 P3304 [SDOI2013]直径 题解与思路重现
想看正解请直接跳过文章前半段。
不知道到底错没错的错解这是一道树的直径的必经边问题。
单单求树的直径是非常简单的。可以通过两次DFS/BFS或一次树形DP完成$\mathrm{O}(N)$的求解。显然，树的直径长度唯一，但构成该长度的链的方案可能不唯一。
-
一道由数学作业延伸出的构造题
先放原题：
将正整数$1, 2, 3, \dots, 30$划分为$k$组，使得每组内任意两数之和不等于任何完全平方数。求$k$的最小值。(《培优新方法》八年级数学 §23 第3题）
嗯，对手搓暴力枚举来说数据确实大了点。抱着“反正也不可能求出正解”的心态，我尝试遍历了这些数，在第$i$遍历时，将符合要求的数依次加入第$i$组。具体来讲，如果数$g$和第$i$组里的任何数之和都不是完全平方数，则将$g$加入该组并在随后的遍历中忽略。最终一共遍历了$3$遍才将所有数分完，所以我大剌剌填了$3$上去。往后一翻——答案就是$3$。
然后某人发表暴论：“这有点像一道编程题。我在一本讲程序设计的书上看到过。”我同意。于是就有了这篇
水帖。 -
一些经常被（错误）拼读的计算机外来词
呃……我个人认为，读对算法或者程序的名字，是对其发明者最大的尊重。
- Manacher 字符串回文算法
- IPA: /ˈmɑːnɛkɛ:/；
其实这玩意俗称为马拉车算法，因为是线性的，很快啊（- 业界似乎没有正统的中文译名。
- Manacher 字符串回文算法
-
洛谷题库 P2569 [SCOI2010]股票交易 简略题解
设 $f(i,j,0/1/2)$ 表示第 $i$ 天持有 $j$ 支股票，并且当天进行了 持有 / 买 / 卖 操作，所能获得的最大的收益。很容易想到以下转移：
$$\begin{aligned}&f(i,j,0) = \max \{f(k,j,t) \mid k < i,t\in\{0,1,2\}\}; \\
&f(i,j,1)= \max \{f(k,p,t) \mid k < i-w, p \leq j,t\in\{0,1,2\}\}; \\
&f(i,j,2)= \max \{f(k,p,t) \mid k < i-w, p \geq j,t\in\{0,1,2\}\} \end{aligned}$$ -
洛谷题库 P1852 跳跳棋 题解与思路重现
我仍然坚持认为这道题不应该放在LCA的专题里面一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊？我的第一反应是“递推出从某个状态开始能达到的所有状态”，时间复杂度大约是$\mathbf{O}(2^{|N|})$（至于为什么底数为$2$，请看完下一节后思考）。但很明显，坐标在$\pm 10^9$范围内的数据可容不下这般折腾。
但鉴于它被放在这个专题中，我们就尝试从树的角度来考虑。