對酒當歌,人生幾何? 譬如朝露,去日苦多

二分图再次学习

第一步开始学习二分图需掌握。1.增广路径是什么?其实二分图就是找增广路径,每找到一条增广路径,ans++。所以要弄清增广路径是什么。2.掌握匈牙利算法。匈牙利算法就是找增广路径的,所以掌握后就算真正学会二分图。困惑:1.无向二分图?有向二分图?无向二分图:比如u跟v是增广路,由于每个点都跑了一次,那么u-v和v-u都找了一次,那么无向二分图最后找的是最大匹配点。有向二分图:如果有这样三个点,a到b,b到c。那么找的时候肯定会找两次,最后是match[b]=a,match[c]=b。所以相当于找了一条路(a->b->c)上边数。第二步二分图最小路径覆盖目的:找出最少路径数覆盖所有点。(什么样的路径由题目定义)无向图:单纯的找出最少路径数覆盖所有点的话。结论:ans=n-二分图最大匹配/2。想一下无向图最大二分图匹配找出了最多匹配了多少点,那覆盖这些点只需(二分图最大匹配/2)个点,其他点都需要一条边,所以是其他点需要(n-二分图最大匹配)个点,相加得出结果。有向图:如果一个士兵在u点,他能顺路一直走下去,但不能回走,问需要多少个这样的士兵。结论:ans=n-二分图最大匹...

感慨

看上一次的博客好像是3.5号,好久没更新了,好像一直在准备省赛,一直在做题,感觉自己其实还是偷懒的时候多,比如现在,本来应该刷题,但是却在感慨最近发生的事。过年的时候有两个愿望,但是一个却都没有实现,现在也是倍感无聊,想不到星期天做什么比较好,打王者(玩够了,不想在玩了),吃鸡(头晕,难受,还是想好好休息一下),出去看个电影(没有人陪,实在是尴尬)。。。所以我周日就没事干了。应该就是洗洗衣服,看看娱乐节目,然后领个快递就结束明天的日程了吧!最近在回味《龙族》,看1的时候,刚开始看得实在是孤独,最后被诺诺接走,应该算是他人生的救世主吧!看第三部,奔这绘梨衣去的,也需是回味自己对XX的向往吧,但是我已不是那个小孩子了,那样的人世界上是不会有的,每个人都有自己的苦衷,而且不会那么单纯,但是看完路明非和绘梨衣相处的6天后,我还是沉默了,深深陷入对绘梨衣的向往,与对路明非的羡慕与不甘吧!(那明天就看龙族2吧!)最近的生活就是这样,已经不像上个学期那样喜欢搞博客了,而且内容质量不是很高,也需以后就会消失吧!

java环境配置

优质博客:https://www.cnblogs.com/liu-en-ci/p/6743106.html一步一步来,看清字义,就会明白。

冰菓

看这部番的缘由是因为听了Lex的推荐吧,听说是刀剑神域同期作品,却没有打过刀剑神域。看完之后真是为《冰菓》惋惜啊!喜欢这部番的缘由,是没有的,就像喜欢一个人一样,不需要什么理由,就是有感觉,内心不能平静。硬要说的话。这部番是2012年制作的,但是放在现在来看,画面的质量依然胜过大多数动漫。我也从这个动漫体会到了青春的气息。男主折木的性格真的有意思。女主超级萌!实在是无法用语言来形容啦!就是内心激动久久不能平静!

扩展KMP

优质博客推荐问题描述:母串S,子串T,求S[i]~S[n-1] (0<=i<n) ,与T的最长公共前缀extend[i]。求解需要next数组辅助,next[i]表示next[i]~next[m-1]与next[0]~next[m-1]的最长公共前缀。我们直接讨论在中间时匹配的情况。已知:1.假如我们extend已经求到了k,该求k+1了。2.位置p代表extend[0,k]能匹配到的最远的位置,并且设取这个最大值的位置为po。3.next数组已知,next[k+1]=len。求extend数组一。k+len<p如上图此时extend[k+1]=next[k+1]=len;S[k+len+1]不会等于T[len],如果它们相等,那么就表示T[k+len-1-po]==T[len],那么next[k+1]=len+1,冲突,那么错误。二。k+len>=p因为我们最远才匹配到p,所以S[p+1]以后的字符和T[p-k]以后的字符一一开始匹配,直到失配为止。如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。然后求extend就结束了,而求n...