手札日記

服務學習心得指南系列 曾經何時 那份信任

真實短篇

補繳外出活動證明走向服務中心，骨氣勇氣向工讀生說道
「上次繳交的證明是活動單位發錯了 … 這是一份新的。」

工讀生轉向交給後頭的領導，在那談了不久，我開始心有點緊張，也許是該結束了吧，那兒的領導走了過來，緩慢地說

「關於這份參加證明，後來有打電話去問，確定沒錯。」
「恩恩，我這個是補繳的。」

沒想到他們還主動聯絡，也許我要對它們改觀了，查證方面卻是格外的嚴格。但在百般愉悅之下，馬上迎來沉重的第二段話

「但是你寫的心得是抄網站上的，有同學參加那活動且心得寫得不錯。」
「沒這樣的吧，我根本沒注意活動官網上寫什麼。」

為什麼，難道就這樣子了嗎？原來我已經只剩下宣傳式海報的心得流了嗎？之前在辦公桌上，看到有人用字體 8 印出不到幾個字的心得，原來我就只有這樣啊。

「如果你有去的話，應該就能寫比較多吧，這個都是抄網站上的，這樣不行，要不然我開給你看看。」
「算了，好吧。」

挫折感是如此地沉重，我不想寫了，到底什麼是心得、至今我又寫了什麼。沮喪地走出服務台，沒想到走出這棟建築物是如此地困難 … 原來天已經這麼黑了 …

「不對！文章我有寫到動漫、美劇，這官網上不會有的吧。」

趕緊回頭再問個清楚，回到服務台招著手問「等等，你說的網站是哪一個？」

「正在印那個網站下來。」

聽著那列表機刷刷的聲音，已經預想到如果不在那個時間點回來，我的心得就會隨著那幾張紙釘起來拿去退件區存放。然後，曾經存在過的證明就消失了。

遞著剛印有網站內容的紙張給我「你看吧，這就是那個網站。」

「那是我的部落格 …」

結論

這件事情他們也很辛苦，畢竟這個時間點的心得大多都是抄襲，平常不參加活動的宅宅為了畢業去弄心得繳交來獲得認可，而我就是其中一個。

非常不屑 服務學習時數 制度，不敢說自己有多麼深有感觸，也不能說具有完善的能力，這樣的制度一開始的用意是好的，相較於其他大學是 完全自主 ，別的大學靠著修課參與就會滿足時數需求，中央大學是全台國立大學中最特別的一個。

曾經訪問過服務學習辦公室這件事情「有多少人會因為這個不能畢業」他們是這麼回答的「微乎其微」這此我又問了一個問題「心得審核中，聽說不少劣質內容也可以申請成功」他們是這麼回答的「這樣的事情應該是沒有，我們都有嚴格把關。」當時基於信任機制，就這麼相信他們說出的內容寫下報告繳交。

台灣之所以開始舉行「服務學習」為畢業門檻，原因是學老美那一套「 它是一種『服務』與『學習』並重的經驗教育方式 」那台灣現況又是如何呢？大約有五種類型如下描述

  • 有大學提供課程規劃完成時數認證
  • 有大學提供導師課程，師生一起規劃
  • 有大學不存在服務學習時數為畢業門檻
  • 有大學不拿服務學習時數為畢業門檻，累積時數換通識課程學分
  • 有大學提供全自主完成時數認證

舉辦服務學習需要心力跟人力，因為要認證 成長 情況，所以內容就相當大眾才能被認可吧，寫一些奇葩的內容會被給予什麼評語呢？成腔濫調的成長是值得寫下的嗎？基於每一個人對自我成長的觀點不同，認可這件事情就成了奇怪的制度，自我的成長卻要由別人來劃分定奪。

就我看來，實際運行就是制度上，麻痺自我的簽名參加，就好像做了服務學習，若去問服務中心就會得到回答「 這是自己選的，也有不少人參加活動是相當用心參與 」反正在某些情況躺著過也是被認可的，如果要去就要做到好，要是預期做不好參與，那也沒有必要麻痺欺瞞自己去參加。如果四年內學到的是欺瞞制度，這股風氣就會延長吧。

這又讓我想到有門課「 比起內容更注重報告 」程式做了什麼不重要，即便你們做了很少，報告看起來很有料就是加分。問了其他學校的助理教授看法「報告吸引錢的方法，實作並不能。」心中頓悟，原來世界並不是想像中的理想。

Read More +
解題區/解題區 - 其他題目

TIOJ 1475 錄製專輯 (Record)

Problem

Jolin 是個愛唱歌的小孩，每次總喜歡邊唱邊用電腦把自己的歌聲錄下來，因此長久下來，在她的電腦裡，已儲存了為數不小的個人歌唱作品。由於耶誕節快要到了，為了準備一份特別的耶誕禮物給爸爸，Jolin 準備從電腦中儲存的個人歌唱作品，挑選幾首歌製成一張個人專輯 CD。由於每張 CD 的容量有限，而Jolin 的個人歌唱作品早已遠遠超過一張 CD 可收錄的容量，因此 Jolin 希望你可以幫她想辦法，讓她所製作的專輯中，能有數目最多的歌曲（請注意：每一首歌只能被收錄一次），同時必需剛好裝滿整張 CD，不留下任何未使用的空間。

Sample Input

1
2
3
4
5
6
5
10 50 30 70 60
80 
5
10 50 30 70 60
20

Sample Output

1
2
2 4
0 0

Solution

實作 C++ 簡單的加法、乘法大數，直接把別提的拿過來用。

套用 0/1 背包問題，額外增加大數紀錄方法數，最後乘上 $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
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
#include <bits/stdc++.h> 
using namespace std;
class BigInteger {
public:
    vector<long long> v;
    long long MAXC;
    BigInteger(int x = 0) {
        v = vector<long long>(10, 0);
        v[0] = x;
        MAXC = 100000000;
        normal();
    }
    BigInteger operator+(const BigInteger &x) const {
        BigInteger r(0);
        r.v.resize(max(v.size(), x.v.size()) + 2, 0);
        for (int i = 0; i < v.size(); i++)
            r.v[i] += v[i];
        for (int i = 0; i < x.v.size(); i++)
            r.v[i] += x.v[i];
        r.normal();
        return r;
    }
    BigInteger operator*(const BigInteger &x) const {
        BigInteger r(0);
        r.v.resize(v.size() + x.v.size() + 2, 0);
        for (int i = 0; i < v.size(); i++) {
            if (v[i] == 0)
                continue;
            for (int j = 0; j < x.v.size(); j++)
                r.v[i+j] += v[i] * x.v[j];
        }
        r.normal();
        return r;
    }
    void normal() {
        for (int i = 0; i < v.size(); i++) {
            if (v[i] >= MAXC) {
                v[i+1] += v[i] / MAXC;
                v[i] %= MAXC;
            }
        }
        int s = (int) v.size() - 1;
        while (s > 0 && v[s] == 0)
            s--;
        v.resize(s+1);
    }
    bool isZero() const {
        if (v.size() > 1)   return false;
        return v[0] == 0;
    }
    bool operator<(const BigInteger &x) const {
    	if (v.size() != x.v.size())
    		return v.size() < x.v.size();
    	for (int i = v.size()-1; i >= 0; i--) {
    		if (v[i] != x.v[i])
    			return v[i] < x.v[i];
    	}
    	return false;
    }
    bool operator==(const BigInteger &x)  const {
        if (v.size() != x.v.size())
            return false;
        for (int i = v.size()-1; i >= 0; i--)
            if (v[i] != x.v[i])
                return false;
        return true;
    }
    void print() {
        printf("%lld", v[v.size()-1]);
        for (int i = (int) v.size() - 2; i >= 0; i--)
            printf("%08lld", v[i]);
    }
};
int main() {
    int N, M, A[128];
    BigInteger f[128] = {};
    f[0] = BigInteger(1);
    for (int i = 1; i < 128; i++)
        f[i] = f[i-1] * BigInteger(i);
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        scanf("%d", &M);
        
        sort(A, A + N);
        int dp[10005] = {};
        BigInteger dp2[10005] = {};
        dp2[0] = BigInteger(1), dp[0] = 0;
        for (int i = 0; i < N; i++) {
            int x = A[i];
            for (int j = M; j >= x; j--) {
                if (dp[j] < dp[j-x] + 1 && !dp2[j-x].isZero())
                    dp[j] = dp[j-x] + 1, dp2[j] = BigInteger(0);
                if (dp[j] == dp[j-x] + 1 && !dp2[j-x].isZero())
                    dp2[j] = dp2[j] + dp2[j-x];
            }
        }
        int a = dp[M];
        BigInteger b = dp2[M] * f[a];
        
        printf("%d ", a);
        b.print();
        puts("");
    }
    return 0;
}
/*
5
10 50 30 70 60
20 
*/
Read More +
解題區/解題區 - 其他題目

