checker 

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#!/usr/bin/env python
#
#   Copyright (C) 2010, 2011 MaskRay
#
#   This program is free software: you can redistribute it and/or modify
#   it under the terms of the GNU General Public License as published by
#   the Free Software Foundation, either version 3 of the License, or
#   (at your option) any later version.
#
#   This program is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU General Public License for more details.
#
#   You should have received a copy of the GNU General Public License
#   along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
#   ------------------------------------------------------------------------------
#
#   checker
#           check programs using testdata

COPYING = '''checker
Copyright (C) 2010, 2011 MaskRay
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
'''

def rreplace(s1, s2, s3):
    p = s1.rfind(s2)
    return s1[:p] + s3 + s1[p+len(s2):] if p != -1 else s1

def test(s, pat1, pat2):
    p = s.find(pat1)
    if p == -1:
        return False
    q = s.find(pat2)
    while q != -1:
        if not p <= q < p+len(pat1):
            return True
        q = s.find(pat2, q+len(pat2))
    return False

if __name__ == '__main__':

    import math, sys, os, re, subprocess, threading, time, tempfile
    from optparse import OptionParser

    def main():

        def print_copying():
            sys.stdout.write(COPYING)
            exit(0)

        usage = '''usage: %prog source [input] [output]
        source  - source file
        input   - suffix of input files (default `in')
        output  - suffix of output files (default `out')'''
        parser = OptionParser(usage=usage)
        parser.add_option('-p', '--path', action='store',
                          dest='path', default='/tmp',
                          help='specify the path of testdata')
        parser.add_option('-i', '--dataid', action='store',
                          dest='dataid', default='', help='specify the data id')
        parser.add_option('-d', '--detail', action='store_true',
                          dest='show_detail', default=False, help='show details')
        parser.add_option('-s', '--showtime', action='store_true',
                          dest='show_time', default=False, help='show time used')
        parser.add_option('-t', '--time-limit', action='store', type='float',
                          dest='time_limit', default=1.)
        parser.add_option('--version', action="callback",
                          callback=lambda o, s, v, p: print_copying(),
                          help="print the COPYING and exit")
        (options, args) = parser.parse_args()

        options.path = os.path.expanduser(options.path)
        if len(args) < 1 or len(args) > 4:
            parser.print_usage()
            sys.exit(1)
        if len(args) < 2:
            args.append('in')
        if len(args) < 3:
            args.append('out')
        r = re.compile('\d+')

        L = [file for file in os.listdir(options.path) if test(file, args[0], args[1])]
        for file in sorted(L, key = lambda x: int(r.findall(x)[-1] if
            r.findall(x) else sys.maxint)):
            if options.dataid != '' and (not r.findall(file) or
                    r.findall(file)[-1] != options.dataid):
                continue
            print('---' + file + '---')

            temp = tempfile.NamedTemporaryFile()
            sub = subprocess.Popen('./main', stdin=open(os.path.join(options.path, file)), stdout=temp)
            bgn = time.time()
            timer = threading.Timer(options.time_limit, sub.terminate)
            timer.start()
            ret = sub.wait()
            end = time.time()
            timer.cancel()

            RESET = '\033[0m'
            if ret == -11:
                print('\033[1;34m' + 'runtime error' + RESET)
            elif ret == -15:
                print('\033[1;35m' + 'time limit exceed' + RESET)
            elif ret == 0:
                sys.stdout.write('\033[1m')
                sys.stdout.flush()
                with open(os.path.join(options.path, rreplace(file, args[1], args[2]))) as f:
                    lines = f.readlines()

                if len(lines) == 1 and re.search('''\d+\.\d+''', lines[0]):
                    res = float(lines[0])
                    with open(temp.name) as f:
                        lines = f.readlines()
                    if len(lines) != 1:
                        print('wrong answer' + RESET)
                    elif math.isnan(float(lines[0])) or abs(float(lines[0])-res) > 1e-9:
                        print('< %f\n---\n> %f\n' % (res, float(lines[0])) + RESET)
                elif 0 == os.system('diff --strip-trailing-cr %s %s %s' %
                                  ('' if options.show_detail else '-q',
                                   os.path.join(options.path, rreplace(file, args[1], args[2])),
                                   temp.name)) and options.show_time:
                    print(RESET + '%.3f second(s)' % (end-bgn))
                else:
                    sys.stdout.write(RESET)
                    sys.stdout.flush()
            else:
                print('\033[1;32m' + 'exit abnormally' + RESET)

    main()

USACO JAN10 Gold

hayturn

