解題區►解題區 - UVa

UVa 11421 - Arranging Cards

Problem

把每一種牌當作字串串在一起，請問第 k 小字典順序的排列為何？並且相同數字 (rank) 的牌不能放在一起。

Sample Input

1
2
3
4
5
6
7
8
9
6 1
2S 3S 3C 4S 4C 4D
6 120
2S 3S 3C 4S 4C 4D
6 121
2S 3S 3C 4S 4C 4D
16 654321234567
2S 3S 4S 5S 2C 3C 4C 5C 2D 3D 4D 5D 2H 3H 4H 5H
0 0

Sample Output

1
2
3
4
Case 1: 2S 4C 3C 4D 3S 4S
Case 2: 4S 3S 4D 3C 4C 2S
Case 3: Not found
Case 4: 5D 4S 2D 5H 3S 4H 5S 2H 3D 2C 5C 4D 2S 3C 4C 3H

Solution

題目最麻煩的地方是 k 必須使用 long long 才裝得下，然而中間運算過程中很容易超過 long long 因此在終止條件上會變得很難處理。

首先我們必須要知道那些牌可以排出哪幾種方法，但是很明顯地基礎的 dp 無法用上，少說狀態也必須是 13 * 2^50 之類的玩相鄰不可同色。

因此最後將牌壓縮成，擁有 4 張一樣、3 張、2 張、1 張的個數，擁有多少種排列方式。在寫遞迴的時候，標記上一次使用哪一類型的牌。為了逃出 overflow 的運算，使用一個 double 類別的輔助陣列，同樣計算方法數。

隨後知道固定類型的方法數，依序從字典順序小的開始窮舉是否要擺放於此位置。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int usedg[16][16][16][16][5];
long long dp[16][16][16][16][5];
double dp2[16][16][16][16][5];
const long long MAXVAL = 1e+18 + 10;
long long g(int f4, int f3, int f2, int f1, int last) {
	if (usedg[f4][f3][f2][f1][last])
		return dp[f4][f3][f2][f1][last];
	usedg[f4][f3][f2][f1][last] = 1; 
	long long &ret = dp[f4][f3][f2][f1][last];
	double &ret2 = dp2[f4][f3][f2][f1][last];
	if (f4 + f3 + f2 + f1 == 0) {
		ret = 1;
		ret2 = 1;
		return 1;
	}
	if (f4 > 0) {
		ret += 4 * f4 * g(f4-1, f3+1, f2, f1, 4);
		ret2 += 4 * f4 * dp2[f4-1][f3+1][f2][f1][4];
	}
	ret = min(ret, MAXVAL);
	if (ret2 > MAXVAL)	return ret;
	if (f3 > 0) {
		if (last == 4) {
			ret += 3 * (f3 - 1) * g(f4, f3-1, f2+1, f1, 3);
			ret2 += 3 * (f3 - 1) * dp2[f4][f3-1][f2+1][f1][3];
		} else {
			ret += 3 * (f3) * g(f4, f3-1, f2+1, f1, 3);
			ret2 += 3 * (f3) * dp2[f4][f3-1][f2+1][f1][3];
		}
	}
	ret = min(ret, MAXVAL);
	if (ret2 > MAXVAL)	return ret;
	if (f2 > 0) {
		if (last == 3) {
			ret += 2 * (f2 - 1) * g(f4, f3, f2-1, f1+1, 2);
			ret2 += 2 * (f2 - 1) * dp2[f4][f3][f2-1][f1+1][2];
		} else {
			ret += 2 * (f2) * g(f4, f3, f2-1, f1+1, 2);
			ret2 += 2 * (f2) * dp2[f4][f3][f2-1][f1+1][2];
		}
	}
	ret = min(ret, MAXVAL);
	if (ret2 > MAXVAL)	return ret;
	if (f1 > 0) {
		if (last == 2) {
			ret += (f1 - 1) * g(f4, f3, f2, f1-1, 1);
			ret2 += (f1 - 1) * dp2[f4][f3][f2][f1-1][1];
		} else {
			ret += f1 * g(f4, f3, f2, f1-1, 1);
			ret2 += f1 * dp2[f4][f3][f2][f1-1][1];
		}
	}
	ret = min(ret, MAXVAL);
	if (ret2 > MAXVAL)	return ret;
	return ret;
}
int card2Num(char suit, char rank) {
	int s, r;
	switch(suit) {
		case 'S': s = 3;break;
		case 'C': s = 0;break;
		case 'H': s = 2;break;
		case 'D': s = 1;break;
	}
	switch(rank) {
		case '2'...'9': r = rank-'0'-2;break;
		case 'T': r = 12;break;
		case 'J': r = 9;break;
		case 'Q': r = 11;break;
		case 'K': r = 10;break;
		case 'A': r = 8;break;
	}
	return r * 4 + s;
}
int main() {
	int cases = 0;
	int N;
	long long K;
	char psuit[] = "CDHS", prank[] = "23456789AJKQT";
	while (scanf("%d %lld", &N, &K) == 2) {
		if (N == 0 && K == 0)
			break;
		char card[10];
		int A[64];
		for (int i = 0; i < N; i++) {
			scanf("%s", card);
			int x = card2Num(card[1], card[0]);
			A[i] = x;
		}
		printf("Case %d:", ++cases);
		int ret[64];
		int NOT_FOUND = 0; 
		K--;
		for (int i = 0; i < N; i++) {
			sort(A+i, A+N);
			ret[i] = -1;
			for (int j = i; j < N; j++) {
				int ch = A[j];
				int cnt[13] = {}, f[8] = {};
				if (i && ch/4 == ret[i-1]/4) 
					continue;
				for (int k = i; k < N; k++)
					cnt[A[k]/4]++;
				int last = cnt[ch/4]--;
				for (int k = 0; k < 13; k++)
					f[cnt[k]]++;
				long long way = g(f[4], f[3], f[2], f[1], last);			
//				printf("%d %d %d %d - %d %lld\n", f[4], f[3], f[2], f[1], last, way);
//				printf("%lld %lf\n", way, dp2[f[4]][f[3]][f[2]][f[1]][last]);
				if (dp2[f[4]][f[3]][f[2]][f[1]][last] > K) {
					swap(A[i], A[j]);
					ret[i] = ch;
					break;
				} else {
					K -= way;
				}
			}
			if (ret[i] == -1) {
				NOT_FOUND = 1;
				break;
			}
//			puts("------");
		}
		if (NOT_FOUND) {
			puts(" Not found");
			continue;
		}
		for (int i = 0; i < N; i++)  {
//			printf("%d\n", ret[i]);
			printf(" %c%c", prank[ret[i]/4], psuit[ret[i]%4]);
		}
		puts("");
	}
	return 0;
}
/*
50 1
2C 2D 2H 2S
3C 3D 3H 3S
4C 4D 4H 4S
5C 5D 5H 5S
6C 6D 6H 6S
7C 7D 7H 7S
8C 8D 8H 8S
9C 9D 9H 9S
TC TD TH TS
JC JD JH JS
QC QD QH QS
KC KD KH
AC AD AH
*/
Read More +
解題區►解題區 - UVa

UVa 1395 - Slim Span

Problem

找一個生成樹，使得最大邊與最小邊的差最小。

Sample Input

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
4 5 
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7
4 6 
1 2 10 
1 3 100 
1 4 90 
2 3 20 
2 4 80 
3 4 40 
2 1 
1 2 1
3 0 
3 1 
1 2 1
3 3 
1 2 2
2 3 5 
1 3 6 
5 10 
1 2 110 
1 3 120 
1 4 130 
1 5 120 
2 3 110 
2 4 120 
2 5 130 
3 4 120 
3 5 110 
4 5 120 
5 10 
1 2 9384 
1 3 887 
1 4 2778 
1 5 6916 
2 3 7794 
2 4 8336 
2 5 5387 
3 4 493 
3 5 6650 
4 5 1422 
5 8 
1 2 1 
2 3 100 
3 4 100 
4 5 100 
1 5 50 
2 5 50 
3 5 50 
4 1 150 
0 0