BZOJ 2038 小 Z 的袜子

Problem

給一個序列，詢問一個區間中任挑兩個數字，這兩個數字相同的機率為何，將答案化簡後輸出。

Sample Input

1
2
3
4
5
6
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output

1
2
3
4
2/5
0/1
1/1
4/15

Solution

莫隊算法命名是莫濤隊伍想出來的，不算是特別算法命名，估計是比賽中想到，目前沒看到英文命名。

莫隊算法處理離線詢問，回答所有答案複雜度為 $O(N^{1.5})$，其中 N 是區間索引值的範圍大小。概念在於分塊處理如下：

  • 對於每個詢問的左端點放置於同一塊去處理
  • 每一次處理一個塊狀的所有詢問
  • 對於同一塊，詢問的右端點嚴格遞增去處理，讓左端點不斷地移動

發現到單獨看左端點指針的移動，約為 $O(N^{1.5})$，只考慮同一塊，最多有 $N$ 的詢問，一個詢問會造成左端點移動 $O(N^{0.5})$。而單獨看又端點指針的移動，約為 $O(N^{1.5})$，由於只會有 $O(N^{0.5})$ 塊，每一塊最慘就是遞增的移動 $O(N)$。

只要轉移區間 (維護區間的答案、計數，例如從 [l, r] 變成 [l, r-1] 的答案維護，把區間左右端點變大變小 1 的轉移計算) 的速度快，則複雜度約為 $O(N^{1.5})$。有不少情況需要 $O(\log N)$ 的其他數據結構維護轉移，複雜度就會變成 $O(N^{1.5} \log N)$，必要時使用塊狀表去作為數據結構進行轉移，當詢問次數 Q 與序列長度 N 呈線性關係，塊狀表支持 $O(1)$ 修改，$O(N^{0.5})$ 統計，那複雜度又能壓回 $O(N^{1.5})$。

能使用莫隊算法的題目，其中也不少能使用持久化結構來完成，若不考慮空間使用量，持久化結構能支持離線預處理、在線詢問。

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 50005;
const int MAXV = 50005;
class Offline {
public:
    struct Event {
        static int PILE;
        int l, r, qid;
        Event(int a = 0, int b = 0, int c = 0):
            l(a), r(b), qid(c) {}
        bool operator<(const Event &x) const {
            if (l / PILE != x.l / PILE)
                return l < x.l;
            return r < x.r; 
        }
    };
    int A[MAXN], N, qsize;
    vector<Event> event;
    vector< pair<long long, long long> > ret;
    void init(int N) {
        this->N = N, qsize = 0;
        event.clear();
        memset(B, 0, sizeof(B));
        for (Event::PILE = 1; Event::PILE * Event::PILE < N; Event::PILE <<= 1);
    }
    void q_add(int l, int r) {
        event.push_back(Event(l, r, qsize));
        qsize++;
    }
    void run() {
        sort(event.begin(), event.end());
        ret.resize(event.size());
        
        int l = 1, r = 0;
        q_stat = 0;
        for (int i = 0; i < event.size(); i++) {
            while (r < event[i].r)	r++, update(A[r], 1);
            while (r > event[i].r)	update(A[r], -1), r--;
            while (l > event[i].l)	l--, update(A[l], 1);
            while (l < event[i].l)	update(A[l], -1), l++;
            long long a, b, len = event[i].r - event[i].l + 1;
            if (len > 1) {
                a = q_stat - len;
                b = len * (len - 1);
            } else {
                a = 0, b = 1;
            }
            ret[event[i].qid] = make_pair(a, b);
        }
    }
private:
    long long B[MAXV], q_stat;
    void update(int x, int val) {
        B[x] += val;
        q_stat += val * 2 * B[x] - 1;
    }
} off;
int Offline::Event::PILE = 16;
long long llgcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int N, M, l, r;
    while (scanf("%d %d", &N, &M) == 2) {
        off.init(N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &off.A[i]);
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &l, &r);
            off.q_add(l, r);
        }
        off.run();
        for (int i = 0; i < off.ret.size(); i++) {
            long long a = off.ret[i].first;
            long long b = off.ret[i].second;
            long long g = llgcd(a, b);
            a /= g, b /= g;
            printf("%lld/%lld\n", a, b);
        }
    }
    return 0;
}
/*
1 1
5
1 1
*/
Read More +
解題區/解題區 - 其他題目

BZOJ 3065 帶插入區間 K 小值

Problem

詢問區間 K 小，額外支持插入一個元素到序列中。

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
10
10 5 8 28 0 19 2 31 1 22 
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27

Sample Output

1
2
3
4
5
6
7
8
9
10
28
2
31
0
14
15
14
27
15
14

Solution

直接修改可持久化塊狀鏈表的那一題 Zerojudge b411 記憶中的序列 2，把可持久化的記憶體拔掉，這樣就免得記憶體需求過大。出題者是想用替罪羊樹掛另一個平衡樹下去做。應該沒設想到塊狀鏈表在此題的速度也不算差。時限 60 秒大概跑了 30 秒，還不比樹套樹來得慢。

