牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共19篇）

省选模拟7 题解

A. 翻转硬币第一眼以为只要保证给定的$k$个点反面就好了，是弱智水题，于是感觉秒切了。然后考完20分，就被秒切了。所以实际上是一道原题。思路大概是对原序列进行异或意义下的差分，于是区间修改转化为两个点的修改。于是问题变化为将初态共$2k$个$1$消为$0$。然后发现每个有意...

状压最短路线段树平衡树差分 dp manacher

2020-01-14

0 400

省选模拟12 题解

A. Colorado Potato Beetle 暴力做法是直接bfs。优化的方法是离散化。将特殊的点的横纵坐标抽出来，然后用这些横纵坐标为1e12*1e12分成一个个块，容易发现每个块内的状态是一致的。然后用与暴力类似的方法即可，注意最后统计的是每个块的实际大小。 B. D...

后缀自动机 dp 状压搜索树链剖分线段树

2020-02-01

0 359

省选模拟31 题解

A. Skip 一眼决策单调性，但是感觉因为带个权值就不好处理了。实际上对权值开个线段树，然后直接在线段树上维护决策单调性就完事了。而且这个式子是一个显然的斜率优化 dp ，在权值线段树上维护凸包也挺套路的。感觉这题没做出来比较可惜，没有想到通过对权值开线段树，来实现权值的无关操作。 ...

状压线段树凸包 dp 决策单调性

2020-02-26

0 410

省选模拟40 题解

A. 染色问题考虑对每条边 $(a,b)$ 附加两种边权 $(x,y)$ 。对于一种染色方案，当 $col_a=col_b$，边权为 $x$，否则边权为 $y$。取 $x=1,y=0$，一种染色方案的贡献是所有边权的乘积，那么答案就是对于每种染色方案的贡献的和。发现这个玩意可以合并。...

组合计数状压网络流二项式反演

2020-03-08

0 754

省选模拟57 题解

A. Max 看到这个数据范围就想一下是不是可以状压。然后发现只有 $m$ 压的下。容易发现题目中的顺序并不关键，其实可以无视掉原有的操作顺序。然后现在给 $1... n$ 每个元素分配一些操作就好了。这样在给第 $i+1$ 个元素分配操作之前，我们只关注已经分配的操作集合、最大的...

树剖扫描线动态dp dp 线段树状压

2020-03-29

0 353

省选模拟86 题解

A. 人生有一点 dp 套 dp 的意思，内层的 dp 就是直接在拓扑序上进行的简单 dp。外层记录的是 dp 的状态，然后 $O(n^3)$ 的做法是显然的。当转移到第 $i$ 个位置的时候，只要关心前面有多少个黑点 dp 值为 $1$，前面有多少个白点 dp 值为 $1$，前面的 d...

字符串状压后缀自动机 dp

2020-05-02

0 380

省选模拟88 题解

A. 或许容易发现 $u,v$ 联通仅当 $u \oplus v$ 能被集合 $S$ 通过 $\oplus$ 运算表出。所以只需要维护线性基内元素个数。然后暴力的做法就是直接线段树分治。然后有一个能进行删除的离线操作是，不断尝试用被删除最晚的替换线性基中的元素。 B. 这就是 ...

线性基莫队根号分治 dp 状压

2020-05-05

0 381

省选模拟101 题解

石子游戏问题可以简单转化为最少能取出多少个数，使得异或和为 \(k\)。显然答案是小于 \(log(A_i)\) 的，因为线性基已经可以拼出所有数了。所以可以考虑枚举这个答案，然后就是 \(dp_{i,j}\) 表示用 \(i\) 个数能否拼出 \(j\)。转移可以用 \(FWT\) 优化，...

状压容斥 fwt dp 筛法

2020-05-20

0 367

noi前第九场题解

A. s1mple 可以发现 0/1 这个限制类似于求路径数，使得路径经过的边权恰好合法。显然可以用容斥来求，这样可以将问题转化为钦定其中若干条边权为 \(1\)，其他边权任意的路径数。这样做有一个好处，原来问题中的 \(2^{n-1}\) 的集合可以缩减状态数。对于钦定之后的若干条 \(1...

dp 多项式后缀自动机拉格朗日插值启发式合并状压字符串

2020-07-21

0 379