牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共19篇）

远古杂题 1

基因匹配Match（数据结构优化dp）题意 1~n 每个数一定出现五次在s1，s2中。求两个字符串的最长公共子序列。考虑n²的暴力写法，对于每一个i，与他相等的一定只有五个。所以可以记录相等的位置优化，分别查询该位置之前的最大值+1转移，Ans记录即可。对于1~n的带修改RMQ，可以...

线段树 dp 状压字符串矩阵

2019-07-17

0 465

远古杂题 2

Base基站选址(线段树优化dp) 首先写dp转移式， $dp(i，j)$表示在第i位修建第j个基站。定义$l(i)$为能覆盖i的最靠左的基站，$r(i)$为能覆盖i的最靠右的基站， l和r数组均可以用二分求出， $dp(i，j)=min( dp(u，j-1)+cost(u，i)...

dp 数学高斯消元期望图论状压

2019-07-17

0 785

模拟53 题解

A. u 一眼差分，在斜线上加一减一。然后发现这样的复杂度是$O(nq)$的，似乎不是很好过。然后发现打差分标记的形式也是连续的，所以差分两次就完了。 B. v 最优决策问题，一般倒着转移，$O(n*2^n)$的dp是显然的。考试时一直在想能否改成三进制状压，只压...

差分期望搜索状压 dp

2019-09-28

0 411

模拟57 题解

A. 天空龙一个很好的性质是：最优方案可以不存在一个颜色A，转化为B再转化为C。因为将A直接转化为C一定更优。所以无需分类讨论，直接用一个sum判断正负就可以了。 B. 巨神兵有向图无环，所以存在拓扑序，所以用分层图dp。设f(i,j)表示已经考虑点集i，并且...

dp 容斥状压拓扑排序

2019-10-03

0 410

模拟88 题解

A. 军训队列仔细看题，会发现问题是随便交换位置。为了使答案更小，显然可以进行排序后$dp$。有$dp_{i,k}=dp_{j-1,k-1}+(a[i]-a[j])^2$。拆开平方式会发现是最简单的斜率$dp$式，而且$a$数组是单调的。所以用单调队列维护一下凸包就完了。因为...

dp 模拟凸包状压

2019-10-26

0 321

模拟90 题解

A. 新的世界显然与顺序无关，所以问题转化为最短路问题。用$dijkstra$的思想贪心。 B. 邻面合并看到这个数据范围，显然是状压。矩形上的操作，考虑轮廓线/插头dp。然而逐个转移似乎有些复杂，所以逐行转移，大力分类讨论。压缩状态的方法有很多。 ...

最短路状压 dp 线段树轮廓线

2019-10-27

0 308

模拟98 题解

A. 线性代数 (algebra) B. 装饰 (decoration) 暴力记录每个点的当前状态和上传状态，可以做到$O(4^n)$ 注意到答案并不大，不妨设最终答案为$k$，考虑在时间点$i$，选择点$j$对最终态的贡献，即对每一层祖先的状态取反。所以可以直...

状压模拟构造题最短路 dp

2019-11-04

0 356

模拟100 题解

A. 组合将两个字符之间建边，问题转化为一笔画，也就是欧拉路问题。所以直接用dfs压栈的方法解决，注意正确使用当前弧优化。 void dfs1(int x){ for(int i=head[x];i;){ if(vis[i>>1]){ head[x]...

dp 线段树图论欧拉路状压

2019-11-05

0 369

模拟109 题解

A. Adore 似乎是显然的状压。 $dp_{i,S}$表示第$i$层，其中每个点到达终点路径条数的奇偶性为$S$的方案数。直接用位运算转移，复杂度是$O(m*k*2^k)$，然后卡卡常（把$k$循环展开）就过了。似乎考虑单次的变化量，可以继续消掉一个$k$，然后就好了。 ...

贪心 bitset 状压 dp

2019-11-11

0 437

数据结构+插头dp+多项式题解乱写

可持久化数据结构 A.森林树上的数据结构常可以启发式合并，用启发式合并的思路合并树上主席树就可以了。 B.影魔一个常见的这种数据结构题的套路是：离线询问，按右端点排序。在右指针扫过去的同时在数据结构（常为线段树）中更新该右端点能产生的答案。同时在数据结构中查询统计右端点对应的区间就好...

单调栈线段树状压 dp 多项式

2019-12-29

0 450