解題區/解題區 - UVa

UVa 12412 - A Typical Homework

Problem

寫一個模擬成績登錄系統的程式。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
0011223344 1 John 79 98 91 100
0022334455 1 Tom 59 72 60 81
0011223344 2 Alice 100 100 100 100
2423475629 2 John 60 80 30 99
0
3
0022334455
John
0
5
1
2
0011223344
0
5
0
4
0

Sample Output

1
略

Solution

純苦工題目。

Try adding 1e-5 to all floating point values as you print them.

難怪會 WA，看到時小夥伴們都傻眼，不過應該也是因為大部分仍然使用 float 輸出，用 double 反而會得到 WA 的例子不在少數。

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
// WTF > Try adding 1e-5 to all floating point values as you print them.
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define eps 1e-5
class Student {
    public:
    string SID, name;
    int CID, score[4];
    Student(int c, int d[], string a = "", string b = "") {
        SID = a, name = b;
        CID = c;
        for (int i = 0; i < 4; i++)
            score[i] = d[i];
    }
    void print() {
        printf("%s %d %s %d %d %d %d %d %.2lf\n", 
            SID.c_str(), CID, name.c_str(),
                score[0], score[1], score[2], score[3], getTotal(), getAvg());
    }
    int getTotal() {
        return score[0] + score[1] + score[2] + score[3];
    }
    double getAvg() {
        return (score[0] + score[1] + score[2] + score[3]) / 4.0 + eps;
    }
};
class SPMS {
    public:
    map<string, int> R_SID;
    vector<Student> students;
    void printMainMenu() {
        puts("Welcome to Student Performance Management System (SPMS).\n");
        puts("1 - Add\n2 - Remove\n3 - Query\n4 - Show ranking\n5 - Show Statistics\n0 - Exit\n");
    }
    void addStudent() {
        char SID[128], name[128];
        int CID, score[4];
        while (true) {
            puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
            scanf("%s", SID);
            if (!strcmp(SID, "0"))
                return;
            scanf("%d %s", &CID, name);
            for (int i = 0; i < 4; i++)	scanf("%d", &score[i]);
            
            if (R_SID[SID]) {
                puts("Duplicated SID.");
            } else {
                R_SID[SID]++;
                Student u(CID, score, SID, name);
                students.push_back(u);
            }
        }
    }
    void removeStudent() {
        char s[128];
        while (true) {
            puts("Please enter SID or name. Enter 0 to finish.");
            scanf("%s", s);
            if (!strcmp(s, "0"))
                return;
            int cnt = 0;
            for (vector<Student>::iterator it = students.begin();
                it != students.end(); ) {
                if (it->SID == s || it->name == s) {
                    cnt++;
                    R_SID[it->SID]--;
                    it = students.erase(it);
                } else {
                    it++;
                }
            }
            printf("%d student(s) removed.\n", cnt);
        }
    }
    int getRank(Student u) {
        int ret = 1;
        for (int i = 0; i < students.size(); i++)
            if (students[i].getTotal() > u.getTotal())
                ret++;
        return ret;
    }
    void queryStudent() {
        char s[128];
        while (true) {
            puts("Please enter SID or name. Enter 0 to finish.");
            scanf("%s", s);
            if (!strcmp(s, "0"))
                return;
            for (vector<Student>::iterator it = students.begin();
                it != students.end(); it++) {
                if (it->SID == s || it->name == s) {
                    printf("%d ", getRank(*it));
                    it->print();
                }
            }
        }
    }
    void printRankList() {
        puts("Showing the ranklist hurts students' self-esteem. Don't do that.");
    }
    void printStatistics() {
        puts("Please enter class ID, 0 for the whole statistics.");
        int CID;
        scanf("%d", &CID);
        
        int pass[4] = {}, fail[4] = {}; // subject
        int sum[4] = {}, n = 0;
        int sumtable[5] = {};
        vector<int> table; // student
        table.resize(students.size(), 0); 
        for (int i = 0; i < students.size(); i++) {
            if (CID && CID != students[i].CID)
                continue;
            n++;
            for (int j = 0; j < 4; j++) {
                sum[j] += students[i].score[j];
                if (students[i].score[j] >= 60) {
                    pass[j]++;
                    table[i]++;
                } else {
                    fail[j]++;
                }
            }
            sumtable[table[i]]++;
        }
        
        for (int i = 3; i >= 1; i--)
            sumtable[i] += sumtable[i+1];
        printf("Chinese\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[0] / n + eps, pass[0], fail[0]);
        printf("Mathematics\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[1] / n + eps, pass[1], fail[1]);
        printf("English\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[2] / n + eps, pass[2], fail[2]);
        printf("Programming\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[3] / n + eps, pass[3], fail[3]);
        printf("Overall:\nNumber of students who passed all subjects: %d\nNumber of students who passed 3 or more subjects: %d\nNumber of students who passed 2 or more subjects: %d\nNumber of students who passed 1 or more subjects: %d\nNumber of students who failed all subjects: %d\n\n",
            sumtable[4], sumtable[3], sumtable[2], sumtable[1], sumtable[0]);
    }
} spms;
int main() {
    int cmd;
    while (true) {
        spms.printMainMenu();	
        scanf("%d", &cmd);
        if (cmd == 0)
            return 0;
        if (cmd == 1)
            spms.addStudent();
        if (cmd == 2)
            spms.removeStudent();
        if (cmd == 3)
            spms.queryStudent();
        if (cmd == 4)
            spms.printRankList();
        if (cmd == 5)
            spms.printStatistics();
    }	
    return 0;
}
/*
1
0011223344 1 John 79 98 91 100
0022334455 1 Tom 59 72 60 81
0011223344 2 Alice 100 100 100 100
2423475629 2 John 60 80 30 99
0
3
0022334455
John
0
5
1
2
*/
Read More +
解題區/解題區 - UVa

UVa 12462 - Rectangle

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
6 3
2 3 1 7 3 5
2 0 1 0 1 2
3 1
2 2 2
0 0 0
5 2
3 2 1 2 3
1 0 1 0 1
6 4
1 2 3 4 5 6
0 1 2 3 1 0
7 2
1 2 3 4 3 2 1
0 1 0 1 0 1 0
10 2
2 1 2 1 1 2 1 2 2 1
1 0 0 0 1 0 0 1 1 0
3 2
1000000000 999999997 999999999
0 1 1
0 0

Sample Output

1
2
3
4
5
6
7
9
6
5
12
10
10
2999999991

Solution

對於每一個長條 h[i]，勢必將往左往右延伸到第一個數值比較低的，因此會得到一個區間 [l, r]，如果 [l, r] 之間不具有所有顏色，則忽略之。反之紀錄 h[i] * (r - l + 1) 是否為最大值。這樣的貪心方式，盡可能會具有最多的顏色，同時考慮到所有最大面積會卡住的地方。

但是窮舉找到每一個 [l, r] 相當費時，這裡運用單調堆的思路，分別從左、從右側往反方向掃描，掃描時維護堆裡面元素呈現遞減情況，分別找到左右端點後，檢查是否區間內有相符的顏色個數。

找所有左右端點只需要 O(n) 時間，但是檢查區間內的顏色個數是否符合則必須 O(nm)。

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
#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
#define MAXN 131072
#define MAXC 32
int h[MAXN], c[MAXN], sumc[MAXN][MAXC];
int L[MAXN], R[MAXN]; 
int main() {
    int N, C;
    while (scanf("%d %d", &N, &C) == 2 && N) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &h[i]);
        for (int i = 1; i <= N; i++)
            scanf("%d", &c[i]);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < C; j++)
                sumc[i][j] = sumc[i-1][j];
            sumc[i][c[i]]++;
        }
        for (int i = 0; i < C; i++)
            sumc[N+1][i] = sumc[N][i]; 
            
        h[0] = h[N+1] = 0;
        stack<int> stk;
        stk.push(0);
        for (int i = 1; i <= N; i++) {
            while (h[i] <= h[stk.top()])
                stk.pop();
            L[i] = stk.top() + 1, stk.push(i);
        }
        
        while (!stk.empty())	stk.pop();
        
        stk.push(N + 1);
        for (int i = N; i >= 1; i--) {
            while (h[i] <= h[stk.top()])
                stk.pop();
            R[i] = stk.top() - 1, stk.push(i);
        }
        
        long long ret = 0;
        for (int i = 1; i <= N; i++) {
            int ok = 1;
            for (int j = 0; j < C; j++)
                ok &= sumc[R[i]][j] - sumc[L[i] - 1][j] > 0;
            if (ok)
                ret = max(ret, (long long) h[i] * (R[i] - L[i] + 1));
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
6 3
2 3 1 7 3 5
2 0 1 0 1 2
3 1
2 2 2
0 0 0
5 2
3 2 1 2 3
1 0 1 0 1
6 4
1 2 3 4 5 6
0 1 2 3 1 0
7 2
1 2 3 4 3 2 1
0 1 0 1 0 1 0
10 2
2 1 2 1 1 2 1 2 2 1
1 0 0 0 1 0 0 1 1 0
3 2
1000000000 999999997 999999999
0 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 12618 - I Puzzle You

Problem

給一個 n = 3 魔術方塊的盤面，找最少操作次數使其每一面顏色都相同。

每一次操作限定旋轉 90 度。如果需要的步數大於 7 步，直接輸出 Impossible。

Sample Input

1
2
3
4
5
4
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY
WWWWWWRRRRRYBBBWOOGGGRRYBBBWOOGGGRRYBBBWOOGGGOOOYYYYYY
WWBWWBWWBRRRBBYOOOWGGBBYOOOWGGRRRRRRBBYOOOWGGYYGYYGYYG
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYGGGYYYYYY

Sample Output

1
2
3
4
Case 1: 0
Case 2: 1
Case 3: 2
Case 4: Impossible

Solution

首先，關於旋轉操作只能手動打表，總共會有 9 種旋轉序列 (窮舉時操作成順、逆兩種)，其中的 6 種序列會使得相鄰的面旋轉 90 度 (必須特別考慮這邊緣的旋轉)。

關於啟發式：六個面中，其中一個面具有最多的顏色，將會是預估的最少移動操作。

這一個啟發式相當重要，也非常難想，參考 http://blog.csdn.net/qq564690377/article/details/16867503

一開始使用 IDA* 的效果似乎不很好，於是換了雙向 BFS (doubling BFS)，由於步數限定 7 步內，從目標狀態建表 4 步內的結果。接著對於每一組詢問，搜索 3 步內的操作，查看是否會相遇。

狀態壓縮可以採用重新命名，也就是最小化表示法，不管顏色，只考慮同構。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
#include <stdio.h> 
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int rotateInfo[9][12] = {
    {1, 4, 7, 13, 25, 37, 46, 49, 52, 45, 33, 21}, // margin rotate begin
    {3, 6, 9, 15, 27, 39, 48, 51, 54, 43, 31, 19},
    {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21},
    {34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45},
    {1, 2, 3, 18, 30, 42, 54, 53, 52, 34, 22, 10},
    {7, 8, 9, 16, 28, 40, 48, 47, 46, 36, 24, 12},
    {2, 5, 8, 14, 26, 38, 47, 50, 53, 44, 32, 20}, // center rotate begin
    {4, 5, 6, 17, 29, 41, 51, 50, 49, 35, 23, 11},
    {22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}
};
int rotateFace[6][9] = { // not center rotate
    {10, 11, 12, 22, 23, 24, 34, 35, 36},
    {18, 17, 16, 30, 29, 28, 42, 41, 40},
    {1, 4, 7, 2, 5, 8, 3, 6, 9},
    {52, 49, 46, 53, 50, 47, 54, 51, 48},
    {21, 20, 19, 33, 32, 31, 45, 44, 43},
    {13, 14, 15, 25, 26, 27, 37, 38, 39}
};
int rotateOrder1[9] = {2, 5, 8, 1, 4, 7, 0, 3, 6};
int rotateOrder2[9] = {6, 3, 0, 7, 4, 1, 8, 5, 2};
int face[6][9] = {
    {1, 2, 3, 4, 5, 6, 7, 8, 9},
    {10, 11, 12, 22, 23, 24, 34, 35, 36},
    {13, 14, 15, 25, 26, 27, 37, 38, 39},
    {16, 17, 18, 28, 29, 30, 40, 41, 42},
    {19, 20, 21, 31, 32, 33, 43, 44, 45},
    {46, 47, 48, 49, 50, 51, 52, 53, 54}
};
map<string, int> Rstep, Bstep;
void adjustInfo() {
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 12; j++)
            rotateInfo[i][j]--;
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 9; j++)
            face[i][j]--;
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 9; j++)
            rotateFace[i][j]--;
}
int isCompleted(const char A[]) {
    for (int i = 0; i < 6; i++) {
        int ok = 1;
        for (int j = 0; j < 9; j++)
            ok &= A[face[i][j]] == A[face[i][0]];
        if (!ok)	return ok;
    }
    return 1;
}
string reduceCube(string u) {
    static int used[128] = {}, R[128], testcase = 0;
    char idx = 'A';
    testcase++;
    for (int i = 0; i < u.length(); i++) {
        if (used[u[i]] != testcase) {
            R[u[i]] = idx++, used[u[i]] = testcase;
        }
        u[i] = R[u[i]];
    }
    return u;
}
string rotateCube(string u, int kind, int dir) {
    static int a, b, c;
    static char tmp[9];
    if (dir == 0) {
        char v[3] = {u[rotateInfo[kind][0]], u[rotateInfo[kind][1]], u[rotateInfo[kind][2]]};
        for (int i = 0; i < 3; i++) {
            a = i * 3, b = i * 3 + 1, c = i * 3 + 2;
            u[rotateInfo[kind][a]] = u[rotateInfo[kind][a + 3]];
            u[rotateInfo[kind][b]] = u[rotateInfo[kind][b + 3]];
            u[rotateInfo[kind][c]] = u[rotateInfo[kind][c + 3]];
        }
        a = 3 * 3, b = 3 * 3 + 1, c = 3 * 3 + 2;
        u[rotateInfo[kind][a]] = v[0];
        u[rotateInfo[kind][b]] = v[1];
        u[rotateInfo[kind][c]] = v[2];
        if (kind < 6) {
            for (int i = 0; i < 9; i++)
                tmp[i] = u[rotateFace[kind][i]];
            for (int i = 0; i < 9; i++)
                u[rotateFace[kind][i]] = tmp[rotateOrder1[i]];
        }
    } else {
        char v[3] = {u[rotateInfo[kind][9]], u[rotateInfo[kind][10]], u[rotateInfo[kind][11]]};
        for (int i = 3; i > 0; i--) {
            a = i * 3, b = i * 3 + 1, c = i * 3 + 2;
            u[rotateInfo[kind][a]] = u[rotateInfo[kind][a - 3]];
            u[rotateInfo[kind][b]] = u[rotateInfo[kind][b - 3]];
            u[rotateInfo[kind][c]] = u[rotateInfo[kind][c - 3]];
        }
        a = 0, b = 1, c = 2;
        u[rotateInfo[kind][a]] = v[0];
        u[rotateInfo[kind][b]] = v[1];
        u[rotateInfo[kind][c]] = v[2];		
        if (kind < 6) {
            for (int i = 0; i < 9; i++)
                tmp[i] = u[rotateFace[kind][i]];
            for (int i = 0; i < 9; i++)
                u[rotateFace[kind][i]] = tmp[rotateOrder2[i]];
        }
    }
    return u;
}
int hfunction(string u) {
    static int used[128] = {}, testcase = 0, cnt = 0;
    int ret = 0;
    for (int i = 0; i < 6; i++) {
        testcase++, cnt = 0;
        for (int j = 0; j < 9; j++) {
            if (used[u[face[i][j]]] != testcase) {
                used[u[face[i][j]]] = testcase;
                cnt++;
            }
        }
        ret = max(ret, cnt - 1);
    }
    return ret;
}
void bfs(string A) {
    queue<string> Q;
    string u, v;
    Rstep.clear();
    A = reduceCube(A); 
    Q.push(A), Rstep[A] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = Rstep[u];
        if (step >= 4)	continue;
        for (int i = 0; i < 9; i++) {
            v = reduceCube(rotateCube(u, i, 0));
            if (Rstep.find(v) == Rstep.end()) {
                Rstep[v] = step + 1;
                Q.push(v);
            }
            v = reduceCube(rotateCube(u, i, 1));
            if (Rstep.find(v) == Rstep.end()) {
                Rstep[v] = step + 1;
                Q.push(v);
            }
        }
    }