Sample Output

1
2
3
4
5
6
7
8
9
1 
20 
0 
-1 
-1 
1 
0 
1686 
50

Solution

窮舉最小邊權重使用，使用 kruscal 找到瓶頸的最大邊。

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[10005];
int p[1005], rank[1005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m, E D[], int &max_edge) {
    max_edge = 0;
    for(int i = 0; i <= n; i++)
        p[i] = i, rank[i] = 1;
    int ee = 0;
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y))
        	max_edge = max(max_edge, D[i].v), ee++;
    }
    return ee == n-1;
}
int main() {
	int n, m, x, y, w;
	while (scanf("%d %d", &n, &m) == 2 && n+m) {
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &x, &y, &w);
			D[i] = E(x, y, w);
		}
		sort(D, D+m);
		int ret = 0x3f3f3f3f, mxedge;
		for (int i = 0; i < m; i++) {
			if (kruscal(n, m-i, D+i, mxedge))
				ret = min(ret, mxedge - D[i].v);
			else
				break;
		}
		printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 10665 - Diatribe against Pigeonholes

Problem

包裹放置於架子上時，盡可能讓兩側的總量越重越好，而中間放置輕的物品。

找到一種放置方式，同時字典順序越小越好。

Sample Input

1
2
3
4
5
6
7
8
9
4
5
BDCECDCBCBCDECDABCEDVBCDBCDBCDABCAED#
7
BGFADCEDGFCDEGCFCGDGCXXDAEDACEACEGFAGFCEDGCEDGBCD#
24
AABACDEDFGHMMJNTBNHGTDFACCDLLPPPERRAMMMMKKKKJJJHHHAAAAGGGQQQLLLLPPPAA#
10
PDJFGEDFANGEHIAEJBHJGEDGJGJEINDFJHEIEDGHFFGHDHGFHAJGIE#

Sample Output

1
2
3
4
5
6
7
8
C B A E D
11 8 3 4 9
C D A B F E G
10 9 5 2 5 7 9
A L G D C B E F I O S U V W X N R T Q J K H M P
11 6 5 4 3 2 2 2 0 0 0 0 0 0 0 2 2 2 3 4 4 5 6 6
E H D A B C I F J G
8 7 6 3 1 0 4 6 7 9

Solution

很明顯地可以使用貪心策略，每一次決定方最左或者是最右邊的項目。

由於要維持最小字典順序，放置兩個物品時

  • 如果這兩個重量相同，則字典順序最小的放前面，最大的放後面。
  • 反之，找到挑一個 同一個重量 字典順序小的放前面。
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
#include <stdio.h> 
#include <algorithm>
#include <vector>
using namespace std;
bool cmp1(pair<int, int> a, pair<int, int> b) {
	return a.second > b.second || (a.second == b.second && a.first < b.first);
}
bool cmp2(pair<int, int> a, pair<int, int> b) {
	return a.second > b.second || (a.second == b.second && a.first > b.first);
}
int main() {
	int testcase, N;
	char s[1024];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf ("%d %s", &N, s);
		pair<int, int> cnt[26] = {}, ret[26];
		for (int i = 0; i < N; i++)
			cnt[i].first = i + 'A';
		for (int i = 0; s[i] != '#'; i++) {
			if (s[i] >= 'A' && s[i] <= 'Z')
				cnt[s[i] - 'A'].second ++;
		}
		int l = 0, r = N - 1;
		for (int i = 0; i < N; ) {
			if (i+1 < N) {
				sort(cnt+i, cnt + N, cmp1);
				if (cnt[i].second != cnt[i+1].second) {
					if (cnt[i].first < cnt[i+1].first) {
						ret[l++] = cnt[i];
						sort(cnt+i+1, cnt + N, cmp2);
						ret[r--] = cnt[i+1];
					} else {
						swap(cnt[i], cnt[i+1]);
						ret[l++] = cnt[i];
						sort(cnt+i+1, cnt + N, cmp2);
						ret[r--] = cnt[i+1];
					}
				} else {
					sort(cnt+i, cnt + N, cmp1);
					ret[l++] = cnt[i];
					sort(cnt+i+1, cnt + N, cmp2);
					ret[r--] = cnt[i+1];
				}
				i += 2;
			} else {
				ret[l] = cnt[i];
				i++;
			}
		}
		for (int i = 0; i < N; i++)
		 	printf("%c%c", ret[i].first, i == N - 1 ? '\n' : ' ');
	 	for (int i = 0; i < N; i++)
		 	printf("%d%c", ret[i].second, i == N - 1 ? '\n' : ' ');
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 10571 - Products

Problem

  • 所有使用的數字不可重複
  • 每一行、每一列恰好使用兩個數字
  • 每行、每列的非零數字相乘恰好符合需求

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
2 12
3 8
3
5 8 18
2 30 12
5
54 6 12 20 88
18 9 132 32 10
10
2 12 30 56 90 132 182 240 306 380
19 36 51 64 75 84 91 96 99 200
0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1   3
2   4
1   2   0
5   0   6
0   4   3
6   3   0   0   0
9   0   1   0   0
0   0  12   0  11
0   0   0   4   8
0   2   0   5   0
1   0   0   0   0   0   0   0   0  19
2   0   0   0   0   0   0   0  18   0
0   3   0   0   0   0   0   0  17   0
0   4   0   0   0   0   0  16   0   0
0   0   5   0   0   0   0  15   0   0
0   0   6   0   0   0  14   0   0   0
0   0   0   7   0   0  13   0   0   0
0   0   0   8   0  12   0   0   0   0
0   0   0   0   9  11   0   0   0   0
0   0   0   0  10   0   0   0   0  20

Solution

直接每一行每一行搜索，過程中預處理所有因數分解，並且同時剪枝不合法的列。

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
#include <stdio.h> 
#include <vector>
#include <assert.h>
using namespace std;
int N, X[16] = {}, Y[16] = {};
int g[16][16] = {};
vector<int> row[16];
vector<int> f[1024];
int used[1024] = {};
int dfs(int idx) {
	if (idx == N) {
		for (int i = 0; i < N; i++, puts("")) {
			for (int j = 0; j < N; j++) {
				if (j) putchar(' ');
				printf("%3d", g[j][i]);
			}
		}
		return 1;
	}
	for (int p = 0; p < N; p++) {
		for (int q = p + 1; q < N; q++) {
			if (row[p].size() == 2 || row[q].size() == 2)
				continue;
			for (int i = 0; i < f[X[idx]].size(); i++) {
				int a, b, ok = 1;
				a = f[X[idx]][i];
				b = X[idx]/a;
				if (used[a] || used[b] || a == b) 
					continue;
				g[idx][p] = a, g[idx][q] = b;
				used[a] = used[b] = 1;
				row[p].push_back(a);
				row[q].push_back(b);
				if (row[p].size() == 2 && row[p][0] * row[p][1] != Y[p]) 
					ok = 0;
				if (row[q].size() == 2 && row[q][0] * row[q][1] != Y[q]) 
					ok = 0;
				if (Y[p]%a || Y[q]%b)	
					ok = 0;
				if (ok) {
					if (dfs(idx + 1)) {
						g[idx][p] = 0, g[idx][q] = 0;
						row[p].pop_back();
						row[q].pop_back();
						used[a] = used[b] = 0;
						return 1;
					}
				}
				g[idx][p] = 0, g[idx][q] = 0;
				used[a] = used[b] = 0;
				row[p].pop_back();
				row[q].pop_back();
			}	
		}
	}
	return 0;
}
int main() {
	for (int i = 1; i < 1024; i++) {
		for (int j = 1; j <= i; j++) {
			if (i%j == 0)
				f[i].push_back(j);
		}
	}
	while (scanf("%d", &N) == 1 && N) {
		for (int i = 0; i < N; i++)
			scanf("%d", &X[i]);
		for (int i = 0; i < N; i++)
			scanf("%d", &Y[i]);
		assert(dfs(0) == 1);
		puts("");
	}
	return 0;
}
/*
2
2 12
3 8
3
5 8 18
2 30 12
5
54 6 12 20 88
18 9 132 32 10
10
2 12 30 56 90 132 182 240 306 380
19 36 51 64 75 84 91 96 99 200
0
*/
Read More +
解題區►解題區 - UVa

UVa 1368 - DNA Consensus String

Problem

給予一堆相同長度的 ATCG 構成的基因，找一段字典順序最小的基因，使得與給定的基因漢明碼距離(有多少位置不同)總和最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
3 
5 8 
TATGATAC 
TAAGCTAC 
AAAGATCC 
TGAGATAC 
TAAGATGT 
4 10 
ACGTACGTAC 
CCGTACGTAG 
GCGTACGTAT 
TCGTACGTAA 
6 10 
ATGTTACCAT 
AAGTTACGAT 
AACAAAGCAA 
AAGTTACCTT 
AAGTTACCAA 
TACTTACCAA

Sample Output

1
2
3
4
5
6
TAAGATAC 
7 
ACGTACGTAA 
6 
AAGTTACCAA 
12

Solution

對於每一個位置，找到字符使用最多次的使用，這樣將可以將此位置的漢明碼距離縮到最短。

最後討論一下相同時所需要的最小字典順序，即可完成。

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 <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
	int testcase;
	int n, m;
	char DNA[64][1024];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++)
			scanf("%s", DNA[i]);
		int hh = 0;
		char ret[1024] = {}, cc[] = "ACGT";
		for (int i = 0; i < m; i++) {
			int cnt[4] = {}, mx = 0;
			for (int j = 0; j < n; j++)
				cnt[find(cc, cc+4, DNA[j][i]) - cc]++;
			
			for (int j = 0; j < 4; j++) {
				if (cnt[j] > cnt[mx])
					mx = j;
			}
			ret[i] = cc[mx], hh += n - cnt[mx];
				
		}
		printf("%s\n%d\n", ret, hh);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 10712 - Count the Numbers