因為有插入操作，不管是主席樹還是函數式線段樹 (這兩個應該是同一個傢伙)，都無法辦到，只能靠可插入的平衡樹。

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
#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <limits.h>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 65536;
const int MAXQ = 262144;
class UnrolledLinkedList {
public:
    struct Node {
        vector<int> A, B;
        Node *next, *alias;
        Node() {
            A.clear(), B.clear(), next = alias = NULL;
        }
        Node* real() {
            if (alias)	return alias;
            return this;
        }
        void insert(int x, int val) {
            if (alias) {
                A = alias->A, B = alias->B;
                alias = NULL;
            }
            A.insert(A.begin() + x, val);
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void erase(int x) {
            int val = A[x];
            A.erase(A.begin()+x);
            B.erase(lower_bound(B.begin(), B.end(), val));
        }
        void change(int x, int val) {
            int t = A[x];
            A[x] = val;
            B.erase(lower_bound(B.begin(), B.end(), t));
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void relax() {
            B = A;
            sort(B.begin(), B.end());
        }
    };
    int PSIZE;
    stack<Node*> mem;
    Node* init(int A[], int n) { // A[1:n]
        free();
        PSIZE = max((int) sqrt(n), 2);
        for (int i = 1; ; i <<= 1) {
            if (i >= PSIZE) {
                PSIZE = i;
                break;
            }
        }
        
        Node *u, *v, *head;
        
        head = newNode();
        u = head, v = NULL;
        for (int i = 1; i <= n; i++) {
            if (u->A.size() == PSIZE) {
                u->next = newNode();
                v = u, u = u->next;
            }
            u->A.push_back(A[i]);
        }
        for (u = head; u != NULL; u = u->next)
            u->relax();
        return head;
    }
    Node* newNode() {
        Node* p = new Node();
        mem.push(p);
        return p;
    }
    Node* cloneNode(Node *u) {
        Node *t = u->real();
        Node *p = new Node();
        *p = *t, p->next = u->next, mem.push(p);
        return p; 
    }
    Node* aliasNode(Node *u) {
        Node *t = u->real();
//		Node* p = new Node();
//		p->alias = t, p->next = u->next, mem.push(p);
//		return p;
        return u;
    }
    Node* erase(Node *ver, int x) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->erase(x - l);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* insert(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l-1 <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->insert(x - l + 1, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* change(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->change(x - l, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    int findRank(Node *ver, int L, int R, int val, int threshold = INT_MAX) {
        Node *u, *v;
        int ret = 0;
        u = ver;
        for (int l = 1, r; u != NULL; u = u->next, l = r+1) {
            r = l + u->real()->A.size() - 1;
            if (L <= l && r <= R) {
                ret += upper_bound(u->real()->B.begin(), u->real()->B.end(), val) - u->real()->B.begin();
                L = r + 1;
            } else if ((l <= L && L <= r) || (l <= R && R <= r)) {
                int i = L - l;
                while (i < u->real()->A.size() && L <= R) {
                    if (u->real()->A[i] <= val)
                        ret++;
                    i++, L++;
                }
            }
            if (ret >= threshold)	return ret;
        }
        return ret;
    }
    int find(Node *ver, int L, int R, int k)  {	// kth-number
        int l = 0, r = 100005, mid, t = 0; // value in A[]
        while (l <= r) {
            mid = (l + r)/2;
            if (findRank(ver, L, R, mid, k) >= k)
                r = mid - 1, t = mid;
            else
                l = mid + 1;
        }
        return t;
    }
    Node* mergeNode(Node *u, Node *v) {
        Node *p, *q;
        Node *a = newNode();
        p = u->real(), q = v->real();
        a->next = v->next;
        a->A.insert(a->A.end(), p->A.begin(), p->A.end());
        a->A.insert(a->A.end(), q->A.begin(), q->A.end());
        a->B.resize(a->A.size());
        merge(p->B.begin(), p->B.end(), q->B.begin(), q->B.end(), a->B.begin());
        return a;
    }
    Node* splitNode(Node *u) {
        Node *t = u->real();
        Node *a = newNode(), *b = newNode();
        int n = t->A.size()/2;
        a->next = b, b->next = u->next;
        a->A.insert(a->A.begin(), t->A.begin(), t->A.begin()+n);
        b->A.insert(b->A.begin(), t->A.begin()+n, t->A.end());
        a->relax(), b->relax();
        return a;
    }
    Node* relaxList(Node *ver) {
        Node *a, *b, *u, *v, *t;
        int need = 0;
        for (u = ver, a = NULL; !need && u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) // merge
            	need = 1;
            if (u->real()->A.size() > (PSIZE<<1))	// split
            	need = 1;
        }
        if (!need)
        	return ver;
        stack<Node*> remove;	// static used 
        for (u = ver, a = NULL; u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) {	// merge
            	if (a == NULL)
            		a = mergeNode(u, u->next), b = a;
            	else
            		b->next = mergeNode(u, u->next), b = b->next;
            	remove.push(u), remove.push(u->next); // static used  
                u = u->next;
            } else if (u->real()->A.size() > (PSIZE<<1)) {	// split
            	if (a == NULL)
            		a = splitNode(u), b = a->next;
            	else
            		b->next = splitNode(u), b = b->next->next;
            	remove.push(u); // static used  
            } else {
            	if (a == NULL)	
                    a = aliasNode(u), b = a;
            	else			
                    b->next = aliasNode(u), b = b->next;
            }
        }
        while (!remove.empty()) { // static used  
        	u = remove.top(), remove.pop();
        	delete u;
        }	    	
        return a;
    }
    void debug(Node *head) {
        Node *u = head;
        printf("[");
    	while (u != NULL) {
        	for(int i = 0; i < u->real()->A.size(); i++)
            	printf("%d%s", u->real()->A[i], i != u->real()->A.size()-1 ? " " : " ");
        	u = u->next;
    	}
    	puts("]");
    }
    void free() {
        return ;
        while (!mem.empty()) {
            Node *u = mem.top();
            mem.pop();
            delete u;
        }
    }
} dream; 
int A[MAXN], n, q;
UnrolledLinkedList::Node *ver[MAXQ];
int main() {
    int x, y, v;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        ver[0] = dream.init(A, n);
//		dream.debug(ver[0]);
        int encrypt = 0;
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'I') {
                // insert A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.insert(ver[i-1], x-1, v);
            } else if (cmd[0] == 'Q') {
                scanf("%d %d %d", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                int t = dream.find(ver[i-1], x, y, v);
                printf("%d\n", t);
                encrypt = t;
                ver[i] = ver[i-1];
            } else if (cmd[0] == 'M') {
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.change(ver[i-1], x, v);
            }
//			dream.debug(ver[i]);
        }
    }
    return 0;
}
/*
5
1 2 3 4 5
9999
4 1 5 2
1 2 1
4 1 5 2
0 1
4 1 5 2
2 1
1 0 5
3 3 9
4 1 1 1
*/
Read More +
解題區/解題區 - Zerojudge

b412. 記憶中的并查集

Problem

維護一個並查集的操作，並且支持版本回溯。