//	printf("4 steps state %d\n", Rstep.size());
}
int bfs2(string A) {
    if (isCompleted(A.c_str()))
        return 0;
    queue<string> Q;
    string u, v;
    Bstep.clear();
    A = reduceCube(A); 
    Q.push(A), Bstep[A] = 0;
    int ret = 0x3f3f3f3f;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = Bstep[u];
        if (Rstep.find(u) != Rstep.end())
            ret = min(ret, step + Rstep[u]);
        if (step >= 3 || step + hfunction(u) >= min(7, ret))
            continue;
        for (int i = 0; i < 9; i++) {
            v = reduceCube(rotateCube(u, i, 0));
            if (Bstep.find(v) == Bstep.end()) {
                Bstep[v] = step + 1;
                Q.push(v);
            }
            v = reduceCube(rotateCube(u, i, 1));
            if (Bstep.find(v) == Bstep.end()) {
                Bstep[v] = step + 1;
                Q.push(v);
            }
        }
    }
    return ret <= 7 ? ret : -1;
}
int main() {
    adjustInfo();
    bfs("WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY");
    int testcase, cases = 0;
    char A[64];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", A);
        int ret = bfs2(A);
        
        printf("Case %d: ", ++cases);
        if (ret == -1)
            puts("Impossible");
        else
            printf("%d\n", ret);
    }
    return 0;
}
/*
      W W W                               1  2  3
      W W W                               4  5  6
      W W W                               7  8  9
R R R B B B O O O G G G         10 11 12 13 14 15 16 17 18 19 20 21
R R R B B B O O O G G G         22 23 24 25 26 27 28 29 30 31 32 33
R R R B B B O O O G G G         34 35 36 37 38 39 40 41 42 43 44 45
      Y Y Y                              46 47 48
      Y Y Y                              49 50 51
      Y Y Y                              52 53 54
4
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY
WWWWWWRRRRRYBBBWOOGGGRRYBBBWOOGGGRRYBBBWOOGGGOOOYYYYYY
WWBWWBWWBRRRBBYOOOWGGBBYOOOWGGRRRRRRBBYOOOWGGYYGYYGYYG
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYGGGYYYYYY
*/
Read More +
解題區/解題區 - UVa