動態規劃， \(F_m\)表示當前要做選擇的奶牛在可以選擇\(w_{m\ldots n-1}\)時可以獲得的最大值。 \(S_m\)表示當前要做選擇的奶牛做完\(w_{m\ldots n-1}\)的最優決策後，下一個奶牛可以取得的最大值。

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
#include <stdio.h>

#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

int w[700000];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &w[i]);
    long long a = 0, b = 0;
    for (int i = n; --i >= 0; )
        if (b+w[i] >= a)
        {
            long long t = a;
            a = b+w[i];
            b = t;
        }
    printf(LLD" "LLD"\n", a, b);
}

island

根據USACL Analysis（後附），根據一個格子周圍格子的佈局，先把一些點轉換爲A，然後繞着A走一圈。

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
#include <cstdio>
using namespace std;

const int H = 1000, W = 1000;
const int dr[] = {0,1,0,-1}, dc[] = {1,0,-1,0};
char a[H][W+1];
int tmp[4], h, w;

void DFS(int r, int c)
{
    if (a[r][c] != '.' || !r || r == h-1 || !c || c == w-1) return;
    int cntA = 0;
    for (int d = 0; d < 4; ++d)
        if (a[r+dr[d]][c+dc[d]] == 'A')
            tmp[cntA++] = d;
    switch (cntA)
    {
        case 2:
            if ((tmp[0]+tmp[1])%2 == 0 || a[r-dr[tmp[0]]-dr[tmp[1]]][c-dc[tmp[0]]-dc[tmp[1]]] != '.')
                break;
            //fall through
        case 3:
        case 4:
            a[r][c] = 'A';
            for (int d = 0; d < 4; ++d)
                DFS(r+dr[d], c+dc[d]);
    }
}

inline bool check(int r, int c)
{
    return 0 <= r && r < h && 0 <= c && c < w && a[r][c] == '.';
}

int main()
{
    scanf("%d%d", &h, &w);
    for (int r = 0; r < h; ++r)
        scanf("%s", a[r]);
    for (int r = 1; r < h-1; ++r)
        for (int c = 1; c < w-1; ++c)
            DFS(r, c);

    int r, c, rr, cc, d = 0, len = 0;
    for (r = 0; r < h; ++r)
        for (c = 0; c < w; ++c)
            if (a[r][c] == 'A')
            {
                --r;
                goto L1;
            }
L1:
    rr = r;
    cc = c;
    do
    {
        int rrr = r+dr[d+1&3], ccc = c+dc[d+1&3];
        if (check(rrr, ccc))
        {
            r = rrr;
            c = ccc;
            d = d+1 & 3;
        }
        else if (rrr = r+dr[d], ccc = c+dc[d], check(rrr, ccc))
        {
            r = rrr;
            c = ccc;
        }
        else if (rrr = r+dr[d+3&3], ccc = c+dc[d+3&3], check(rrr, ccc))
        {
            r = rrr;
            c = ccc;
            d = d+3 & 3;
        }
        ++len;
    }while (r != rr || c != cc);
    printf("%d\n", len);
}

telephone

先把題目中給出的樹有根化，對於一個頂點u，如果它有不超過K/2個孩子還未被分配， 可以把它們中最多2*K個在u處連接起來。如果有孤立孩子並且還未配對完K對孩子， 那麼只能和u子樹外的頂點配對，這相當於u是其parent的未分配頂點。

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
#include <cstdio>
#include <vector>
using namespace std;

const int N = 100000;
int k, res = 0;
vector<int> e[N];

int compute(int u, int p)
{
    int t = e[u].size() == 1;
    for (vector<int>::iterator it = e[u].begin(); it != e[u].end(); ++it)
        if (*it != p)
            t += compute(*it, u);
    if (t <= k*2)
        return res += t/2, t%2;
    res += k;
    return 0;
}

