「学习笔记」网络流 点击查看目录 目录 「学习笔记」网络流 知识点 一些基础定义 最大流 Ford-Fulkerson算法（增广路算法） Edmonds-Karp算法 Dinic算法 最小割 费用流 EK费用流 ZKW费用流 例题 [SCOI2007]蜥蜴 [SDOI2015]星际战争 士兵占领 [HNOI2007]紧急疏散EVACUATE [SDOI2009]晨跑 [SDOI2016]数字配对 [SCOI2007]修车 [NOI2012]美食节 [AHOI2009]最小割 定义部分名词括号内写个英文是为了方便起函数名变量名。 \rvalue/\rv...

「学习笔记」组合计数与中国剩余定理 点击查看目录 目录 「学习笔记」组合计数与中国剩余定理 知识点 排列 错排列 组合数 式子 一些性质 卢卡斯定理 谔项式定理 谔项式反演 形式零 形式一 形式谔 小技巧：线性推阶乘逆元 中国剩余定理（CRT） 做法 证明 EXCRT ExLucas 问题 拆为CRT 构造余数 构造函数 代码 例题 排列组合 排队 题意 思路 Code Combination 思路 Code [SDOI2016]排列计数 思路 代码 [ZJOI2010]排列计数 思路 代码 BZOJ2839集合计数 思路 代码 牡牛...

「解题报告」[POI2008]PER-Permutation 点击查看目录 目录 「解题报告」[POI2008]PER-Permutation 思路 代码 不理解哪里难了，学过扩卢并且推一下式子基本就是两眼切吧。 个人感觉顶多上位紫。 思路 首先设\(f_i\)表示前\(i-1\)位固定，第\(i\)位选一个比原来小的，后面随便排的方案数。 显然\((\sum_{i=1}^{n}f_i)+1\)为答案，那么考虑如何快速求出\(f_i\)。 考虑用“交换”的思想，即在后\(n-i\)个数中找到比\(a_i\)小的数和它换一下，然后再随便排。 然而这里是可重集，所以还要...

「杂题乱写」AtCoderDP26题 \(\text{AtCoderDP26}\)题题单。 前言 最近听说\(\text{AtCoder}\)上有个\(\text{DP26}\)题挺好的，于是向@\(\text{SoyTony}\)要了题单并开始做，希望可以加强我的DP能力。 果然我还是爱DP的。 预计暑假集训结束前正好做完，希望能完成这个\(\text{flag}\)。 开头的题比较简单，就不写太多了。 2022/08/11。 寒假开始前做完还差不多 其实就剩三个题了，但咕了四个月。 2022/12/25 一年之内居然做完了😅 2023/05/13 正文 A:Frog1 思路 ...

