Leaf Duo

一年没写代码了，这周又开始拿起我那二把刀，开始切题了……
看到我们的小妹妹写了积木城堡这个题，于是我也从这题开始了……
简单的 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

[OI][Vijos 1214]伤心的AsukaNoKaze (3)
[OI][Vijos 1107]环游大同 80 天 (2)
NOIP2007 完结 (11)
clock() in C++ (0)
看看我的计算机 (1)

关于 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
[...]