在Makefile中自动生成依赖

论坛里有人写了一个用于自动生成C/C++依赖的脚本。但是他的脚本处理不同目录的源文件时会有些问题，.o 会生成在当前目录，而不是和 .cc 同一个目录。

gcc 其实有一些生成用于 Makefile 规则的选项，-M 等，说明如下：

  • -MM，忽略依赖中的系统头文件

  • -MF，指定生成的规则文件的路径

  • -MT，指定规则的目标

  • -MP，对每一个依赖创建一个 force target，典型输出：

    test.o: test.c test.h
test.h:

    没有这个选项的话是不会有 test.h: 的

Read More

用rss2email阅读feeds

很久没用rss的阅读器了，以前曾用过 emacs 的 newsticker ，不支持HTML。也用过Google Reader，打开速度太慢，而且对Pentadactyl不友好。

把feeds转成邮件来阅读

我的想法是找一款工具，把feeds转换成邮件，由本地的procmail处理（归类），然后再用mutt阅读。

Read More

用Makefile搭建博客

缘起

我几乎不会 HTML，不会使用 Perl、Python 的库，不会 PHP 和 Ruby，不懂 JavaScript，但也想搭个博客。

尝试 WordPress

首先选择的是 WordPress，基本上是照着 这篇文章 做的，在 tusooa 和 phoenixlzx 的大力帮助下，注册了个 .tk 的域名和一个免费服务器，基本上算是搭起来了。不过有些不满意的地方，最讨厌的是它不是用标记语言写的，有些繁琐。

Read More

用Expect连接无线网络

垃圾的无线网卡驱动

我的无线网卡是 Broadcom BCM57780，这个东西，Linux下的无线驱动做得非常烂。以前我用Gentoo Portage中的net-wireless/broadcom-sta，后来听 microcai 的，直接在 menuconfig 里配置。这个驱动对应的模块名称是 brcmsmac，必须编译成模块（编译进内核的话，我没成功打开无线过）。它还需要 firmware，而且路径是定死的（使用其他名称是不行的，至少我没成功）。它在 dmesg 中的信息非常简略，如果你 firmware 的路径配置错的话，每次启动有一定机率 dmesg 会提示你正确的路径（这个……）。

Read More

genkernel

第一次为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
2
3
4
5
6
Device Drivers
    Network device support
        PHY Device support and infrastructure
            [*] Drivers for Broadcom PHYs
        Ethernet (100 Mbit)
            [*] Broadcom Tigon3 support

我的framebuffer的配置：

1
emerge -av v86d
1
2
3
4
5
6
7
8
9
10
11
12
General Setup ->
    (/usr/share/v86d/initramfs) Initramfs source file(s)
Device Drivers
    <*> Connector - unified userspace <-> kernelspace linker
    Support for frame buffer devices
        [*] Enable firmware EDID
        [*] Enable Video mode handling helpers
    [ ] Enable Tile Blitting Support #选择了这一项 CONFIG_FB_CON_DECOR 选项就没有了
        [*] Userspace VESA VGA graphics support
    Console display driver support
        Framebuffer Console Support
            [*] Support for the Framebuffer Console Decorations

Awesome 3 debian menu

Awesome 3 里可以启用 debian menu，方法是新建一个带 x 属性的文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/install-menu
# this file has to be executable
# put under ~/.menu-methods
# will run by update-menus
# default generate ~/.config/awesome/menu.lua
# you need to require("menu") to use menu.debian_menu

compat="menu-1"

!include menu.h

compat="menu-2"
outputencoding= "UTF-8";

function q($s) = "\"" esc($s,"\\\"") "\"";
function s($s) = replacewith(replacewith($s,"/","_"), " ", "_");
function findicon($filename)=
       ifelsefile($filename, q($filename),
        iffile("/usr/share/pixmaps/" $filename,
                   q("/usr/share/pixmaps/" $filename)));
function x11menu()= "\t{"q(title())","q($command) ifnempty($icon, ","findicon($icon))"},\n";
function textmenu()= "\t{"q(title())", \"x-terminal-emulator -e \".."q($command) ifnempty($icon, ","findicon($icon))"},\n";

supported;
    x11= x11menu();
    text= textmenu();
endsupported;

startmenu=      s($section)" = {\n";
endmenu=        "}\n";
submenutitle=   "\t{"q(title())","s($section)"},\n";
genmenu=        "menu.lua";
rootsection=    "debian_menu";
userprefix=     "/.config/awesome/";
preoutput=      "-- automatically generated file. Do not edit (see /usr/share/doc/menu/html)\n\nmodule(\"menu\")\n\n";

放在 ~/.menu-methods下，然后运行

1
$ update-menus

这样就会在 ~/.config/awesome 下面建立 menu.lua，然后在 lua.rc 里做如下修改：

1
2
3
4
5
6
7
8
9
10
-- Load Debian menu entries
require("debian.menu")



mymainmenu = awful.menu({ items = { { "awesome", myawesomemenu, beautiful.awesome_icon },
                                    { "open terminal", terminal },
                    { "debian", debian.menu.Debian_menu.Debian }
                                  }
                        })

参考：http://awesome.naquadah.org/wiki/Awful.menu

