匈牙利算法是二分图匹配的一个简单算法. 算法的实现方式: 1.遍历左部点,观察是不是存在这个点所连的增广路劲,假如存在ans++.2.找增广路径,判断其是否为自己相连的点,假如是假如这个点还没被连接或是这个点可以让原来连接它的点寻找新的连接点的话,我们就连接它.然后找到即结束. 证明: 采用反证法,假如说还有一条边可以连接.那么它的连接方式无法两种,一种是直接连接(显然是不可能存在这种情况的.),第二种是间接连接,那么就和我说的找增广路径矛盾,至此就证明了,当前匹配一定是最大匹配. 代码: #include <bits/stdc++.h> using namespace std; ...

每天都好困，我今天要早睡早起，虽然才刚醒。

思路: 做这种题,第一步就是搞清楚题目要干什么,其实这个题目就是判断一个式子是否成立： 我们观察可以发现,每次都只有第一项不一定是的倍数,其他一定是的倍数.那么每次我们都判断下,然后将.然后一直处理到即可,假如中途不成立,那么输出,否则就是.当然还有个值得注意的地方就是你代码应该先检测-1,再检测1.比如说你m=1,你检测-1/+1都是可以的,但是你先+1的话,就会死循环. 代码: #include <bits/stdc++.h> using namespace std; int main() { int w,m; cin>>w>>m; while(m) {...

思路: 首先我们知道最大连续子序列的和的dp方程是:.这题要我们求使得某一度乘以,然后求.一个显然的暴力是左边求一次最大连续子序列,右边求一次最大连续子序列,然后中间乘以.但是这样的时间复杂度是的,显然不可取.那我们换种思路直接线性dp.令表示到了第几个数,状态是哪个.这里我们设立三个状态::表示以结尾且未使用的的.表示以结尾的.表示以结尾且考虑了情况的.然后答案就是对三种状态取个.那么三种状态的转移方程如下: . . . 时间复杂度就降到了. 代码: #include <iostream> using namespace std; typedef long long ll; co...

1900:1.Beautiful Array .2.Vanya and Scales .3.Train Hard, Win Easy .4.Classy Numbers .5.Dima and Salad .6.Generating Sets .7.Stars Drawing (Hard Edition) .8.Chladni Figure.9.Spy Syndrome 2 .10.Subsequences (hard version) . 2000:1.Relay Race .2.PLEASE .3.Coprime Subsequences .4.Work Group .5.Microtra...

打atcoder去了,这里留坑,会补完的(好像都是会的算法)!

不会构造... 思路: 我们先将图进行黑白染色,然后将白点的最高位和第id位设置为0,其余为1,保证白点相互之间不连通,然后黑色点将其最高位设置为1,其它和白色相邻的点设置成1.然后因为中间缺了些1,黑色点也是不连通的,然后这样构造就保证了黑色点只与相邻的白色点相连. 代码: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e2+5,M=2; vector<int>g[N],x[M]; ll w[N],pos[N]; void dfs(int u,int f...

#我的最爱歌单#

前言: 思维不够,看到这种陌生的题目无从下手. 思路: 这题应该做过一次的人会觉得它其实并不难.主要思想:把边权->点权.这样做的好处是,无论你怎么分配点权,在环内的异或值一定为(前提是环内的一定合法.)做题步骤也是围绕这些性质来的.1.首先判断给定的点是否有矛盾,就是你给一个点赋值,它假如是环的话,有矛盾,那么它的异或值为.然后你这个点的异或值会和你之前给定它的异或值不同.2.找有多少联通块,不同的联通块是独立事件,用乘法原理.然后点权的设置,其实本身存在重复,就是你把所有点取反和不取反,这两种情况的边权是一样的.然后本身没有限制,假设联通块大小是,那么就是.去除重复就是.3.考虑限制...

前言: emmm,不单单只是水贴吧,也分享下某些东西...自己觉得挺有用的,虽然自己本身也只是个大二蒟蒻. 听课: 我本身是那种特别没耐心的那种人,老师讲课,我总是和旁边的同学聊天,导致emmm.所以很多时候我都没有那份专注度,当然我打代码的时候还是有的.以前很多帖子都推介大雪菜(Y总),他讲的确实挺好的.但是我疫情期间的后几个月一直跟他学习的,也学到了许多(尤其是stl的用法.)以前看到set就头晕.也写了很多题,算法进阶指南刷了200多个吧(大多是看他题解和视频写的.)我是一个很害怕bug的人,然后y总的代码其实都比较好懂.然后尤其是写某些题,比如数独2啊,之类的...要我写我肯定害怕.然...

直接dp即可. #include <bits/stdc++.h> using namespace std; const int N=2e3,M=12; double f[N][M];//第i个人在第j轮生出的概率. double F[N][N];//第i名战胜第j名的概率. int main() { int n,m; scanf("%d%d",&n,&m); int K=(1<<n); for(int i=1;i<=K;i++) for(int j=1;j<=K;j++) { int x;scanf("%d&qu...

小时候过年对我来说是一件兴奋的事情，因为那段时间我可以获得短暂的富裕且自由的生活。记得那个时候最开心的还是小伙伴们都有钱了，然后就一起去网吧打cf(不是codeforces)。然后买几包槟榔，几桶泡面，饮料不亦乐乎的吃吃喝喝玩玩，然后回家就在路边放雷王之类的鞭炮。怀恋i！

前言: lpt太菜了,打算学完树上的算法(差不多所有吧)和二分图(基本所有),然后多项式(模板),然后寒假就结束,然而这对lpt来说也是一件困难的事呢.毕竟还有比赛补题,和一些杂七杂八的事和题. 题单: 二分图

前言: 很久很久以前就看到这个题目.记得这题应该是小乔出的.当时我队友来问我,我跟他讲了一下35分的做法.因为那个时候太菜了,不会容斥原理. 思路: 这题前面1000个数据直接dp即可.后面1e5,直接组合数预处理+容斥原理即可. 代码: #include <bits/stdc++.h> using namespace std; const int N=2e5+5,M=1e3+5,P=5; const int mod=998244353; typedef long long ll; ll dp[M][M]; ll f[N],ivf[N]; ll ans[P]; bool mp[M]...