UVa 12886 - The Big Painting

Problem

兩個 2D 模式找出現的次數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo

Sample Output

1
4

Solution

做法來源：http://www.csie.ntnu.edu.tw/~u91029/StringMatching.html#5

演算法筆記－2D String Matching: Baker-Bird Algorithm

步驟 1.
把 T 橫切成一條一條，
把 P 橫切成一條一條，
然後每一條 T 都執行 Multi-Pattern String Matching，例如Aho-Corasick Algorithm。
如果第 a 條 P ，從 T[i,j] 開始出現，那麼就進行紀錄：M[i,j] = a。
M 是一個跟 T 一樣大的陣列。

步驟 2.
把M直切成一條一條，
每一條M都執行String Matching，例如Morris-Pratt Algorithm。
看看是否出現1234567…n這個字串（剛剛P共有n條）。

要點
當 P 有某兩條相同時，則要小心處理，把這兩條的編號設為相同。
AC 自動機不用跑匹配的後綴，因為必然是沒有的，所以在這裡的 AC 自動機寫法比較特別。

速度看起來挺慢的，也許 hash 或者是 FFT 某方面對於這種會稍微快一點？

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
// similar 11019 - Matrix Matcher 
#define MAXN 2048
char T[MAXN][MAXN], P[MAXN][MAXN];
int M[MAXN][MAXN];
//<AC automation>
struct Node {
    Node *next[26], *fail;
    int matched, label;
    Node() {
        fail = NULL;
        matched = -1;
        label = -1;
        memset(next, 0, sizeof(next));
    }
};
int insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx;
    p = root;
    for(i = 0; str[i]; i++) {
        idx = str[i]-'a';
        if(p->next[idx] == NULL)
            p->next[idx] = new Node();
        p = p->next[idx];
    }
    if(p->label == -1)
        p->label = label;
    return p->label;
}
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 < 26; 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];
        }
    }
}
void quertACautomaiton(const char* str, Node *root, int row) {
    static Node *p, *q;
    static int i, idx;
    p = root;
    for(i = 0; str[i]; i++) {
        idx = str[i]-'a';
        while(p != root && p->next[idx] == NULL)
            p = p->fail;
        p = p->next[idx];
        p = (p == NULL) ? root : p;
        q = p;
        M[row][i] = -1;
        if(q != root && q->label >= 0)
            M[row][i] = q->label;
    }
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 26; i++)
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        delete nd;
    }
}
//</AC automation>
int kmpTable[MAXN];
void KMPtable(int P[], int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPMatching(int T[], int P[], int tlen, int plen) {
    int i, j;
    int matchCnt = 0;
    for(i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1) {
            matchCnt++;
            j = kmpTable[j];
        }
    }
    return matchCnt;
}
int main() {
    int testcase;
    int n, m, x, y;
    int i, j, k;
    int pattern[MAXN], str[MAXN];
    while(scanf("%d %d", &x, &y) == 2) {
        scanf("%d %d", &n, &m);
    	Node *root = new Node();
        for(i = 0; i < x; i++) {
            scanf("%s", P[i]);
            pattern[i] = insertTrie(P[i], root, i);
        }
        for(i = 0; i < n; i++)
            scanf("%s", T[i]);
            
        buildACautomation(root);
        for(i = 0; i < n; i++)
            quertACautomaiton(T[i], root, i);
            
        /*for(i = 0; i < x; i++)
            printf("%d xx\n", pattern[i]);
        for(i = 0; i < n; i++, puts(""))
            for(j = 0; j < m; j++)
                printf("%3d ", M[i][j]);*/
        KMPtable(pattern, x);
        int ret = 0;
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++)
                str[j] = M[j][i];
            ret += KMPMatching(str, pattern, n, x);
        }
        printf("%d\n", ret);
        freeTrie(root);
    }
    return 0;
}
/*
4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo
*/
Read More +
解題區/解題區 - UVa

