Goodbye Bingshen UOJ 282 长度测量鸡

比赛快结束时听说uoj有比赛,抱着娱乐的心态去看了第一题,没什么思路,写了个贪心,就去ow体验无限平局的乱斗模式(ctf夺旗模式)。写了一个平方级别的贪心,尽可能的去满足刻度,不满足就输出-1,后来测了一下发现竟然水到了50分,貌似好像只有3这一个点的值我的贪心和标算算的不一样……然后多case,呵[……]

Read more

POJ2594 Treasure Exploratio 二分图匹配+floyd求闭包

题意为给你一张有向图,可以从很多点派出很多机器人,机器人可以一直顺着边走,问至少几个机器人才能遍历所有的点。

显然这是求最小路径覆盖,而且有可能有边相交的情况,所以我们先跑一遍floyd求闭包,然后在进行二分图匹配,最后输出点数-最大匹配即可。

注意处理多case情况
[crayon-[……]

Read more

匈牙利算法(二分图匹配)学习笔记

作用:进行二分图最大匹配

可以简单理解为,左面一列男生,右面一列女生,男生只会选择特定的几个女生中的一个在一起,问最多有几对男女可以在一起。

我们举个例子,比如a喜欢 c,d b只喜欢c,那么如果我们最初让a和c在一起,那么b就找不到人了,所以这时候我们要尝试看看a能不能换一个人在一起,[……]

Read more

2776 寻找代表元 匈牙利算法 二分图匹配

题面:给出n个社团的人员组成,每个社团选中间一人当社长,每人最多当一个社长,求最多选出几个社长

题解:匈牙利算法跑一下就可以了。

STLmap 学习笔记

最近尝试通过迭代器反向遍历map,然后就鬼畜了,发现自己map还有一些细节不太了解,所以来写篇博客。

MAP是什么?

MAP提供一对一的下标访问。

举一个简单的例子,加入你有用数组记录一些东西,个数很少,但是下标可能会非常大,比如10^15,所以我们此时使用传统数组是不合适的,我们[……]

Read more

FFT学习笔记

昨天参悟了一天FFT,总算是理解了,今天的莫比乌斯反演也不太懂,干脆弃疗,决定来认真水一发博客。

什么是FFT?

FFT(Fast Fourier Transformation),即为快速傅氏变换,是离散傅氏变换(DFT)的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立[……]

Read more

测试文档