ZJU 1638. Greedy Island 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Greedy Island
Time Limit: 5 Seconds      Memory Limit: 32768 KB
Gon and Killua are engaged in a game of Greedy Island. The goal of the game is to collect 100 spell cards distributed all over the game. A spell card has three properties: Attack, Defense and Special. The numeric value of each property is between 0 and 100. Each card can be used only ONCE. All the spell cards must be stored in the Book - the initial item of the game. The Book can store at most 50 spell cards, so Gon and Killua can have at most 100 spell cards in all. Now Gon and Killua have n spell cards, and they want to use A cards for Attack, B cards for Defense and C cards for Special uses (A + B + C <= 100). If n > A + B + C, they have to discard some cards.

They would like to know the maximum sum of the Attack value in Attack Group, Defense value in Defense Group and Special value in Special Group. If there are multiple solutions, choose the solution with the maximum sum of ALL the properties of all the cards.

Input

The first line contains an integer T (1 <= T <= 10), the number of test cases.

For each test case, the first line contains a single integer n (n <= 100,100); the next line contains three integers A, B and C (A, B, C >= 0, A + B + C <= n); the following n lines contain the Attack value, Defense value and Special value of the n spell cards.


Output

For each test case, print the maximum sum of Attack value in Attack Group, Defense value in Defense Group and Special value in Special Group, and maximum sum of ALL the properties of all the cards in one line, separated with one space.


Sample Input

2
3
1 1 1
100 0 0
0 100 0
0 0 100
4
1 1 1
12 32 44
33 48 37
37 38 33
46 79 78

Sample Output

300 300
163 429

有 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int N = 100100;
struct Card { int a, b, c, s; bool valid; } cards[N];
bool cmp_by_a(const Card &x, const Card &y) {return x.a > y.a || x.a == y.a && x.s > y.s; }
bool cmp_by_b(const Card &x, const Card &y) {return x.b > y.b || x.b == y.b && x.s > y.s; }
bool cmp_by_c(const Card &x, const Card &y) {return x.c > y.c || x.c == y.c && x.s > y.s; }

const int V = 100*3+4;
bool flag[V];
int h[V], mincost;
struct Edge {int v, c, w; Edge *next, *pair; } *e[V], pool[V*10], *pit = pool;
void insert(int u, int v, int c, int w)
{
    *pit = (Edge){v, c, w, e[u]}; e[u] = pit++;
    *pit = (Edge){u, 0, -w, e[v]}; e[v] = pit++;
    e[u]->pair = e[v];
    e[v]->pair = e[u];
}
bool relabel(int sink)
{
    int d = INT_MAX;
    for (int u = 0; u <= sink; u++) if (flag[u])
        for (Edge *it = e[u]; it; it = it->next)
            if (it->c > 0 && !flag[it->v])
                d = min(d, h[it->v]+it->w-h[u]);
    if (d == INT_MAX) return false;
    for (int u = 0; u <= sink; u++)
        if (flag[u]) h[u] += d;
    return true;
}
int augment(int u, int d, int src, int sink)
{
    if (u == sink)
        return mincost += (h[src]-h[sink])*d, d;
    flag[u] = true;
    int old = d;
    for (Edge *it = e[u]; it; it = it->next)
        if (it->c > 0 && !flag[it->v] && h[it->v]+it->w == h[u]) {
            int dd = augment(it->v, min(d, it->c), src, sink);
            it->c -= dd, it->pair->c += dd;
            if (!(d -= dd)) break;
        }
    return old-d;
}

int main()
{
    int cases, n, A, B, C;
    for (scanf("%d", &cases); cases--; ) {
        scanf("%d%d%d%d", &n, &A, &B, &C);
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", &cards[i].a, &cards[i].b, &cards[i].c);
            cards[i].s = cards[i].a+cards[i].b+cards[i].c;
            cards[i].valid = false;
        }

        nth_element(cards, cards+A+B+C, cards+n, cmp_by_a);
        for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
        nth_element(cards, cards+A+B+C, cards+n, cmp_by_b);
        for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
        nth_element(cards, cards+A+B+C, cards+n, cmp_by_c);
        for (int i = 0; i < A+B+C; i++) cards[i].valid = true;
        int nn = 0;
        for (int i = 0; i < n; i++)
            if (cards[i].valid)
                cards[nn++] = cards[i];
        n = nn;

        const int sink = 4+n, tsrc = sink+1, tsink = tsrc+1;
        pit = pool;
        memset(e, 0, sizeof(e));
        mincost = 0;
        insert(0, 1, A, 0);
        insert(0, 2, B, 0);
        insert(0, 3, C, 0);
        for (int i = 0; i < n; i++) {
            const int foo = cards[i].s;
            insert(4+i, 1, 1, cards[i].a*100000+foo); mincost -= cards[i].a*100000+foo;
            insert(4+i, 2, 1, cards[i].b*100000+foo); mincost -= cards[i].b*100000+foo;
            insert(4+i, 3, 1, cards[i].c*100000+foo); mincost -= cards[i].c*100000+foo;
            insert(tsrc, 4+i, 3, 0);
            insert(4+i, sink, 1, 0);
        }
        insert(1, tsink, n, 0);
        insert(2, tsink, n, 0);
        insert(3, tsink, n, 0);
        insert(sink, 0, INT_MAX, 0);

        memset(h, 0, sizeof(h));
        do while (memset(flag, 0, sizeof(flag)), augment(tsrc, INT_MAX, tsrc, tsink));
        while (relabel(tsink));
        do while (memset(flag, 0, sizeof(flag)), augment(0, INT_MAX, 0, sink));
        while (relabel(sink));
        printf("%d %d\n", (-mincost)/100000, (-mincost)%100000);
    }
}