dp 状压dp    2018-09-21 10:32:51    154    0    0
Problem 求 n" role="presentation" style="position: relative;">nnn 个模式串,能匹配其中 k" role="presentation" style="position: relative;">kkk 个的字符串的个数 匹配的含义为 若为 "?" 则与所以字母都匹配,若为字母,则需相同 Solution 首先看的 n" role="presentation" style="position: relative;">nnn 很小,然后可能使用状压 dp" role="presentation" style
tarjan 点双    2018-09-20 12:04:16    202    0    0
Solution 先 tarjan" role="presentation" style="position: relative;">tarjantarjantarjan 求点双。 对于每一个连通块,如果其中没有割点,则说明需要在其中建立两个出口;只有一个割点,那么就需要在非割点处选一个建立出口;如果有大于等于两个割点,则不需要建立出口 Code #include <cstdio>#include <cstring>#include <stack>#include <vector>#include <algori
dp 斜率优化dp    2018-09-19 00:07:18    5    0    0
Problem 先有一些工厂,每个工厂有一些成品。先要在其中一些工厂的位置建立仓库,建立仓库会有一定的费用。每个没设立仓库的地方将成品运送至下面的仓库,费用为成品数乘距离。山脚一定有一个仓库。问最少需要的花费是多少 工厂 i" role="presentation" style="position: relative;">iii 距离工厂 1" role="presentation" style="position: relative;">111 的距离 xi" role="presentation" style="position: relative;">xixix_i
dp 斜率优化dp    2018-09-18 22:18:59    1    0    0
Solution 首先可以得到 dp" role="presentation" style="position: relative;">dpdpdp 方程 f[i]=max(f[j]+a(sum[i]&#x2212;sum[j])2+b(sum[i]&#x2212;sum[j])+c)" role="presentation" style="position: relative;">f[i]=max(f[j]+a(sum[i]−sum[j])2+b(sum[i]−sum[j])+c)f[i]=max(f[j]+a(sum[i]−sum[j])2+b(sum[i]−
字典树 学习笔记    2018-09-18 21:28:08    1    0    0
Problem 给定一个非负整数序列 a" role="presentation" style="position: relative;">aa{a},初始长度为 n" role="presentation" style="position: relative;">nnn。 有M个操作,有以下两种操作类型: 1&#x3001;A" role="presentation" style="position: relative;">1、A1、A1、A x" role="presentation" style="position: relative;">xx x:
dp 斜率优化dp 学习笔记    2018-09-18 21:14:55    3    0    0
Solution f[i]=min(f[j]+(i&#x2212;j&#x2212;1+sum[i]&#x2212;sum[j]&#x2212;L)2)" role="presentation" style="position: relative;">f[i]=min(f[j]+(i−j−1+sum[i]−sum[j]−L)2)f[i]=min(f[j]+(i−j−1+sum[i]−sum[j]−L)2)f[i]=min(f[j]+(i-j-1+sum[i]-sum[j]-L)^2) 为了方便计算,我们定义 a[i]=i+sum[i]" role="p
dp 容斥 树状数组    2018-09-17 22:17:55    68    0    0
Problem 给你一个序列,若此时这个序列不是非降的,那么从中删除一个数,知道删到非降为止。 问有多少种操作方案 Solution 定义 f[i]" role="presentation" style="position: relative;">f[i]f[i]f[i] 表示长度为 i" role="presentation" style="position: relative;">iii 的非降子序列个数 容斥一下, ans=&#x2211;f[i]&#x2217;(n&#x2212;i)!&#x2212;f[i+1]&#
lca 思维    2018-09-17 20:33:21    66    0    0
Problem 有三个棋子在一个一条数轴上,可以使其中一枚为轴,另一枚跳过去,但跳的过程中不能越过第三枚棋子。 给定初始状态,问能否达到最终状态,如果可以最少需要几步 Solution 首先先判断可不可以。 我们可以讲初末状态都转变成不能再走的状态,显然对于每种情况这种状态只有一个。 那如果不能再继续的状态一样,说明他们肯定是可以通过变换得到的;反之,最终状态都不同,显然不能跳出来... 这样我们记录下状态、跳的步数。 类似 lca" role="presentation" style="position: relative;">lcalcalca 的操作,看跳这
dp    2018-09-17 20:04:47    59    0    0
Problem 用 M" role="presentation" style="position: relative;">MMM 种长为 K" role="presentation" style="position: relative;">KKK 的印章(每种颜色均不同),给长为 N" role="presentation" style="position: relative;">NNN 的纸条盖章。 问最后会得到多少种不同的状态。 Solution 反过来想,答案就是总数减去不合法情况。 总数也就是每个块随便选颜色,即 mn" role="presentat
dp 树形    2018-09-17 19:27:49    63    0    0
Problem Bessie" role="presentation" style="position: relative;">BessieBessieBessie 站在一个点,每个叶节点可以放一个士兵,士兵和 Bessie" role="presentation" style="position: relative;">BessieBessieBessie 都可以随意走动。 如果士兵和 Bessie" role="presentation" style="position: relative;">BessieBessieBessie 在同一点,那么 Bessie" ro
文档导航