解題區/解題區 - UVa

UVa 814 - The Letter Carrier's Rounds

Problem

模擬郵件發送的協定訊息，給定給一台 mail server 上的使用者名稱，接著發送群組訊息。

每一組發送者，會按照輸入順序的 mail server，將相同的 server 上的使用者統一發送，如果存在不合法的使用者名稱，必須回傳找不到，如果對一個 mail server 中都沒有合法使用者，則忽略此次傳送。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
Connection between Cairo and MexicoCity
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Conrado@MexicoCity>
     250
     RCPT TO:<Lisa@MexicoCity>
     550
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between Cairo and SanFrancisco
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Shariff@SanFrancisco>
     250
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between London and HongKong
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Chen@HongKong>
     250
     DATA
     354
     Thanks for the report!  --Fiona
     .
     250
     QUIT
     221
Connection between London and Paris
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Natasha@Paris>
     550
     QUIT
     221

Solution

一個純模擬的題目，關於此類協定可以在計算機網路中學到。

保證寄信者都是合法的，小心每一行的資訊可能很長，用 char array 很容易 buffer overflow。也因此掛了很多 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
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <vector> 
using namespace std;
set<string> MTA;
int readMTA() {
    string cmd, mta, name;
    int n;
    while (cin >> cmd) {
        if (cmd == "*")	return 1;
        cin >> mta >> n; 
        for (int i = 0; i < n; i++) {
            cin >> name;
            MTA.insert(string(name) + "@" + string(mta));
        }
    }
    return 0;
}
void parse_address(const string& s, string& user, string& mta) {
  int k = s.find('@');
  user = s.substr(0, k);
  mta = s.substr(k+1);
}
int main() {
    string msg;
    readMTA();
    while (cin >> msg) {
        if (msg[0] == '*')	break;	
        vector<string> user, mta, mail;
        set<string> S;
        vector<int>	used;
        string u, m;
        parse_address(msg, u, m);
        user.push_back(u), mta.push_back(m);
        while (cin >> msg && msg[0] != '*') {
            parse_address(msg, u, m);
            if (S.count(u + "@" + m))	continue;
            S.insert(u + "@" + m);
            user.push_back(u), mta.push_back(m);
        }
        while (getchar() != '\n');
        while (getline(cin, msg) && msg[0] != '*')
            mail.push_back(msg);
        used.resize(user.size(), 0);
        for (int i = 1; i < user.size(); i++) {
            if (used[i])	continue;
            printf("Connection between %s and %s\n", mta[0].c_str(), mta[i].c_str());
            printf("     HELO %s\n", mta[0].c_str());
            printf("     250\n");
            printf("     MAIL FROM:<%s@%s>\n", user[0].c_str(), mta[0].c_str());
            printf("     250\n");
            int s = 0;
            for (int j = i; j < user.size(); j++) {
                if (mta[j] == mta[i]) {
                    used[j] = 1;
                    printf("     RCPT TO:<%s@%s>\n", user[j].c_str(), mta[j].c_str());
                    if (MTA.count(user[j] + "@" + mta[j]))
                        printf("     250\n"), s++;
                    else
                        printf("     550\n");
                }
            }
            if (s > 0) {
                printf("     DATA\n");
                printf("     354\n");
                for (int j = 0; j < mail.size(); j++)
                    printf("     %s\n", mail[j].c_str());
                printf("     .\n");
                printf("     250\n");
            }
            printf("     QUIT\n");
            printf("     221\n");
        }
    }
    return 0;
}
/*
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*
*/
Read More +
解題區/解題區 - UVa

UVa 810 - A Dicey Problem

Problem

給一個 2D 地圖，上面放置一骰子，人從 2D 地圖的下方往上方看，骰子必須貼著某一條邊，往上下左右的地方滾過去，滾的時候必須滿足，其骰子上方的點數與地圖該格的點數相同，或者是移動到星號位置。

一開始給定骰子面向玩家的點數、以及骰子上方的點數，骰子滾動出去回到原本地方的最短路徑為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DICEMAZE1
3 3 1 2 5 1
-1 2 4
5 5 6
6 -1 -1
DICEMAZE2
4 7 2 6 3 6
6 4 6 0 2 6 4
1 2 -1 5 3 6 1
5 3 4 5 6 4 2
4 1 2 0 3 -1 6
DICEMAZE3
3 3 1 1 2 4
2 2 3
4 5 6
-1 -1 -1
END

