牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

模拟75 题解

A. 导弹袭击想到了凸包，推出了题中的式子，然而没有继续推下去。或者说，高考数学线性规划没有学好。一种导弹的飞行时间函数为： $z_i=A*\frac{1}{a_i}+B*\frac{1}{b_i}$ 似乎显然是一个线性规划式，设$x=\frac{1}{a_i},y=\frac{1}...

dp 单调栈凸包高斯消元倍增

2019-10-16

0 0

模拟76 题解

A. 序列观察部分分，可以得到一些奇怪的构造方法。比如当$N=A*B$，直接将数按$A$的大小或$B$的大小分块就可以了接着打表，发现似乎全部的情况都可以通过类似的方法构造出来。只要对后面的部分分块，前面不足的部分不用分块。 B. 购物奇妙的数的范围很宽泛，达...

构造题 dp 组合计数

2019-10-17

0 297

模拟78 题解

A. 串串香送分题。发现用$kmp$复杂度也是$O(n)$，和直接哈希的复杂度是一样的。所以直接双模哈希硬干就完了。 B. 糊涂图在不加边的情况下，因为存在拓扑序，问题是简单的。所以可以先处理出不加边情况下，每个点达哥获胜的概率，其实这个数组也表示走奇数步后无...

Hash KMP 拓扑排序 dp 倍增直径

2019-10-18

0 360

模拟80 题解

A. 贝尔数这个数据范围，似乎显然是矩阵快速幂。对模数质因数分解就会发现每个质因子只出现一次且很小。所以考虑求出$mod$每个质因子的结果并$crt$合并。题中已经给出了贝尔数在模$p$意义下的一个公式，所以直接保存$p$个贝尔数，矩阵快速幂转移就可以了。 B...

线性代数矩阵 AC自动机 dp 二分图网络流

2019-10-20

0 368

模拟83 题解

A. 最大异或和异或是不进位加法。具有一个很好的性质：$a\ xor\ b=c$ $\rightarrow$ $c\ xor\ b=a$ 若所有点的异或和为$0$,那么显然平手。若异或和不为$0$,先手只要将最高位的$1$选到必胜。 B. 简单的括号序...

dp 结论题组合计数位运算分块最短路

2019-10-23

0 400

模拟84 题解

A. Smooth 考虑用已有的光滑数推出新的光滑数。显然每次可以取出最小的光滑数，并乘每个质因子插入堆中。需要通过哈希表打标记来解决重复计数的问题。复杂度为$O(kblogk)$，空间应该也承受不住。正解显然不带$log$。因为我们每次取出的都是最小的光滑数，其实堆有些多余。...

单调队列 Hash dp

2019-10-24

0 0

模拟86 题解

A. 异或位运算所以按位考虑。数位$dp$统计每一位$0/1$的取值个数，随便乘一乘就出结果了。 B. 取石子 $O(n^4)$的$dp$是显然的。可以发现$dp$中必败的状态是很少的。所以直接打表所以可以用必败的状态刷表进行$dp$，复杂度是对的。 ...

数位dp 博弈论 dp 位运算

2019-10-25

0 431

模拟87 题解

A. maze 做过类似的题，维护最短路对于$k$的一个凸包，答案就是凸包与$y=s$直线交点的横坐标，这个还挺难打的。然而答案显然具有单调性，所以直接二分答案就完了。实际上，这个二分答案的操作，等价于选定直线$x=mid$，求出$x=mid$与凸包的交点的纵坐标，并通过这个纵坐标与$...

凸包二分答案 dp 线段树字符串

2019-10-25

0 374

模拟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