int main()
{
    int n;
    scanf("%d%d", &n, &k);
    for (int i = n; --i; )
    {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    compute(0, -1);
    printf("%d\n", res);
}
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
USACO JAN10 Problem 'island' Analysis

by John Pardon

This problem requires nothing more than a modified flood-fill algorithm. Our strategy is too add squares to the main island until the optimal path is just to follow the boundary of the main island. Note that this would not work without the assumption that the main island is connected.

Consider the following four configurations:

?.?    ?..    ?.x    ?.A
A.A    A..    A..    A..
?A?    ?A?    ?A?    ?A?
(I)   (II)   (III)  (IV)
Let's focus on the center square of each of these configurations.

In (I), clearly there is no reason why FJ's ship would ever want to visit the center square; he would just have to leave again. Thus the problem remains unchanged if we change the center square to 'A'.

In (II), the situation is similar. A path like:

 V
?|.
A+->
?A?
can be changed to:

 V
?++
A.+>
?A?
with no increase in length. Thus we may change the center to square to 'A'.

In (III), we may not change the center square to an 'A', because then it wouldn't be possible to go around the main island without also going around the 'x' in the upper-right corner.

In (IV), we may also not change the center square to an 'A', at least not unless the top center square or the right center square is changed to an 'A' first.



After making the modifications (I) and (II) as many times as possible, the optimal solution is to follow the boundary of the main island, and this can just be simulated in order to find its length. Doing (I) and (II) as many times as possible is a modified flood-fill and can be done with a DFS. A solution follows:

PyGTK迷宮生成器mazer

隨機生成一個迷宮 

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
#!/usr/bin/env python

from sys import stdout
from random import randrange, shuffle
import gtk

BORDER = 10
LENGTH = 24

class mazer():
    def __init__(self, maxw, maxh):
        self.maxw, self.maxh = maxw, maxh
        self.map = [[False for c in xrange(self.maxw*2+1)] for r in xrange(self.maxh*2+1)]
        self.map[randrange(1, self.maxh*2, 2)][0] = True
        self.map[randrange(1, self.maxh*2, 2)][self.maxw*2] = True
        self.DFS(randrange(1, self.maxw*2, 2), randrange(1, self.maxh*2, 2))

    def run(self):
        window = gtk.Window()
        window.set_title('mazer')
        window.connect('destroy', gtk.main_quit)

        darea = gtk.DrawingArea()
        darea.size(LENGTH*self.maxw+BORDER*2, LENGTH*self.maxh+BORDER*2)
        darea.connect('expose_event', self.expose)
        window.add(darea)

        window.show_all()
        gtk.main()

    def DFS(self, x, y):
        self.map[y][x] = True
        ds = [(1,0),(0,1),(-1,0),(0,-1)]
        shuffle(ds)
        for d in ds:
            if 0 <= x+d[0]*2 < self.maxw*2 and 0 <= y+d[1]*2 < self.maxh*2 and not self.map[y+d[1]*2][x+d[0]*2]:
                self.map[y+d[1]][x+d[0]] = True
                self.DFS(x+d[0]*2, y+d[1]*2)

    def expose(self, widget, data):
        for y in xrange(self.maxh+1):

2013年8月17日更新

現在知道這個算法的名稱了：recursive backtracking，可以參見拙作完美迷宮生成算法

三柱漢諾塔相關擴展問題

設盤子編號爲，編號大的尺寸大，有三根柱子。

輸出初始局面（所有盤子都在1號柱子）到終止局面（所有盤子都在3號柱子）的最優方案。 時間複雜度： 經典遞歸，略。

輸出最優方案中某一局面之前經過的步驟數。 時間複雜度：

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
#include <cstdio>
#include <cstdlib>
using namespace std;

const int N = 1000;
int pos[N+1], nmoves = 0;

void move(int maxdisc, int src, int dst)
{
    if (pos[maxdisc] == 6-src-dst)
    {
        fprintf(stderr, "error: this is not a midway of the best solution.\n");
        exit(1);
    }
    if (pos[maxdisc] == src)
    {
        if (maxdisc > 1)
            move(maxdisc-1, src, 6-src-dst);
        pos[maxdisc] = dst;
    }
    else
    {
        nmoves += 1 << maxdisc-1;
        if (maxdisc > 1)
            move(maxdisc-1, 6-src-dst, dst);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);
    move(n, 1, 3);
    printf("It is a midway of the best solution and there is/are %d move(s) before.\n", nmoves);
}

輸出當前局面（不一定是最優解的中間步驟）到終止局面的最優方案。 時間複雜度：

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
#include <cstdio>
using namespace std;

const int N = 1000;
int pos[N+1], nmoves = 0;

void move(int disc, int dst)
{
    if (pos[disc] == dst) return;
    for (int i = disc-1; i; --i)
        move(i, 6-pos[disc]-dst);
    printf("%d: %d -> %d\n", disc, pos[disc], dst);
    pos[disc] = dst;
    ++nmoves;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);

    //for (int i = n-1; i; --i)
    //    move(i, pos[n]);

    for (int i = n; i; --i)
        move(i, 3);

    printf("total moves: %d\n", nmoves);
}

輸出當前局面下，把所有盤子移動到任一根柱子的最優方案。 時間複雜度：Ο(2^N)

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
#include <cstdio>
using namespace std;

const int N = 1000;
int pos[N+1], nmoves = 0;

void move(int disc, int dst)
{
    if (pos[disc] == dst) return;
    for (int i = disc-1; i; --i)
        move(i, 6-pos[disc]-dst);
    printf("%d: %d -> %d\n", disc, pos[disc], dst);
    pos[disc] = dst;
    ++nmoves;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);
    for (int i = n-1; i; --i)
        move(i, pos[n]);
    printf("total moves: %d\n", nmoves);
}