Problem

找一個數字 M 介於 [A, B] 之間，且中間的 substring 包含 N 的個數為何。

Sample Input

1
2
3
4
3 17 3
0 20 0
0 150 17
-1 -1 -1

Sample Output

1
2
3
2
3
2

Solution

建立一個 AC 自動機，使用傳統的 AC 自動機 dp，每一個節點當作一般 AC 自動機的走訪，並且猜測下一步的所有匹配符號。

為了要卡住上限，增加經過的狀態是否一直為前幾次臨界上限，若一直在上限，則搜索範圍將會被限制。

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
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[10], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[20][2]; // [string length][upper y/n]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = str[i] - '0';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
void clearDp(Node *root) {
	queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        memset(nd->dp, 0, sizeof(nd->dp));
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
    }
}
long long dp(Node *root, int len, char pattern[]) {
    queue<Node*> Q;
    Node *nd, *p;
    clearDp(root);
    root->dp[0][1] = 1;
    int k, i, j;
    long long ret = 0;
    for(k = 0; k < len; k++) {
        Q.push(root);
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for (j = 0; j < 2; j++) {
	            for (i = (k == 0); i <= (j ? pattern[k]-'0' : 9); i++) {
	                if(nd->next[i] != NULL) {
	                    if(nd->next[i]->eos) { // matching
	                    	if (j && i == pattern[k]-'0') {
	                    		long long t = 0;
	                    		for (int p = k + 1; p < len; p++)
	                    			t = t * 10 + pattern[p] - '0';
	                    		t++;
	                    		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %lld ++ %lld\n", k, j, nd->ASCII, i, nd->dp[k][j] * t, t);
	                    	} else {
	                    		long long t = 1;
	                    		for (int p = k + 1; p < len; p++)
	                    			t *= 10;	
	                    		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %d ++\n", k, j, nd->ASCII, i, nd->dp[k][j] * t);
	                    	}
	                    	continue;
	                    } 
						if (j == 0 || (j == 1 && i < pattern[k] - '0'))
	                    	nd->next[i]->dp[k+1][0] += nd->dp[k][j];
	                    else if(j == 1 && i == pattern[k] - '0')
	                    	nd->next[i]->dp[k+1][1] += nd->dp[k][j];
	                    if(j == 0)
	                    	Q.push(nd->next[i]);
	                } else {
	                    p = nd;
	                    while(p != root && p->next[i] == NULL)
	                        p = p->fail;
	                    p = p->next[i];
	                    if(p->eos) { // matching
                    		if (j && i == pattern[k]-'0') {
	                    		long long t = 0;
	                    		for (int p = k + 1; p < len; p++)
	                    			t = t * 10 + pattern[p] - '0';
	                    		t++;
	                    		ret += nd->dp[k][j] * t;
	                    	} else {
	                    		long long t = 1;
	                    		for (int p = k + 1; p < len; p++)
	                    			t *= 10;
	                    		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %d ++\n", k, j, nd->ASCII, i, nd->dp[k][j] * t);
	                    	}
	                    	continue;
	                    }
						if (j == 0 || (j == 1 && i < pattern[k] - '0'))
	                    	p->dp[k+1][0] += nd->dp[k][j];
	                    else if(j == 1 && i == pattern[k] - '0')
	                    	p->dp[k+1][1] += nd->dp[k][j];
	                }
	            }
        	}
        }
    }
    return ret;
}
long long getDistinctNumberWith(int n, int m) { // #number <= n, has substring m
	if (n < 0) 
		return 0;
	char pattern[26], s[26];
	sprintf(pattern, "%d", m);
	Node *root = new Node();
    insertTrie(pattern, root, 1);
    for(int i = 0; i < 10; i++) {
    	s[0] = i + '0', s[1] = '\0';
    	insertTrie(s, root, 0);
    }
    buildACautomation(root);
    sprintf(pattern, "%d", n);
    long long ret = 0;
    int nlen = strlen(pattern);
	ret += dp(root, nlen, pattern);
	for	(int i = 1; i < nlen; i++) {
		pattern[i-1] = '9', pattern[i] = '\0';
//		printf ("%s %d %d --------\n", pattern, i, dp(root, i, pattern));
		ret += dp(root, i, pattern);
	}
    if (m == 0)	
		ret++;
    freeTrie(root);
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, a, b;
    while(scanf("%d %d %d", &a, &b, &n) == 3 && a >= 0) {
    	long long R, L;
		R = getDistinctNumberWith(b, n);
		L = getDistinctNumberWith(a - 1, n);
        printf("%lld\n", R - L);
    }
    return 0;
}
/*
731653830 735259500 735
735259500 735259500 735
3 17 3
0 20 0
0 150 17
-1 -1 -1
*/
Read More +
網頁設計►NodeJs

Nodejs upload server 簡易上傳下載

Github upload-server

上傳的設定，要特別注意公開讀取的問題，採用 express 架構下，如果設定再 public 資料夾下，則任何人上傳都可以被任何人讀取。

中間有遇到一個問題 到底能不能限制使用者上傳速度

上網查了很多資料，不管是從前端還是後端，前端限制基本上沒有任何用處，後端則在這個架構中沒有找到相關的 API 限制，從作業系統中下手，則必須要找到 nodejs 執行緒中的網路限制。

奮鬥好幾天，仍然沒有這個解決方案。

Read More +
網頁設計►JQuery

Simple Works Gallery

起源

鄰近要大學推研究所的時刻，自己做過什麼作品來說，對於推甄時相當重要，一直都沒有好好整理過自己做過什麼，有多少能拿出檯面的項目，現在發現除了 ACM 解題和曾經幫別人寫的作業以外，沒有幾項可以吸引到人的。一樣做一個 hexo tag plugin，將作品展示櫃用一個 generator.js 的方式，將展示櫃內容呈現出來，傳入的方式為 json。同樣地，你可以在這個部落格上方的 Works 看到相關作品介紹。

