这个题是倍增+hash,细节比较多…… 题目描述 有一张\(n\)个点\(m\)条边的有向图,每条边上都带有一个字符,字符用一个数字表示。 求以每个点为起点的最长路,输出走过的边的字符构成...
DP
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\)眼就切掉了这...
[2018.10 雅礼] w 题解【树形DP】
特别神奇+巧妙+玄学的树形DP,但是也很经典。 题目背景 \(\frac 14\)遇到了一道水题,双完全不会做,于是去请教小\(\text{D}\)。小\(\text{D}\)看了\(0.607^2\)眼就切掉了这题,嘲讽了\(...
牛客 202H 卡牌游戏 题解【概率期望】【递推】
是一道思路简单的期望题。 题目描述 小贝喜欢玩卡牌游戏。某个游戏体系中共有\(N\)种卡牌,其中\(M\)种是稀有的。小贝每次和电脑对决获胜之后都会有一个抽卡机会,这时系统会随机从\(N...
[2018.10雅礼] 折射 题解【DP】【前缀和】
这个题的50分做法比100分做法要麻烦……但是100分有点反人类了 题目描述 小\(\mathrm{Y}\)十分喜爱光学相关的问题,一天他正在研究折射. 他在平面上放置了\(n\)个折射装置,希望利...
洛谷 P2577 [ZJOI2005]午餐 题解【贪心】【DP】
不是很熟悉但是很有用的DP转移 题目描述 上午的训练结束了,THU ACM小组集体去吃午餐,他们一行\(N\)人来到了著名的十食堂。这里有两个打饭的窗口,每个窗口同一时刻只能给一个人打饭。...
洛谷 P1119 灾后重建 题解【floyd】【DP】
floyd一开始思路想错了……还多加了一维? 题目背景 B地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村庄的...