牛客237787563号

未归档

/ 注册

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

图论杂题

矩阵游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1059 刚开始以为只要每行每列都存在一个1，就是可行的解，然后发现可以被yxm简单的数据hack掉： 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 正解是...

图论二分图树上差分桶线段树 wqs二分

2019-07-16

0 386

模拟80 题解

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

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

2019-10-20

0 368

模拟85 题解

A. 表达式密码观察样例，发现答案就是将减法拆为一个减法和多个加法，于是就完了。 B. 电压机制发现问题是认为一条边相邻的两个点颜色相同并不考虑这条边，问图能否二分图染色。暴力做法是$O(nm)$的。仔细想想就可以发现：对于奇环，不能二分图染色，所以必须选择奇...

二分图 tarjan 贪心

2019-10-25

0 697

网络流杂题二

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

网络流二分图

2019-12-09

0 405

网络流杂题一

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

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

2019-12-08

0 523

省选模拟13 题解

A. 同桌的你每个人渴望与一个人当同桌。容易发现这个关系形成内向基环树森林。问题转化为求基环树森林的最大匹配。任意选一条环上的边，分别尝试该边为匹配边、非匹配边即可。 B. 大水题一个常用的但想不到的东西：将每种颜色出现次数的差值为定值，转化为对颜色序列差分后相等。然...

二分图二分答案 Hash 差分基环树 2sat

2020-02-01

0 474

省选模拟8 题解

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

网络流二分图分块线段树

2020-01-17

0 553

省选模拟9 题解

A. Surprise me 直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。于是可以套用莫比乌斯反演。最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\su...

二分图虚树图论结论题莫比乌斯函数点分治提交答案

2020-01-17

0 654

省选模拟24 题解

A. U.N.OWEN就是她吗？字典序最大，只需要贪心。考虑用网络流来做这个题。每次二分一个答案，然后对当前操作和之前进行的操作与每个元素直接建边，判断是否存在完美匹配。因为题中保证了一个特殊性质，考虑通过霍尔定理优化。点集 $X,Y$ 存在完美匹配，仅当 $\forall Z ...

线段树生成函数二分图多项式最短路

2020-02-14

0 412

省选模拟35 题解

A. two 考虑现在要通过蓝边删掉红边。其实等价于要找出有哪些红边，满足恰好只有一个端点在蓝边的儿子方向子树中。考虑对蓝树跑出一个 $dfs$ 序来，那么问题转化为恰好一个端点在给定区间中。这像是一个二维偏序问题。考虑以线段树下标为其中的第一维，第二维进行排序处理。然后用一个 $...

单调指针点分治多项式二分图网络流线段树

2020-03-02

0 334