下載

Download on Github

使用

仍然以 github 上的 project 為優先版本。以下的內容也許不是最新版本。

html

當前採用 json 的原因是因為可以藉由較簡單的方式，以及往後可能使用 ajax 的方式運作。這樣彈性也許會比較大。

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
<script type="text/works-gallery">
{
  "works" : [
      {
        "title": "Chat Room Application",
        "cover": "http://i.imgur.com/oUO30I6.jpg",
        "description": "計算機網路－一個簡單的網路聊天室<br/> Socket programming practice (Java)",
        "download": ["https://github.com/morris821028/hw-ChatRoom"],
        "demo": [],
        "video": ["https://www.youtube.com/watch?v=7ExCn1ipKeg"]
      },
      {
        "title": "Magic Circle",
        "cover": "http://i.imgur.com/Fv8ebBY.jpg",
        "description": "jquery-magic-circle, write funny for friends",
        "download": ["https://github.com/morris821028/jquery-magic-circle"],
        "demo": ["http://morris821028.github.io/jquery-magic-circle"],
        "video": ["https://www.youtube.com/watch?v=TWqmGeuIJLo"]
      },
      {
        "title": "Hex Image Gallery",
        "cover": "http://i.imgur.com/VMf2G1v.png",
        "description": "create beautiful hexagon shapes with CSS3, jquery, write funny for friends",
        "download": ["https://github.com/morris821028/jquery-hex-gallery"],
        "demo": ["http://morris821028.github.io/jquery-hex-gallery/"],
        "video": []
      }
  ]
}
</script>