UVa 12881 - Ricochet Robots

Problem

一款神秘的團隊遊戲，機器人需要彼此合作，使得 1 號機器人恰好停留在 X 上面。盤面最多給定 4 個機器人。

每一個時刻，最多有一個機器人進行移動，此時會將其他機器人視為障礙物，每次選擇其中一個方向，並且要移動到碰到障礙物為止。

在有限步數內找到一個最小步數，如果找不到輸出無解。

Sample Input

1
2
3
4
5
6
7
8
9
10
2 5 4 10
.2...
...W.
WWW..
.X.1.
1 5 4 10
.....
...W.
WWW..
.X.1.

Sample Output

1
2
6
NO SOLUTION

Solution

把多個機器人的座標作為一個狀態。狀態紀錄時，除了 1 號機器人外，其他機器人的座標視為集合看待，適當地減少搜索狀態。

跟預期想的相同，全搜索不致於造成狀態總數過大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int N, W, H, L;
struct state {
    pair<int, int> xy[4];
    bool operator<(const state &a) const {
        for (int i = 0; i < N; i++)
            if (xy[i] != a.xy[i])
                return xy[i] < a.xy[i];
        return false;
    }
    void normal() {
        sort(xy + 1, xy + N);
    }
};
char g[16][16];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int isValid(int x, int y) {
    return x >= 0 && y >= 0 && x < H && y < W;
}
int bfs(state init, int L) {
    state u, v;
    queue<state> Q;
    map<state, int> R;
    int x, y, tx, ty;
    int used[11][11] = {}, testcase = 0;
    init.normal();
    Q.push(init), R[init] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = R[u];
        if (g[u.xy[0].first][u.xy[0].second] == 'X')
            return step;
        if (step > L)
            continue;
        testcase++;
        for (int i = 0; i < N; i++) {
            x = u.xy[i].first, y = u.xy[i].second;
            used[x][y] = testcase;
        }
        for (int i = 0; i < N; i++) {
            x = u.xy[i].first, y = u.xy[i].second;
            for (int j = 0; j < 4; j++) {
                tx = x, ty = y;
                while (isValid(tx + dx[j], ty + dy[j])) {
                    if (g[tx + dx[j]][ty + dy[j]] == 'W')
                        break;
                    if (used[tx + dx[j]][ty + dy[j]] == testcase)
                        break;
                    tx += dx[j], ty += dy[j];					
                }
                v = u, v.xy[i] = make_pair(tx, ty);
                v.normal();
                if (R.find(v) == R.end()) {
                    R[v] = step + 1;
                    Q.push(v);
                }
            }
        }
    }
    return 0x3f3f3f3f;
}
int main() {
    while (scanf("%d %d %d %d", &N, &W, &H, &L) == 4) {
        for (int i = 0; i < H; i++)
            scanf("%s", g[i]);
        
        state init;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (g[i][j] >= '1' && g[i][j] <= '9')
                    init.xy[g[i][j] - '1'] = make_pair(i, j);
            }
        }
        
        int ret = bfs(init, L);
        if (ret > L)
            puts("NO SOLUTION");
        else
            printf("%d\n", ret);
    }
    return 0;
}
/*
2 5 4 10
.2...
...W.
WWW..
.X.1.
1 5 4 10
.....
...W.
WWW..
.X.1.
*/
Read More +
解題區/解題區 - UVa