輸出當前局面下，把所有盤子移動到任一根柱子的最優方案所需步數。 時間複雜度：

易知，必定把移動到處 否則的話，需要至少步，不會最優。 所以所在位置就是 目標柱子

注意到如果初始時都在同一個根柱子上，那就不用再管它們了。 只需考慮

之所以要移動，要麼是爲了給比它編號大的盤子讓路，要麼是因爲要把它移動到目標柱子。 所以，如果要把移動到某根柱子，那麼也應該移動到柱子

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
#include <stdio.h>

const int N = 10000;
int cnt = 0, pos[N+1];

void move(int maxdisc, int dst)
{
    if (!maxdisc) return;
    int src = pos[maxdisc], aux = 6-src-dst;
    if (src == dst)
        move(maxdisc-1, dst);
    else
    {
        move(maxdisc-1, aux);
        cnt += 1 << maxdisc-1;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &pos[i]);
    move(n-1, pos[n]);
    printf("%d\n", cnt);
}

總結一下，對於求方案的問題，因爲最壞情況下步驟數可以達到，所以以上源碼在漸進意義上達到最優複雜度。

對於求步驟數（無須輸出方案），以上源碼時間複雜度都是，由於輸入時間已達到，所以在漸進意義上也達到了最優複雜度。

GTK+黑白棋reversi

