爱飞鱼的blog

给定一个非负整数序列 ，初始长度为 。 有 个操作，有以下两种操作类型：

多次询问两点间的瓶颈路，也就是u到v所有路径中边权的最小值最大。 Sol：考虑先将所有询问离线。考虑建立最大生成树的过程，设联通块s1和s2要被边权为w的边连通。对于存在点u在s1,v在s2的询问的答案就是w。为了保证时间复杂度我们考虑启发…

Solution：利用异或的可逆性，先算区间异或前缀和，问题转化回上题，注意处理边界，对于只有一个数的情况，直接赋初值解决 是一个序列中没有出现过的最小非负整数。 给出你一个长度为 的非负整数序列以及 个询问，每次询问先给你一个整数 ，然后…

纯数学题 对随机的数字大小分类讨论，计算概率的时候利用高中几何概型的线性规划手法进行计算。 状态：表示袋中有i只白鼠j只黑鼠时，A获胜的概率 起点： 终点： 转移： 1.先手拿到白鼠： 2.先手黑鼠，后手白鼠： 这种情况不用处理 3.先手黑…

https://www.acwing.com/problem/content/description/4012/ Acwing long double卡常，注意cin读小数。

其实这类算法更多的是解决子集和 （sum of subset） 问题，因此也叫 SOS DP。 也就是对于i从1-n我们希望求出 一个平凡的做法是直接枚举子集： 引入高维前缀和可以优化到

二分图最大匹配可以转换成网络流模型。 将源点连上左边所有点，右边所有点连上汇点，容量皆为1。原来的每条边从左往右连边，容量也皆为1，最大流即最大匹配。 如果使用 Dinic 算法 求该网络的最大流，可在O(sqrt(n) * m)求出。