「闲话随笔」势能分析法 点击查看目录 目录 「闲话随笔」势能分析法 简介 分析 例题 二进制计数器 单调栈 Splay 这闲话已经被催了两天了，累死我了。 感谢joke3579帮我找到了Tarjan的论文。虽然没看懂只截了一下里面的图。 语文考了82，需要单独给语文老师发作业，很闹心。 今日推歌：盲龙默虎feat.洛天依vs言和。 iKz老师的《一年一度武斗大赛》系列是不是快要更了？ 简介 一种挺神奇的分析时间复杂度的方法。 一个算法/数据结构单次操作的复杂度难以计算时可以用势能分析法。 分析 设第\(i\)次操作的时间复杂度为\(a_i\)，显然总复杂度为\(...

「学习笔记」平衡树基础：Splay和Treap 点击查看目录 目录 「学习笔记」平衡树基础：Splay和Treap 知识点 平衡树概述 Splay 旋转操作 Splay操作 插入\(x\) 查询排名为\(k\)的数 查询\(x\)的排名 查询\(x\)的前驱 查询\(x\)的后继 删除\(x\) 代码 替罪羊树 Treap FHQ_Treap 树套树 平衡树的区间操作 例题 P3391文艺平衡树 思路 P4036[JSOI2008]火星人 思路 P4309[TJOI2013]最长上升子序列 思路 星系探索 思路 代码 知识点 平衡树概述 ...

「学习笔记」二分图 点击查看目录 目录 「学习笔记」二分图 知识点 定义及判定 二分图最大匹配 二分图最小点覆盖 二分图最大独立集 例题 P7368[USACO05NOV]AsteroidsG 思路 P2319[HNOI2006]超级英雄 思路 WaySelection 题意 思路 文理分班 题意 思路 放置机器人 题意 思路 猫和狗 题意 思路 「重要提醒」：学过网络流后你会发现这玩意很不重要，唯一需要了解的就是其定义。 知识点 定义及判定 定义：存在一种方案把点分为两个集合，使得同一个集合内的点没有连边的图。 比如这张图（byOI...

「学习笔记」数位DP 意义不大的题不写了。 点击查看目录 目录 「学习笔记」数位DP 概述 例题 P2657[SCOI2009]windy数 思路 代码 P4317花神的数论题 思路 P4124[CQOI2016]手机号码 思路 代码 haha数 题意 思路 代码 0和1的熟练 题意 思路 代码 苍与红的试炼 题意 思路 代码 概述 数位DP一般用来解决「在一个较大的区间内统计具有一定特征的数的数量」的问题。 数位DP一般有两种做法： 递推法：首先需要预处理出具有一定条件的数的个数，然后将上限按数位拆分开来考虑贡献。 暴搜法：直接记忆化...

「学习笔记」BSGS 点击查看目录 目录 「学习笔记」BSGS Baby-stepGiant-step 问题 算法 例题 DiscreteLogging 代码 P3306[SDOI2013]随机数生成器 思路 P2485[SDOI2011]计算器 思路 Matrix 思路 代码 Baby-stepGiant-step 问题 在\(O(\sqrt{p})\)的时间内求解 \[a^x\equivb\pmodp\] 其中\(a\perpp\)，方程的解\(x\)满足\(0\lex<p\)。 算法 首先根据费马小定理\(a^{p-1}\...

「学习笔记」AC自动机 点击查看目录 目录 「学习笔记」AC自动机 算法 问题 思路 代码 例题 KeywordsSearch 玄武密码 单词 病毒 最短母串 文本生成器 背单词 密码 禁忌 前置：「学习笔记」字符串基础：Hash，KMP与Trie。 好像对例题的讲解越来越抽象了？ 算法 问题 求\(n\)个单词在一个长度为\(m\)的文章里出现过多少个。 思路 很多文章都说这玩意是Trie树+KMP，我觉得确实可以这样理解但是不完全一样。 KMP有两种理解方式：求Border或失配指针，AC自动机用的是「失配指针」这个理解方式。 KMP的失配指针指向的是一...

「杂题乱写」ABC293ABC295 点击查看目录 目录 「杂题乱写」ABC293ABC295 ABC293 D|TyingRope E|GeometricProgression F|ZeroorOne G|TripleIndex Ex|OptimalPathDecomposition ABC294 D|Bank E|2xNGrid F|SugarWater2 G|DistanceQueriesonaTree ABC295 D|ThreeDaysAgo E|KthNumber F|substr=S G|MinimumReachableCity 这个ABC...

「学习笔记」莫比乌斯反演 点击查看目录 目录 「学习笔记」莫比乌斯反演 前置知识 整除分块 积性函数 线性筛任意积性函数 莫比乌斯反演 莫比乌斯函数 莫比乌斯反演公式 例题 [HAOI2011]Problemb YY的GCD [SDOI2014]数表 DZYLovesMath [SDOI2015]约数个数和 [SDOI2017]数字表格 于神之怒加强版 [国家集训队]Crash的数字表格/JZPTAB [湖北省队互测2014]一个人的数论 前置知识 整除分块 考虑快速求： \[\sum_{i=1}^{n}\left\lfloor\dfrac{n}{i...