用Haskell写的快排:
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (p:xs) = left ++ p:right
where
left = qsort $ filter (<p) xs
right = qsort $ filter (>=p) xs
用C++模板写的快排:
template<class T>
struct qsort;
template<>
struct qsort<null> : null {};
template<class p, class xs>
struct qsort<list<p, xs> > {
typedef typename qsort<typename filter<less<p>, xs>::type>::type left;
typedef typename qsort<typename filter<notless<p>, xs>::type>::type right;
typedef typename concat<left, list<p, right> >::type type;
};
不要理会那些晦涩的语法, 凭直觉去看就够了.
Continue Reading »
PIMPL是C++中一个古董级的隐藏实现的技巧, 通常当我们需要设计一个类而又只希望暴露它的接口时有两种选择. 一是写一个抽象类, 然后继承它; 二是使用PIMPL, 把实现塞到cpp文件里隐藏起来. 其原理在pongba的blog上有很好的阐述. 本文主要讲一下PIMPL实现过程中容易被忽略的const指针问题.
Continue Reading »
2010年2月8号0点5分, 我走出机房, 1教一如既往地安静, 然后, 被我的脚步声打破, 然后, 雾夜, 吓到了我.
Continue Reading »
---title: [PKU][2283][Different Digits]
----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2283
----date: 2010-01-30
-problem: 给你一个数n, 要你找一个n的倍数m, 要求m中不同的数字个数k最少, 其次m要尽量小.
solution: 关键公式是a%b=(a/10)%b+(a%10)%b, 由鸽笼原理可知k的上限为2, m的位数最多为n位, 所以可以枚举k=1,2两种情况, 其中k=2时需要BFS, 并且由于这个公式, BFS状态数最多为n.
----tags: tag_r,tag_h,digit,bfs,mod,string,pigeonhole
----code: http://docs.google.com/View?id=dgtsspfh_1083fhnv5qdd
Continue Reading »
-contest: 34th ACM/ICPC Asia Regional Shanghai
----date: 20091025
----team: BlueGene
--author: Answeror
-----tag: DP,Hungary,BFS,DFS,Hash,Kruskal,字符串,数论,俄罗斯方块,字典序,完美匹配,继续增广路,最大团,欧几里德最小生成树,二分图匹配,模拟.
solution: http://docs.google.com/fileview?id=0BwxLvD9mcDNtMTBiMmExN2ItMmI0MC00YjkyLWI1NmYtOTg4NWM1ZjQ0YTY1&hl=en
Continue Reading »
---title: 日出东城, 日落西野
-----tag: 草莓100%,动漫,漫画,纯爱,理想,爱情,河下水希,御姐进行时
----link: http://comic.92wy.com/go/info_304.htm
Continue Reading »
--author: Answeror
---title: [PKU][1780][Code]
----link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1780
----date: 2009-10-16
-problem: 用0到9组成长度为n(≤6)的串可以有10^n种方法, 可以用一个长度为10^n+n-1的串来包含所有这些串, 使得每个串在这个长串中只出现一次, 方法是对于当前长串长度为n-1的后缀, 其后添加一个数, 使得此时长度为n的后缀没有在前面出现过, 重复这个步骤就可以构造出长串, 现在告诉你n, 要求你字典序输出这个长串.
solution: 栈实现的欧拉回路, 最后对结果逆序数出.
-----tag: 欧拉回路,字典序,字符串,栈
----link: http://docs.google.com/View?id=dgtsspfh_117fq5swtcn
Continue Reading »
网上转了一圈, 一般图乃至二分图最小支配集似乎没有多项式时间的方法, 不过求树的最小支配集倒是十分容易, 只要树形DP即可, 下面是两个典型的例子, 特别注意f[][1]的取值是由统计子节点sum值时是否包含dp[][0]来决定的.
Continue Reading »