expect2004

分类

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章（共149篇）

LG3803 「模板」快速傅里叶变换 FFT

问题描述 LG3803 题解点我 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; const int maxn=1350000; const double Pi=acos(-1); int...

2019-12-31

0 448

BZOJ5339/LG4593 「TJOI2018」教科书般的亵渎拉格朗日插值

问题描述 [BZOJ5339](https://www.lydsy.com/JudgeOnline/problem.php?id=5339） LG4593 题解打出暴力之后，发现就是 \(F(x)=\sum\limits_{i=1}^{x}{i^{m+1}}\) 的时间复杂度比较高 ...

2019-12-29

0 608

LG4781 「模板」拉格朗日插值拉格朗日插值

问题描述 LG4781 题解多项式点值转系数的方法。时间复杂度 \(O(n^2)\)，要线性求逆。求 \(n+1\) 次多项式的拉格朗日插值式子： \[F(k)=\sum\limits_{i=0}^{n}{y_i \times \prod\limits_{i \neq j}{\...

2019-12-28

0 547

LOJ155 「模板」无源汇有上下界可行流上下界网络流

问题描述 $ n $ 个点，$ m $ 条边，每条边 $ e $ 有一个流量下界 $ \text{lower}(e) $ 和流量上界 $ \text{upper}(e) $，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。 https://www.luogu.com....

2019-12-27

0 441

BZOJ2820/LG2257 YY的GCD 莫比乌斯反演

问题描述 BZOJ2820 LG2257 题解求 \(\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{[gcd(i,j)==p]}}\) ，其中 \(p\)为质数，\(n<m\) 。考虑不要求 \(gcd(i,j)\) 为质数时的做法：...

2019-12-21

0 553

BZOJ2127/LG1646 happiness 新建点最小割

问题描述 BZOJ2127 LG1646 题解和文理分科差不多收益最大 -> 损失最小 -> 最小割分别新建点表示互相关系就行了 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace ...

2019-12-21

0 482

BZOJ3894/LG4313 文理分科新建点最小割

问题描述 BZOJ3894 LG4313 题解显然一个人只能选文/理 -> 一个人只能属于文（S）、理（T）集合中的一个可以把选择文得到 \(art\) 的收益看做选择文失去 \(science\) 的收益，也就是最小割了。考虑如何处理周围人都选对于文科，再新建一个 ...

2019-12-21

0 468

TopCoder12727 「SRM590Hard」FoxAndCity 最小割离散变量模型

问题描述一张 \(N\) 个点无向图，边权都为 \(1\) ，添加若干条边，最小化 \(\sum\limits_{1 \le i \le n,i \in N_{+}}{(a_i-b_i)^2}\)。 \(b_i\) 是输入的， \(a_i\) 是 \(1\) 号点到 \(i\) 号点的最短路。 ...

2019-12-21

0 725

TopCoder12808 「SRM594Medium」FoxAndGo3 二分图最大独立集

问题描述一个 \(N \times N\) 围棋棋盘，任意两个白子不相邻，你要加入若干个黑子并提出白子，最大化空格数目。 submit 题解显然最终棋盘的局面不能够一个白子和它周围的空格都是空的，只能属于「空」或「不空」。所以是个二分图。二分图最大独立集=总点数-二分...

2019-12-20

0 491

Codechef RIN 「Codechef14DEC」Course Selection 最小割离散变量模型

问题描述提供中文版本好评，一直以为 Rin 是题目名字... pdf submit 题解参考了东营市胜利第一中学姜志豪的《网络流的一些建模方法》（2016年信息学奥林匹克中国国家队候选队员论文）读了之后很有感触，这里节选一段话：最小割模型的本质是将点的集合 \(V\...

2019-12-17

0 535