UVa 12870 - Fishing

Problem

有 N x M 個魚池，接著要進行釣魚，為了防止生態滅絕，必須要餵兩次魚才能釣一次魚。餵魚時必須嚴格往右下角餵，釣魚也必須依序嚴格往右下角餵。很特別的是，釣魚、餵魚不影響魚池內的數量 (WTF)。餵魚成本、釣魚獲益都等於該魚池的數量，可以選擇在同一個魚池餵魚或者是釣魚。

求最大獲益為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
2
4 4
1 1 1 4
1 3 1 1
1 1 2 1
1 1 1 1
3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output

1
2
2
0

Solution

兩個路徑獨立，分開計算最大獲益路徑，直接著手 dp，找左上到右下，挑數個進行釣魚和餵魚動作。

每一個位置多紀錄已經挑了多少個魚池動作，隨後窮舉到底要怎麼組合來得到最佳獲益。

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 <math.h>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 128
int dp[MAXN][MAXN][MAXN];
int dp2[MAXN][MAXN][MAXN];
int main() {
    int testcase;
    int n, m, A[128][128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &A[i][j]);
        int nm = min(n, m);
        int lenMAX[128] = {}, lenMIN[128] = {};
        for (int i = 0; i <= nm; i++) {
            lenMAX[i] = 0;
            lenMIN[i] = -0x3f3f3f3f;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k <= nm; k++) {
                    dp[i][j][k] = 0, dp2[i][j][k] = -0x3f3f3f3f;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j][1] = max(dp[i][j][1], A[i][j]);
                dp2[i][j][1] = max(dp2[i][j][1], -A[i][j]);
                for (int k = 1; k <= nm; k++) {
                    if (i > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i-1][j][k]);
                    }
                    if (j > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i][j-1][k]);
                    }
                    if (i > 0 && j > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + A[i][j]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i-1][j-1][k-1] - A[i][j]);
                    }