Sample Output

1
2
3
4
5
6
7
8
DICEMAZE1
  (1,2),(2,2),(2,3),(3,3),(3,2),(3,1),(2,1),(1,1),(1,2)
DICEMAZE2
  (2,6),(2,5),(2,4),(2,3),(2,2),(3,2),(4,2),(4,1),(3,1),
  (2,1),(2,2),(2,3),(2,4),(2,5),(1,5),(1,6),(1,7),(2,7),
  (3,7),(4,7),(4,6),(3,6),(2,6)
DICEMAZE3
  No Solution Possible

Solution

每一個 2D 位置 (x, y) 會有兩個骰子資訊做為紀錄，只需要知道骰子的兩個面，即可知道骰子的結構。

針對其狀態進行 bfs 搜索，手動打表維護骰子滾動的資訊。

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
#include <stdio.h>
#include <string.h> 
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define MAXSTATE 65536
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct state {
    int x, y, top, front;
    state *prev;
} states[MAXSTATE];
int statesIdx;
int n, m, sx, sy, dtop, dfront;
int g[32][32];
state* getNewState(int x, int y, int dtop, int dfront, state *prev = NULL) {
    state *p = &states[statesIdx++];
    assert (statesIdx < MAXSTATE);
    p->x = x, p->y = y, p->top = dtop, p->front = dfront, p->prev = prev;
    return p;
}
int diceTable[7][7]; // [front][top] = right
void rotateDice(int dir, int dtop, int dfront, int &rtop, int &rfront) {
    rtop = rfront = 1;
    if (dir == 0) { // roll up
        rtop = dfront, rfront = 7 - dtop;
    } else if (dir == 1) { // roll down
        rtop = 7 - dfront, rfront = dtop;
    } else if (dir == 2) { // roll left
        rfront = dfront;
        rtop = diceTable[dfront][dtop];
    } else if (dir == 3) { // roll right
        rfront = dfront;
        rtop = 7 - diceTable[dfront][dtop];
    }
}
void bfs(int sx, int sy, int dtop, int dfront) {
    statesIdx = 0;
    int used[32][32][7][7] = {}; // used[x][y][dtop][dfront]
    int tx, ty, tdtop, tdfront;
    queue<state*> Q;
    state *u, *v;
    Q.push(getNewState(sx, sy, dtop, dfront));
    used[sx][sy][dtop][dfront] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        for (int i = 0; i < 4; i++) {
            tx = u->x + dx[i], ty = u->y + dy[i];
            if (tx <= 0 || ty <= 0 || tx > n || ty > m)
                continue;
            if (g[tx][ty] != -1 && g[tx][ty] != u->top)
                continue;
            if (tx == sx && ty == sy) { // back to start square, print result
                vector< pair<int, int> > ret;
                state *p = u;
                ret.push_back(make_pair(sx, sy));
                while (p != NULL) {
                    ret.push_back(make_pair(p->x, p->y));
                    p = p->prev;
                }
                for (int i = ret.size() - 1, j = 0; i >= 0; i--, j++) {
                    if (j%9 == 0)	printf("  ");
                    if (j%9 != 0)	printf(",");
                    printf("(%d,%d)", ret[i].first, ret[i].second);					if (j%9 == 8 || i == 0)	{
                        if (i)	printf(",\n");
                        else	puts("");
                    }
                }
                return ;
            }
            rotateDice(i, u->top, u->front, tdtop, tdfront);
            if (used[tx][ty][tdtop][tdfront])
                continue;
            used[tx][ty][tdtop][tdfront] = 1;
            v = getNewState(tx, ty, tdtop, tdfront, u);
            Q.push(v);
        }
    }
    puts("  No Solution Possible");
}
int main() {
    // diceface[front][top] = right
    diceTable[1][2] = 4, diceTable[1][3] = 2, diceTable[1][4] = 5, diceTable[1][5] = 3;
    diceTable[2][1] = 3, diceTable[2][3] = 6, diceTable[2][4] = 1, diceTable[2][6] = 4;
    diceTable[3][1] = 5, diceTable[3][2] = 1, diceTable[3][5] = 6, diceTable[3][6] = 2;
    diceTable[4][1] = 2, diceTable[4][2] = 6, diceTable[4][5] = 1, diceTable[4][6] = 5;
    diceTable[5][1] = 4, diceTable[5][3] = 1, diceTable[5][4] = 6, diceTable[5][6] = 3;
    diceTable[6][2] = 3, diceTable[6][3] = 5, diceTable[6][4] = 2, diceTable[6][5] = 4;
    
    char testcase[1024];
    while (scanf("%s", testcase) == 1) {
        if (!strcmp("END", testcase))
            break;
        scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &dtop, &dfront);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &g[i][j]);
        printf("%s\n", testcase);
        bfs(sx, sy, dtop, dfront);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1665 - Islands