  • 合併兩個堆
  • 詢問兩個元素是否同堆
  • 版本回溯

Sample Input

1
2
3
4
5
6
2 5
2 1 2
1 1 2
2 1 2
1 1
3 0 3

Sample Output

1
2
3
0
1
0

Solution

持久化概念，相當於維護 parent[] 陣列的版本，這一點可以利用可持久化線段樹來維護。

並查集的查詢功能不修改 parent[] 陣列，合併操作卻有可能修改數個 parent[]，為了降低記憶體用量，盡可能少用路徑壓縮這個技巧，雖然在一般並查集都會使用這個來加速，否則很容易變很慢，是因為持久化是會拉低速度，因為持久化需要 $O(\log N)$ 的時間去更改 parent[]，單筆路徑壓縮長度為 $M$ 個點，需要 $O(M \log N)$ 的調整，$M$ 在並查集中是常數類。

詢問不多時用啟發式合併就好，將小堆的元素合併到大堆中。效能會比較好。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
const int MAXN = 3000000;
class SegementTree {
public:
    struct Node {
        Node *lson, *rson;
        pair<int, int> val;
    } nodes[MAXN];
    int nodesize, L, R;
    Node* init(int l, int r) {
        nodesize = 0;
        L = l, R = r;
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        if (nodesize >= MAXN)
            exit(0);
        return &nodes[nodesize++];
    }
    Node* cloneNode(Node *p) {
        if (nodesize >= MAXN)
            exit(0);
        Node* u = &nodes[nodesize++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        u->lson = u->rson = NULL;
        if (l == r) {
            u->val = make_pair(l, 1);
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, pair<int, int> val, int l, int r) {
        Node *u = cloneNode(p);
        if (l == r) {
        	u->val = val;
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, val, l, mid);
        	else
         		u->rson = change(p->rson, x, val, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, pair<int, int> val) {
        return change(p, x, val, L, R);
    }
    pair<int, int> find(Node *ver, int x, int l, int r) {
        if (l == r)
        	return ver->val;
        int mid = (l + r)/2;
        if (x <= mid)
            return find(ver->lson, x, l, mid);
        else
            return find(ver->rson, x, mid+1, r);
    }
    pair<int, int> find(Node *ver, int x) {
        return find(ver, x, L, R);
    }
    // disjoint set
    pair<int, int> findp(Node *ver, int x) {
        pair<int, int> p = find(ver, x);
        return x == p.first ? p : findp(ver, p.first);
    }
    Node* joint(Node *ver, int x, int y) {
        pair<int, int> a = findp(ver, x);
        pair<int, int> b = findp(ver, y);
        if (a.first == b.first)
            return ver;
        Node *u = ver;
        if (a.second > b.second) {
            u = change(u, b.first, make_pair(a.first, b.second));
            u = change(u, a.first, make_pair(a.first, a.second + b.second));
        } else {
            u = change(u, a.first, make_pair(b.first, a.second));
            u = change(u, b.first, make_pair(b.first, a.second + b.second));
        }
        return u;
    }
} segTree;
const int MAXQ = 262144;
SegementTree::Node *ver[MAXQ];
int main() {
    int n, m;
    int cmd, x, y, v;
    while (scanf("%d %d", &n, &m) == 2) {
        ver[0] = segTree.init(1, n);
        int encrypt = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d", &cmd);
            cmd ^= encrypt;
            if (cmd == 0) { 		// back
                scanf("%d", &v);
                v ^= encrypt;
                ver[i] = ver[v];
            } else if (cmd == 1) {	// joint
                scanf("%d %d", &x, &y);
                x ^= encrypt, y ^= encrypt; 
                ver[i] = segTree.joint(ver[i-1], x, y);
            } else if (cmd == 2) {	// find
                scanf("%d %d", &x, &y);
                x ^= encrypt, y ^= encrypt;
                pair<int, int> a = segTree.findp(ver[i-1], x);
                pair<int, int> b = segTree.findp(ver[i-1], y);
                int t = a.first == b.first;
                printf("%d\n", t);
                ver[i] = ver[i-1];
                encrypt = t;
            } else {
                puts("WTF");
                return 0;
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b411. 記憶中的序列 2

Problem

動態區間 K 小，有四種操作

  • 插入元素
  • 刪除元素
  • 修改元素
  • 版本回溯
  • 詢問某個區間的第 K 小元素

Sample Input

1
2
3
4
5
6
7
8
5
1 2 3 4 5
5
4 1 5 2
3 0 3
6 3 7 0
1 0
5 0 4 3

Sample Output

1
2
3
2
1
2

Solution

每次操作最多增加 $O(\sqrt{n})$ 記憶體，需要針對節點作抽象化，修改節點時再進行實體化，如此一來不用針對搜索路徑上的每一節點都進行複製，一般持久化平衡樹進行時，會直接複製整個節點，但塊狀鏈表若是複製下去會退化成時間、空間都是 $O(n)$ 的情況。

詢問時仍然需要二分搜索答案，看答案是否符合 K 小元素，也就是說要得到某個元素在區間中的排名。

塊狀鏈表代碼很醜，看看就好。如果需要支持修改、增加元素的區間 K 小，雖然複雜度高，但常數小、記憶體快取優勢，速度不比二元樹類型的資料結構來得慢，不管需不需要持久化塊狀鏈表都是這類型不錯的選擇。

另解

假設詢問為 $Q$ 個，聽說可以用區間 $[1, 2NQ]$ 的線段樹之類的超大區間線段樹，必要的探訪時進行開花 (將子節點打開)，利用標記計算相對位置來進行查詢。相對位置計算大概會在邊緣情況崩潰。

至於柳柳州提到的替罪羊樹是樹套樹下去持久化，每一個節點表示一個區間，接著在節點中建造一個平衡樹來查找區間 K 小元素。這樣的做法一樣需要二分搜索答案。但塊狀鏈表在速度跟記憶體都贏了，因為樹套樹的常數比較大，增加的記憶體也多。

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
#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <limits.h>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 32767;
const int MAXQ = 131072;
class UnrolledLinkedList {
public:
    struct Node {
        vector<int> A, B;
        Node *next, *alias;
        Node() {
            A.clear(), B.clear(), next = alias = NULL;
        }
        Node* real() {
            if (alias)	return alias;
            return this;
        }
        void insert(int x, int val) {
            if (alias) {
                A = alias->A, B = alias->B;
                alias = NULL;
            }
            A.insert(A.begin() + x, val);
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void erase(int x) {
            int val = A[x];
            A.erase(A.begin()+x);
            B.erase(lower_bound(B.begin(), B.end(), val));
        }
        void change(int x, int val) {
            int t = A[x];
            A[x] = val;
            B.erase(lower_bound(B.begin(), B.end(), t));
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void relax() {
            B = A;
            sort(B.begin(), B.end());
        }
    };
    int PSIZE;
    stack<Node*> mem;
    Node* init(int A[], int n) { // A[1:n]
        free();
        PSIZE = max((int) sqrt(n), 2);
        for (int i = 1; ; i <<= 1) {
            if (i >= PSIZE) {
                PSIZE = i;
                break;
            }
        }
        
        Node *u, *v, *head;
        
        head = newNode();
        u = head, v = NULL;
        for (int i = 1; i <= n; i++) {
            if (u->A.size() == PSIZE) {
                u->next = newNode();
                v = u, u = u->next;
            }
            u->A.push_back(A[i]);
        }
        for (u = head; u != NULL; u = u->next)
            u->relax();
        return head;
    }
    Node* newNode() {
        Node* p = new Node();
        mem.push(p);
        return p;
    }
    Node* cloneNode(Node *u) {
        Node *t = u->real();
        Node *p = new Node();
        *p = *t, p->next = u->next, mem.push(p);
        return p; 
    }
    Node* aliasNode(Node *u) {
        Node *t = u->real();
        Node* p = new Node();
        p->alias = t, p->next = u->next, mem.push(p);
        return p;
    }
    Node* erase(Node *ver, int x) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->erase(x - l);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* insert(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l-1 <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->insert(x - l + 1, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* change(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->change(x - l, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    int findRank(Node *ver, int L, int R, int val, int threshold = INT_MAX) {
        Node *u, *v;
        int ret = 0;
        u = ver;
        for (int l = 1, r; u != NULL; u = u->next, l = r+1) {
            r = l + u->real()->A.size() - 1;
            if (L <= l && r <= R) {
                ret += upper_bound(u->real()->B.begin(), u->real()->B.end(), val) - u->real()->B.begin();
                L = r + 1;
            } else if ((l <= L && L <= r) || (l <= R && R <= r)) {
                int i = L - l;
                while (i < u->real()->A.size() && L <= R) {
                    if (u->real()->A[i] <= val)
                        ret++;
                    i++, L++;
                }
            }
            if (ret >= threshold)	return ret;
        }
        return ret;
    }
    int find(Node *ver, int L, int R, int k)  {	// kth-number
        int l = 0, r = 100000, mid, t = 0; // value in A[]
        while (l <= r) {
            mid = (l + r)/2;
            if (findRank(ver, L, R, mid, k) >= k)
                r = mid - 1, t = mid;
            else
                l = mid + 1;
        }
        return t;
    }
    Node* mergeNode(Node *u, Node *v) {
        Node *p, *q;
        Node *a = newNode();
        p = u->real(), q = v->real();
        a->next = v->next;
        a->A.insert(a->A.end(), p->A.begin(), p->A.end());
        a->A.insert(a->A.end(), q->A.begin(), q->A.end());
        a->B.resize(a->A.size());
        merge(p->B.begin(), p->B.end(), q->B.begin(), q->B.end(), a->B.begin());
        return a;
    }
    Node* splitNode(Node *u) {
        Node *t = u->real();
        Node *a = newNode(), *b = newNode();
        int n = t->A.size()/2;
        a->next = b, b->next = u->next;
        a->A.insert(a->A.begin(), t->A.begin(), t->A.begin()+n);
        b->A.insert(b->A.begin(), t->A.begin()+n, t->A.end());
        a->relax(), b->relax();
        return a;
    }
    Node* relaxList(Node *ver) {
        Node *a, *b, *u, *v, *t;
        int need = 0;
        for (u = ver, a = NULL; !need && u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) // merge
            	need = 1;
            if (u->real()->A.size() > (PSIZE<<1))	// split
            	need = 1;
        }
        if (!need)
        	return ver;
        	
        for (u = ver, a = NULL; u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) {	// merge
            	if (a == NULL)
            		a = mergeNode(u, u->next), b = a;
            	else
            		b->next = mergeNode(u, u->next), b = b->next;
                u = u->next;
            } else if (u->real()->A.size() > (PSIZE<<1)) {	// split
            	if (a == NULL)
            		a = splitNode(u), b = a->next;
            	else
            		b->next = splitNode(u), b = b->next->next;
            } else {
            	if (a == NULL)	
                    a = aliasNode(u), b = a;
            	else			
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    void debug(Node *head) {
        Node *u = head;
        printf("[");
    	while (u != NULL) {
        	for(int i = 0; i < u->real()->A.size(); i++)
            	printf("%d%s", u->real()->A[i], i != u->real()->A.size()-1 ? " " : " ");
        	u = u->next;
    	}
    	puts("]");
    }
    void free() {
        while (!mem.empty()) {
            Node *u = mem.top();
            mem.pop();
            delete u;
        }
    }
} dream; 
int A[MAXN], n, q;
UnrolledLinkedList::Node *ver[MAXQ];
int main() {
    int x, y, v, cmd;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        ver[0] = dream.init(A, n);
//		dream.debug(ver[0]);
        int encrypt = 0;
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            scanf("%d", &cmd);
            cmd ^= encrypt;
            if (cmd == 0) {			// back version v
                scanf("%d", &v);
                v ^= encrypt;
                ver[i] = ver[v];
            } else if (cmd == 1) { 	// insert A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.insert(ver[i-1], x, v);
            } else if (cmd == 2) {	// delete A[x]
                scanf("%d", &x);
                x ^= encrypt;
                ver[i] = dream.erase(ver[i-1], x);
            } else if (cmd == 3) {	// make A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.change(ver[i-1], x, v);
            } else if (cmd == 4) {
                scanf("%d %d %d", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                int t = dream.find(ver[i-1], x, y, v);
                printf("%d\n", t);
                encrypt = t;
                ver[i] = ver[i-1];
            } else {
                puts("WTF");
                return 0;
            }
//			dream.debug(ver[i]);
        }
    }
    return 0;
}
Read More +
學校課程/資訊安全

近代加密 複習 續

前言

幾乎是密碼學基礎數論，看來也走到這了。

亂來

隨便寫寫，上課不專心真是抱歉。

  1. Given an integer $x$, what is the requirement to let the multiplcative inverse $x^{-1}$ exist when modulo $p$? if $x^{-1} \mod p$ exists, please write down the equation (based on Fermat’s theorem) used to compute $x^{-1} \mod p$. (5%)

    1. condition: $gcd(x, p) = 1$ for multiplcative inverse $x^{-1}$ exist when modulo $p$
    2. Fermat’s theorem : $x^{p-1} = 1 \mod p \Rightarrow x^{p-2} \times x = 1 \mod p$ $x^{-1} = x^{p-2} \mod p$

  2. What is the Euler totient function $\phi(n)$? Please answer $\phi(77) = ?$

    $\phi(n)$ 表示 1 到 n 之內的整數，有多少與 n 互質的個數。
    $\phi(77) = 77 \times (1 - 1 / 7) \times (1 - 1 / 11) = 60$

  3. Whais the discrete logarithm problem? (5%)
    對於等式 $y = x^a \mod p$，已知三整數 y, x, p，解出 a 的問題。詳見小步大步算法 baby-step-giant-step，複雜度 $O(\sqrt p)$

  4. What is a hybrid cryptography? (5%)
    $$\text{hybrid cryptosystem } = \text{ public-key cryptosystem } + \text{ symmetric-key cryptosystem}$$

    • public-key cryptosystem
      提供 key encapsulation，就是 key 的安全性和簽章認證，保護 key 傳輸、保管上的問題。
    • symmetric-key cryptosystem
      提供 data encapsulation，提供高效率的加解密效能。

  5. What are the two primary reasons of using a cryptographic hash before signing a signature? (5%)
    cryptographic hash 密碼雜湊函數，通常會計算 $hash(M)$

    • 單向不可逆
      難以給定一個雜湊值，並且逆推得到當初輸入的數值。
      • 提供訊息修改檢查，相同的訊息進行雜湊，高機率會是不同。
        $hash(M1) \neq hash(M2)$，如果 M1 和 M2 差異只有數個 bits 不同。
      • 防止在傳輸過程中被竄改。對於簽章則更難竄改成相同雜湊值且具有 意義 的訊息 $M'$。
    • 容易計算
      將一個長度很大的訊息，壓縮一個固定長度的數值，這數值方便後續算法計算用加密算法的部分。

  6. Please write down the RSA public key encryption and decryption process (including public key and private key generation process). (10%)

    1. $N = p \times q$
    2. $\phi(N) = (p-1)(q-1)$
    3. $gcd(\phi(N), e) = 1, \phi(N) > e > 1$
    4. $d = e^{-1}, e \times d = 1 \mod ø(N)$
    5. public $e, N$
    6. private $p, q, d$

  7. Please develop a left-to-right binary exponentiation algorithm without “conditional jump” which is usually dangerous to some engineering attack. (10%)
    Montgomery Ladder 

    1
    2
    3
    4
    5
    R[0] = 1, R[1] = p
    for i = n-1 to 0, step = -1
        R[1-a[i]] = R[0] * R[1]
        R[a[i]] = R[a[i]] * R[a[i]]
    return R[0]

  8. Below is the DSA signature scheme in which $p$ is a large prime, $q$ is a 160-bit prime factor of (p - 1), $g$ is an integer of order $q$ modulo $p$. Let $x$ be the signer’s private key and $y = g^x \mod p$ be the public key.

    1. How to generate an integer $g$ ? (5%)

    2. Please complete the following nissing steps of the scheme. (10%)

    3. Please describe a trick for speeding up DSA’s on-line signing process. (5%)

      _______________________________________________________________________
Signing algorithm                 Verification algorithm
_______________________________________________________________________
r = (g^k mod p) mod q             w = s^-1 mod q
k is a random integer             u1 = (SHA(m) * w) mod q
s = ________________              u2 = (r * w) mod q
m is the messgae                  v = _________________
the signature is (s,r)            if v = r then the signature is correct

    • $g = h^{(p-1)/q} \mod p$ ，其中隨機亂數 $h$，滿足 $g > 1$ 即可。
      從費馬小定理中，有一個比較特別的計算來得到 order $q$，所謂的 order $q$ 就是在前 $q$ 個 $g^i \mod p$ 下不會出現重複 (循環長度至少為 $q$)，從觀察中得知循環長度 $L$ 滿足 $L | p-1$，也就是說 $L$ 是 $p-1$ 的因數，$q$ 則是要找到一個大循環，讓攻擊者更難找到 $x$，又因為 $L$ 是其因數，由於 $q$ 是 $p-1$ 的其中一個質因數，則保證是一個最小循環節的要求。

    • $s = k(SHA(m) + x \times r)$ $v = g^{u1} y^{u2}$

    • 可以 offline 去預處理隨機亂數 $k$，事先計算一堆的 $r$、$z = k^{-1}x \times r$，那麼計算 $s$ 可以非常的快速，$s = k^{-1} SHA(M) + z \mod p$，假設 hash 計算快速，只動用到一次乘法和加法，相較於 RSA 的簽章方法，少了指數次方運算。

  9. Under the following certificate hierarchy, please provide all the details of how end user A checking the correctness of end user C’s public key by verifying a sequence of certificates. Note: User A only knows X’s public key, but does NOT have the root Z’s public key directly. (10%)
    若 A 要確認 C 給的 public key 是否正確，則依循以下步驟來確認

    1. C 拿出 Y<<C>>，拿 Y 的 public key 進行確認 C 的 public key。
    2. 再檢查 Y 的 public key，Y 拿出 Z<<Y>>，拿 Z 的 public key 進行確認 Y 的 public key。
    3. 再檢查 Z 的 public key，Z 拿出 X<<Z>>，拿 X 的 public key 進行確認 Z 的 public key。
    4. 由於我們知道 X 的 public key (藉由實地臨櫃面對面確認 X 的 public key)，最後驗證 C 給的是正確的 public key。
            Z
    ／ ＼          Notation used
   X     Y         X<<A>>:
 ／ ＼    ＼       A's certificate issued by X
A     B     C

  10. Pleasewrite down the Diffie-Hellman key exchange protocol (including the public key and private key generation process). (10%) What is the man-in-middle (or the middle person) attack? (5%)

    • 共同決定一個大質數 $p$ 和一個基底 $g$ (全部人都知道)
    • 每個人 A 擁有自己的 private key $x_A$ ($x_A < p - 1$)
    • 每個人 A 計算自己的 public key $y_A$ ($y_A = g^{x_A} \mod p$)

    假設有兩個人 A, B 要通訊，則把自己的 public key 交給對方，共同產生出一把暫時的 key $K_{AB}$ 進行通訊加密。

    • 對於 A 來說會接收到 $y_B$，計算$K_{AB} = (y_B)^{x_A} = g^{x_B \times x_A} \mod p$
    • 對於 B 來說會接收到 $y_A$，計算$K_{AB} = (y_A)^{x_B} = g^{x_A \times x_B} \mod p$
    • 由於離散對數是一個困難問題，很難藉由攔截紀錄來得到對方的 private key $x_A$，因此有一定的安全性。

    假若現在要進行中間人 C 的攻擊，則會在一開始交換 $K_{AB}$ 的時候插入到其中通訊。

    • A 發送 $y_A$ 給 B 時，受到 C 的攔截。
    • C 知道 A 想要跟 B 通訊，則把自己的 $y_C$ 發送給 B，並且也傳一份給 A。
    • B 以為是 A 要進行通訊，實質拿到 $y_C$ 而非 $y_A$。
    • 產生兩把 key$K_{AC}, K_{CB}$，C 就偷偷在中間偷聽，並且作為中繼傳送訊息，需要解密 (拿$K_{AC} \text{ or } K_{CB}$) 之後再進行加密$K_{CB} \text{ or } K_{AC}$ 送給另一方。

    如何防止中間人攻擊，大約有幾種方法，但牽涉到可信任第三方、計算速度。

    • 發送訊息上，計算時間的延遲不得超過一定限制，否則可能存在中間人攻擊。
    • 藉由可信任第三方 CA (Certificate Authority) 來驗證彼此的 public key 歸屬於誰
      由 CA 簽認$Sign_{CA}(\text{public key || owner_id || expiration date || ...})$，如此一來如果存在 C 中間人，則轉交 $y_C$ 給 B 時，B 就會藉由 CA 驗證得到 owner_id 不是通訊對象 A。如果 CA 不可信任，則可以讓 C 簽一個$Sign_{CA}(\text{public key C || owner_A || expiration date || ...})$ 來欺騙 A 和 B，也就是說 CA 和 C 偷偷在私底下做了黑心勾當，那麼中間人攻擊仍是存在的。

  11. Both message authentication code (MAC) and digital signature can be used to provide the functionality of message origin and integrity check. Please briefly describe these two techniwues and compare percisely the difference between these two techniques. (10%)
    message authentication code (文件訊息鑑別) 顧名思義就是針對 message 進行驗證，確認發送者身分和資料完整性，相較於 digital signature (數位簽章) 也是做相同的事情，訊息量不同且產生出來的結果也大不相同。通常文件訊息鑑別會破壞儲存資訊，藉由雙方共享的 key 來進行身分認證，可用暫時性的 key，若採用非對稱式則需要額外的數位簽章來輔助驗證發送者。而數位簽章則是提供有效期限內的使用，這把驗證的 public key 必須存在比較長的時間。
    數位簽章簽定時不知道對方怎麼簽，但能驗證是他簽的並且只有他簽得出來，文件訊息鑑別通常知道對方用什麼流程輸出一樣的數值。

類型\性質 加密類型 輸出訊息 碰撞情況 重複使用
文件訊息鑑別 普遍上對稱式 不管多長都固定長度 存在 相同輸入 - 相同輸出
數位簽章 非對稱式 視情況而定 視情況而定 相同輸入 - 可能不同輸出
Read More +
手札日記

人之何以為人、105 號公路 外出紀錄

前言

現在學校活動也告一段落，即將要進入淡季，因此對於活動時數認證會變得更加麻煩。學校活動大多都是剩下營隊，當然也只有工作人員才能參與來替換時數，只能參與一半的半吊子可是無法融入進去的。於是被催著去參加校外活動來補這一個門檻問題。

來到中壢，基本上也就只有在校園、火車站及租房地點三角範圍內行動，對於其他地點一概不知，在中壢的學校有中原、元智以及我們中央，之前有被學長帶去中原夜市，若要自行出發還算個挑戰，曾考慮騎車去參加活動，但在前幾天去演練騎車過去時，卻不知不覺繞回學校，中壢的環狀分布、高架橋之路線讓我卻步，看來還是搭公車較為妥當。

去過中原夜市，卻沒進過中原大學，去過元智大學參加程式競賽，卻不知道怎麼自行前往。早上聽完一場演講後，趕緊搭公車轉兩次過去，在一個小時內就抵達中原，比預期中還來得順暢。在提早到達後，走在不同的校園觀望，看看不同地方的感覺，也許是股錯覺，由於騎腳踏車的人少，顯得人群非常的多，而且相較於中央更容易在路上見到女生，想到畢業學長回來學校的時候說一句「怎麼一眼望過去幾乎都男生」突然有點感觸，即使每三個人就有一個人女生，只比中原少一點，在戶外的大椅上不少學生坐在哪裡，顯得更加地活絡。也許只是太少出門，對中央不慎了解吧。

  • 全人博雅講壇 「人之何以為人：一個20萬年的故事」－李家維
  • 服務 X 學習 X 旅行 X 夢想 - 不做不會怎麼樣，做了我們很不一樣 「105 號公路-泰緬邊境」－黃婷鈺

場一狀態

在講座開始前就明顯地感受到不同的風氣，開幕前來個留外的音樂表演，同時也請學校校長來說本校的希望不要拿通識的營養學分，正是舉辦這一系列全人教育講座的目的，講座規模不大，卻有不少校外人士和同學入場，相信仍有不少同學是來混時數的，包括我自己。

「人之何以為人：一個 20 萬年的故事」這演講標題不外乎就是在描述人類演化的過程，這 20 萬年間的不斷地挖考出來的化石，訴說人類的起源，為什麼要知道自己的起源與文明發展？能在人類文明習慣中了解不少疑惑，如為什麼總是成對科學人雜誌 - 「 演化路上夫妻同心 」、科學人雜誌 - 「 天天上網的靈長類 」 … 等。

不少相似的化石指出，智人與其他類似的族群之間的相似程度，雖然基因只有一點點不同，造就體能、合作、學習、腦容量 … 等都有所差異，為了度過險惡的環境，單純體能良好的人種消失，會合作延續文明的種族存活下來，靠的只是一點點變異。這讓我想到動畫《攻殼機動隊》對於文明的看法，人類之所以能成長到這一個地步都是靠一個 外部記憶體 - 文明，那我們真的是擁有自我嗎？還是順著文明的發展？但我想當人們不缺物質時，才能去想這些無關緊要的事情。

《攻殼機動隊》

到底該不該去怪罪努力、後天學習？還是去怪罪刻印在 DNA 上的排序？曾經為了存活繁衍導致的基因，而基因養成習慣。從計算機科學的廣義算法中的基因算法可以裡也到，人類之間的基因變異不算少，這有沒有影響呢？就如電影《蠢蛋進化論》中的基因變化，不見得聰明靈敏，只要適合生存即可。很多行為是沒有道理的，有些演化也是沒有道理的，在用現代的眼光去看待過去的演化價值時，本身就是件很奇怪的事情。

《蠢蛋進化論》

《天佑美國》當我們不在意文明時，還需要文明嗎

回過頭來看看講者提到的科學人雜誌，人耐不住寂寞也是因為曾經有段長久的日子需要彼此扶持，度過那段艱辛的冰河時期。現今環境還算充裕下，人可以不見到其他人，藉由上網交流資訊，雖然這可以交流資訊，但卻難以得到實質的幫助。從現在觀點來看，人其實也很單純，藉由學習外部遺留的文明來成長，所以才看起來聰明，大家也都知道若沒有傳承，人類根本走不到今日。

場一心得

中原講座的發問其實還挺有趣的，發問相當踴躍，原來在別校是這種情況，即使是一些課本上的內容、電視影集的科幻劇情都拿出來問，講者當然只能回答這不確定，至少不能斷言去否定。講者大部分的內容都可從國高中學的歷史中理解到，藉由後續學習的資訊也可以明白這些小道理，大部分都是在描述科學人雜誌上的資訊，有興趣可以去讀讀。

場二狀態

講者的描述有點囧，也許是狀態不好吧，可能尚未習得說話術，對於分享感覺是難以用文字去描述。儘管如此，藉由之前學到的文明與族群的通識課程，大概能猜到她想描述些什麼，就由我來說說吧！

首先，講者在大學混了四年不感興趣的專業，在四年存夠了錢，前往泰緬邊境的難民營中去當國際志工，泰緬邊境難民營是因為兩個民族之間的糾紛導致。國際志工是什麼？國際志工能做什麼？到底是誰需要誰？還是在別人艱困的環境下，只是想要藉由別人的艱困來充實富足自己的知識？

我對於國際志工不甚了解，但對於文明與文明之間的隔閡有點認識，很多人就會用體驗、參觀的方式去遊走各地，因為旅行是跳脫環境最簡單的方法！想要跳脫環境就去存個錢吧，去別的環境了解自己有多麼無知且高傲，看著別人過著自認為窮困的生活，不了解當地的文化，卻又想幫忙他們的窘境。

對於這件事情，我的看法如下，常說「人只能自救」，國際志工去幫忙不少只是「 偽善 」瞧不起別人的文化、可憐他們的處境，去了那裏，只能觀察別人的生活，有時還需要當地人照顧生活。去那兒 體驗 ，就跟別人來家裡 觀光 的感覺一樣，尤其是在戰亂複雜的關係下，志工除了送物質協助無關戰爭的人外，請思考有沒有可能把他們牽涉進去，因為提供給對方敵人協助，那志工算不算敵人？這要特別小心，當我們在台灣成長，沒有那種經驗是很正常的，懵懂無知的情況下，被用另外一種方式教導「 幫助別人 」是件好事，因此就把這套邏輯用到另一個國情上。

請跟沒有計畫性的幫助說再見！

之前在網路上看到一篇文章《本滿懷熱血的教山區孩童，學生竟對志工老師說：「叔叔阿姨，請你們不要再來我們這義教了…」 》link，開頭第一句「我們沾沾自喜著自己的偉大、奉獻。但是，我們到底為他們做了什麼？」正是描述志工的心境，也正是講者有提及到不少跟著一起去當志工的同學在那裏覺得自己的心很空虛，的確若沒有對自己夠了解時，突然用自己所謂的理解去理解別人時，回饋得到的那種失落感正是那股空虛。

《Fate/Stay UBW》這世代充斥著多餘之人

學校教育是活在這個社會的學習過程，但不就是人類太多、過於群聚，相依彼此產生不少抽象式的職位，並非對物而是對人、對制度的職位，把偏鄉小孩帶來教育城市的生活技巧，對於他們能學到什麼實質內容？跟著大家一起進入城市搶那一鍋粥嗎？原始心中那股純樸到哪去了？講者描述到學校因為有一位長者去世而停課，學生們都跑去為那位長者送行，這是學校教育做到的嗎？還是生活教育體驗到的？

書本的內容可以協助他們理解這個世界，但並不是替他們指引出路的方法。教育這一舉動大多是為了未來生存技能存在，身為一個教育者是否又想過「教育是否又抹殺掉另外一種全然不同的世界觀」這是兩難的取捨，並不是往哪個目標走就是對的，而是要把這概念在教學的背後告訴學生吧。

場二心得

講者描述上還有趣的，想必是出國體驗後的衝擊巨大，有些事情無法用言語來描述吧。

並不是所有講者都能闡述有多成功的一面，或者是自己體驗多麼豐富的內容，這場演講充分地從講者身上看出那種衝擊，說話言之有物、做事持之以恆，君子不多話、默默做事，人的一生充滿困惑，很多事實無法二分化、二值化，去累積吧！也許有一天就能化作一生最美妙的道理。

Read More +
手札日記

如何經營有聲有色的課堂悅音 外出紀錄

前言

想到不久前高中教我資訊的啟蒙老師打電話回來，問我要不要回去去當資訊老師，如果要當老師，必須先修完 32 學分以上的教育學程才行，就以當前的狀況是沒辦法完成，因為牽涉到實習，延畢去完成也至少需要一年半的時間。

接到老師打電話來是還不錯的驚喜，在這可能延畢與困惑的季節上來說，來了點與眾不同的聲響，雖然學校成績還算不錯，但要是當個老師可能還有點缺陷，之所以可能會延畢都是要求全人教育吧，不曉得到底要怎麼當一個普通的大學生呢。

狀態

現在還差許多參加活動的時數，這一場講座是教導 教師 為主，對於老師上課的好壞，其一專業知識，其二教學方法，針對如何說話、上台解說給學生聽是一門功夫，不外乎地從一般說話就能知道有些人上台說話不行，即使是枯燥乏味、或者是非常簡單的課程內容，如何在台上持續講一兩個小時？又要如何講得不讓學生覺得費力？

上台長篇大論一番，對於內容感到好奇的學生，講者用什麼語調影響不大，那對於其他學生肯定是很重要的，上台教學有如演戲歌唱，若不是這樣，大概就像是一個古老的自動播放機吧，如何把一句話說得長、不造成聽者的負擔。

此課程由台師大音樂系老師來講課，一開始活動就請各位老師用平常的方式來介紹自己的名字、職位、專業，「大家好，我叫XXX，目前是中央大學資工系學生」在這一群教師中，混有一個學生的自我介紹是很緊張的，輪到自己真想找個洞鑽。唯一沒想到這場活動也是互動式，就之前參與教師研習的打工，明白許多研習活動都是互動式的，馬上就會請老師設計課程之類的，這一點應該早點想到。

如果教師四肢受傷，那嗓音的影響力就非常大。上台說話就像演歌，那麼從說話技巧開始，從一般的生理性的平直對談、口技、口哨、喉音、泛音 … 等，看來要從合唱團開始練起，如何避免氣音、粗啞，練習圓滑發音，將音調拉高 …。把一句話盡量往上揚，讓整個說話具有和氣、輕鬆的對談，這會對聽者更為舒服，把講話方式弄得輕鬆，這樣也可以講得長，聲帶比較不會受傷。

在授課前二、三十分鐘前就要喝好足夠的水，並且在授課時是實地補充水分，若是在授課一半才進行補水，很容易造成聲帶受傷。對於一名教師，說話是生命，聽到不少老師都是靠喉糖 … 等方式作為後續應急的方案，看來授課真是場戰爭。這也讓我想到光是上台講個二、三十分鐘，喉嚨隔天就有點不行，也許只是平時沒有磨練說話的緣故。

此外還有特別談論到千萬要避免「滔滔不絕」一旦需要趕課，總是來個加快說話速度版本來授課，想必要好好演一齣戲都辦不到，在這裏看起來是沒有辦法解決的課題。

結論

要講好一場課，先去卡拉 OK 練唱吧！

別像許多講者，久久碰一次麥克風，人轉、麥克風不轉的有趣情景就能少見。如果沒有麥克風要講一整天課是很累人的，但麥克風有時會沒電，在沒有麥克風的狀態，也必須練練如何把話傳得遠，藉由拉高音量，用較沉的方式比較合適，說話需要氣量、聲帶健康，講師建議少喝冰品刺激食道肺部，作為一個以說話的職業多喝溫水吧，為了講話的氣量多多運動吧。

Read More +
學校課程/介面設計

遊戲問卷設計 Game Guestionnaire

問卷設計跟面試方法一樣，如何了解使用者的需求與能力，如何發問、如何誘導都是相當有趣的。對於每一種人格特質，在面對不同問題的問法時，作答的難易度是有影響的，這對面試官也是相當重要的課題，因此需要了解到問題設計的方法。

關於問卷

問卷通常會分成兩種

  • 定量分析
    詢問回答者的意見 程度 ，通常採用二值化，在從正到反極劃分數個單位，讓使用者選擇。
  • 定性分析
    單純詢問使用者的 看法 ，在不給予任何提示下，讓使用者根據自身的經驗回答問題。

當不知道問題的答案分布，既不是好與壞兩者，那麼定量分析就不能作為評估，採用開放式作答的定性分析，讓使用者回答它們所理解的，通常開放式有一個缺點，會導致過於雜亂的回答，很難得到期望的答案。想必很多人在不理解 問題描述 就會答非所問。定量分析的面向去設計，會得不到意想不到的答案，兩種方法各有優缺。

問卷設計

按照上述的兩種情況分成 選項 跟 申論 兩種。申論題就不必說，留給使用者提出自己的看法，欄位設計就是文字欄位而非選項欄位。

特別介紹一下選項部分，通常會有 是 / 否 、 喜歡 / 不喜歡 ，再複雜一點就是 非常喜歡 - 喜歡 - 沒意見 - 不喜歡 - 非常不喜歡 。如果在量表中只有偶數選項，通常是不存在中立立場，希望每個應答者都給予一個立場去回答，反之在奇數選項中，給予中立立場的應答機會，通常會得到非常多的 沒意見 此時有效問卷的數量相對少。

關於面談

面談通常會分成三種

  • 結構化
    封閉式對答，在已知答案中做決策。循序讓使用者回答問題。
  • 半結構
    相較於結構化問題，不要求詢問順序性，或者是確切的答案回答。
  • 非結構
    問題會隨著應答者回答的方式變化。

通常第三者的非結構面談相當輕鬆，如果變化問題不特別刁難，面談者也會根據應答者的能力詢問相關問題。然而在結構化問題中，相當一板一眼，容易對應答者感到緊張，當問題卡住的時候，接下來的問題就會影響到應答者的狀態。半結構化則介於兩者之間。

團體面談

  • 部分應答者很容易被忽略，需要主持人去引導，觀察每個應答者在聽取其他人回答的肢體語言，適時地將每個人的意見引出。
  • 很難獲得想要的資訊。
  • 回答之間會相互影響。

特別小心主持人不應該讓面談者們 達到共識 ，而是讓他們分享所知。誤導或誘答的情況應該避免，否則有可能會造成馬拉松領先者帶著一群人走錯方向的感覺。感覺不少情況會設下陷阱去讓面談者誤答，在問題描述上不給予明確的規範，在算法問題上也常常會這樣，至於算不算誤答就不曉得，當一個人對問題的背景認知不同時，問題本身就不一樣，能不能 取悅 面試官呢？

歸納問卷

回收問卷後，利用定性方式去得到的答案是最難分析，只能靠觀察去理解，對於定量方式去設計的，將要看採用的數學模型來決策，例如消頭去尾後得到的平均數、眾數、中位數 … 等。不管哪一種方案，要看應答者的文化習慣，是否會造成不願意表態，極端情況是否正常 … 等因素，適時地消去一些實驗數據進行統計。

問卷介面也要有所區別，通常會有數個相似領域的問題，整合在一起，並且給予一個問題大綱有助於對問題的理解，特別注意到問題設計時要確定題目是否能二極化。

各組設計

最奇葩的要來了，針對認知風格進行問卷調查，針對先前設計的遊戲，不同認知風格對遊戲介面的觀感。，各組提出的問卷問題如下：

塔防遊戲

  • 遊戲中介面的引導對你有哪些幫助？
  • 升級頁面的兵種介紹對你有何影響？
  • 過多提示會不會扼殺你對遊戲的興趣？為什麼？
  • 你覺得遊戲中哪一個功能最不直觀？為什麼？
  • 是否希望一開始就解鎖所有關卡？為什麼？
  • 無法順利通關時，你都如何應對？
  • 升級頁面的兵種能力數值是否能幫助你理解兵種特性？如果不行，希望如何改善？
  • 你覺得遊戲中哪一個功能最不直觀？為什麼？
  • 你覺得遊戲中在哪個部分自由度不夠？希望如何改善？
  • 你希望遊戲中哪些介面能夠讓你自行調整？

角色扮演

  • 你覺得主畫面看起來如何 (例如背景顏色、排版、標題等等)或是其他？
  • 你覺得說明文件的詳細度以及對於操作的說明還有排版等恰當嗎，能助你了解遊戲怎麼進行？
  • 關卡劇情有沒有讓你覺得充滿故事性、關聯性，讓你進入遊戲中？
  • 遊戲的流程、難度、還有系統的圖示資訊你覺得夠完善嗎，能幫助你遊戲順利？
  • 你覺得遊戲的音樂選擇跟切換時機有讓你覺得非常合理，並且具有強大代入感嗎？
  • 您覺得遊戲難度是否可以自行解決？為什麼

我們組所提出的七個問題如下

  • 您覺得遊戲難度是否可以自行解決？為什麼
  • 您最喜歡、討厭這遊戲哪一部分，討厭的話，想改成什麼？
  • 您覺得遊戲內介面的看法如何？
  • 您對於介面的動畫效果的看法如何？
  • 您玩完這款遊戲後，對遊戲目標瞭解程度 (例如劇情 …)？
  • AI 擬真程度對遊戲操作的感受？
  • 原本期望的效果、事物卻沒在遊戲中的是什麼？

解謎遊戲

  • 在遊戲進行當中在覺得最困難的部分為何？
  • 如果在遊戲中加入選關模式，你有什麼看法？
  • 對於遊戲介面，你認為有什麼可以改善的地方？
  • 教學關卡對你學習遊戲的操作模式有什麼影響？
  • 對於破關後才加入競速模式，你有什麼看法？
  • 你認為遊戲劇情有何改善空間？

問卷統計範例

本課程教學極為詭異，應該請全班人一起填，總共才七組來卻只要求自己去找 課程班上 十個人來填問卷，互填對方設計的遊戲問卷難道這麼困難嗎？老師應該要直接請全班來填寫吧，用鼓勵的方式，居然在畢業前一周要大家填問卷，一星期統計好並且報告，明顯地大家都在忙畢業典禮的拍照，問卷也很晚統計回來。

當然十個人的樣本數只能自我安慰，下什麼結論都是不具有信用的，只好按照老師的調調亂扯一通。就算遊戲做得再差，問卷回饋不如預期的對答，也許按照自己的預測方式去報告就行，問卷感覺就是裝飾用的。自己的教授自己靠北？

問卷結果

分別對於兩個版本，非常非常少的實驗數據。

遊戲難度 Holist 認為難度簡單，對遊戲進行不算困難，對於 Serialist 比較有新事物認知上的起手問題。

在遊戲偏好上，大部份的 Holist 看到了整體的光影效果對此深感好奇，而 Serialist 不少指出遊戲說明上的困惑與扣除血量的細節。

在遊戲內介面上，Holist 對於道具切換、使用狀態有強烈的要求，太過簡潔的界面是介意的地方，而在 Serialist 對於顏色要求較為強烈，對於簡介的介面設計滿意。

在遊戲介面動畫上，Holist 比較偏向回答遊戲內部的元素動畫，而 Serislist 則比較在意流血效果和字體閱讀。在這一部分的回答可以說是有點誤導，預期是想要讓他們回應遊戲介面動畫，而非遊戲內的元素動畫。

在遊戲目標上，一致都朝著遊戲通關目標為基準，而非劇情走向，估計是劇情走向對遊戲進行流程不影響，所以沒有必要去注意遊戲劇情內容。

在人工智慧 AI 上，Holist 比較偏向滿意，對有一些與現實邏輯不合的反應介意，對於 Serialist 對於 AI 的反應比較兩極，有好有壞。

對於預測遊戲進行上，Holist 比較想要的是局部性改變，例如效果與道具使用上、遊戲進行邏輯、新的功能利於闖關。而 Serialist 比較喜歡全局性的擴充，如新增關卡、不同類型的通過條件、關卡成就感、角色成長的需求。

課程意見

請不要一堂課的結尾就喊出成績來決定一個學生的價值，若要從認知風格中挑選一種分類，老師的認知風格屬於一種衝動型，部分是需要不斷反思來接受新的資訊。不強求這門課的走向，但從做遊戲方面，可說是此次教學的創舉，既然要我們寫程式，麻煩就以資工系的方式引導，時間跟計劃不是一兩個星期前講就了事，牽涉到設計與構思，不給一個明確的方向，導致各組面向不同種遊戲，類型不同的遊戲設計出來就不能隨意說好與壞，若是要符合你們口味的網路學習，那直接說做益智遊戲即可，有些探討問題也因遊戲類型扯不上關係。

若要用小組程式作業、設計作為不上課的理由實在說不過去，導致這一學期很多次沒上課，起碼可以一個小時上課，後兩個小時討論的方式。而在論文上台報告卻有報告老師的同一篇論文，導致報告內容重複且冗長。上課投影片請不要用講稿模式 (兩攔筆記式，另一半的筆記欄位不知道給誰看的)，可以請助教弄全螢幕的投影片。

Read More +