文章

1. 题目 传送门＝￣ω￣＝ 2. 题解 一开始看错题以为是统计条数不用判重。。。 统计最长下降子序列条数且不能有重复序列。。。 最先想到 hash 一下。。。 可是显然，$2^{31}$次方连 int 都存不下。。。你一个个数出来还不 gg。。。 设 $f(i)$为以第 $i$个数字结尾的最长下降 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 我记得我一年前在考试中推出了递推式。。。 可是我现在居然不会做了／（ㄒｏㄒ）／～～ 为什么我的智力可以下降的如此迅速。。。 首先，不难发现 a 到 b 的编辑距离=b 到 a 的编辑距离 设 $f(i,j)$为 A 的前 i 个字符到 B 的前 j 个字符的 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 此题还是很简单的。 如果是个链。。。 设 $f1[i][j],f2[i][j]$分别为区间 $[i,j]$合并后的最大值、最小值。不难得到递推式： $f1[i][j]=max\{f1[i][k]+f1[k+1][j]|i<=k<j&#9 阅读更多…

嗯嗯，这题啊，正解应该是 trie 树。 不过如果你够大佬，比如 xzy，就可以用 dfs 轻松 5msA 掉。 而本蒟蒻的 trie 树不仅代码量> 大佬 xzy，而且还用了 44ms。 真是失败。 好吧，思路是建立一棵 trie 树，然后对于字符串中的每一个字符，如果其前一个字符是某个单词 阅读更多…

继 KB 用 TRIE 树、XZY 用 DFS 将此题在 5ms 内 AC 后，本人也跟风用 KMP 来 AC 了此题，耗时 258ms。我真是太弱了。垃圾地我竟然写了 72 行！而且还是最慢的。。。 题意：用给定的一些字符串拼凑新的字符串，给定的字符串的可被拼凑的最长前缀的长度是多少？有约 200 阅读更多…

[latexpage] 题意：特工 YYF 潜入敌方根据地，历经千辛万苦后他站在了一条地雷路的第一格。伴随着音乐和鼓点，他每一步有 p 的概率往前走一格，(p-1) 的概率跳过一格到达第二格。求他生还的概率。地雷少于 11 个，但位置可能达到 108 大小。 思路：因为 YYF 不被某个地雷炸死当且 阅读更多…

1. T1 拦截导弹 啊，看过无数遍了。。。 显然数据要求 $nlogn$。。。 唔，想不起来了。。。 于是开始手动模拟过程，根据脑海中的残留片段，似乎找出了做法，又证明了一下正确性，就 AC 啦。 LIS 的 nlogn 做法自行百度（CY 听到了吗＝￣ω￣＝）代码： #include <bit 阅读更多…

来自 CY 的礼物 T1: 导弹拦截 题意：就是求最长不升子序列和最长下降子序列长度，要求是 O(nlogn) 的算法 看到这题一股气每喘上来，前几天刚看的最长某某序列 nlogn 优化，结果觉得太偏门了，没有学，结果。。。考场上临时脑补出来了。其实我只打了最长下降子序列的算法，对于最长上升子序列， 阅读更多…

概率与期望 DP 题意：给定一个矩阵，从 (1,1) 出发，有一定几率留在原地、向下走，向右走，求走到 (r,c) 平均要走多少步 (每次移动算两步)？ 注意有可能有的格子没有几率向下向右走 思路：设 f[i][j] 为 (i,j) 走到 (r,c) 的期望步数，p[i][j][k] 为 (i,j) 阅读更多…

T1 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷： 虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷 达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有 的导弹。 N<=100 阅读更多…