网络流学习笔记（上）

• 网络流 24 题

0.前记

学术较浅，有问题欢迎大佬们指出。

说好的打完 CSP 就开始学网络流，结果颓了快一个月才开始，打算从头到尾学一遍，但是快打 noip 了，感觉这玩意 noip 也不一定考，还是先把较为基础的东西学了吧，所以就又在“网络流学习笔记”的后面加了个“（上）”，noip 之后一定学一定学。

：

• 0.前记
• 1.网络和流
• 2.最大流
  • 2.1 增广路
  • 2.2 FF 算法
  • 2.3 EK 算法
  • 2.4 Dinic 算法
  • 2.5 ISAP 算法
• 3.网络流常用模型
  • 3.1 二分图最大匹配
  • 3.2 最大流最小割定理
  • 3.3 二者取一式问题
  • 3.4 路径覆盖问题
• 4.费用流
  • 4.1 最小费用最大流
  • 4.2 二分图最大权完美匹配
• 5.后记

P8030 [COCI2021-2022#3] Ekoeko 题解

原题链接

题目描述

给定一个正整数 和一个由 个小写字母组成的字符串。

交换字符串的相邻两个字母视为一次操作。求使得原串的前 个小字母和后 个完全相同所需的最少操作次数。

对于这道题目，我们从部分分入手。（以下下标从 开始）

前记

备战 CSP2022-J/S，基础算法觉得没大问题，图论觉得差不多，数据结构觉得差很多但不想学，“迫不得已”复习 DP。（太基础的就没写，大多数为理论知识。）

本人学术尚浅，有问题请指出。

1.线性动态规划

线性动态规划，也就是每个状态都可以由编号比它小的点转移；作为最简单的一类动态规划，其更像是 DP 的引入，更为简单，反而不像背包、区间、树形 DP 等有较为通用的思路，更重要的是思想。LIS 问题就很好的体现了线性动态规划的思想。

P7777 『JROI-2』Shelter 题解

题目链接：P7777 『JROI-2』Shelter

省流：二分求单谷函数的谷值。

前记

蒟蒻的第二篇题解。

一般的二分和 算法其他人都已经说的很明白了，这里提供一种新的思路——不用特判，个人认为好理解，好写的二分。

提高组模拟赛二 T1,尽管做出来的人不少，但还是想要写一个证明

首先我们要知道

（曾经在 这里 写过）

不太严谨的证明：

同余&逆元&CRT学习笔记

前记

upd 2022/10/9 14:36:06 : 修改了一些错误。

upd 2022/10/17 19:36:54 : 修改了 Latex 格式。

第一篇学习笔记

之前搞了好几天，后来发现忘得差不多了，又重新温习，顺便做个笔记；涉及众多式子，如果有错请指出

考试推了半天最后没来得及写完。

应该算是半道数论了，由于是按照和升序排序，所以我们先考虑求出目标位置三个数之和为多少。

题解给出的方法是组合数学，但正经人谁写组合数学啊， 还不如写个暴力找规律

长话短说

前面不说了，后半部分就是问你一个方案数，最少用几个平台可以造出

随便试一个

当为

到每个平台的方案数为

校内模拟赛提前一个小时交代码并AK祭

没事干就直接写 T4 题解吧

写得太烂了

为什么别人写的都是

则方程有解当且仅当 。

只有我的这么奇怪

P8298 [COCI2012-2013#2] POPUST题解

贪心好题

P8298 [COCI2012-2013#2] POPUST

前记

蒟蒻第一篇题解

题目描述

Mirko 像熊一样饥饿，发现了一家当地餐馆。这家餐厅提供 顿饭，并且有一个有趣的定价政策：每顿饭都有两个指定价格， 和 。Mirko 点的第一道菜只需要付 元，其他菜都需要付 元。

Mirko 无法决定点多少菜。为了更简单地作出决定，他向你求助。对于任意 ，点 道菜最少要付的钱。Mirko 不在乎他点了哪些特别的饭菜，也不管他点菜的顺序，但他不会点两道同样的菜。