当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

由于每个门只会被两个钥匙控制,那么两个钥匙的选或不选就能建立起一种对应关系。即如果门本来是开着的,那么用了一把必须用另一把,不用一把必须不用另一把;如果们本来是开着的,那么不用一把必须用另一把,用了一把必须不用另一把。

Tarjan 跑 2-SAT 随手切,注意 nm 不要搞反。

READ MORE

到这题为止网络流 24 题也快刷完了呢,还剩下几道码量特大的等着以后有空去浪费时间(逃

这题一眼最小费用最大流,一开始我想了个类似于 NOI2008 志愿者招募 之类的利用满流的方法,但是一直没有调出来。后来怂了,直接连边,最后因为有个 - 1 没有删干净还是调了老半天。orz ,我还是太菜了。

把每一天分成两个节点,一个接受干净的毛巾,一个输出用过的毛巾。直接在这两个点之间连边显然不现实,我们可以分别把这两个点和源点、汇点连边。然后再按照题目条件一一连上对应边。这样最大流肯定能够跑满,求最小费用的话就是这图的最小费用最大流了。

这告诉我们对于不清楚的知识点不要瞎用。

READ MORE

题意:

给你个 1000 \times 1000 的矩阵,每次交换任意两个不重合的子矩阵,求最后的结果

如果你是一位数据结构学傻的选手(像我),那么第一感觉肯定是用平衡树做,复杂度 O(m \times n \log n) ,不过不幸的是,由于常数巨大,最后得分甚至可能不如暴力的 memcpy

如果你是一个不会高级数据结构的普及选手你说不定就能想到链表。维护一个矩形的链表,然后每次交换就分别把两块矩阵取出再拼接上去。

READ MORE

巧妙的使用满流的特性解决问题。

对每一天,连一条容量为 INF - 需求人数 的边,对于补充的人连一条容量为 INF ,花费为价格的边。

对这个图跑最小费用最大流,其中最大流一定是 INF ,最小费用即答案。

READ MORE

黑历史警告:此处为 memset0 的黑历史,请宽容对待!

这其实是一个比赛啊啊啊啊啊!

反正考得超级辣鸡的!

这是我第一次参加ACM类的比赛,估计也是我的第一次写游记吧。 这次参加浙大校赛的,不光有他们大学生,还有各路中学生;同时,我也在队伍里面发现了小学生的踪影(就差幼儿园的了)。 整体的氛围还是比较愉快的,可能是因为三个人一起做题的关系吧,没有OI那么压抑。

这次比赛给了我们一点经验,也让我们看到了很多不足的地方(同时我现场领悟了如何数组模拟链表,thanks to fjk)

READ MORE