//                    printf("%d %d %d %d\n", i, j, k, dp2[i][j][k]);
                }
                for (int k = 1; k <= nm; k++)
                    lenMAX[k] = max(lenMAX[k], dp[i][j][k]), lenMIN[k] = max(lenMIN[k], dp2[i][j][k]);
            }
        }
        int ret = 0;
        for (int i = 2; i <= nm; i += 2) {
            ret = max(ret, lenMAX[i/2] + lenMIN[i]);
//            printf("%d %d %d\n", i, lenMAX[i/2], lenMIN[i]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
 9999
 4 4
 1 1 1 4
 1 3 1 1
 1 1 2 1
 1 1 1 1
 3 5
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 3 4
 0 0 1 0
 0 0 2 0
 0 1 0 0
 2 2
 0 1
 2 0
 2 3
 10 20 30
 30 4 50
 3 2
 10 20
 30 30
 4 50
 */
Read More +
解題區/解題區 - UVa

UVa 12866 - Combination

Problem

Total number of odd entries in first n rows of Pascal’s triangle.

對於巴斯卡三角形找奇數的個數。

Sample Input

1
2
3
4
2 3
10 20
100 200
0 0

Sample Output

1
2
6
70

Solution

下面是巴斯卡三角形 (組合數) 前 n 行為奇數的總個數。

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, 119, 135, 139, 147, 155, 171, 179, 195, 211, 243, 245, 249, 253, 261, 265, 273, 281, 297, 301, 309, 317, 333, 341, 357, 373, 405, 409, 417, 425, 441, 449, 465, 481, 513, 521

在 A006046 可以得到遞迴公式：

  • a(0) = 0
  • a(1) = 1
  • a(2k) = 3 * a(k), a(2k+1) = 2*a(k) + a(k+1)

但是在第三項中可以發現到有可能指數增加，由於會被拆分成兩項，所以這方法不太可行。

如果打印每一行的奇數個數出來，四四分組，會發現組合是以 2 的冪次增長的組合，而組合之間恰好是兩倍的關係。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1 2 2 4  ----------- sum 9
2 4 4 8  ----------- sum 27
--
2 4 4 8 
4 8 8 16 ----------- sum 81
-- prev x 2
2 4 4 8 
4 8 8 16 
4 8 8 16 
8 16 16 32 ----------- sum 273  
-- prev x 2
2 4 4 8 
4 8 8 16 
4 8 8 16 
8 16 16 32 
4 8 8 16 
8 16 16 32
...

觀察如上所述，遞推之。

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> 
// https://oeis.org/A006046
// a(0) = 0, a(1) = 1, a(2k) = 3*a(k), a(2k+1) = 2*a(k) + a(k+1).
long long f(long long n) {
    if (n < 2)	return n;
    if (n&1) 
        return f(n/2) * 2 + f(n/2 + 1);
    else
        return f(n/2) * 3;
}
unsigned long long dp[50] = {};
unsigned long long g(long long n) {
    if (n == 0)	return 0;
    if (n == 1)	return 1;
    if (n == 2)	return 3;
    if (n == 3)	return 5;
    if (n == 4)	return 9;
    if (n == 5)	return 11;
    if (n == 6)	return 15;
    if (n == 7)	return 19;
    long long i, j;
    for (i = 1, j = 1; 8 * i < n; i <<= 1, j++);
//	printf("%lld %lld %lld %lld\n", j, n, i, n - 4 * i);
    return dp[j] + 2 * g(n - 4 * i);
}
int main() {
    dp[1] = 9, dp[2] = 27;
    for (int i = 3; i < 50; i++)
        dp[i] = dp[i - 1] * 3;
     
//	int C[105][105] = {}, totsum = 0;
//	C[0][0] = 1;
//	for (int i = 0; i < 100; i++) {
//		C[i][0] = 1;
//		int sum = 1;
//		for (int j = 1; j <= i; j++) {
//			C[i][j] = (C[i-1][j] + C[i-1][j-1])&1;
//			sum += C[i][j];
//		}
//		totsum += sum;
//		printf("%2d: %5d %5d\n", i, sum, totsum);
//	}
//	for (int i = 0; i < 50; i++) {
//		for (int j = 0; j <= i; j++)
//			printf("%d", C[i][j]);
//		puts("");
//	}
    long long L, R;
    while (scanf("%lld %lld", &L, &R) == 2) {
        if (L == 0 && R == 0)
            break;
//		printf("%lld %lld\n", f(R + 1), g(R + 1));
//		long long ret = f(R + 1) - f(L);
//		printf("%lld\n", ret);
        unsigned long long ret2 = g(R + 1) - g(L);
        printf("%llu\n", ret2);
    }
    return 0;
}
Read More +
雜言筆記

ACM-ICPC 訓練爭議

這場爭論還在持續中，活在什麼環境就會有什麼樣的想法，沒有全區的誰對誰錯。老子就是看那群台清交不爽啊！努力、聰明從來都不是問題，不能讓人佩服得心服口服就會不滿，認知差異、體諒差異，並非積極消除差異。

拿努力、聰明的成果當作區隔、拒絕的手段，倒不如說「空閒時間會嘗試用自己的方法。」不做其實沒差。等到沒了戰友，那又是什麼困境呢？

大家好，我是 morris (morris821028)，被點名來說對於 ACM-ICPC 競賽資源在各校分配不均的看法。

首先，有個共識台清交都有系統式訓練，若說沒有系統式訓練，至少還有一群默默在背後敲代碼的同學、學長一起奮鬥。訓練環境有資源、有伴、有敵，對於非台清交的學生大多數沒有這樣的方式學習，但我覺得沒必要用相同的模式運作、也辦不到。

有教授、學長們引領固然不錯，能在有限時間內達到競賽水平，從高中開始當 ACMer 的我來說，很多人大學才開始學這領域，兩年就能上戰場的牛人，當然會先精神崩潰一下，然後吵著、罵著「他們有資源啊！」當時也這麼暗地著罵著，仔細想想自己沒有辦法在所謂系統式訓練下苟延殘喘，已經在沒有督促下學習很久，把我關進籠子學習，大概只會見到越來越低落的 morris。

對我來說，講講自己有多討厭你們的才華、罵罵你們所擁有的資源，心裡才會舒坦點。間歇性地說這些，明白自己永遠不會跟你們用同一個方式做事、學習。「爭取」作為一個求上進的舉動？爭取到後，才發現自己多麼不合適，還不如讓適合的人運用這些資源。

我們被放上同一個架子上面比價，所以才會這麼不滿。「這麼不滿？那為什麼還要自找苦吃？」只是想學、還不想輸，願意用那數倍的時間來驗證自己的價值，也許不會被兜售出去，起碼價值還有機會留下，用不同的方式引領不一樣的人。

「就算如此我也不想輸」－《三月的獅子》

分配不均很正常，不然要拿什麼作為目標？等把自己所擁有的資源啃食完後，自然而然地就會找到、接觸新的資源，這樣比較有尋寶的樂趣？

「因為找不到解答，就什麼都不做」是無法解決任何問題的－《三月的獅子》

我來自東部的花蓮，要說高中學習資源，少之又少！學長們也要在西部學校讀書，哪有空回學校教人，回來教一兩隻小貓？

高中－花蓮高中資優班，但也別想太多，咱們資優班不看整體分數的高低，考試靠單科成績決勝負，並且三年不換人。因此才有專題課選擇資訊的機會，從上高中開始才接觸這領域，一開始非常討厭寫程序，打從心底就排斥它。

靠著抄同學的作業活過來，老師教了語法基礎後，就發布挑戰－「寒暑假在 Zerojudge 完成 100 題」大家也知道 ZJ 很多水題，自然而然地成為生活中的一部分，水題寫個一天也不是問題，也許就是東部小孩的權力吧，不是為了競賽成績而學。

參加 NPSC、資訊科能力競賽，當時參加三年 NPSC 連一題都沒寫出來，根本不會讀檔操作，拿了錯誤訊息回來還真不知道是沒有讀檔成功還什麼的，就這麼度過三年比賽。在 NPSC 0 題，幾乎可以說是高中傳承的零題傳統。

在東區資訊科能力競賽中，程設部分都是數學模擬，跟西部的題目大相逕庭。決戰點都是在計概，那時不喜歡讀書的我幾乎都拿了期望值回來。最後一年進了全國賽，程設題目幾乎全寫，興沖沖地排隊等測試，那時還有「寫比較多題的人排前面」測試完後，拿了慘不忍睹的成績，早知道乾脆不寫。測試一結束，就趕緊搭車回花蓮，連頭都不想回。

(以上略－)

如果多少認識我，都明白我英文不好、中文理解也不行，出去比賽還需要一個高強度容忍的翻譯機，不然寫到一半的翻桌。這樣的能力絕對上不了台清交，大學就讀中興大學，隨後嘗試轉學到台清交成，但是沒有成功。最後在茵可的邀約才到中央大學。

也不是說要多麼有系統的訓練，學校課程沒有台清交的課程繁重，我們一學期的課程內容說不定還比不上台清交幾周的內容，有比較多時間慢慢寫程式，即使進步很慢，寫得好 (易懂)、寫得快比起寫得正確來得有趣。

我不適合比賽，跟學長們玩了幾次全國競賽，創下學校成績新高之後，就這麼解散。不弄 Topcoder、Codeforces 及 Google Code Jam，一來是看完題目差不多比賽就結束，二來介面和流程一度讓我精神崩潰，所以窩在簡單的 UVa 裡面打混。

打混的方式－東抄抄西抄抄，因為想要 AC、想出題，所以才學某些噁心的算法。看代碼、看題解學習就是我的學習方式，看了也不見得懂，那為什麼還要怕去看別人寫的？所有都由自己想、自己解決對我來說是奢侈，有 CSDN 可以靠，對我來說資源很夠，就怕沒能力理解。

部落格的部分內容根本不是寫給別人看的，整個 google 就是我的 codebook，寫完就會忘、理解透徹也會忘、自己做的報告也會忘。

啊，像我這般被人需要還是第一次啊－《遊戲人生》

可喜可賀 可喜可賀－《甘城輝煌樂園救世主》

Read More +
解題區/解題區 - UVa

UVa 12795 - Ecology

Problem

給 N x N 個 grid，每一格有權重，找到一個連通子圖，其大小恰好為 M，並且具有最大權重。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 6
31 12 7 1 14
23 98 3 87 1
5 31 8 2 99
12 3 42 17 88
120 2 7 5 7
4 8
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1

Sample Output

1
2
377
72

Solution

Number of fixed polyominoes with n cells.

Number of fixed polyominoes with n cells. (Formerly M1639 N0641)
1, 2, 6, 19, 63, 216, 760, 2725, 9910, 36446, 135268, 505861, 1903890, 7204874, 27394666, 104592937, 400795844, 1540820542, 5940738676, 22964779660, 88983512783, 345532572678, 1344372335524, 5239988770268, 20457802016011, 79992676367108, 313224032098244, 1228088671826973

連通子圖 n = 10 也不過 36446，對於所有位置嘗試擺放，也不過 O(36446 * 50 * 50)，給 60 秒還跑不出來。

關於窮舉連通圖的部分，想像成生成樹，這棵樹必然要有 M 個節點，適時要在葉節點返回，然後在其他尚未長出來的地方繼續生長。根據尤拉路徑最多走 2M 步，窮舉 2M 步進行建造。

為了加快窮舉速度，將找到的 polyominoes 依據長寬儲存，窮舉時先 greedy 估算這個矩形內部能產出最好的 polyominoes 可能是多少，如果已經低於已知解就直接放棄。

只能說測資不隨機，有極端測資，照理來講不用建表的速度應該會稍微快了些。

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
#include <stdio.h> 
#include <vector>
#include <map>
#include <algorithm>
#include <set> 
#include <string.h>
#include <assert.h>
using namespace std;
int g[64][64], n, m;
int used[64][64];
pair<int, int> path[64], pre[64][64];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct Area {
    vector<pair<int, int> > V;
    bool operator<(const Area &a) const {
        for (int i = 0; i < V.size(); i++) 
            if (V[i] != a.V[i])	return V[i] < a.V[i];
        return false;
    }
    Area() {
        V.clear();
    }
};
// Number of fixed polyominoes with n cells. https://oeis.org/A001168
set<Area> shape[16][16][16];
void storeArea(Area a) {
    sort(a.V.begin(), a.V.end());
    int x, y, mx, my;
    x = a.V[0].first, y = a.V[0].second;
    mx = x, my = y;
    for (int i = 0; i < a.V.size(); i++) {
        x = min(x, a.V[i].first), y = min(y, a.V[i].second);
        mx = max(mx, a.V[i].first), my = max(my, a.V[i].second);
    }
    for (int i = 0; i < a.V.size(); i++)
        a.V[i].first -= x, a.V[i].second -= y;
    sort(a.V.begin(), a.V.end());
    shape[a.V.size()][mx - x][my - y].insert(a);
    assert(mx - x >= 0 && mx - x < 16 && my - y >= 0 && my - y < 16);
}
void dfs(int idx, int x, int y, int pick, int m) {
    if (pick == m) {
        Area t;
        for (int i = 0; i < pick; i++)
            t.V.push_back(path[i]);
        storeArea(t);
        return ;
    }
    if (idx >= 2 * m)
        return;
    vector< pair<int,int> > test;
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i], 
            ty = y + dy[i];
        if (used[tx][ty])
            continue;
        pre[tx][ty] = make_pair(x, y);
        path[pick] = make_pair(tx, ty);
        used[tx][ty] = 1;
        dfs(idx+1, tx, ty, pick + 1, m);
        test.push_back(make_pair(tx, ty));
    }
    if (pre[x][y].first != -1) // stop on leaf
        dfs(idx+1, pre[x][y].first, pre[x][y].second, pick, m);
    for (int i = 0; i < test.size(); i++) {
        int tx = test[i].first,
            ty = test[i].second;
        used[tx][ty] = 0;
    }
}
int place(int x, int y, int n, const Area &a) {
    int ox = x, oy = y;
    int sum = 0;
    for (int i = 0; i < a.V.size(); i++) {
        x = ox + a.V[i].first;
        y = oy + a.V[i].second;
        if (x < 0 || y < 0 || x >= n || y >= n)	return 0;
        sum += g[x][y];
    }
    return sum;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j < 32; j++)
            for (int k = 0; k < 32; k++)
                pre[j][k] = make_pair(-1, -1);
        pre[11][11] = make_pair(-1, -1);
        path[0] = make_pair(11, 11);
        used[11][11] = 1;
        dfs(1, 11, 11, 1, i);
        used[11][11] = 0;
        int sum = 0;
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < i; k++)
                sum += shape[i][j][k].size();
        } 
