2010-01-02

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的透明贴图：

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];
        }
}

2010-01-01

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/，手动下载一个个文件……

2009-12-19

称球问题扩展——根据当前已知信息选择最优称量方案

似乎是某个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类) 一边。

2009-11-23

NOIP 2004 数字游戏（虫食算）

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

one
+  nine
+ fifty
+twenty
-------
eighty

a
+a
--
bc

方法是枚举进位+解方程，涉及的字母以及各个位上的进位作为变量，然后解方程。这样可以用　各个位上的进位　和　字母变量中的自由变量　表示　其他字母变量。枚举　各个位上的进位　和　字母变量中的自由变量　以求出　其他字母变量，以此得到各组解。使用方法：根据要求解的式子设置各个变量，N、M设置得大点没关系，L要正好等于式子的行数，然后输入L行字符串

2009-11-23

Dancing Links+Algorithm X求解数独

#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考了靶形数独，可能前一天我还敲了一遍这段代码……

2009-11-14

.emacs

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

(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下的各种工具，此兴悠哉！来机房也不都是来做题的，来“操机”的不少，我觉得隐隐有危机，果不其然后来机房就只在一周的少数几天开放了。