Problem

給一個地勢圖，詢問若高度低於 x 時，有多少連通子圖。

Sample Input

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

Sample Output

1
2 3 1 0 0

Solution

由於詢問操作的 x 是嚴格遞增，可以發現盤面上的元素越來越少。如果反過來操作，從高度 x 由大到小開始詢問，就可以發現元素越來越多，同時是一個聯集的操作，如此一來可以使用并查集運行。

把每一個高度位置，從高到低排序，針對詢問依序將地點放置進去，每次的放置必須與相鄰存在的元素進行聯集。

為了加快速度

  • 使用基數排序，加快對於一開始需要的排序成本，已達到線性需求。
  • 優化輸入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm> 
using namespace std;
#define MAXN 1024
int g[MAXN][MAXN], h[131072], out[131072];
int parent[MAXN * MAXN], weight[MAXN * MAXN];
struct Pos {
    int x, y, h;
    Pos(int a = 0, int b = 0, int c = 0):
        x(a), y(b), h(c) {}
    bool operator<(const Pos &a) const {
        return h > a.h;
    }
};
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return 0;
    if (weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
Pos D[MAXN * MAXN], TMP[MAXN * MAXN];
void RadixSort(Pos *A, Pos *B, int n) {
    int a, x, d, C[256];
    Pos *T;
    for(x = 0; x < 4; x++) {
        d = x * 8;
        for(a = 0; a < 256; a++)     	C[a] = 0;
        for(a = n-1; a >= 0; a--)      	C[(A[a].h>>d)&255]++;
        for(a = 256 - 2; a >= 0; a--)   C[a] += C[a+1];
        for(a = n-1; a >= 0; a--)   	B[--C[(A[a].h>>d)&255]] = A[a];
        T = A, A = B, B = T;
    }    
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    const int dx[] = {0, 0, 1, -1};
    const int dy[] = {1, -1, 0, 0};
    int testcase, n, m, q, tx, ty;
//	scanf("%d", &testcase);
    ReadInt(&testcase);
    while (testcase--) {
//		scanf("%d %d", &n, &m);
        ReadInt(&n);
        ReadInt(&m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
//				scanf("%d", &g[i][j]);
                ReadInt(&g[i][j]);
//		scanf("%d", &q);
        ReadInt(&q);
        for (int i = 0; i < q; i++)
//			scanf("%d", &h[i]);
            ReadInt(&h[i]);
        
        int didx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                D[didx++] = Pos(i, j, g[i][j]);
            }
        }
        RadixSort(D, TMP, n*m);
        int idx = 0, nm = n*m, sum = 0;
        Pos u;
        for (int i = nm; i >= 0; i--)
            parent[i] = i, weight[i] = 1;
        for (int i = q - 1; i >= 0; i--) {
            while (idx < nm && D[idx].h > h[i]) {
                sum++;
                u = D[idx++];
//				printf("add %d %d - %d\n", u.x, u.y, u.h);
                for (int j = 0; j < 4; j++) {
                    tx = u.x + dx[j], ty = u.y + dy[j];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    if (g[tx][ty] > h[i]) {
                        sum -= joint(u.x * m + u.y, tx * m + ty);
                    }
                }
            }
            out[i] = sum;
//			printf("%d\n", sum);
        }
        for (int i = 0; i < q; i++)
            printf("%d ", out[i]);
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - 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 +