//		printf("complete %d %d\n", i, sum);
    }
    while (scanf("%d %d", &n, &m) == 2) {
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &g[i][j]);
            }
        }
        
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int mx[16] = {}, mxx = 0, tmp;
                for (int p = 0; p < m && i + p <= n; p++) {
                    mxx = 0;
                    for (int q = 0; q < m && j + q <= n; q++) {
                        mx[q] = max(mx[q], g[i+p][j+q]);
                        mxx = max(mxx, mx[q]);
                        if (mxx * m <= ret)	continue;
                        vector<int> D;
                        for (int a = i; a <= i+p; a++)
                            for (int b = j; b <= j+q; b++) 
                                D.push_back(g[a][b]);
                        sort(D.begin(), D.end(), greater<int>());
                        tmp = 0;
                        for (int a = 0; a < m; a++)
                            tmp += D[a];
                        if (tmp <= ret)		continue;
                        for (set<Area>::iterator it = shape[m][p][q].begin(); 
                            it != shape[m][p][q].end(); it++) {
                            ret = max(ret, place(i, j, n, *it));
                        }
                    }
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
5 6
31 12 7 1 14
23 98 3 87 1
5 31 8 2 99
12 3 42 17 88
120 2 7 5 7
4 8
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1
3 5
0 5 0
5 5 5
0 5 0
10 5
733 950 26 696 512 570 327 531 829 600 
499 459 728 877 673 464 368 438 566 599 
512 631 242 499 919 931 688 602 490 172 
587 745 704 453 475 370 47 439 705 844 
133 449 264 732 361 612 196 635 739 853 
944 872 938 228 74 296 604 677 801 27 
763 628 650 40 558 159 7 500 405 423 
450 455 26 543 881 87 292 431 74 546 
349 115 568 589 390 40 606 802 434 479 
732 890 361 334 208 439 118 18 494 894 
*/
Read More +
解題區/解題區 - UVa

UVa 12761 - Blue Chips

Problem

N 個人圍繞一圈，每一個回合自身的分數為相鄰距離小於 D (不包含自己) 的權重總和 mod N。

請問在 K 個回合後，最大分數和擁有最大分數的人分別為何？

Sample Input

1
2
3
1
3 3 1
1 2 2

Sample Output

1
2
1
2 3

Solution

由於 K 很大，明顯地是一道矩陣 D&C。

把遞迴公式建造出來，可以在 O(N^3 log 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int mod = 10000;
struct Matrix {
    int v[64][64];
    int row, col; // row x col
    Matrix(int n, int m, int a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++) {
            for(int k = 0; k < col; k++) {
                if (v[i][k])
                    for(int j = 0; j < x.col; j++) {
                        ret.v[i][j] += v[i][k] * x.v[k][j],
                        ret.v[i][j] %= mod;
                    }
            }
        }
        return ret;
    }
    Matrix operator+(const Matrix& x) const {
        Matrix ret(row, col);
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                ret.v[i][j] = v[i][j] + x.v[i][j];
            }
        }
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
    Matrix powsum(int k) {
        if (k == 0) return Matrix(row, col, 0);
        Matrix vv = powsum(k/2);
        if (k&1) {
            return vv * (Matrix(row, col, 1) + vv) + vv;
        } else {
            return vv * (Matrix(row, col, 1) + vv);
        }
    }
};
int main() {	
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout); 
    int testcase, N, K, D;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &D);
        mod = N;
        Matrix m(N, N), a(N, 1);
        for (int i = 0; i < N; i++)
            scanf("%d", &a.v[i][0]), a.v[i][0] %= N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if ((abs(i - j) <= D || N - abs(i - j) <= D) && i != j)
                    m.v[i][j] = 1;
            }
        }
        Matrix ret = (m ^ K);
        ret = ret * a;
        int mn = 0x3f3f3f3f;
        for (int i = 0; i < N; i++) {
            mn = min(mn, ret.v[i][0]);
        }
        printf("%d\n", mn);
        int f = 0;
        for (int i = 0; i < N; i++) {
            if (ret.v[i][0] == mn) {
                if (f)  putchar(' ');
                f = 1;
                printf("%d", i + 1);
            }
        }
        puts("");
    }
    return 0;
}
/*
 1
 3 3 1
 1 2 2
 */
Read More +