解題區/解題區 - UVa

UVa 11869 - SOAP Response

Problem

給一個 SOAP 的回應格式，解析給定的回應，並且提供屬性查找。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
8
<a good="true" wants="no">
<b>
<c contest="running">
<d ballon="no">
</d>
</c>
</b>
</a>
4
a.b.c.d["ballon"]
a.c["contest"]
a.b.c["contest"]
c["contest"]

Sample Output

1
2
3
4
5
Case 1:
no
Undefined
running
Undefined

Solution

SOAP 類似 HTML XML 那種，在不少網路上的諮詢服務都會有這一套規則。

不過看到這一道題目很簡單，保證輸入格式一定可以相互匹配且完整，那使用遞迴 parsing 輸入，建造一個 tree 出來，同時子樹不會出現相同的命名。

建造樹出來之後，詢問就沿著樹走訪即可。

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
#include <stdio.h> 
#include <string.h>
#include <map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
struct Node {
    string name;
    map<string, string> attr;
    vector<int> son;
    void init() {
        attr.clear();
        son.clear();
    }
};
Node node[32767];
int nodesize;
char s[1024];
void parsingAttr(string line, Node &p) {
    string ign = "<>=", attr, val;
    for (int i = 0; i < line.length(); i++) {
        if (ign.find(line[i]) != string::npos) {
            line[i] = ' ';
        }
    }
    stringstream sin(line);
    sin >> p.name;
    while (sin >> attr >> val) {
        p.attr[attr] = val.substr(1, val.length()-2);
//		cout << attr << "+++" << val << endl;
    }
}
int build(string line) {
    int label = ++nodesize;
    Node &p = node[label];
    p.init();
    parsingAttr(line, p);
    while (gets(s)) {
        if (s[1] == '/')
            break;
        p.son.push_back(build(s));
    }
    return label;
}
int main() {
    int testcase, cases = 0, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        while(getchar() != '\n');
        gets(s);
        nodesize = 0;
        int root = build(s);
        scanf("%d", &m);
        while (getchar() != '\n');
        printf("Case %d:\n", ++cases);
        while(m--) {
            gets(s);
            string ign = ".[]", token;
            for (int i = 0; s[i]; i++) {
                if (ign.find(s[i]) != string::npos) {
                    s[i] = ' ';
                }
            }
            stringstream sin(s);
            int pos = root;
            string res = "Undefined";
            sin >> token;
            if (token == node[pos].name) {
                while (sin >> token) {
                    if (token[0] == '"') {
                        string a = token.substr(1, token.length()-2);
                        if (node[pos].attr.find(a) != node[pos].attr.end())
                            res = node[pos].attr[a];
                        break;
                    } else {
                        int f = 0;
                        for (int i = 0; i < node[pos].son.size(); i++) {
                            if (token == node[node[pos].son[i]].name) {
                                f = 1;
                                pos = node[pos].son[i];
                                break;
                            }
                        }
                        if (!f)
                            break;
                    }
                }
            }
            printf("%s\n", res.c_str());
        } 
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11651 - Krypton Number System

Problem

  • 相鄰數字不可相同
  • 不可前導為 0
  • score 分數為任兩個相鄰位數相減平方的總和

請問在 base 下，指定 score 的數字有多少個。

Sample Input

1
2
3
2
6 1
5 5

Sample Output

1
2
Case 1: 9
Case 2: 80

Solution

首先，可以知道每一次增加的總數最多為 (base - 1) (base - 1)，因此我們的狀態紀錄之少要追溯到當前分數 n - (base - 1) (base - 1)。

然而由於 score 過大，不可直接著手 dp[score][tail_digit] 之類的 dp 計算。仍可以計算於 (base - 1) * (base - 1) 以下的情況。

接著，利用遞迴公式 (線性變換矩陣 ?)，每一項為 a[score][tail_digit]，而分數必須保留到當前 score - (base - 1) * (base - 1)，因此狀態將會有 (base - 1) * (base - 1) * base，也就是矩陣最大上限 5 * 5 * 6 = 150。

矩陣的部分，可以假想每一次在尾數多增加一個 digit 上去，而在初始項部分仍必須依靠 dp 去計算。矩陣快速乘法直接套用 D&C 在 O(n^3 log k) 完成，並且計算時，盡可能將無用的 0 忽略計算，否則很容易 TLE。

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
#include <stdio.h> 
#include <string.h>
const unsigned long long mod = 1LLU<<32;
struct Matrix {
    unsigned long long v[150][150];
    int row, col; // row x col
    Matrix(int n, int m, long long 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 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;
    }
};
int main() {
    int testcase, cases = 0, base, score;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &base, &score);
        printf("Case %d: ", ++cases);
        int N = (base - 1) * (base - 1);
        
        unsigned long long dp[64][64] = {}; // [sum][tail_digit] = #way 
        for (int i = 0; i <= N; i++)
            dp[0][i] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < base; j++) {
                for (int k = 0; k < base; k++) {
                    int d = (j - k) * (j - k);
                    if (i + d > N || j == k)
                        continue;
                    dp[i+d][k] += dp[i][j];
                    dp[i+d][k] %= mod;
                }
            }
        }
        
        if (score <= N) {
            unsigned long long ret = 0;
            for (int i = 1; i < base; i++)
                ret = (ret + dp[score][i])%mod;
            printf("%llu\n", ret);
            continue;
        }
        int r, c;
        r = c = (base - 1) * (base - 1) * base;
        Matrix x(r, c), y(c, 1);
        for (int i = 1; i <= N; i++)
            for (int j = 0; j < base; j++)
                y.v[(i-1) * base+j][0] = dp[i][j];
        for (int i = base; i < r; i++)
            x.v[i - base][i] = 1;
        for (int i = 0; i < base; i++) {
            for (int j = 0; j < base; j++) {
                if (i == j)	continue;
                int d = N - (i - j) * (i - j);
                x.v[(N-1)*base + i][d*base + j] = 1;
            }
        }
