日志 - r_64的博客

(*c),d=2//len('''
;/*)var a,b:longint;begin read(a,b);writeln(a+b) end.*/
#include <stdio.h>
a,b;main(){scanf("%d%d",&a,&b);printf("%d",a+b);return 0;}
/*'''),3
print(sum(map(int,input().split())))
#*/

见我的submission。C，Pascal，Python。

老年退役狗不务正业
阅读全文

Hack狂魔养成记(雾)

2016-04-28 18:35:13 By r_64

打个广告

(就是写了个脚本扒程序。。感觉好暴力啊。。

upd

欢迎热爱hack的同学来加强uoj的数据! ~~(其实就是：玩了一天就玩腻了。。不准备再玩了。。)~~

这是我第一次玩github。。

阅读全文

CTSC2008 river

2015-07-27 11:38:42 By r_64

先回顾一下题目吧，给定一个$n$个元素的偏序集(就当是DAG的传递闭包)，求：

1)最长反链的长度；

2)一个最长反链；

3)哪些元素可能在最长反链中。

很久以前看到这个题的时候我还没有意识到它就是dilworth定理。。。然后看着题解做了第一问。觉得“第二问好像很水的样子，随便构造就出来了”，可是试了很多种方案都没有构造出来。百度上搜到的blog都是“bzoj上只有第一问的数据，那么我就只做第一问吧”，然后问了一些同学他们也不知道第二问怎么做的样子。某天膜了一下vfk的博客，发现了dilworth定理的一个证明，可惜不是构造性的(就是我不能看着这个证明就构造处一个最长反链)。

最近几天搜到了一个网页。

我就抄袭一下这个上面的内容，顺便orz回答这个问题的大爷。。。

回忆一下最小链覆盖的求法。令$n$为偏序集的点数，建立一个二分图，$X$部的$i$号点用$x(i)$表示，$Y$部的$i$号点用$y(i)$表示。对于偏序集中的一条关系$u < v$，在$x(u)$与$y(v)$之间连边。令$m$为二分图的最大匹配的大小。则答案为$n-m$。

构出了二分图之后我们可以构出其最大独立集$I$(怎么构的话英文wiki和上面的网页上都有吧)。对于一个$1\le i\le n$，如果$x(i)\in I$且$y(i)\in I$，那么将$i$加入我们的反链$A$。

首先我们证明$A$的确是个反链。否则的话假设$u\in A,v\in A,u < v$。那么应该存在$x(u)$到$y(v)$的边。而$x(u),y(v)$却是在同一个独立集中的。所以产生矛盾，$A$是反链。

然后我们证明这个反链的大小至少为$n-m$。把独立集中的点称作黑点，其他点称作白点。那么黑点的数目是$2n-m$。而黑点的数目=$|A|$+(满足$x(i)\in I$或$y(i)\in I$的$i$的数目)，后者不会超过$n$，则前者至少是$n-m$。

这样！我们构造出了一个大小至少是$n-m$的反链！然后最小链覆盖的大小就是$n-m$，反链的大小不会超过它，所以这个反链的大小就是$n-m$，且是我们要求的最大反链。

鼓掌熊