需要一点点复杂度优化+常数优化 题目背景 企鹅豆豆做完了作业,找你帮他检查。 题目描述 豆豆写的作业由小写字母组成。但由于一道题有多种答案,所以答案中除了小写字母以外还有.和*。...
DP
洛谷 P1941 NOIp2014提高组 飞扬的小鸟 题解【背包】
一道送好多分的完全背包题。 题目描述 \(\text{Flappy Bird}\)是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道...
单调序列 题解【构造】【DP】【找规律(雾】
考试读错题了导致没有\(\text{AK}\)。 题目描述 \(\text{GISPZJZ}\)有一个长度为\(n\)的序列\(a_1,a_2,\dots ,a_n\)。序列的所有元素都是\(1\)或者\(2\)。我们称一序列是该序列的不下降...
完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】
后效性处理+背包合法性转化…又是玄学操作,不过感觉对DP的理解又深入了一些。 题目描述 有\(n\)种物品,物品的体积分别为\(V_1,V_2,\dots,V_n\),且每种物品的数量都可以看做是无限多的...
洛谷 P3959 NOIp2017提高组 宝藏 题解【状态压缩】【DP】【生成树】【贪心】
还是在NOIp2018前写出了这道2017谜之状压。 问题描述 参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了\(n\)个深埋在地下的宝藏屋,也给出了这\(n\)个宝藏屋之间可供开发的 \(m\)条...
牛客 178A 最长路 题解【拓扑排序】【贪心】【分层图】【哈希】【倍增】
这个题是倍增+hash,细节比较多…… 题目描述 有一张\(n\)个点\(m\)条边的有向图,每条边上都带有一个字符,字符用一个数字表示。 求以每个点为起点的最长路,输出走过的边的字符构成...
Adore 题解【DP】【状态压缩】
奇怪的状压+神奇的转移。 题目背景 小\(\text{w}\)偶然间看到了一个\(\text{DAG}\)。 题目描述 这个\(\text{DAG}\)有\(m\)层,第一层只有⼀个源点,最后一层只有一个汇点,剩...
洛谷 P2679 NOIp2015提高组 子串 题解【DP】【字符串】
NOIp前复习想到这个之前做过的毒瘤DP,没想到现在依然毒瘤。 题目描述 有两个仅包含小写英文字母的字符串\(A\)和\(B\)。 现在要从字符串\(A\)中取出\(k\)个互不重叠的非空子串...
洛谷 P2279 [HNOI2003]消防局的设立 题解【树形DP】【解题报告】
这个题真的有点毒瘤,发现现在的树形DP都好厉害啊…… 题目描述 2020年,人类在火星上建立了一个庞大的基地群,总共有\(n\)个基地。起初为了节约材料,人类只修建了\(n-1\)条道路来连接这...
[2018.10 雅礼] v 题解【概率期望】【DP】【状态压缩】
这个题除了考期望、状压,考察的就是怎么压空间+时间了吧。 题目背景 \(\frac 14\)遇到了一道水题,又完全不会做,于是去请教小\(\text{D}\)。小\(\text{D}\)看了\(0.607\)眼就切掉了这...