//		puts("");
//		for (int i = 0; i < r; i++, puts(""))
//			for (int j = 0; j < c; j++)
//				printf("%lld ", x.v[i][j]);
//		for (int i = 0; i < c; i++, puts(""))
//				printf("%lld ", y.v[i][0]);
        Matrix z = (x ^ (score - N)) * y;
        unsigned long long ret = 0;
        for (int i = 1; i < base; i++)
            ret = (ret + z.v[(N-1) * base + i][0])%mod;
        printf("%llu\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11097 - Poor My Problem!

Problem

給一張圖 (有向圖)，請問從起始點走到特定點的路徑，花費 / 經過邊數 最小值為何？

並且最多經過 1000 條邊 (含)，邊可以重複走。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3 2 0
0 1 100
1 2 200
3
0
1
2
 
5 5 0
0 1 3
1 2 4
2 3 5
2 4 6
4 3 1
2
2
3

Sample Output

1
2
3
4
5
6
0.0000 0
100.0000 1
150.0000 2
3.5000 2
3.5000 4

Solution

如果沒有限制最多經過的邊，將會相當難辦事，因為一直繞就可以將平均值拉下，而會繞多久可能要玩一下環狀收斂，最小平均環，然後檢查是否會經過這個環抵達目的地 …

當然這一題已經給定最大使用邊數，定義狀態為 dp[i][j] 使用 j 條邊抵達目的地 i 的最小花費。按照 spfa 的精神不斷更新即可。

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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
    int to, w;
    edge(int a = 0, int b = 0):
        to(a), w(b) {}
};
vector<edge> g[1024];
int dp[1024][1024], inq[1024][1024];
const int MAXE = 1000;
void solve(int source, int N) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= MAXE; j++)
            dp[i][j] = 0x3f3f3f3f;
    queue<int> X, E;
    int u, v, w, e;
    dp[source][0] = 0;
    X.push(source), E.push(0);
    while (!X.empty()) {
        u = X.front(), X.pop();
        e = E.front(), E.pop();
        inq[u][e] = 0;
        if (e == MAXE)	continue;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].to, w = g[u][i].w;
            if (dp[v][e+1] > dp[u][e] + w) {
                dp[v][e+1] = dp[u][e] + w;
                if (!inq[v][e+1]) {
                    inq[v][e+1] = 1;
                    X.push(v), E.push(e+1);
                }
            }
        }
    }
}
int main() {
    int N, M, S, Q;
    int x, y, w;
    while (scanf("%d %d %d", &N, &M, &S) == 3) {
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(edge(y, w));
        }
        
        solve(S, N);
        
        scanf("%d", &Q);
        while (Q--) {
            scanf("%d", &x);
            double ret = 1e+30;
            int e = -1;
            if (x == S)
                ret = 0, e = 0;
            else {
                for (int i = 1; i <= MAXE; i++) {
                    if (dp[x][i] != 0x3f3f3f3f) {
                        if ((double)dp[x][i]/i < ret) {
                            ret = (double)dp[x][i]/i;
                            e = i;
                        }
                    }
                }
            }
            if (e == -1)
                puts("No Path");
            else
                printf("%.4lf %d\n", ret, e);
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11421 - Arranging Cards

Problem

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

Sample Input

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

Sample Output

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

Solution

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int usedg[16][16][16][16][5];
long long dp[16][16][16][16][5];
double dp2[16][16][16][16][5];
const long long MAXVAL = 1e+18 + 10;
long long g(int f4, int f3, int f2, int f1, int last) {
    if (usedg[f4][f3][f2][f1][last])
        return dp[f4][f3][f2][f1][last];
    usedg[f4][f3][f2][f1][last] = 1; 
    long long &ret = dp[f4][f3][f2][f1][last];
    double &ret2 = dp2[f4][f3][f2][f1][last];
    if (f4 + f3 + f2 + f1 == 0) {
        ret = 1;
        ret2 = 1;
        return 1;
    }
    if (f4 > 0) {
        ret += 4 * f4 * g(f4-1, f3+1, f2, f1, 4);
        ret2 += 4 * f4 * dp2[f4-1][f3+1][f2][f1][4];
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f3 > 0) {
        if (last == 4) {
            ret += 3 * (f3 - 1) * g(f4, f3-1, f2+1, f1, 3);
            ret2 += 3 * (f3 - 1) * dp2[f4][f3-1][f2+1][f1][3];
        } else {
            ret += 3 * (f3) * g(f4, f3-1, f2+1, f1, 3);
            ret2 += 3 * (f3) * dp2[f4][f3-1][f2+1][f1][3];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f2 > 0) {
        if (last == 3) {
            ret += 2 * (f2 - 1) * g(f4, f3, f2-1, f1+1, 2);
            ret2 += 2 * (f2 - 1) * dp2[f4][f3][f2-1][f1+1][2];
        } else {
            ret += 2 * (f2) * g(f4, f3, f2-1, f1+1, 2);
            ret2 += 2 * (f2) * dp2[f4][f3][f2-1][f1+1][2];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f1 > 0) {
        if (last == 2) {
            ret += (f1 - 1) * g(f4, f3, f2, f1-1, 1);
            ret2 += (f1 - 1) * dp2[f4][f3][f2][f1-1][1];
        } else {
            ret += f1 * g(f4, f3, f2, f1-1, 1);
            ret2 += f1 * dp2[f4][f3][f2][f1-1][1];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    return ret;
}
int card2Num(char suit, char rank) {
    int s, r;
    switch(suit) {
        case 'S': s = 3;break;
        case 'C': s = 0;break;
        case 'H': s = 2;break;
        case 'D': s = 1;break;
    }
    switch(rank) {
        case '2'...'9': r = rank-'0'-2;break;
        case 'T': r = 12;break;
        case 'J': r = 9;break;
        case 'Q': r = 11;break;
        case 'K': r = 10;break;
        case 'A': r = 8;break;
    }
    return r * 4 + s;
}
int main() {
    int cases = 0;
    int N;
    long long K;
    char psuit[] = "CDHS", prank[] = "23456789AJKQT";
    while (scanf("%d %lld", &N, &K) == 2) {
        if (N == 0 && K == 0)
            break;
        char card[10];
        int A[64];
        for (int i = 0; i < N; i++) {
            scanf("%s", card);
            int x = card2Num(card[1], card[0]);
            A[i] = x;
        }
        printf("Case %d:", ++cases);
        int ret[64];
        int NOT_FOUND = 0; 
        K--;
        for (int i = 0; i < N; i++) {
            sort(A+i, A+N);
            ret[i] = -1;
            for (int j = i; j < N; j++) {
                int ch = A[j];
                int cnt[13] = {}, f[8] = {};
                if (i && ch/4 == ret[i-1]/4) 
                    continue;
                for (int k = i; k < N; k++)
                    cnt[A[k]/4]++;
                int last = cnt[ch/4]--;
                for (int k = 0; k < 13; k++)
                    f[cnt[k]]++;
                long long way = g(f[4], f[3], f[2], f[1], last);			
//				printf("%d %d %d %d - %d %lld\n", f[4], f[3], f[2], f[1], last, way);
//				printf("%lld %lf\n", way, dp2[f[4]][f[3]][f[2]][f[1]][last]);
                if (dp2[f[4]][f[3]][f[2]][f[1]][last] > K) {
                    swap(A[i], A[j]);
                    ret[i] = ch;
                    break;
                } else {
                    K -= way;
                }
            }
            if (ret[i] == -1) {
                NOT_FOUND = 1;
                break;
            }
//			puts("------");
        }
        if (NOT_FOUND) {
            puts(" Not found");
            continue;
        }
        for (int i = 0; i < N; i++)  {
//			printf("%d\n", ret[i]);
            printf(" %c%c", prank[ret[i]/4], psuit[ret[i]%4]);
        }
        puts("");
    }
    return 0;
}
/*
50 1
2C 2D 2H 2S
3C 3D 3H 3S
4C 4D 4H 4S
5C 5D 5H 5S
6C 6D 6H 6S
7C 7D 7H 7S
8C 8D 8H 8S
9C 9D 9H 9S
TC TD TH TS
JC JD JH JS
QC QD QH QS
KC KD KH
AC AD AH
*/
Read More +
解題區/解題區 - UVa

UVa 1395 - Slim Span

Problem

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

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
4 5 
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7
4 6 
1 2 10 
1 3 100 
1 4 90 
2 3 20 
2 4 80 
3 4 40 
2 1 
1 2 1
3 0 
3 1 
1 2 1
3 3 
1 2 2
2 3 5 
1 3 6 
5 10 
1 2 110 
1 3 120 
1 4 130 
1 5 120 
2 3 110 
2 4 120 
2 5 130 
3 4 120 
3 5 110 
4 5 120 
5 10 
1 2 9384 
1 3 887 
1 4 2778 
1 5 6916 
2 3 7794 
2 4 8336 
2 5 5387 
3 4 493 
3 5 6650 
4 5 1422 
5 8 
1 2 1 
2 3 100 
3 4 100 
4 5 100 
1 5 50 
2 5 50 
3 5 50 
4 1 150 
0 0

Sample Output

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

Solution

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[10005];
int p[1005], rank[1005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m, E D[], int &max_edge) {
    max_edge = 0;
    for(int i = 0; i <= n; i++)
        p[i] = i, rank[i] = 1;
    int ee = 0;
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y))
        	max_edge = max(max_edge, D[i].v), ee++;
    }
    return ee == n-1;
}
int main() {
    int n, m, x, y, w;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            D[i] = E(x, y, w);
        }
        sort(D, D+m);
        int ret = 0x3f3f3f3f, mxedge;
        for (int i = 0; i < m; i++) {
            if (kruscal(n, m-i, D+i, mxedge))
                ret = min(ret, mxedge - D[i].v);
            else
                break;
        }
        printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10665 - Diatribe against Pigeonholes

Problem

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

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

Sample Input

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

Sample Output

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

Solution

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

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

  • 如果這兩個重量相同，則字典順序最小的放前面，最大的放後面。
  • 反之，找到挑一個 同一個重量 字典順序小的放前面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h> 
#include <algorithm>
#include <vector>
using namespace std;
bool cmp1(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second || (a.second == b.second && a.first < b.first);
}
bool cmp2(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second || (a.second == b.second && a.first > b.first);
}
int main() {
    int testcase, N;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf ("%d %s", &N, s);
        pair<int, int> cnt[26] = {}, ret[26];
        for (int i = 0; i < N; i++)
            cnt[i].first = i + 'A';
        for (int i = 0; s[i] != '#'; i++) {
            if (s[i] >= 'A' && s[i] <= 'Z')
                cnt[s[i] - 'A'].second ++;
        }
        int l = 0, r = N - 1;
        for (int i = 0; i < N; ) {
            if (i+1 < N) {
                sort(cnt+i, cnt + N, cmp1);
                if (cnt[i].second != cnt[i+1].second) {
                    if (cnt[i].first < cnt[i+1].first) {
                        ret[l++] = cnt[i];
                        sort(cnt+i+1, cnt + N, cmp2);
                        ret[r--] = cnt[i+1];
                    } else {
                        swap(cnt[i], cnt[i+1]);
                        ret[l++] = cnt[i];
                        sort(cnt+i+1, cnt + N, cmp2);
                        ret[r--] = cnt[i+1];
                    }
                } else {
                    sort(cnt+i, cnt + N, cmp1);
                    ret[l++] = cnt[i];
                    sort(cnt+i+1, cnt + N, cmp2);
                    ret[r--] = cnt[i+1];
                }
                i += 2;
            } else {
                ret[l] = cnt[i];
                i++;
            }
        }
        for (int i = 0; i < N; i++)
         	printf("%c%c", ret[i].first, i == N - 1 ? '\n' : ' ');
     	for (int i = 0; i < N; i++)
         	printf("%d%c", ret[i].second, i == N - 1 ? '\n' : ' ');
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10571 - Products

Problem

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

Sample Input

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

Sample Output

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

Solution

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h> 
#include <vector>
#include <assert.h>
using namespace std;
int N, X[16] = {}, Y[16] = {};
int g[16][16] = {};
vector<int> row[16];
vector<int> f[1024];
int used[1024] = {};
int dfs(int idx) {
    if (idx == N) {
        for (int i = 0; i < N; i++, puts("")) {
            for (int j = 0; j < N; j++) {
                if (j) putchar(' ');
                printf("%3d", g[j][i]);
            }
        }
        return 1;
    }
    for (int p = 0; p < N; p++) {
        for (int q = p + 1; q < N; q++) {
            if (row[p].size() == 2 || row[q].size() == 2)
                continue;
            for (int i = 0; i < f[X[idx]].size(); i++) {
                int a, b, ok = 1;
                a = f[X[idx]][i];
                b = X[idx]/a;
                if (used[a] || used[b] || a == b) 
                    continue;
                g[idx][p] = a, g[idx][q] = b;
                used[a] = used[b] = 1;
                row[p].push_back(a);
                row[q].push_back(b);
                if (row[p].size() == 2 && row[p][0] * row[p][1] != Y[p]) 
                    ok = 0;
                if (row[q].size() == 2 && row[q][0] * row[q][1] != Y[q]) 
                    ok = 0;
                if (Y[p]%a || Y[q]%b)	
                    ok = 0;
                if (ok) {
                    if (dfs(idx + 1)) {
                        g[idx][p] = 0, g[idx][q] = 0;
                        row[p].pop_back();
                        row[q].pop_back();
                        used[a] = used[b] = 0;
                        return 1;
                    }
                }
                g[idx][p] = 0, g[idx][q] = 0;
                used[a] = used[b] = 0;
                row[p].pop_back();
                row[q].pop_back();
            }	
        }
    }
    return 0;
}
int main() {
    for (int i = 1; i < 1024; i++) {
        for (int j = 1; j <= i; j++) {
            if (i%j == 0)
                f[i].push_back(j);
        }
    }
    while (scanf("%d", &N) == 1 && N) {
        for (int i = 0; i < N; i++)
            scanf("%d", &X[i]);
        for (int i = 0; i < N; i++)
            scanf("%d", &Y[i]);
        assert(dfs(0) == 1);
        puts("");
    }
    return 0;
}
/*
2
2 12
3 8
3
5 8 18
2 30 12
5
54 6 12 20 88
18 9 132 32 10
10
2 12 30 56 90 132 182 240 306 380
19 36 51 64 75 84 91 96 99 200
0
*/
Read More +
解題區/解題區 - UVa

UVa 1368 - DNA Consensus String

Problem

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

Sample Input

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

Sample Output

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

Solution

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    int n, m;
    char DNA[64][1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", DNA[i]);
        int hh = 0;
        char ret[1024] = {}, cc[] = "ACGT";
        for (int i = 0; i < m; i++) {
            int cnt[4] = {}, mx = 0;
            for (int j = 0; j < n; j++)
                cnt[find(cc, cc+4, DNA[j][i]) - cc]++;
            
            for (int j = 0; j < 4; j++) {
                if (cnt[j] > cnt[mx])
                    mx = j;
            }
            ret[i] = cc[mx], hh += n - cnt[mx];
                
        }
        printf("%s\n%d\n", ret, hh);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10712 - Count the Numbers

Problem

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

Sample Input

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

Sample Output

1
2
3
2
3
2

Solution

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[10], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[20][2]; // [string length][upper y/n]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = str[i] - '0';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
void clearDp(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        memset(nd->dp, 0, sizeof(nd->dp));
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
    }
}
long long dp(Node *root, int len, char pattern[]) {
    queue<Node*> Q;
    Node *nd, *p;
    clearDp(root);
    root->dp[0][1] = 1;
    int k, i, j;
    long long ret = 0;
    for(k = 0; k < len; k++) {
        Q.push(root);
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for (j = 0; j < 2; j++) {
                for (i = (k == 0); i <= (j ? pattern[k]-'0' : 9); i++) {
                    if(nd->next[i] != NULL) {
                        if(nd->next[i]->eos) { // matching
                        	if (j && i == pattern[k]-'0') {
                        		long long t = 0;
                        		for (int p = k + 1; p < len; p++)
                        			t = t * 10 + pattern[p] - '0';
                        		t++;
                        		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %lld ++ %lld\n", k, j, nd->ASCII, i, nd->dp[k][j] * t, t);
                        	} else {
                        		long long t = 1;
                        		for (int p = k + 1; p < len; p++)
                        			t *= 10;	
                        		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %d ++\n", k, j, nd->ASCII, i, nd->dp[k][j] * t);
                        	}
                        	continue;
                        } 
                        if (j == 0 || (j == 1 && i < pattern[k] - '0'))
                        	nd->next[i]->dp[k+1][0] += nd->dp[k][j];
                        else if(j == 1 && i == pattern[k] - '0')
                        	nd->next[i]->dp[k+1][1] += nd->dp[k][j];
                        if(j == 0)
                        	Q.push(nd->next[i]);
                    } else {
                        p = nd;
                        while(p != root && p->next[i] == NULL)
                            p = p->fail;
                        p = p->next[i];
                        if(p->eos) { // matching
                    		if (j && i == pattern[k]-'0') {
                        		long long t = 0;
                        		for (int p = k + 1; p < len; p++)
                        			t = t * 10 + pattern[p] - '0';
                        		t++;
                        		ret += nd->dp[k][j] * t;
                        	} else {
                        		long long t = 1;
                        		for (int p = k + 1; p < len; p++)
                        			t *= 10;
                        		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %d ++\n", k, j, nd->ASCII, i, nd->dp[k][j] * t);
                        	}
                        	continue;
                        }
                        if (j == 0 || (j == 1 && i < pattern[k] - '0'))
                        	p->dp[k+1][0] += nd->dp[k][j];
                        else if(j == 1 && i == pattern[k] - '0')
                        	p->dp[k+1][1] += nd->dp[k][j];
                    }
                }
        	}
        }
    }
    return ret;
}
long long getDistinctNumberWith(int n, int m) { // #number <= n, has substring m
    if (n < 0) 
        return 0;
    char pattern[26], s[26];
    sprintf(pattern, "%d", m);
    Node *root = new Node();
    insertTrie(pattern, root, 1);
    for(int i = 0; i < 10; i++) {
    	s[0] = i + '0', s[1] = '\0';
    	insertTrie(s, root, 0);
    }
    buildACautomation(root);
    sprintf(pattern, "%d", n);
    long long ret = 0;
    int nlen = strlen(pattern);
    ret += dp(root, nlen, pattern);
    for	(int i = 1; i < nlen; i++) {
        pattern[i-1] = '9', pattern[i] = '\0';
//		printf ("%s %d %d --------\n", pattern, i, dp(root, i, pattern));
        ret += dp(root, i, pattern);
    }
    if (m == 0)	
        ret++;
    freeTrie(root);
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, a, b;
    while(scanf("%d %d %d", &a, &b, &n) == 3 && a >= 0) {
    	long long R, L;
        R = getDistinctNumberWith(b, n);
        L = getDistinctNumberWith(a - 1, n);
        printf("%lld\n", R - L);
    }
    return 0;
}
/*
731653830 735259500 735
735259500 735259500 735
3 17 3
0 20 0
0 150 17
-1 -1 -1
*/
Read More +
網頁設計/NodeJs

Nodejs upload server 簡易上傳下載

Github upload-server

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

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

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

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

Read More +