缘起
我几乎不会 HTML,不会使用 Perl、Python 的库,不会 PHP 和 Ruby,不懂 JavaScript,但也想搭个博客。
尝试 WordPress
首先选择的是 WordPress,基本上是照着 这篇文章 做的,在 tusooa 和 phoenixlzx 的大力帮助下,注册了个 .tk 的域名和一个免费服务器,基本上算是搭起来了。不过有些不满意的地方,最讨厌的是它不是用标记语言写的,有些繁琐。
我的无线网卡是 Broadcom
BCM57780,这个东西,Linux下的无线驱动做得非常烂。以前我用Gentoo
Portage中的net-wireless/broadcom-sta
,后来听
microcai 的,直接在 menuconfig 里配置。这个驱动对应的模块名称是
brcmsmac,必须编译成模块(编译进内核的话,我没成功打开无线过)。它还需要
firmware,而且路径是定死的(使用其他名称是不行的,至少我没成功)。它在
dmesg 中的信息非常简略,如果你 firmware
的路径配置错的话,每次启动有一定机率 dmesg
会提示你正确的路径(这个……)。
第一次为gentoo编译内核,发现默认选项没有有线网络支持(没有eth0设备),也不管哪些选项是自己真正需要的,选了很多。恰好linux-2.6.34-gentoo
出来了,就尝试着重新配置一下。
1 | genkernel --bootloader=grub --menuconfig --no-clean all |
以前不知道要用--no-clean
,每次编译都要花很长时间,这个选项可以让genkernel
不去执行
make clean
,第二次编译花的时间就会少很多
File systems <> The Extended 4 (ext4) filesystem #我大部分分区用的是 ext4,这一项默认没有设 <> Reiserfs support #/usr/portage 下有很多目录和小文件,所以我单独挂载在一个 reiserfs 分区 -- Native language support <> Simplified Chinese charset (CP936, GB2312) <*> Traditional Chinese charset (Big5)
Executable file formats / Emulations [*] IA32 Emulation #这个好像是执行 32-bit ELF 的,否则像 firefox-bin wine 等就无法运行
我的网卡是Broadcom Corporation NetLink BCM57780 Gigabit Ethernet PCIe
1 | Device Drivers |
我的framebuffer的配置:
1 | emerge -av v86d |
1 | General Setup -> |
Awesome 3 里可以启用 debian menu,方法是新建一个带 x 属性的文件
1 | #!/usr/bin/install-menu |
放在 ~/.menu-methods下,然后运行
1 | $ update-menus |
这样就会在 ~/.config/awesome 下面建立 menu.lua,然后在 lua.rc 里做如下修改:
1 | -- Load Debian menu entries |
1 | Greedy Island |
有 n (n <= 100100) 张卡片,卡片 i 有 a_i b_i c_i 三个属性,选则不超过 A 张用于提升属性一,不超过 B 张提升属性二,不超过 C 张提升属性三,每张卡片只能用于提升一种属性。求三种属性提升值之和的最大值,若有多解,最大化 sigma(S_i),S_i = A_i + B_i + C_i。
容易构建最大费用最大流模型,但顶点数很多,需要优化。 以 (A_i, S_i) 为关键字,保留最大的 A+B+C 张卡片 以 (B_i, S_i) 为关键字,保留最大的 A+B+C 张卡片 以 (C_i, S_i) 为关键字,保留最大的 A+B+C 张卡片
1 |
|
题目大意:有一个长为 N 的整数数列,每次可以把一个数增减一,求最少次数使得有连续 K 个数相同。 下面程序用 Size balanced tree 实现,卫星数据是子树节点数和子树关键字和。
1 | #!/usr/bin/env python |
动态规划, \(F_m\)表示当前要做选择的奶牛在可以选择\(w_{m\ldots n-1}\)时可以获得的最大值。 \(S_m\)表示当前要做选择的奶牛做完\(w_{m\ldots n-1}\)的最优决策后,下一个奶牛可以取得的最大值。
1 |
|
根据USACL Analysis(后附),根据一个格子周围格子的布局,先把一些点转换为A,然后绕着A走一圈。
1 |
|
先把题目中给出的树有根化,对于一个顶点u,如果它有不超过K/2个孩子还未被分配, 可以把它们中最多2*K个在u处连接起来。如果有孤立孩子并且还未配对完K对孩子, 那么只能和u子树外的顶点配对,这相当于u是其parent的未分配顶点。
1 |
|
1 | USACO JAN10 Problem 'island' Analysis |
随机生成一个迷宫
1 | #!/usr/bin/env python |
现在知道这个算法的名称了:recursive backtracking,可以参见拙作完美迷宫生成算法
设盘子编号为
输出初始局面(所有盘子都在1号柱子)到终止局面(所有盘子都在3号柱子)的最优方案。
时间复杂度:
输出最优方案中某一局面之前经过的步骤数。 时间复杂度:
1 |
|
输出当前局面(不一定是最优解的中间步骤)到终止局面的最优方案。
时间复杂度:
1 |
|
输出当前局面下,把所有盘子移动到任一根柱子的最优方案。 时间复杂度:Ο(2^N)
1 |
|
输出当前局面下,把所有盘子移动到任一根柱子的最优方案所需步数。
时间复杂度:
易知,必定把
注意到如果
之所以要移动
1 | #include <stdio.h> |
总结一下,对于求方案的问题,因为最坏情况下步骤数可以达到
对于求步骤数(无须输出方案),以上源码时间复杂度都是