css

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
.wg-container
{
	background: none repeat scroll 0% 0% #2d2d2d;
	border-color: #ddd;
	border-style: solid;
	border-width: 1px 0;
	color: #ccc;
	line-height: 25.6px;
	margin: 0 -20px;
	overflow: auto;
	padding: 15px 20px;
	position: relative;
	text-align: center;
	width: 100%;
	z-index: 0;
}
.wg-container hr
{
	background: #333;
	background-image: -moz-linear-gradient(to right, #333, #ccc, #333);
	background-image: -ms-linear-gradient(to right, #333, #ccc, #333);
	background-image: -o-linear-gradient(to right, #333, #ccc, #333);
	background-image: -webkit-linear-gradient(to right, #333, #ccc, #333);
	border: 0;
	height: 5px;
}
.wg-item
{
	list-style: none;
}
.wg-item .inner
{
	height: 160px;
}
.wg-item li
{
	display: block;
	float: left;
	margin: 16px;
	width: 45%;
}
.wg-item li .header
{
	border: 4px solid #b4b4b4;
	box-shadow: 1px 1px 1px 1px #ccc;
	cursor: pointer;
	float: left;
	height: 256px;
	margin: 5px;
	moz-box-shadow: 1px 1px 1px 1px #ccc;
	overflow: hidden;
	position: relative;
	webkit-box-shadow: 1px 1px 1px 1px #ccc;
	width: 100%;
}
.wg-item li .header:hover a
{
	moz-transform: scale(1.2);
	ms-transform: scale(1.2);
	o-transform: scale(1.2);
	transform: scale(1.2);
	webkit-transform: scale(1.2);
}
.wg-item li .header a
{
	left: 0;
	moz-transition: all 300ms ease-out;
	ms-transition: all 300ms ease-out;
	o-transition: all 300ms ease-out;
	position: absolute;
	transition: all 300ms ease-out;
	webkit-transition: all 300ms ease-out;
}
.wg-item li .image
{
	background-size: cover;
	display: block;
	height: 95%;
	moz-background-size: cover;
	padding: .5em;
	webkit-background-size: cover;
	width: 100%;
}
.wg-item li h3
{
	font-size: 24px;
	font-weight: normal;
	line-height: 22px;
	margin-bottom: 10px;
	margin-top: 10px;
	text-align: center;
}
.wg-item li h3 a:hover
{
	text-decoration: none;
}
.wg-item li ul.links
{
	float: right;
}
.wg-item li .links li
{
	display: block;
	margin-left: 5px;
	margin-right: 0 !important;
	width: initial;
}
.wg-item li .links li a
{
	background: #65a9d7;
	border-radius: 5px;
	box-shadow: 0 1px 0 #000;
	color: #fff;
	font-family: Georgia,Serif;
	font-size: 16px;
	padding: 5.5px 11px;
	text-decoration: none;
	text-shadow: 0 1px 0 rgba(0,0,0,0.4);
	vertical-align: middle;
	webkit-border-radius: 5px;
	webkit-box-shadow: 0 1px 0 #000;
}
.wg-item .description
{
	font-size: 16px;
	margin: .2em 0;
	text-align: left;
}

hexo plugin

我已經把產生方式寫在 hexo-tag-oj 裡頭，下載使用 hexo-tag-plugin

不過相關的 js 還有 css 要自己擺放，請參考上面的描述項目。

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
{\% ojblock works \%}
{
  "works" : [
      {
        "title": "Chat Room Application",
        "cover": "http://i.imgur.com/oUO30I6.jpg",
        "description": "計算機網路－一個簡單的網路聊天室<br/> Socket programming practice (Java)",
        "download": ["https://github.com/morris821028/hw-ChatRoom"],
        "demo": [],
        "video": ["https://www.youtube.com/watch?v=7ExCn1ipKeg"]
      },
      {
        "title": "Fuzzy System",
        "cover": "http://i.imgur.com/C44Hbrg.png",
        "description": "計算型智慧－廣義型演算法最佳化<br/>Car simulation implements PSO, GA, and fuzzy system (Java)",
        "download": ["https://github.com/morris821028/hw-FuzzySystem"],
        "demo": [],
        "video": ["https://www.youtube.com/watch?v=kt2mu679elU"]
      },
      {
        "title": "UML Editor",
        "cover": "http://i.imgur.com/JCCweao.png",
        "description": "物件導向程式設計－UML 編輯器架構設計<br/>OO design practice & make UML Editor (Java)",
        "download": ["https://github.com/morris821028/hw-UML-Editor"],
        "demo": [],
        "video": ["https://www.youtube.com/watch?v=DKDFy6uFk8Y"]
      },
      {
        "title": "MapleStory 遊戲仿作",
        "cover": "http://i.imgur.com/i62nNgG.png",
        "description": "由於硬碟損壞代碼沒有救回來，只剩下舊版，收錄於 chat room 製作中的一環，由於課程時間不夠，沒有做完。 (Java)",
        "download": ["https://github.com/morris821028/hw-ChatRoom"],
        "demo": [],
        "video": ["https://www.youtube.com/watch?v=TWqmGeuIJLo"]
      },
      {
        "title": "Magic Circle",
        "cover": "http://i.imgur.com/Fv8ebBY.jpg",
        "description": "jquery-magic-circle, write funny for friends",
        "download": ["https://github.com/morris821028/jquery-magic-circle"],
        "demo": ["http://morris821028.github.io/jquery-magic-circle"],
        "video": ["https://www.youtube.com/watch?v=TWqmGeuIJLo"]
      },
      {
        "title": "Hex Image Gallery",
        "cover": "http://i.imgur.com/VMf2G1v.png",
        "description": "create beautiful hexagon shapes with CSS3, jquery, write funny for friends",
        "download": ["https://github.com/morris821028/jquery-hex-gallery"],
        "demo": ["http://morris821028.github.io/jquery-hex-gallery/"],
        "video": []
      }
  ]
}
{\% endojblock \%}
Read More +
網頁設計►JQuery

Jquery Hex Image Gallery

起源

六角形的圖片廊道，一開始給定的是提案是做出一個圖片展示櫃，可是想到要放在這個 hexo 部落格，要做到類似的相簿功能其實是很麻煩的，還有必須要關聯 generator 的產生方式，才能製作出相對的 static website，那只好將項目弄成單獨一頁，而這一頁要怎麼製作其實很難捉摸。失敗的設計總是這樣子開始的。

由於圖片量太大的話，變成一開始載入速度會太慢，因此找來了 lazyload.js，但是跟展示窗口銜接上仍有一些問題，無法適時地反映操作，所以需要 call back 操作，否則圖片會載入失敗。再者是原本六角 CSS 問題，找來網路上提供的 CSS，發現更換大型圖片的時候，會造成圖片顯示不正常，因此在這一塊費時了相當長的時間來符合預期的操作。

此項目已經放在我的 Github 上面，同時你也可以在這個 blog 上方的 Picture 中看到 demo，萬萬沒想到居然有人願意 Star 標記，真的是相當令人動容啊，從來沒想過有人對於這樣的蠢製作感興趣。

下載

Download on Github

Demo

使用

仍然以 github 上的 project 為優先版本。以下的內容也許不是最新版本。

html

為了方便產生器運行，產生方式採用 json 的生成方式。相關的動畫製作引入

  • jquery.lazyload.js 圖片動態載入
  • jquery.als.link-1.6.js 幻燈片的展示窗口 (經過修改，來完成跳轉操作)

當前採用 json 的原因是因為可以藉由較簡單的方式，以及往後可能使用 ajax 的方式運作。這樣彈性也許會比較大。

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
<!DOCTYPE html>
<html>
  <head>
    	<meta charset="utf-8"/>
    	<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js" type="text/javascript"></script>
    	<script src="js/jquery.hex.gallery.js" type="text/javascript"></script>	
      	<script src="js/jquery.lazyload.js" type="text/javascript"></script> 
      	<script src="js/jquery.als.link-1.6.js" type="text/javascript"></script> 
    	<link rel="stylesheet" href="css/style.css">	
  </head>
  <body>
  	...
	     <script type="text/hex-gallery">
{
  "album" : [
      {
        "cover": {"title": "<h4>THEME</h4><hr /><p>Stephanie Dola</p>", "class": "hex-1"},
        "photo": [
          {"imgur": "http://i.imgur.com/yIoACHc.gif"},
          {"imgur": "http://i.imgur.com/uINck6K.gif"},
          {"imgur": "http://i.imgur.com/zOZJEex.gif"}
        ]
      },
      {
        "cover": {"title": "<h4>THEME</h4><hr /><p>萌～萌～哒～</p>", "class": "hex-2"},
        "photo": [
          {"imgur": "http://i.imgur.com/YSmWA3g.gif"},
        ]
      },
      {
        "cover": {"title": "<h4>THEME</h4><hr /><p>其他</p>", "class": "hex-3"},
        "photo": [
          {"imgur": "http://i.imgur.com/vpKzynV.gif"},
          {"imgur": "http://i.imgur.com/rctEEyS.gif"}
        ]
      }
  ]
}
	   </script>
	...
  </body>
</html>

css

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
.hex-container
{
	display: block;
	height: 320px;
	position: relative;
	width: 800px;
}
.hex
{
	animation: animatedBackground 10s linear infinite;
	background-color: #ccc;
	background-position: 50% 50%;
	background-repeat: no-repeat;
	background-size: cover;
	float: left;
	font-family: Georgia,"Microsoft YaHei","Times New Roman",serif;
	font-weight: bold;
	height: 86px;
	margin: 25px 5px;
	moz-animation: animatedBackground 10s linear infinite;
	moz-background-size: cover;
	ms-animation: animatedBackground 10s linear infinite;
	position: relative;
	text-align: center;
	webkit-animation: animatedBackground 10s linear infinite;
	webkit-background-size: cover;
	width: 150px;
	zoom: 1;
}
.hex.hex-gap
{
	margin-left: 86px;
}
.hex a
{
	display: block;
	height: 100%;
	left: 0;
	position: absolute;
	text-indent: -9999em;
	top: 0;
	width: 100%;
}
.hex .corner-1
{
	moz-transform: rotate(60deg);
	ms-transform: rotate(60deg);
	o-transform: rotate(60deg);
	transform: rotate(60deg);
	webkit-transform: rotate(60deg);
}
.hex .corner-1:before
{
	moz-transform: rotate(-60deg) translate(-87px,0);
	moz-transform-origin: 0 0;
	ms-transform: rotate(-60deg) translate(-87px,0);
	ms-transform-origin: 0 0;
	o-transform: rotate(-60deg) translate(-87px,0);
	o-transform-origin: 0 0;
	transform: rotate(-60deg) translate(-87px,0);
	transform-origin: 0 0;
	webkit-transform: rotate(-60deg) translate(-87px,0);
	webkit-transform-origin: 0 0;
}
.hex .corner-2
{
	moz-transform: rotate(-60deg);
	ms-transform: rotate(-60deg);
	o-transform: rotate(-60deg);
	transform: rotate(-60deg);
	webkit-transform: rotate(-60deg);
}
.hex .corner-2:before
{
	bottom: 0;
	moz-transform: rotate(60deg) translate(-44px,-12px);
	ms-transform: rotate(60deg) translate(-44px,-12px);
	o-transform: rotate(60deg) translate(-44px,-12px);
	transform: rotate(60deg) translate(-44px,-12px);
	webkit-transform: rotate(60deg) translate(-44px,-12px);
}
.hex .corner-3
{
	moz-transform: rotate(0);
	ms-transform: rotate(0);
	o-transform: rotate(0);
	transform: rotate(0);
	webkit-transform: rotate(0);
}
.hex .corner-3:before
{
	moz-transform: rotate(0) translate(-12px,-44px);
	ms-transform: rotate(0) translate(-12px,-44px);
	o-transform: rotate(0) translate(-12px,-44px);
	transform: rotate(0) translate(-12px,-44px);
	webkit-transform: rotate(0) translate(-12px,-44px);
}
.hex .inner
{
	color: #eee;
	position: absolute;
	right: 0;
	top: 0;
	display: inline;
	float: left;
	width: 98.3333%;
	margin: 0px 0.833333%;
}
.hex .inner a
{
	color: #fff;
	text-indent: 0;
}
.hex h4
{
	margin: 0;
}
.hex hr
{
	border: 0;
	border-top: 1px solid #eee;
	margin: 15px auto;
	width: 60%;
}
.hex p
{
	font-size: 22px;
	margin: 0 auto;
	width: 80%;
}
.hex.hex-1
{
	background: #74cddb;
}
.hex.hex-2
{
	background: #f00;
}
.hex.hex-3
{
	background: #80b971;
}
.hex.hex-back
{
	background: #80b971;
}
.hex.hex-back a
{
	padding: 0 4px;
}
.hex .corner-1,.hex .corner-2,.hex .corner-3
{
	backface-visibility: hidden;
	background: inherit;
	height: 100%;
	left: 0;
	moz-backface-visibility: hidden;
	ms-backface-visibility: hidden;
	o-backface-visibility: hidden;
	overflow: hidden;
	position: absolute;
	top: 0;
	webkit-backface-visibility: hidden;
	width: 100%;
}
.hex .corner-1:before,.hex .corner-2:before,.hex .corner-3:before
{
	backface-visibility: hidden;
	background: inherit;
	background-repeat: no-repeat;
	content: '';
	height: 173px;
	left: 0;
	moz-backface-visibility: hidden;
	ms-backface-visibility: hidden;
	o-backface-visibility: hidden;
	position: absolute;
	top: 0;
	webkit-backface-visibility: hidden;
	width: 173px;
}
.hex-caption
{
	background-color: rgba(0,0,0,0.5);
	color: #fff;
	left: 0;
	moz-transition: all 300ms ease-out;
	ms-transition: all 300ms ease-out;
	o-transition: all 300ms ease-out;
	position: absolute;
	transition: all 300ms ease-out;
	webkit-transition: all 300ms ease-out;
}
.hex:hover .hex-simple-caption
{
	moz-transform: translateY(-100%);
	ms-transform: translateY(-100%);
	o-transform: translateY(-100%);
	transform: translateY(-100%);
	visibility: visible;
	webkit-transform: translateY(-100%);
}
.hex-simple-caption
{
	bottom: -60px;
	display: block;
	height: 30px;
	line-height: 25pt;
	text-align: center;
	visibility: hidden;
	width: 100%;
}
.hex-background
{
	left: -80px;
	position: absolute;
	top: -136px;
	width: 900px;
	z-index: -1;
}
.hex-background .hex
{
	background-color: #708090;
}
.als-viewport
{
	height: 390px;
	margin: 0 auto;
	overflow: hidden;
	position: relative;
}
.als-wrapper
{
	list-style: none;
	position: relative;
}
.als-item
{
	cursor: pointer;
	display: block;
	float: left;
	position: relative;
	text-align: center;
}
.als-prev,.als-next
{
	clear: both;
	cursor: pointer;
	position: absolute;
}
.als-container
{
	background: none repeat scroll 0% 0% #2d2d2d;
	border-color: #ddd;
	border-style: solid;
	border-width: 1px 0;
	color: #ccc;
	line-height: 25.6px;
	margin: 0 -20px;
	overflow: auto;
	padding: 15px 20px;
	position: relative;
	text-align: center;
	width: 100%;
	z-index: 0;
}
.als-container .als-item
{
	display: block;
	margin: 0 5px;
	margin: 0 auto;
	min-height: 120px;
	min-width: 100px;
	padding: 4px 0;
	text-align: center;
	vertical-align: middle;
}
.als-container .als-prev
{
	font-size: 30px;
	left: 30px;
}
.als-container .als-next
{
	font-size: 30px;
	right: 30px;
}
.als-container .als-prev,.als-container .als-next
{
	top: 175px;
}
.icon-arrow-left
{
    display:inline-block;
    width:32px;
    height:32px;
    line-height:32px;
    border-top:3px solid #aaa;
    border-right:3px solid #aaa;
    -ms-transform:rotate(225deg);
    -moz-transform:rotate(225deg);
    -webkit-transform:rotate(225deg);
    transform:rotate(225deg);
}
.icon-arrow-right
{
    display:inline-block;
    width:32px;
    height:32px;
    line-height:32px;
    border-top:3px solid #aaa;
    border-right:3px solid #aaa;
    -ms-transform:rotate(45deg);
    -moz-transform:rotate(45deg);
    -webkit-transform:rotate(45deg);
    transform:rotate(45deg);
}

架構

hex page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<div class="hex-container">
	<div class="hex-background">
		<div class="hex hex-gap" style="background-image: url();">
			<div class="corner-1"></div>
			<div class="corner-2"></div>
			<div class="corner-3"></div>
			<div class="inner"></div>
		</div>
		<div class="hex" style="background-image: url();">
			<div class="corner-1"></div>
			<div class="corner-2"></div>
			<div class="corner-3"></div>
			<div class="inner"></div>
		</div>
		...
	</div>
</div>

原本網路提供 hex 只有 corner-1 和 corner-2，這樣的做法無法產生 cover 的圖示，因此這裡增加 corner-3，但仍然會看到一條一條格線在斜邊上，不過已經相當足夠。

1
2
3
4
5
6
7
8
9
10
11
12
13
<div class="als-container" id="als-container_0" data-id="als-container_0">
	<div class="als-viewport" data-id="als-viewport_0" style="width: 800px; height: 328px;">
		<ul class="als-wrapper" data-id="als-wrapper_0" style="width: 4800px; height: 328px;">
			<li class="als-item" data-linkid="-6" id="als-item_0_0" style="left: 0px;">
				insert hex page
			</li>
			<li class="als-item" data-linkid="-1" id="als-item_0_0" style="left: 0px;">
				insert hex page
			</li>
			...
		</ul>
	</div>
</div>

根據原本的 jquery.als-1.6.js 並沒有提供跳轉的操作，也就是說不能直接 shift 到指定位置，只能倚靠往左和往右的觸發，因此特別自己增加了 data-linkid 為操作手段。

hexo blog plugin

我已經把產生方式寫在 hexo-tag-oj 裡頭，下載使用 hexo-tag-plugin

不過相關的 js 還有 css 要自己擺放，請參考上面的描述項目。

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
{\% ojblock hex \%}
{
  "album" : [
      {
        "cover": {"title": "<h4>THEME</h4><hr /><p>Stephanie Dola</p>", "class": "hex-1"},
        "photo": [
          {"imgur": "http://i.imgur.com/yIoACHc.gif"},
          {"imgur": "http://i.imgur.com/4pzxseN.jpg"}
        ]
      },
      {
        "cover": {"title": "<h4>THEME</h4><hr /><p>萌～萌～哒～</p>", "class": "hex-2"},
        "photo": [
          {"imgur": "http://i.imgur.com/YSmWA3g.gif"},
          {"imgur": "http://i.imgur.com/5IHR8bQ.gif"}
        ]
      },
      {
        "cover": {"title": "<h4>THEME</h4><hr /><p>其他</p>", "class": "hex-3"},
        "photo": [
          {"imgur": "http://i.imgur.com/vpKzynV.gif"},
          {"imgur": "http://i.imgur.com/rctEEyS.gif"}
        ]
      }
  ]
}
{\% endojblock \%}

#

Read More +
手札日記

專注于足下，才能走得更遠

足下

仔細想想，已經要準備迎來大四生活，也差不多是要決策是否要讀研究所的時候，而我除了 UVa 外，網頁 Web 語言也稍微懂了基礎、Linux 指令也摸了幾下、hacker 技巧也在旁圍觀了不少，算是大三這一年一大進步，過往幾年都沒有這麼快速進展過。

之前張媽媽教授說的 「學得廣不如學得深」 學廣很難，但是又稱不上獨樹一幟的可用之才，取代性難易將決定薪水 (不過分紅好像也是另外一個重點)。這一年到處摸摸也大概自己擅長什麼項目，我想目前認為可以讀讀書上的內容理解，但總是沒有記在心裡，說到印象深刻的大多都是偏向數學類型，其他記不牢的，既然書本可查，為何要記。

其實如果說學得深，寫了這麼久的 ACM-ICPC 題目，是那種拿不上檯面的新手版 C/C++，而且既然有出題必然存有代碼解答，發現擅長的不是當下想到相同的解法，而是把大家給予的解法找到一個更精簡更快速的寫法 (code) 和做法 (think) 。因為我可以沒有壓力地慢慢寫，直到了現在 UVa 2400+ ，沒有準備比賽的壓力，已知無法成為相同能力之人，那就成為平凡人最強。

這個暑假看了什麼

根據距離上一次截圖的情況看來，說說中間的空白時期

日劇

《花子與安妮》

翻拍一部小說而來，描述一個翻譯家花子的故事，至於安妮的部分遲遲沒有解釋是誰，更有網友戲稱為 《花子與貴安》 ，因為花子 (從演員 吉高由里子 飾演少女到婦女時期的時候)，不斷地講了一句有一句的貴安 (有問候和祝福之意，用於語末助詞)，看到 “安” 一字的出現，難免會認為是問好之意，不斷地講問候人家是否安好，還真是莫名其妙。

這個翻譯家花子，出身農稼家，但是比其他兄弟姊妹愛讀書 (雖然還看不懂文字)，因此受到花子父親送到東京修女學院採用 受助生 (意思差不多是公費生) 讀到成年，就讀的時候萬萬沒想到整間學校還有規定一定要講英文的日子 (傳教士不意外)，沒錯，為什麼我只是想來這裡讀書，為什麼還要受到 英文災難 ，又不是千金大小姐從小接觸英文，一上課就學這麼難的，還是學字母吧！英文寫作的時候，還偷偷修女的情書交作業呢。

因為我對英文一竅不通，為什麼要遭遇這種 ... 我只是想要飽讀自己最喜歡的書才來這裡的啊！

其實看了前面還挺有感覺的，看到英文不好的人也可以這樣翻身，但是最後就只剩下英文，可謂 窮得只剩下英文 ，不禁流涕。在 bilibili 站上撥放的 《花子與安妮》每一集都會出現 舔脖君 ，看著片頭吉高穿著和服露出修長的脖子，想必這位仁兄也按耐不住，繼續看下去也算是打發打發時間，畢竟沒有 《海女》 演得這麼活潑歡樂。

你已經成功讓我受盡恥辱了

《最高離婚》

這一部在描述兩對夫妻離婚、沒有結婚的夫妻卻要離婚，說到劇情最有趣的就是 瑛太 飾演的處女座男生，各種歡樂呢！

** 「小哥，兩個人吃的是飯，一個人吃的是飼料！」 **大家一起來吃飼料吧！每天為了吃飼料而出門，為了飼料而賺錢。

劇情起伏看似不大，笑點藏得相當豐富，建議想要細細品味的人才去看， 官方吐槽 也相當不錯呢 wwwwww，推薦給學長們看，果然生活情調和品味有所差別，導致看這部日劇的感想也是天差地遠。瑛太後來跑去當宅宅迷鄰家女生的偶像真的是太有同感了。

歌詞「備受欺凌 死宅在家 遊戲中心 是我歸宿 廢材如我 心懷大志 即便受辱 早成習慣 敬請自便 电电电电电电电电 电电电电 电電波組.inc 今天依舊 慌亂掙扎 周而復始 輪迴進化 以吾個性 奪取天下 生存之地 蕩然無存 只為夢想 現在點燃 電波激情 …」

「比起聰明有知識的人，能讓別人振作起來的人 才更有價值」

「總是問別人精神好不好的人，真的很招人煩，也有人平常就無精打采的，人家明明無精打采也活得很好，你就別用所有人都要神采奕奕的標準去過問別人的生活。」

「這裡就是我的容身之所啊！」

《同窗生》

被網友戲稱 中年偶像劇 (相對少年偶像劇，倒不是大陸《鄉村愛情》那種狗血劇情)，比起隔壁棚《晝顏》相當純情多了！中年戀愛劇場似乎在日本需求也越來越高，很多日劇也開始因為演員而提高平均年齡了？

說來看這一部，一部分是因為其中兩個的演員來自於日劇《First Class》(澤尻龍英華的復出之作)，蠢萌情侶組，感覺萌萌哒！原來國中同學到了 40 歲的時候，還可以這麼逗趣自在地聊天，甚至談戀愛？！多麼青澀的青春綻放啊，都有各自的孩子，仍然不以此為障礙，完成國中未完成的旅程。

嗚嗚，國中就有好感的對象到底哪裡找，國中同學會在數十年後還能召集得到不少人來聚聚，仔細想想還真不科學。也許在我這一代已經是不太可能，各自忙各自的，高中同學會去過幾次，一群台清交活得如此耀眼，前途似錦的人生就等著他們。同學會總是如此地意外連連，可以看到其他人不同的突破和演進。

「像阿遼，一直成績很好的人也會有某種人性的缺陷的。」

「你不覺得摩天輪和人生很相似嗎？一點一點地移動著，往上爬著，然而迎來頂峰，攀上最高點，之後就一路向下」

一路上成績不錯、事業有成、家境不錯的遼介，即使結了婚，卻沒想到原本妻子滿腦子只為了孩子希望丈夫能夠安穩地賺錢讓孩子上更好的學習環境，一昧地被認為只是一個賺錢機器的遼介而言，無非是一個歸不得的地方，沒有自己想要活著的家庭，於是跟蠢萌的主編 (First Class 的主編) 談情說愛，因為彼此都有工作，又有不少共同好友，交往起來沒有壓力，使得彼此之間吸引力非凡。未來將要怎麼活著，真的是一大決策。而俺們的男主角卻是從大公司辭職，因為自己原本的妻子在同一家公司上班跟同事出軌而離婚，繼承父業的洗衣店小老闆。

** 「正因為開的是洗衣店，讓各種東西付諸流水才是我所擅長的！」 **

然後遇到曾經一起 私奔 的女主角，聽到就有點犯了 FFF 團的怒火怎麼可以曾經有這一段經驗，俺曾經在網路上交網路女友 (性別不談) 的經驗也是不錯，但是沒有實體還是有段落差啊！故事還在連載中，敝人覺得還可以，平淡風味小品誠心推薦。

動畫

《歡迎加入 NHK》

這一部可是宅出頭的故事，門不出戶的宅宅如何走出門工作，中間經歷過了什麼心路歷程，某方面來說還真是遇到各種貴人 (不離不棄的基友、曾經嚮往的 學姊 以及最重要的小岬指導員)，「人啊，只要餓了就會想出去工作，如果不愁基本需求的話，就會以最低需求的方式活下去。」

「足不出戶轉眼已有三年，馬上就要邁向第四年了！」

「要是靠祈禱就能治好家裡蹲的話就不用這麼辛苦了。」

「現在的你是很醜陋、沒出息、又骯髒。」

「我也很想過很普普通通的人生就好了啊。」

我想，很多人也許不明白 「為何而宅，而你不宅？」 ，不只有身理上的宅，心理層面也可以宅，如果知道未來沒有目標，那為什麼要奮鬥？如果不能對社會有所貢獻，活著又是為了什麼？沒有皮膚的那一層面紗，更沒有如聖人般的個性，那到底又是要怎麼與世間接軌。女主小岬想要藉由指導男主走出 NEET 來得到對自己的救贖， 「這麼做，感覺至少還有人需要我」 小岬的這一套心聲不斷地在心裡溢滿，不擅長的事情太多，總覺得沒人需要我，就算有人需要我，但覺得自己做得不夠好，會帶給別人失望和困擾。

「沒想到 ... 會在這種地方迎接我人生的結局啊」

「可是 ... 能夠跟她(學姊)一起的話，也就無所謂了。」

「因為就算真的有神明存在，祂也一定是壞人。」

** 學姊 **「我們的人生到底有什麼意義呢？」

「祝你幸福, 學姊」

「我是個超級御宅族啦」

「去死吧，噁心的御宅混蛋，像你們這種爛人都從世上消失吧！」

故事結尾不是相當耀眼的一頁，雖不是耀眼的光輝，起碼也是有一片曙光在， 「昏暗不明的光芒比起什麼都沒有都好。」 擷取自《The Knick 尼克病院》，何等樂觀的說法！上一句的對話是 「世間上沒有變得更好的解藥」來自於莎士比亞。看這一部動畫，甚至還覺得比不上男主，沒遇過那樣的 學姊 ，更別說小岬這般救世主的存在，其實學姊是個外貌不錯，性格卻相當低沉的人，正因為外貌的讒言不在少數，祝學姊幸福，找到一個不錯的伴侶 (;´Д`)

經歷了自殺派對、網路沉迷、GAL GAME 製作、外出指導、受到老鼠會的詐欺 … 等，故事不少社會寫實，小岬果然是半翼天使，也好想跟天使簽訂契約啊。裡面不離不棄的基友跟著學長 (男主) 一起奮鬥一段時間，也教會了男主如何不被網路性別給欺騙，這麼感人的反串腳色，真的不推不行。

《妄想代理人》

這一部是今敏作品，主要好看的是第八集，其他的主題比較偏向意識流，這部動畫本身也是一部妄想，當妄想成為謠言，每個人就會將自己的不愉快找一個妄想的代理人來宣洩，這也是最主要的含意，代理人本身不存在，但是人們把妄想投到同一個不存在的實體，久而久之，大家都誤信了這個代理人的存在。

裡面最有趣的還是片頭、片尾曲，詭異的風格稱不上難聽，搭配動畫顯得相當有深意，也許偷偷被暗示了什麼呢。今敏導演已經過世了，受到癌症的折磨，不得不把其中一部作品中斷製作，今敏的遺書寫得相當有內容，有趣的人可以去查閱一下，這讓我想到 《歡迎加入 NHK》 裡頭也一段名人遺書的對談，寫了《人間失格》的太宰治到底寫了什麼樣的遺書呢？

「要和大家一起死」

「世道不濟，連死神都忙得顧不上我們了」

「那麼 ... 終於要 ...」

啊啊啊啊

喂喂，下次要怎麼死呢？

電影

《莫札特》

一部自傳類型的電影，描述音樂神童的莫札特一生以及看似基友卻心懷忌妒的朋友，莫札特雖然過得相當不懂禮數、相當荒誕的生活，但也是因為這樣的緣故，能夠創作出出格的作品，最後因為長時間沒有曬到太陽又加上過勞而死，在寫完最後一部委託歌曲而睡眠中死去。

不得不說這一部片長有點久，真羨慕他的一生可以被後人拍篇成電影，他所做的各種曲目沒有任何的草稿備份，總是一次完成所有音調，為了過著他荒誕糜爛的生活，他只好不斷地創作歌曲來換取那微薄收入，但是很不幸地能知曉他能力價值的人很少，怕得罪上頭的人而不敢接受新穎的曲風和內容，當下能不必言諱的只有莫札特，知音者少啊！只有那心懷忌妒的朋友想要收他的創作為己用能理解他的好。不得不說， 「最討厭你的人，有時反而是最理解你的人。」

就好像是生理上的慾望，卻又不給我施展的才華

給我能力，請求你

笑我，把我的平庸展現給大家看

你也差不多啊？你只會在吃東西時才離開房間

我有我的才能，而你有的是財富

這個暑假做了什麼

老妮可說的 AI 對話部分，真是覺得相當困難去完成呢。

UVa 2200-2400

兩個月衝個將近 200 題大致上沒有問題，倚靠前人們留下的足跡，我還能更強。當然原本是想要做點別的事情，畢竟有時候每天寫個 5 ~ 10 題，整天就這樣沒了，上司老妮可提議要不要繼續寫到 2400，雖然已經被喊到 3000 題，不過仔細想像除了精盡人亡外，根本突破不了數學和題目理解的障礙，時間上似乎也辦不到，總之還是到了最初曾提議的 2400。來到了 World List Rank 10 (個人認為當作是宅排行也不錯，畢竟題目不難，慢慢解還是相當容易的，恆心是難的)。

Web Design

這也是老妮可的提案，因此也做來玩玩，不少也都是套用加修改，從基礎打起不太可能。談到設計，我的演化速度還真是慢，總是創造出非常人使用的格式和操作。

六角形的圖片廊道，一開始給定的是提案是做出一個圖片展示櫃，可是想到要放在這個 hexo 部落格，要做到類似的相簿功能其實是很麻煩的，還有必須要關聯 generator 的產生方式，才能製作出相對的 static website，那只好將項目弄成單獨一頁，而這一頁要怎麼製作其實很難捉摸。失敗的設計總是這樣子開始的。

由於圖片量太大的話，變成一開始載入速度會太慢，因此找來了 lazyload.js，但是跟展示窗口銜接上仍有一些問題，無法適時地反映操作，所以需要 call back 操作，否則圖片會載入失敗。再者是原本六角 CSS 問題，找來網路上提供的 CSS，發現更換大型圖片的時候，會造成圖片顯示不正常，因此在這一塊費時了相當長的時間來符合預期的操作。

此項目已經放在我的 Github 上面，同時你也可以在這個 blog 上方的 Picture 中看到 demo，萬萬沒想到居然有人願意 Star 標記，真的是相當令人動容啊，從來沒想過有人對於這樣的蠢製作感興趣。

鄰近要大學推研究所的時刻，自己做過什麼作品來說，對於推甄時相當重要，一直都沒有好好整理過自己做過什麼，有多少能拿出檯面的項目，現在發現除了 ACM 解題和曾經幫別人寫的作業以外，沒有幾項可以吸引到人的。一樣做一個 hexo tag plugin，將作品展示櫃用一個 generator.js 的方式，將展示櫃內容呈現出來，傳入的方式為 json。同樣地，你可以在這個部落格上方的 Works 看到相關作品介紹。

中斷的虛擬機課程

這個課程的理論並不難懂，假設環境在 Ubuntu 上的 KVM，進行不中斷的 migration 操作，多個電腦共用同一個硬碟操作，將其中一台機器的記憶體內容 copy 到另外一台機器上，然後將服務傳給另一台工作，這樣的好處在於可以不長時間中斷服務。

而我們採用的 project 就是要測試這個不中斷的服務，因此需要一個 web application，寫了一個 nodejs 寫的 upload server，如果要用之前寫的 travis reporter 提供的 web socket 來完成 chat room 也是可以的，不過最麻煩的還是在於虛擬機的架設，要用橋接器 bridge 來連入實體機上的虛擬機，由於有網路層面的操作，分配 ip 的個數造成相當大的困擾，通常伴隨著子網域的操作會比較方便，這樣不中斷服務才能更為明顯，更新 router、DNS 的時間才會縮短，才不會造成 TCP 嘗試時間過長而中斷。

但是這樣的環境相當難架設，少說幾乎要 3 個 ip 和 2 台機器，沒有實驗室的我而言，生出這樣環境是相當困難的，在此之前已經將 web application 到位完成，隨後跟著同組的學長一層一層突破網卡和 VM 設定問題，但是之後一位學長研究所換學校，而另一個跟著教授指導跑去忙產學合作，於是我選擇放棄接下來的製作。

雜事小記

七月

這一個月還在上虛擬機課程，每隔一到兩天上一次課，剩餘時間都在寫 UVa、blog 設定、 妮可 project、右下角 ukagaka 的設計，娛樂就是看動畫、日劇、晚上出門跑步。過著相當單調的生活。暑宿在學校，在只有一個人申請的房間內度過，沒有任何學長或者是同學在附近，學長們大部分都畢業搬走，剩我一個人呢。

真羨慕幾位學長可以免役不當兵，於是學長就去科技公司上班，有幾次還來問一下公司代碼的製作和撰寫，其實我會的只有演算邏輯和基礎 STL Library 使用，能幫上忙的項目相當少，也許充當工程師的黃色小鴨 (找一個定物進行描述問題本身，然後說到一半自然會有解答) 吧。

八月

已經五個多月沒有回家，這時候我姊叫我去東華大學工讀個五天，工讀的內容就是教師研習活動的相關事宜，只是沒想到大部分教師都是我的高中老師啊！國文、數學、化學、生物老師們都來了，這是何等殘酷考驗，這個不成才的傢伙有什麼臉面對老師， 「我已經快撐不下去了」 不斷地在心中默念。

跟著原本東華大學的大哥大姊們一起工作，沒想到東華大學居然有所謂的五年大學碩，也許是因為科系問題，大四就可以預讀研究所課程，再讀一年就可以碩班畢業，神秘的設計，對於工作還是很笨拙，腦子太久沒做生活操作，即使是泡茶端點心都會有問題呢。

在家生活兩個星期，下學期打算住外面了，宿舍不好抽也怕室友。兩個星期後回到中央，發現暑宿宿舍居然有人來住？偷住？房間凌亂的曾度難以想像，這實在是太可怕了。目前住在學校外面，一個人也要過得萌～萌～哒！

別校同學問道今年要不要參加 NCPC ，這讓我遲疑了一會，要找小夥伴呢，真怕露出本性和傷害別人之間的感情呢。受到比賽的創傷後，為什麼還要不斷地虐待自己啊。有小夥伴 (如 inker 神) 願意包容我的話，我當然義不容辭加入，來找我吧 (つд⊂)

為什麼

感謝

  • 調教兼指導－老妮可

附錄

『no medicine in the world can do thee good』
『even a dim light is better than no light at all』

It's where I live.

就算興奮也得忍住

不行，會興奮的

Read More +