牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

模拟29 题解

A. 壕游戏不会做，以为是贪心。结果发现贪心是错的。正解是网络流中的费用流。将每条边$i$拆为$c_i$条边，将所有边建出来，每条边的费用为$a_i*j+b_i$，$1<=j<=c_i$。然后可以直接跑费用流。然而复杂度$O(mk^2)=O(跑不过)$，死了...

数位dp 网络流 AC自动机 dp 主席树

2019-08-22

0 357

模拟80 题解

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

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

2019-10-20

0 368

省选模拟3 题解

A. 好题很神仙的做法。考虑颜色数较小的情况，可以直接通过状压$dp$实现。对于颜色数较大，不妨通过随机数将每种颜色都映射到$k$的范围内。显然这个玩意不会使答案更优，但是这样不一定能找出正确的答案。然而算一下就可以发现，这个玩意的正确性高达$\frac{k!}{k^k}$，所以...

容斥 AC自动机

2019-12-24

0 325

省选模拟71 题解

A. 王子这个数据范围加上很奇怪的限制，其实就应该是网络流了。可以首先钦定选择了 $A$ 类，然后将其中的一些替换为 $B$ 类。其实与志愿者招募那个题挺像的，只不过原来是对于每个点选择 $[l,r]$ 个区间。但是现在的问题是要求每个区间选择 $[l,r]$ 个数点。其实并不难...

网络流分块 trie树 AC自动机线段树 set

2020-04-15

0 477

字符串乱写

loj6158 考虑在一个位置放上加号，\(S=A+B\)。若末尾存在 \(0\) ，一定是说 \(A\) 的最后一个数字与 \(B\) 的最后一个数字相加为 \(10\)。（特别的，需要特判二者末尾均为 \(0\) 这个情况）对于进位的问题，其实就是要求 \(A\) 前面的数字与 \(B\) ...

字符串 AC自动机 ST表分块后缀自动机线段树

2020-07-06

0 379