Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 为了便于叙述，我们将二分图分为左边的点与右边的点来叙述。我们称二分图匹配成功的边为匹配边，称匹配成功的点为匹配点，二分图匹配数为匹配边的条数。 于是最小顶点数等于二分图匹配数。 先证明最小顶点数大于等于二分图匹配数。从反面考虑，少于二分图匹配数的顶点绝对不可能覆盖二分图，因为这些顶点无法覆盖所有的匹配点。 再证明至少存在一个数量为二分图匹配数的顶点集，可以覆盖二分图。 正面来做，我们先来找这个集合。 我们来对二分图进行染色，从右边任取一个非匹配点开始，我们沿着二分图的边走，遵循这样一种走法：“标记右边未匹配边的顶点，并从右边未匹配边的顶点出发，按照边：未匹配->匹配->未匹配…，的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边。重复上述过程，直到右边不再含有未匹配边的点。”（注意标记就是染色的意思）（注意孤立点没路走，直接染色，不要忽视）（为了让读者深入理解，笔者故意不 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 第一题P2756 飞行员配对方案问题 求二分图匹配，输出谁和谁匹配 使用反向边是否存在流量来输出路径。 第二题P2762 太空飞行计划问题 求有向图的最大权闭合子图 将正权点连接s,容量为点权,负权点连接t容量为点权绝对值,所求得的一个割将图分为两部分,我们发现所有正点权的和减去该简单割，便是与s相连的闭合图的权，因为最小割所以最大权闭合图（即给定常数c，求c-a的最大值，等价于求c减去a的最小值）。注意跑完最大流以后，与s相连的点构成的点集就是最大权闭合图。学会了使用bfs之后 的lv数组来输出路径 第三题P2764 最小路径覆盖问题 求DAG的最小路径覆盖 用原图建立一个两层的新图，如果原图中存在边i->j我 们建立的新图就有第一层的点i流到第二层的点j，最后建立超级源点流向 所有的第一层图的点，建立超级汇点，由所有第二层的图流入，用DAG的总点数减去去所求的最大流就是最小路径。 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 想必大家都知道的组合数在正整数上有：$$C_{a}^{b}=\frac{a!}{b!(a-b)!}$$ 但很少有人知道这个公式在实数领域上也是成立的： 也就是说$n!$在实数上有定义 $x!=\gamma(x+1)…\gamma(x)$为伽马函数 下面问题转移到伽马函数上面了，但是在这里我们所用到的伽马函数的性质只有这一条 $\gamma(x)=(x-1)\gamma(x-1)$ 为什么这样说呢，因为我们不需要计算$x!$，我们要算的是这个式子 $$C_{a}^{b}=\frac{a!}{b!(a-b)!}=\frac{\gamma (a+1)}{\gamma (b+1)\gamma(a-b+1)}$$ 下面给出几个简单的我们来算一下$$C_{4.5}^{3} =\frac{4.5!}{3!1.5!} =\frac{\ga ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162// 斜率优化// 对于dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式// 为简化描述我们可以只考虑min情况// 我们对式子中不同的j作差// 这里姑且用j与k表示// 不妨设k>j// 得到差f(k)-f(j)+h(i)*(g(k)-g(j))// 如果k优于j那么上式<=0// f(k)-f(j)+h(i)*(g(k)-g(j))<=0// 如果g函数满足单调，为了方便 我们假设他单调增// 则【f(k)-f(j)】/【g(k)-g(j)】<=h(i)// 斜率找到，就是最大且小于h(i)的一组相邻点的斜率，这时 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 暴力枚举因子法123456789101112131415161718192021222324252627282930313233343536//素数筛与合数分解//预处理O（sqrt(n)），询问O（sqrt（n））//调用find_ini() getfac（）const int maxn=3e6+5;int prime[maxn],prime_,not_prime[maxn]={1,1};void prime_ini(){// 素数不可能筛到longlong范围 for(int i=2; i<maxn; i++){ if(!not_prime[i])prime[prime_++]=i;//把质数收录 for(int j=0; 1ll*i*prime[j]<maxn; j++){ ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 给个n，让你构造一个$n\times n$的矩阵满足每一行每一列都是1-n的排列且对于所有的i!=j都有A[i，j]!=A[j，i] ​ 奇数很好处理，但是偶数不好搞， ​ 对于一个偶数2k ​ 我们假设构造出了k*k的矩阵B是成立的了 ​ 看这个矩阵C[i,j]=B[i,j]+k ​ C B1 ​ B2 C ​ 我们把B1沿着自己的主对角线翻转 ​ 那么现在B2与B1关于2k*2k主对角线对称 ​ 我们让B2中的1变成2，2变成3，3变成4 ​ 构造完成

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108// 最低位的1 -> x&-x// 去掉最低位的1 -> x&(x-1)// 有效数字全是1 -> (x&(x+1))==0//把最低位的0 变成1-> x|(x+1)//取出最低位的0并变成1 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 博弈常常是acm中的签到题，能不能快速拿下，这得看本事。 局面决定一切首先有以下的结论： 胜负取决于局面 如果当前局面能转移给对手的一个输的局面，那么对手就输 如果当前局面转转移给对手的全是赢的局面，那么对手就赢 依据上诉三条规则，博弈题目也可以通过模拟来实现找规律 例题1有a，b两个数字，两人轮流操作，每次可以选择两个之中较小的数字，然后另一个数字减去选择数字的任意倍数（不能减到负数），直到其中一个为0，不能操作为败。比如2，8可以转移为（2，6）（2，4）（2，2）（2，0） 题解 不妨设$a\ge 2b$ 如果局面(a%b+b,b)先手赢，则局面(a,b)先手就赢 如果局面(a%b+b,b)先手输，则a,b先手可以花样拿使得后手得到(a%b+b,b), 最后先手还是赢 对于其他a，b其实只有一种拿法，简单处理一下，细心就行了 例题2有一个从1到n的连续自然数序列，两人轮流 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 给你一个括号数组，里面有不同种类的括号，每个种类都有左右两种括号，左右括号可以结合，很多组询问，问你一个区间内括号是否匹配，1.一个空的字符串是一个合法的文档。2.如果A,B都是合法的文档，那么AB也是合法的文档。3.如果S是合法的文档，那么aSb也是合法的文档，其中a,b是同一种括号，并且a是左括号，b是右括号 用栈来模拟，对于每一个括号，我们用数组L记录当处理完这个括号（压入栈并完成当前匹配）的栈顶元素的下标，当我们判断[l,r]时之用比较L[l-1]与L[r]即可

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 对于尺取法，一般用于线性表的处理。 我们有两个指针一样的东西，l和r分别指向两个元素，l于r之间的东西就是我们尝试维护的东西。 例题1询问序列中和大于s的子串的最小长度。 题解 初始左端点为0，右端点为n-1, 长度为n-1 如果当前区间不满足，同时右移左右端点 如果当前区间满足，最小长度自减 例题2询问序列中以第k个元素为起点的长度为n的子串的前缀和的最小值大于s的最小i 题解 设立一个前缀和最小值，以及区间和，让尺子长度逐渐增大，增大到N时结束 如果当前区间最小值满足，右移右端点，更新区间和，如果区间和小于于最小值，那么当我们右移左端点时当前最小前缀和在右端点不动时永远都是整个区间和，右移左端点直到区间和大于s，迭代 例题3询问序列中与值t相差最小的子串和 题解 ​ 对前缀和排序，再尺取 ​ 如果右端点减去左端点大于t，尝试用此时的端点来更新答案，然后右移左端点，如果右端点 ...