今天把Haskell的Typeclass Eq和Ord在C++中用CRTP做了个简单的实现, 写完了才想起来boost里也有类似的(更强大)实现.
Helanic Abyss
I am the answer.
Dream Control
看了Science America的一篇关于怎样控制梦的文章, 虽然很多内容大抵早就知道了, 不过还是有几条挺好玩的.
仅仅关于控制自己的梦, 大致有几点比较有意思:
- 想梦见什么, 或者想在梦中解题(梦中的想法通常没什么逻辑性, 所以也不是什么题目都合适), 方法似乎只有睡前不断想, 最好在床边放上照片或者字条什么的.
- 醒的时候不能马上起来, 否则会忘记.
- 想知道自己在做梦(lucid-dream), 方法除了睡前自我暗示(告诉自己自己可以控制梦境), 睡多点(貌似是废话)以外, 还可以在梦中做判断, 有两种判断比较奏效:
- 在梦中阅读. 梦中阅读的时候通常看不清字, 或者句子意义不明.
- 在梦中拨开关什么的, 比如灯. 在梦中通常这些开关都坏了.
- 在lucid-dream里解题很低效.
{ZJU}{3296}{Connecting the Segments}
-problem: 给你一个长度不大于50000的串, 问它最少可以由多少个回文子串拼接而成, 子串可以重叠. solution: 原串拼接反转串后构造后缀数组, RMQ预处理height数组, 再预处理出以i为首的最长回文子串长度, 然后贪心. ----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3671 ----code: https://docs.google.com/document/pub?id=1V2_nl-QEyeBW8PODGwwdVXTABTTmoineOnBo2H2gT_Q
{Ural}{1092}{Transversal}
-problem: 一个(2n+1)*(2n+1)的网格, n< =20, 里面是'+'或'-'. 每次可以同时翻转2n+1个格子, 使'+'变成'-'或者反之, 要求这2n+1个格子的行, 列都不相同. 现在要你输出翻转步骤, 使得最后'+'的数量不超过2n. solution: 贪心. 关键是如何用两次操作翻转一个矩形的4个角. ----link: http://acm.timus.ru/problem.aspx?space=1&num=1092 ----code: https://docs.google.com/document/pub?id=1sEOzqZiI9kz-qBkkSjblq9_PafP8xCg2rrhw17CKGD0
德国馆需要排4个小时的队吗?
今天去世博会. 上午10:20到的德国馆. 看见队尾的牌子上写着4小时, 心里有点凉, 但是因为决定今天一定要看德国馆的, 所以就排了.
大概过了一个大棚的时间, 感觉人流前进的速度还是挺快的, 感觉用不到2小时, 但具体要多少却说不清. 想起来前一阵子看的[编程珠玑]上的little定律, 就试着估算了一下时间.
little定律大概是这么个意思:
队列中物体的平均数量为进入速率与平均滞留时间的乘积.
我是这么估算的:
每个大棚有11根支柱, 每两根支柱之间间隔2.5m, 所以每条走道长25m.
每1m长的走道里有大概5人, 所以每条走道里有约125人. 每个大棚里有4条走道, 一共9个大棚, 加上外面的人算有10个大棚, 这样总共大概有5000人.
走完一条走道需要将近3分钟, 所以人流量0.7人/s.
根据little定律需要5000/0.7s, 大约2个小时.
事实上我们用了2小时10分钟. 于是之后我又算了一下意大利馆大概需要排40分钟, 于是就去了.
事实证明little定律还是挺靠谱的.
顺便一提, 意大利馆非常赞!
Functional Programming & Metaprogramming
用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;
};
不要理会那些晦涩的语法, 凭直觉去看就够了.
{ZJU}{2865}{A very easy task}
-problem: 高精度乘方求和(Power Sum) solution: 用Sp(n)的二重和(double series solution)展开形式. ----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1864 ----code: http://docs.google.com/document/pub?id=1tFlPaaZwzEyJpAM-0mpu0Ubd6RBuxzfy3yn2IwnhsiQ
{ZJU}{2866}{Overstaffed Company}
-problem: 一棵树n<50000节点, 每个节点上有<1000000人, 问每个节点的子节点(可以是非直接)人数比自己多的节点数量. solution: 树状数组(以人数为下标)+树形DP ----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1866 ----code: http://docs.google.com/document/pub?id=1bFekAUqaPJBXzOvU3qDokRi2n83ggHbB0SFyrwlv2O4
PIMPL & Const & Pointer
PIMPL是C++中一个古董级的隐藏实现的技巧, 通常当我们需要设计一个类而又只希望暴露它的接口时有两种选择. 一是写一个抽象类, 然后继承它; 二是使用PIMPL, 把实现塞到cpp文件里隐藏起来. 其原理在pongba的blog上有很好的阐述. 本文主要讲一下PIMPL实现过程中容易被忽略的const指针问题.
雾夜
2010年2月8号0点5分, 我走出机房, 1教一如既往地安静, 然后, 被我的脚步声打破, 然后, 雾夜, 吓到了我.
Continue Reading »