一年没写代码了，这周又开始拿起我那二把刀，开始切题了……
看到我们的小妹妹写了积木城堡这个题，于是我也从这题开始了……
简单的 0/1 背包，渐进时间复杂度（大概）是 O(N*n*n)，渐进空间复杂度（大概）是 O(N*n*n)，其中 N 为城堡数量， n 为组成每个城堡的积木数。
这题有着 Vijos 的一贯传统，就是题目描述令人 confused，就这题来说，从中间抽取积木还能使城堡不倒，不得不说是有一定功力，抽出的积木就扔在一边，不能不说是浪费。其实这都可以在题目中说清楚的。
开始做，一开始用了 bitset （在 NOIP 中允许使用），结果 TLE ；后来优化了读入，还是 TLE，后来砍掉了 bitset ，用 boolean array，提交无数次后（Vijos 最近服务器有问题，运行程序忽快忽慢，随机 TLE 的现象时有发生），终于 AC 了。
代码可以看这里，其他 vijos 的代码也在那里。
事实证明， bitset 的效率并不高，竞赛的时候应远离 bitset …… （这也可能跟 Vijos 所用编译器的实现有关）
Tags:
algorithm,
C++,
OI,
Vijos
Related Posts
为了启动的时候能更快一点，我把要加载的模块直接写进了 /etc/rc.conf （方法看这里），启动确实快了。不过有的时候还是有些郁闷……
很少用 USB flash drive，偶尔用，郁闷了，怎么看也没这个设备，只有两块硬盘，很久之后发现没加载模块，于是加载之：
又过了很长时间，用到打印机。很少打印东西，而且这个打印机比较难搞，所以导致我每次用打印机都心惊肉跳……这回直接找不到打印机了，良久之后，发现应该加载一个模块……
唉……
注意下，如果你用 2.4 内核的话，应该加载 printer 这个模块，详细的可以看 ArchWiki 的说明。
启动是快了，可是要记得加载模块啊……
提醒下自己，下次别忘了。
Tags:
Linux,
module,
printer,
USB
Related Posts
关于 ibus 的新闻已经不少了，鉴于我也忍不了 SCIM 和 fcitx 了，所以准备投靠 ibus 。这次是在 Archlinux 上安装的，先写 PKGBUILD ，装好之后没有引擎……晕菜……
然后扔掉包直接装， OK 了，最后改了一下 PKGBUILD ，也 OK 了。
PKGBUILD 仅仅是到了能用的程度。
用了一下，感觉起码比 SCIM 和 fcitx 都要漂亮，至于 bug ，我就打了这么几个字，还没找出什么来，看起来不错。
这个是 ibus-git 的 PKGBUILD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #Contributor: leafduo<leafduo@gmail.com>
pkgname=ibus-git
pkgver=git
pkgrel=1
pkgdesc="a next generation input framework."
arch=('i686' 'x86_64')
license=('GPL')
depends=('python' 'dbus-python>=0.83.0' 'automake' 'autoconf')
makedepends=('git')
url="http://code.google.com/p/ibus/"
source=()
md5sum=()
install=ibus.install
build() {
cd $startdir/src
git clone git://github.com/phuang/ibus.git ibus
cd ibus
./autogen.sh --prefix=/usr
make || return 1
make DESTDIR=$pkgdir install || return 1
} |
对应的 ibus.install
1
2
3
4
5
6
7
8
9
10
11
| post_install() {
/usr/bin/gtk-query-immodules-2.0 > /etc/gtk-2.0/gtk.immodules
}
post_upgrade() {
/usr/bin/gtk-query-immodules-2.0 > /etc/gtk-2.0/gtk.immodules
}
post_remove() {
/usr/bin/gtk-query-immodules-2.0 > /etc/gtk-2.0/gtk.immodules
} |
ibus-pinyin-git 的 PKGBUILD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #Contributor: leafduo<leafduo@gmail.com>
pkgname=ibus-pinyin-git
pkgver=git
pkgrel=1
pkgdesc="pinyin input method for ibus"
arch=('i686' 'x86_64')
license=('GPL')
depends=('python' 'dbus-python>=0.83.0' 'automake' 'autoconf' 'ibus-git')
makedepends=('git')
url="http://code.google.com/p/ibus/"
source=()
md5sum=()
build() {
cd $startdir/src
git clone git://github.com/phuang/ibus-pinyin.git ibus-pinyin
cd ibus-pinyin
./autogen.sh --prefix=/usr
make || return 1
make DESTDIR=$pkgdir install || return 1
} |
当然，你可以在这里找到我所有的 PKGBUILD。
Tags:
Arch,
Archlinux,
ibus,
IME,
Linux,
PKGBUILD
Related Posts
小小学习了一下 LaTeX ，于是找个东西小试牛刀，来证明一下二项式定理吧，用数学归纳法证明的。
具体的大家看下面的附件吧：
二项式定理的证明
TeX 源文件
同样，还是请大家提提意见，拍拍砖，非常感谢。
P.S. 这里有我收集的一些关于 LaTeX 的资料。
Tags:
LaTeX,
Linux,
Tex,
typesetting,
XeLaTex
Related Posts
家长放假，非得出去玩，于是去了……
7号下午到的北京，三个多小时的动车还不错，不过北京南站实在是太绕了，在里面怎么也出不来啊……北京南站其实还没修好，好多东西还没有……
晚上跑王府井去了，其实也不过是那样，去一次并没有什么，也就是些卖东西的，不过要是住在那边的话还是比较方便。卖什么的都有，书、食品、茶叶、手表 etc. 那个外文书店的中文也不知道是谁写的，让我看成“外交书店”……看到下面的英文才知道，哦，原来是外文书店……那天晚上中国队踢球，踢的怎么样就不说了，不过球迷还真是热情，大屏幕下面围了一堆，每个大屏幕下面还有警车，呵呵。乱七八糟地买了点东西，然后撤退了。
第二天坐火车去承德，这车可真够慢的，花的时间比从济南到北京还长，还过一堆隧道……清朝那些人也不嫌累……
其实那里也热，不过比北京要好些。承德的出租貌似都很少开空调。街面上有点乱，不过宾馆饭店之类的还挺好。
下午去避暑山庄，皇帝办公和住的地方跟故宫差不了多少，布局基本上是一样的，当然面积貌似要小些。这里有承认《中俄瑷珲条约》、签订《北京条约》的地方……
后面山区里还有大片的林子，不容易啊。里面还有鹿，据说是野鹿，还不少呢。之后去划船，然后就走了。
清朝的皇帝真能享受，挑这么个有山有水的地方，奢侈啊……
吃饭，看奥运会开幕式，我觉得演出还不错，不过点火没什么意思，要是原先设计的凤凰点火的话，我觉得还不错。这次开幕式的技术实在是 awesome ，大家可以了解一下。
另外，我们可爱的 Windows 又不负众望地蓝屏了（李宁手持火炬飞越蓝屏！），真的是非常成功。这次用的操作系统是 Windows XP embedded ，硬件支持是联想，是谁的问题啊？
承德这地方，避暑山庄比市区大得多……所以，第三天也就没什么地方了，也就是有个外八庙。
对宗教没什么兴趣，就是去看看。先去的普宁寺（大佛寺），那个佛据说是同类中最大的。然后去普陀宗乘之庙（布达拉宫），就是台阶多，累人。
下午坐火车走人，在北京转车回济南，到济南快十一点了……
下次去的时候看看 Apple Store & BUAA 。
最后，上照片：
Tags:
life,
travel,
windows
Related Posts
