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

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