牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共23篇）

模拟26A 题解

A. marshland 考试时想到了网络流，然而不会建图，就死了。正解是最大费用可行流。比较容易想到的是将每个点拆为两个点， s连没有危险值的入点，没有危险值的入点连有危险值的入点，入点出点之间限流有费用，出点再连没有危险值的出点，这些出点连向t。不断跑spfa，通过有流量...

二分答案网络流后缀数组 bitset 树链剖分

2019-08-20

0 385

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

网络流杂题二

A. 无限之环正解的思路并没有局限于原图中的网络流，而是将网格图黑白染色。将源点向黑点建边，黑点向可以连接的白点建边，之后原图无缝拼接可以简单地转化为跑最大流之后能够满流。所以只要考虑如何加入翻转次数的限制。因为流量必须全部流向同一个状态，简单拆分为四个方向似乎并不是可行的。题解...

网络流二分图

2019-12-09

0 405

网络流杂题一

A. 奇怪的游戏网格图在网络流中往往对应着黑白染色，当然还有四色染色等奇怪的东西。建图并不难，但是二分的思想是很好的。考虑如何检验一个答案$x$，将黑点视为二分图的左部点，白点视为二分图的右部点。一次操作对应一组相邻黑白点$+1$，所以直接建图看能否跑满流就完了。然而需要注意，显...

区间dp dp 二分答案网络流二分图

2019-12-08

0 523

网络流杂题三

A. 1565: 植物大战僵尸考虑保护关系可能会出环，也就是其中任何一个一定不能被选。注意环的出边也是无法被选的。注意要找的环的出边并不是网络流建的图的出边，因为网络流反映的是必须选的关系，即由被保护者到保护者。然后就是简单的最大权闭合子图。 B. 寿司餐厅似乎并不是很难...

网络流二分答案

2019-12-09

0 290

省选模拟1 题解

A. 天空碎片正解很麻烦，所以打表找规律 B. 未来拼图发现这个式子是一个简单的循环卷积式，所以要求的实际上是一个多项式在$mod\ x^n$意义下的平方根个数和最小字典序平方根。然而本题所要求的循环卷积与一般情况下的$2^k$不同。然而这个复杂度，可以直接做暴力DFT，即直...

多项式网络流

2019-12-24

0 393

省选模拟2 题解

A. 铁轨建设暴力插头dp+网络流判断可行性，可以拿到85分。然而这个题看起来就很像无限之环，只要稍微改一下建图就好了。然而这个建图还蛮难想到的。 B. 圈地游戏因为不会做+看不懂题解+std太长，所以咕掉了。 C. 组合数学 70分部分分：考虑到状态数很少，直接暴...

dp 网络流二项式反演容斥组合计数

2019-12-24

0 408

省选模拟8 题解

A. 序列发现较难维护的是后一个信息。所以考虑直接分块维护。为每个块开一个vector，表示这个块中所有元素对vector中的所有元素依次取过max。因为取max的性质，这个vector中的元素只需要保留单调递增的部分。在查询的时候和暴力重构一些块的时候，可以直接在vector中...

网络流二分图分块线段树

2020-01-17

0 553

图论专项测试

A. center 分别考虑每一条边。二分答案，问题转化为判定是否存在可行区间。然后列式子发现存在三种限制的形态，而其中的一种（含有或运算）并不是一个线性算法能够解决的。盲猜这种情况并不多见，剪枝暴力$AC$。个人认为三分的算法是伪的，见数据（不能hack三分算法，但不单谷）： ...

二分答案最短路网络流三分二进制分组

2020-01-30

0 488