language: C99 + GTK+ algorithm：對棋盤各個格子設置權值，計算總值 icon：程序截圖 license: GNU General Public License v3 revision control: Mercurial bead-black.png bead-white.png texture1.png texture2.png: 8pm(http://hi.baidu.com/eightpm) 提供

gdk透明貼圖好像有點麻煩（以前 Win32 API 用得是 TransparentBlt）

菜單採用GtkUIManager，可以看demo：/usr/share/gtk-2.0/demo/ui_manager.c的透明貼圖：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void pixbuf_transparent(GdkPixbuf *dst, const GdkPixbuf *src, gint dstx, gint dsty, guint transcolor)
{
    guchar r = (transcolor & 0xFF0000) >> 16;
    guchar g = (transcolor & 0x00FF00) >> 8;
    guchar b = transcolor & 0x0000FF;
    guchar *p = gdk_pixbuf_get_pixels(dst),
           *q = gdk_pixbuf_get_pixels(src);
    int d = gdk_pixbuf_get_n_channels(src),
        dd = gdk_pixbuf_get_rowstride(src),
        d2 = gdk_pixbuf_get_n_channels(dst),
        dd2 = gdk_pixbuf_get_rowstride(dst),
        w = gdk_pixbuf_get_width(src),
        h = gdk_pixbuf_get_height(src);
    for (int y = 0; y < h; ++y)
        for (int x = 0; x < w; ++x)
        {
            guchar *pp = p + (dsty+y) * dd2 + (dstx+x) * d2;
            guchar *qq = q + y * dd + x * d;
            if (qq[0] != r || qq[1] != g || qq[2] != b)
                pp[0] = qq[0], pp[1] = qq[1], pp[2] = qq[2];
        }
}

GTK+ tic-tac-toe（井字棋）

語言：C99 圖標是隨手塗鴉的 界面部分抄襲 http://sourceforge.net/projects/tictactoegtk/（作者：Obada Denis(obadadenis@gmail.com)，javajox(javajox@users.sourceforge.net)） 算法是 min-max search 版本控制系統採用 8pm 推薦的 Mercurial 項目首頁：http://code.google.com/p/rayup/ ＃裏面還有些其他亂七八糟的東西 Download：hg clone https://rayup.googlecode.com/hg/ rayup 沒有安裝 Mercurial 的話，可以訪問 http://code.google.com/p/rayup/source/browse/，手動下載一個個文件……

稱球問題擴展——根據當前已知信息選擇最優稱量方案

似乎是某個TopCoder SRM的題目。

N 個球，有一個是壞的，壞球重量與好球不同（略輕/重於好球）。有一個天平，可以告知左右兩邊孰重孰輕，最小化最壞情況下稱量次數，給出稱量方案。下面討論該問題的一個擴展——如何通過已知信息（即之前稱量結果，之前的稱量結果可能不是最優的）選擇下一步稱量方案，最小化最壞情況下的稱量次數。

根據已有信息把所有球分爲4類： - 肯定是好球 - 不可能比好球輕（不能確定是否爲壞球） - 不可能比好球重（不能確定是否爲壞球） - 不知道任何信息

每個球必定屬於以上四類中的某一類。我們只需知道每一類的數目即可，具體編號無關緊要。令\(s[nh][nl][nu]\)表示有\(nh\)個1類球，nl 個2類球，nu 個3類球，最壞情況下需要稱量的次數。枚舉一邊放置的各類型球數 lh(1類),ll(2類),lu(3類)，枚舉另一邊放置的各類型球數 rh(1類),rl(2類),ru(3類),re(0類)。如果兩邊都有0類球，那麼我們可以在兩邊各移去一個。我們可以保證0類球只出現在一邊，不妨設爲 rh(1類),rl(2類),ru(3類) 一邊。

Read More

NOIP 2004 數字遊戲（蟲食算）

下面程序可計算如下形式的式子：

1
2
3
4
5
6
7
8
9
10
11
one
+  nine
+ fifty
+twenty
-------
eighty

a
+a
--
bc

方法是枚舉進位+解方程，涉及的字母以及各個位上的進位作爲變量，然後解方程。這樣可以用　各個位上的進位　和　字母變量中的自由變量　表示　其他字母變量。枚舉　各個位上的進位　和　字母變量中的自由變量　以求出　其他字母變量，以此得到各組解。使用方法：根據要求解的式子設置各個變量，N、M設置得大點沒關係，L要正好等於式子的行數，然後輸入L行字符串

Read More

Dancing Links+Algorithm 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
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <algorithm>
#include <limits>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 9, LEN = 3; //size
const int MAX_R = N*N*N, MAX_C = N*N*4, MAX = MAX_C+1+MAX_R*4;
int L[MAX], R[MAX], U[MAX], D[MAX], size[MAX_C+1], column[MAX];
int res[N*N]; //result
pair<int, int> mean[MAX]; //first: pos. second: number

int mapping[256];
char mapping2[N];

void insert(int cur, int left, int right, int top)
{
        L[cur] = left; R[cur] = right;
        U[cur] = U[top]; D[U[cur]] = cur;
        D[cur] = top; U[top] = cur;
        column[cur] = top;
        ++size[top];
}

void remove(int c)
{
        L[R[c]] = L[c];
        R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
                for (int j = R[i]; j != i; j = R[j])
                {
                        U[D[j]] = U[j];
                        D[U[j]] = D[j];
                        --size[column[j]];
                }
}

void resume(int c)
{
        for (int i = U[c]; i != c; i = U[i])
                for (int j = L[i]; j != i; j = L[j])
                {
                        U[D[j]] = j;
                        D[U[j]] = j;
                        ++size[column[j]];
                }
        L[R[c]] = c;
        R[L[c]] = c;
}

bool DLX(int k)
{
        if (R[MAX_C] == MAX_C) return true;
        int c, mins = numeric_limits<int>::max();
        for (int i = R[MAX_C]; i != MAX_C; i = R[i])
                if (size[i] < mins)
                        mins = size[i], c = i;
        remove( c );
        for (int i = D[c]; i != c; i = D[i])
        {
                for (int j = R[i]; j != i; j = R[j])
                        remove(column[j]);
                res[mean[i].first] = mean[i].second;
                if (DLX(k+1)) return true;
                for (int j = L[i]; j != i; j = L[j])
                        resume(column[j]);
        }
        resume( c );
        return false;
}

int main()
{
        char str[N*N+1], tmp[N*N+1];
        str[0] = 0;
        mapping['1'] = 0; mapping2[0] = '1';
        mapping['2'] = 1; mapping2[1] = '2';
        mapping['3'] = 2; mapping2[2] = '3';
        mapping['4'] = 3; mapping2[3] = '4';
        mapping['5'] = 4; mapping2[4] = '5';
        mapping['6'] = 5; mapping2[5] = '6';
        mapping['7'] = 6; mapping2[6] = '7';
        mapping['8'] = 7; mapping2[7] = '8';
        mapping['9'] = 8; mapping2[8] = '9';
        while (strlen(str) < N*N)
                scanf("%s", tmp), strcat(str, tmp);

        int cur = MAX_C+1;
        for (int i = 0; i <= MAX_C; ++i)
        {
                L[i] = i-1; R[i] = i+1;
                U[i] = i; D[i] = i;
                size[i] = 0;
        }
        L[0] = MAX_C; R[MAX_C] = 0;
        for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                        if (str[i*N+j] == '.')
                        {
                                for (int k = 0; k < N; ++k)
                                {
                                        insert(cur, cur+3, cur+1, i*N+k); mean[cur++] = make_pair(i*N+j, k);
                                        insert(cur, cur-1, cur+1, N*N+j*N+k); mean[cur++] = make_pair(i*N+j, k);
                                        insert(cur, cur-1, cur+1, N*N*2+(i/LEN*LEN+j/LEN)*N+k); mean[cur++] = make_pair(i*N+j, k);
                                        insert(cur, cur-1, cur-3, N*N*3+i*N+j); mean[cur++] = make_pair(i*N+j, k);
                                }
                        }
                        else
                        {
                                const int k = mapping[str[i*N+j]];
                                insert(cur, cur+3, cur+1, i*N+k); mean[cur++] = make_pair(i*N+j, k);
                                insert(cur, cur-1, cur+1, N*N+j*N+k); mean[cur++] = make_pair(i*N+j, k);
                                insert(cur, cur-1, cur+1, N*N*2+(i/LEN*LEN+j/LEN)*N+k); mean[cur++] = make_pair(i*N+j, k);
                                insert(cur, cur-1, cur-3, N*N*3+i*N+j); mean[cur++] = make_pair(i*N+j, k);
                                res[i*N+j] = k;
                        }

        if (!DLX(0))
                puts("No solution.");
        else
                for (int i = 0; i < N; ++i, puts(""))
                        for (int j = 0; j < N; ++j)
                                putchar(mapping2[res[i*N+j]]);
}

2013年8月17日更新

NOIP 2009考了靶形數獨，可能前一天我還敲了一遍這段代碼……

.emacs

.emacs 很多 elisp 文件是通過 gentoo portage 安裝的，部分不在 portage 裏的放在了 ~/.emacs.d 下面

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
(progn (cd "~/.emacs.d") (normal-top-level-add-subdirs-to-load-path))
(add-to-list 'load-path "~/.emacs.d")

; ----------
; window spliting
; ----------
(global-set-key (kbd "M-3") 'split-window-horizontally)
(global-set-key (kbd "M-2") 'split-window-vertically)
(global-set-key (kbd "M-1") 'delete-other-windows)
(global-set-key (kbd "M-s") 'other-window)


; ----------
; dired
; ----------
(setq dired-recursive-copies (quote always))
(setq dired-recursive-deletes (quote top))
(add-hook 'dired-mode-hook
(lambda ()
(define-key dired-mode-map (kbd "<return>")
'dired-find-alternate-file) ; was dired-advertised-find-file
(define-key dired-mode-map (kbd "^")
(lambda () (interactive) (find-alternate-file "..")))
; was dired-up-directory
))



; ----------
; ecb
; ----------
(require 'ecb)

; ----------
; yasnippet
; ----------
;(add-to-list 'load-path "~/.emacs.d/yasnippet-0.6.1c")
(require 'yasnippet)
(yas/initialize)
; (yas/load-directory "/usr/share/emacs/etc/yasnippet/snippets")
(yas/load-directory "~/.emacs.d/yasnippet/snippets")


; ----------
; ido
; ----------
(require 'ido)
(ido-mode 1)


; ----------
; gdb-many-windows
; ----------
(setq gdb-many-windows t)


; ----------
; iswitchb & ibuffer
; ----------
(defalias 'list-buffers 'ibuffer)

(iswitchb-mode 1)
(put 'narrow-to-page 'disabled nil)
(put 'narrow-to-region 'disabled nil)


; ----------
; mew
; ----------

(autoload 'mew "mew" nil t)
(autoload 'mew-send "mew" nil t)
(if (boundp 'read-mail-command)
(setq read-mail-command 'mew))
(autoload 'mew-user-agent-compose "mew" nil t)
(if (boundp 'mail-user-agent)
(setq mail-user-agent 'mew-user-agent))
(if (fboundp 'define-mail-user-agent)
(define-mail-user-agent
'mew-user-agent
'mew-user-agent-compose
'mew-draft-send-message
'mew-draft-kill
'mew-send-hook))


; ----------
; miscellaneous
; ----------
(add-hook 'text-mode-hook (lambda () (hl-line-mode 1)))
(global-linum-mode 1)
(column-number-mode 1)
(blink-cursor-mode 0)
(show-paren-mode 1)
(recentf-mode 1)
(setq default-directory "~/")
(global-set-key (kbd "C-x k") 'kill-this-buffer)
(setq ring-bell-function 'ignore)

(setq inhibit-startup-message t)
(setq initial-scratch-message "")

(defalias 'yes-or-no-p 'y-or-n-p)

(defun my-make-CR-do-indent ()
(define-key c-mode-base-map "\C-m" 'c-context-line-break))
(add-hook 'c-initialization-hook 'my-make-CR-do-indent)


; ----------
; auto-complete
; ----------

(setq hippie-expand-try-functions-list
'(try-expand-dabbrev
try-expand-dabbrev-visible
try-expand-dabbrev-all-buffers
try-expand-dabbrev-from-kill
try-complete-file-name-partially
try-complete-file-name
try-expand-all-abbrevs
try-expand-list
try-expand-line
try-complete-lisp-symbol-partially
try-complete-lisp-symbol))
(global-set-key [(meta ?/)] 'hippie-expand)



(require 'auto-complete)
(setq ac-auto-show-menu 0.2)


; ----------
; gccsense
; ----------
(require 'gccsense)
(add-hook 'c-mode-common-hook
(lambda ()
(local-set-key (kbd "M-TAB") 'ac-complete-gccsense)))


; ----------
; semantic
; ----------
; (semantic-load-enable-code-helpers)
; (setq semanticdb-default-save-directory "~/.emacs.d/semanticdb")
; (global-set-key (kbd "M-TAB") 'semantic-ia-complete-symbol-menu)


; ----------
; company-mode
; ----------
; (setq company-idle-delay t)
; (setq company--disabled-backends '(company-pysmell company-ropemacs))


; ----------
; lisp
; ----------
(add-hook 'lisp-interaction-mode-hook '(lambda () (eldoc-mode 1) (auto-complete-mode 1)))
(add-hook 'emacs-lisp-mode-hook '(lambda () (eldoc-mode 1) (auto-complete-mode 1)))
(add-hook 'slime-mode '(lambda() (eldoc-mode 1) (auto-complete-mode 1)))
(defalias 'eb 'eval-buffer)
(defalias 'er 'eval-region)
(defalias 'ee 'eval-expression)
(defalias 'elm 'emacs-lisp-mode)
(defalias 'eis 'elisp-index-search)


; ----------
; python
; ----------
(add-hook 'python-mode-hook '(lambda() (eldoc-mode 1)))


; ----------
; cc
; ----------
(defun my-c-mode-common-hook ()
(c-set-style "k&r")
(setq tab-width 4 indent-tabs-mode nil c-basic-offset 4)
(c-toggle-auto-hungry-state 1)
(c-toggle-electric-state 1)

(auto-complete-mode 1)
; (company-mode 1)
(add-to-list 'c-cleanup-list 'brace-else-brace)
(add-to-list 'c-cleanup-list 'brace-elseif-brace)
(add-to-list 'c-cleanup-list 'brace-catch-brace)
(add-to-list 'c-cleanup-list 'defun-close-semi)
(add-to-list 'c-cleanup-list 'one-liner-defun)


)
(add-hook 'c-mode-common-hook 'my-c-mode-common-hook)


(defun my-c-initialization-hook ()
(define-key c-mode-base-map "\C-m" 'c-context-line-break))
(add-hook 'c-initialization-hook 'my-c-initialization-hook)


(global-set-key "%" 'match-paren)
(defun match-paren (arg)
"Go to the matching paren if on a paren; otherwise insert %."
(interactive "p")
(cond ((looking-at "\\s\(") (forward-list 1) (backward-char 1))
((looking-at "\\s\)") (forward-char 1) (backward-list 1))
(t (self-insert-command (or arg 1)))))

; ----------
; cscope
; ----------
(require 'xcscope)
(setq cscope-do-not-update-database t)


; ----------
; goto-char
; ----------
(defun wy-go-to-char (n char)
"Move forward to Nth occurence of CHAR.
Typing `wy-go-to-char-key' again will move forwad to the next Nth
occurence of CHAR."
(interactive "p\ncGo to char: ")
(search-forward (string char) nil nil n)
(while (char-equal (read-char)
char)
(search-forward (string char) nil nil n))
(setq unread-command-events (list last-input-event)))

(define-key global-map (kbd "C-c f") 'wy-go-to-char)


; ----------
; hilight-tail
; ----------
(require 'highlight-tail)
(setq highlight-tail-colors
'(("black" . 0)
("#bc2525" . 25)
("black" . 66)))
(highlight-tail-mode 1)


; -----
; font
; -----
(set-default-font "Envy Code R VS-18")


; ----------
; color-theme (ir-black)
; ----------
(require 'color-theme)
(color-theme-initialize)

;; IR_Black Color Theme for Emacs.
;;
;; David Zhou
;;
;; The IR_Black theme is originally from:
;;
;; http://blog.infinitered.com/entries/show/8
;;
;; This theme needs color-theme.
;;
;; To use, put this in your init files:
;;
;; (require 'color-theme)
;; (color-theme-initialize)
;; (load-file "path/to/color-theme-irblack.el")
;; (color-theme-irblack)


(defun color-theme-irblack ()
(interactive)
(color-theme-install
'(color-theme-irblack
((background-color . "#000000")
(background-mode . dark)
(border-color . "#454545")
(cursor-color . "#888888")
(foreground-color . "#F6F3E8")
(mouse-color . "#660000"))
(default ((t (:background "#000000" :foreground "#F6F3E8"))))
(vertical-border ((t (:background "#666666"))))
(blue ((t (:foreground "blue"))))
(border-glyph ((t (nil))))
(buffers-tab ((t (:background "#141414" :foreground "#CACACA"))))
(font-lock-comment-face ((t (:foreground "#7C7C7C"))))
(font-lock-constant-face ((t (:foreground "#99CC99"))))
(font-lock-doc-string-face ((t (:foreground "#A8FF60"))))
(font-lock-function-name-face ((t (:foreground "#FFD2A7"))))
(font-lock-builtin-face ((t (:foreground "#96CBFE"))))
(font-lock-keyword-face ((t (:foreground "#96CBFE"))))
(font-lock-preprocessor-face ((t (:foreground "#96CBFE"))))
(font-lock-reference-face ((t (:foreground "#C6C5FE"))))

(font-lock-regexp-grouping-backslash ((t (:foreground "#E9C062"))))
(font-lock-regexp-grouping-construct ((t (:foreground "red"))))

(linum ((t (:background "#000000" :foreground "#666666"))))

(minibuffer-prompt ((t (:foreground "#888888"))))
(ido-subdir ((t (:foreground "#CF6A4C"))))
(ido-first-match ((t (:foreground "#8F9D6A"))))
(ido-only-match ((t (:foreground "#8F9D6A"))))
(mumamo-background-chunk-submode ((t (:background "#222222"))))

(font-lock-string-face ((t (:foreground "#A8FF60"))))
(font-lock-type-face ((t (:foreground "#FFFFB6"))))
(font-lock-variable-name-face ((t (:foreground "#C6C5FE"))))
(font-lock-warning-face ((t (:background "#CC1503" :foreground "#FFFFFF"))))
(gui-element ((t (:background "#D4D0C8" :foreground "black"))))
(region ((t (:background "#660000"))))
(mode-line ((t (:background "grey75" :foreground "black"))))
(highlight ((t (:background "#111111"))))
(highline-face ((t (:background "SeaGreen"))))
(left-margin ((t (nil))))
(text-cursor ((t (:background "yellow" :foreground "black"))))
(toolbar ((t (nil))))
(show-paren-mismatch ((t (:background "#FF1100"))))
(underline ((nil (:underline nil))))

;; mumamo
(mumamo-background-chunk-major ((t (:background "#000000"))))
(mumamo-background-chunk-submode1 ((t (:background "#0A0A0A"))))
(mumamo-background-chunk-submode2 ((t (:background "#0A0A0A"))))
(mumamo-background-chunk-submode3 ((t (:background "#0A0A0A"))))
(mumamo-background-chunk-submode4 ((t (:background "#0A0A0A"))))

;; diff-mode
(diff-added ((t (:background "#253B22" :foreground "#F8F8F8"))))
(diff-removed ((t (:background "#420E09" :foreground "#F8F8F8"))))
(diff-content ((t nil)))
(diff-header ((t (:background "#0E2231" :foreground "#F8F8F8"))))


;; nxml
(nxml-delimiter ((t (:foreground "#96CBFE"))))
(nxml-name ((t (:foreground "#96CBFE"))))
(nxml-element-local-name ((t (:foreground "#96CBFE"))))
(nxml-attribute-local-name ((t (:foreground "#FFD7B1"))))

)))

(color-theme-irblack)
(custom-set-variables
;; custom-set-variables was added by Custom.
;; If you edit it by hand, you could mess it up, so be careful.
;; Your init file should contain only one such instance.
;; If there is more than one, they won't work right.
'(canlock-password "30539d11124ba9fd0c889bdd7e4471cf6a3bfe95")
'(dired-dwim-target t)
'(ecb-options-version "2.40")
'(ecb-primary-secondary-mouse-buttons (quote mouse-1--mouse-2))
'(highlight-changes-colors nil))
(custom-set-faces
;; custom-set-faces was added by Custom.
;; If you edit it by hand, you could mess it up, so be careful.
;; Your init file should contain only one such instance.
;; If there is more than one, they won't work right.
)
(put 'scroll-left 'disabled nil)
(put 'set-goal-column 'disabled nil)
(put 'dired-find-alternate-file 'disabled nil)

2013年8月17日更新

記得這是NOIP 2009前的停課時期，我做題無聊了就折騰Linux下的各種工具，此興悠哉！來機房也不都是來做題的，來“操機”的不少，我覺得隱隱有危機，果不其然後來機房就只在一週的少數幾天開放了。