最近课上老师让写一个类似 ls 命令的程序，还要求要有颜色。上网查了查，有一种方法，大概是输出一个特殊的控制字符 \033, 然后再在后面加一些其它的配置啥的。比如，如果想在一般的文字中，输出一段蓝色的文字，可以这么做：

puts("\033[0;34m这些字会是蓝色的，\033[0m而这些字是正常的。\n");

阅读全文

不知道 WH 怎么想的，在 HUST 的测试版 OJ 上 clone 了一个比赛，作为我们的周末训练竞赛题。今天中午从宿舍和两个舍友来到图书馆，浪费了一下时间，就到了 12 点半。此时，比赛开始了。

A – A Very Simple Problem

一开始，我非常自然地去看 A 题（HUST 1563）。题目中的配图光荣地挂了，我就用 Chrome 的 Inspect Element, 看到了题号，然后到稳定版的 OJ 下看原题，就好了。A 题说的是一个三维空间里，一个 a × b × c 的立方体里，有一个半径为 r 的球，其球心坐标在 (x, y, z) 处。题目保证球不会和立方体产生切割，也不会在立方体之外。然后给球一个 (u, v, w) 的初速，问你在 t 单位时间后，球心位置在哪里。其中，球的任何碰撞都是完全弹性碰撞，不会损耗任何动能，并且不计任何摩擦，任何的反弹都遵循光的反射原理。

阅读全文

其实这是一道裸的最短路问题，用来测试模板比较好。里面的 trick 是边数给在顶点数之前。

原题地址：http://poj.org/problem?id=2387

我是为了测试用堆优化了的 Dijkstra 算法，才写的这道题。代码前几次犯了一些很 naive 的错误，不过居然有的数据也能对，很神奇。最杯具的事情是，这个用堆优化过的代码，使用了大量的 STL 容器，导致运行时间达到了 235ms 之巨。瞬间感觉堆的优势就因 STL 而消失殆尽了。

阅读全文

首先声明标题只是抱怨性质的话。

今天本来是想写一个带堆优化的 Dijkstra 算法的，我不愿意自己写一个堆，所以就打算用 STL 的相应代码来实现。据我目前所知，STL 里有两种方式维护一个堆，一种是用 priority_queue, 一种是用 make_heap, push_heap, pop_heap 一类的函数。由于 priority_queue 不能实现修改堆中的 key 操作（也就是最大堆中的 Increase-key, 或者最小堆中的 Decrease-key 操作），而且封装得太紧，所以我选用了后者。

由于 Dijkstra 算法中，有一步是要找到最小 dist 的那个顶点，这一步如果用堆优化，就可以把复杂度从 n 降为 1（其主要的开销在堆的维护上，所以总复杂度是 nlogn）。但是有的时候某些已知顶点 v 的 dist 是会改变的，所以这个时候需要把堆里与 v 对应的 key 进行修改。为了修改这个元素，首先要知道这个元素的下标为几何，这个时候可以维护一个数组，其下标为 v 的元素指向堆中相应的代表 v 的元素。这个时候麻烦就来了：如果对堆进行了修改，刚才所述的数组也同样需要修改。这个时候貌似 make_heap 之类的函数也无能为力了。

阅读全文

这道题的题意是，有 1 × 2 的多米诺骨牌，中间有一条线将其分成两个 1 × 1 的小块，每个小块上可以有 0 ~ 6 的整数。现在给出 n (1 ≤ n ≤ 100) 个多米诺骨牌，你要把它们接起来，并且相邻的两个多米诺骨牌相接的小块的数字要相同。问你是否存在这样一种方法，如果存在则输出具体的方案，如果有多种方案则输出一个即可；否则输出 No solution.

原题地址：http://acm.sgu.ru/problem.php?contest=0&problem=101

阅读全文

首先惊悉功夫网将 GoDaddy 的 NS 给墙了。联想到近几天在学校的 DNS 服务器查不到自己的域名的 IP, 不禁一阵寒意。小站如此和谐，域名怎会被认证呢？后来看到月光博客里的提示，说可以把 NS 改成一些其它的免费 NS, 而不要把域名托管到国内，随后我就找了这么一家服务商。具体是什么就不说了，有软文之嫌啊。不知道以后能不能正确解析，师母已呆吧。

然后我想起博客上的回复评论以前是有 AJAX 的，现在都没发现。这是很奇怪的事情。开始以为是 WordPress 更新之后，我的老主题 out 了，不兼容了。好吧，经过各种折腾，其实不是主题的问题，而是用了 WP Minify 导致的。这个插件把各种 JavaScript 脚本和 CSS 整合成一个文件，可以加快网页读取速度。后来我在其设置页上把 comment-reply 给排除了，就好了。顺便排除了 Image Lazy Load, 这样久违的延迟载入功能又回来了。我猜出现这样的原因可能是我的某个 JavaScript 有问题，连累了其它的文件吧。

首先感慨一下，现在的动车都好谨慎。这次我们坐的动车，在近某站之前，说什么“由于停留时间较短，请不是本站下车的旅客不要外出散步”，结果“由于信号原因”，一直不敢开出，硬生生晚点了 50 分钟。然而似乎大家都很理解，没有什么抱怨，可能是因为上次事故的教训吧。

到了金华已是中午 12 点多，和叶总寒暄几句后，马上赶到浙江师范大学，那个热啊，真是符合热身赛的精神了。比赛场地是在机房，有两层，不过据说下半年的区域赛会在新建的体育馆内举行。找到位置后，两个队友过于兴奋，居然看到桌上的信封就想拿，那可是题目啊，比赛还没开始。

阅读全文

这个比赛居然有 7 题，不过既然有个 Easy 在标题上，那么肯定很多水题的。不过几场 Div 2 下来，还没有到 Div 1, 还是略挫了啊……

很有意思的是这个比赛有一部分是 host 在 Codeforces 上的，似乎官方是俄文，和 Codeforces 国籍相同啊。

我在比赛开始后半个小时才意识到注册了这个比赛。当时还在 Google Camp 里，情急之中做了 2 题，然后看了 C 题才回的宿舍。

阅读全文

曾经我写过一篇文章，说怎样在 Arch Linux 里搭建一个个人的 Git 服务器。当时我以为，在 GDM 的配置文件里写上 Exclude=git 就可以把 git 用户排除在登录界面上，其实这样是错误的。

后来我上网时发现有人说，如果把用户的 ID 改成 1000 以内的数字，就可以在 GDM 中自动隐藏这个用户。

阅读全文

最近各种项目，而且很多是小团队合作的，所以免不了要弄版本控制。最近比较主流的版本控制工具还是 Git, 所以我就打算在 Arch Linux 下搭建一个 SSH 的 Git 服务器。

服务器上搭建 Git

首先服务器上得有 Git 和 SSH Server 吧。在 Arch Linux 上安装这两个软件：

~ # pacman -S git sshd

在服务器上创建 Git 的专有账户：

~ # useradd git

再去 /etc/passwd 里把 git 账号的 /bin/bash 改成 /usr/bin/git-shell , 这样的话，别人就只能通过这个账号进行 Git 操作，而不能使用命令行。

阅读全文