2014-08-02

UVa 12283 - Halloween Costumes

Problem

依序參加派對，每一個派對要求的服裝可能有所不同，可以衣服一件套一件去參加下一場派對，一旦脫下來服裝將不會穿第二次，請問至少要準備幾件才能參與所有派對。

Sample Input

4 
1 1 
1 
2 2 
1 1 
3 2 
1 2 1 
7 3 
1 2 1 1 3 2 1

Sample Output

Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 4

Solution

dp[l][r] 表示參與區間 [l, r] 從 l 開始的最少服裝數。

假設一開始已經穿著 l-th 的服裝，則將可以在參加完後脫掉，或者是到同一個另外一個場所之後考慮是否要脫掉。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dp[105][105], a[105];
int dfs(int l, int r) {
    if(l > r)	return 0;
    int &ret = dp[l][r];
    if(ret != -1)	return ret;
    ret = min(dfs(l+1, r), dfs(l, r-1))+1;
    for(int i = l+1; i <= r; i++) {
        if(a[l] == a[i])
            ret = min(ret, dfs(l+1, i) + dfs(i+1, r));
    }
    return ret;
}
int main() {
    int cases = 0, testcase, n, m;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        memset(dp, -1, sizeof(dp));
        printf("Case %d: %d\n", ++cases, dfs(0, n-1));
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12260 - Free Goodies

Problem

有n个糖果，每个糖果有p，j两个值，现在有两个人Petra和Jan，Prtra的取糖果方式是优先去p值大的j值小的；Jan取糖果的方式是尽量让自己开心值（取出糖果的j值和）大的情况下让Petra的开心值（取出糖果的p值和）也大，给出先选糖果的人，问说最后两人的开心值分别为多少。

這裡可以明白有兩種策略

Petra 只求讓自己最高 - 貪心
Jan 自己最高的情況下，Petra 盡可能地高

Sample Input

Sample

1
2
3

170 130
14 16
9 10

Solution

Petra 使用貪心，將糖果數值按照 P 降排序，來作為 dp 時候 Petra 轉移用的順序，只要確保 Petra 會根據這個順序從大挑到小。

並且確保前 i 個糖果時，Jan 不會拿超過 i/2 個糖果 (否則表示交替順序不符合規則)，Jan 可以選擇先讓 Petra 分配到大的 P，而自己先去取大的 J。

dp[i][j] 表示前 i 個糖果，Jan 分配到 j 個的最佳策略 (J, P)。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <functional>
using namespace std;
const char name[2][10] = {"Petra", "Jan"};
pair<int, int> D[1024];
pair<int, int> dp[1024][512];
bool cmp(pair<int, int> p, pair<int, int> q) {
    if(p.first != q.first)
        return p.first > q.first;
    return p.second < q.second;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int testcase, n;
    char s[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %s", &n, s);
        
        for(int i = 1; i <= n; i++) {
            int p, j;
            scanf("%d %d", &p, &j);
            D[i] = make_pair(p, j);
        }
        sort(D+1, D+1+n, cmp);
        
        int base = 0;
        if(!strcmp(name[0], s)) {
            base = D[1].first;
            for(int i = 1; i < n; i++)
                D[i] = D[i+1];
            n--;
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= (i+1)/2; j++) {
                dp[i][j] = make_pair(dp[i-1][j].first, dp[i-1][j].second + D[i].first);
                if(j)
                    dp[i][j] = max(dp[i][j], 
                        make_pair(dp[i-1][j-1].first + D[i].second, dp[i-1][j-1].second));
            }
        }
        printf("%d %d\n", dp[n][(n+1)/2].second + base, dp[n][(n+1)/2].first);
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 11893 - Fabulous DAGy

Problem

原本是一張 DAG，增加一條有向邊會使得存有一個環，而這個環將會通過所有的點一次。

現在給予加完後的結果，是否存在一條有向邊，使得原本的 DAG 變成符合上述條件的圖。

Sample Input

Sample Output

1 2	Yeah, I'm superman Your DAGy was initially defected!

Solution

由於只能通過所有點一次的環，對於 DAG 而言，替除掉應該加入的邊會發現到拓樸排序只能是唯一的長鏈狀。

因此窮舉拔掉所有可能的邊，並且檢查是否能夠符合長鏈狀的拓樸順序。

#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int indeg[512], outdeg[512], mg[512][512];
vector<int> g[512];
int check(int st, int banu, int banv, int n) {
    queue<int> Q;
    int in[512], out[512], visited = 0, u, v;
    for(int i = 0; i < n; i++)
        in[i] = indeg[i], out[i] = outdeg[i];
    Q.push(st), in[banv]--, out[banu]--;
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        visited++;
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(--in[v] == 0)
                Q.push(v);
        }
        if(Q.size() > 1)	return 0;
    }
    return visited == n && mg[u][st];
}
int main() {
    int testcase, n, m, u, v;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        memset(mg, 0, sizeof(mg));
        memset(indeg, 0, sizeof(indeg));
        memset(outdeg, 0, sizeof(outdeg));
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            mg[u][v] = 1;
            g[u].push_back(v);
            indeg[v]++, outdeg[u]++;
        }
        int ret = 0;
        for(int i = 0; i < n && !ret; i++) {
            for(int j = 0; j < g[i].size() && !ret; j++) {
                u = i, v = g[i][j];
                if(indeg[v] == 1 && outdeg[u] == 1) {
                    ret |= check(v, u, v, n);
                }
            }
        }
//		puts(ret ? "YES" : "NO");
        puts(ret ? "Yeah, I'm superman" : "Your DAGy was initially defected!");
    }
    return 0;
}
/*
5 6
0 1
1 2
2 3
3 4
4 0
1 3
*/

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 11874 - Travel Company

Problem

給一個 N 個城市的地圖，每一條路徑上會有成本和獲益，希望找到一條送貨的環道，是否存在一個環道使得獲益是成本的 P 倍。

Sample Input

Sample Output

1
2
3

Case 1: YES
Case 2: NO
Case 3: YES

Solution

最小比例環的應用，事實上可以把題目化簡為負環檢查，將每一條邊的權重定義為 expense * p - income，只要負環存在則存有一條環道的 獲益/成本 > P

點數很少，直接用 floyd 在 O(n^3) 找解。

#include <stdio.h> 
#include <string.h>
#include <algorithm> 
using namespace std;
int g[128][128];
int main() {
    int testcase, cases = 0;
    int n, m, p, x, y, income, expense;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &n, &m, &p);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                g[i][j] = 0xf3f3f3f;
        while(m--) {
            scanf("%d %d %d %d", &x, &y, &income, &expense);
            g[x][y] = min(g[x][y], expense * p - income);
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
        int ret = 0;
        for(int i = 0; i < n; i++)
            ret |= g[i][i] < 0;
        printf("Case %d: %s\n", ++cases, ret ? "YES" : "NO");
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 997 - Show the Sequence

The problem of finding the next term of a given sequence of numbers is usually proposed in QI tests. We want to generate the N terms of a sequence from a given codification of the sequence.

Let S = (Si)i $\scriptstyle \in$$\scriptstyle \mathbb {N}$ denote a sequence of real numbers whose i -order term is Si . We codify a constant sequence with the following operator:

S = [ n] meaning that Si = n $\displaystyle \forall$i$\displaystyle \in$$\displaystyle \mathbb {N}$,

where n$\in$$\mathbb {Z}$ . We also define the following operators on a given sequence of numbers S = (Si)i $\scriptstyle \in$$\scriptstyle \mathbb {N}$ :

V = [ m + S ] meaning that
$Vi = \displaystyle \cases{m & , $i=1$ \cr V{i-1}+ S{i-1} & , $i > 1$ \cr}; $

V = [ m * S ] meaning that
$Vi = \displaystyle \cases{m \ast S_{1} & , $i=1$ \cr V_{i-1} \ast S_i & , $i > 1$ \cr}; $

where m$\in$$\mathbb {N}$ . For example we have the following codifications:

[2 + [1]] = 2, 3, 4, 5, 6 ... 	
[1 + [2 + [1]]] = 1, 3, 6, 10, 15, 21, 28, 36 ...
[2 * [1 + [2 + [1]]]] = 2, 6, 36, 360, 5400, 113400 ...
[2 * [5 + [- 2]]] = 10, 30, 30, -30, 90, -450, 3150 ...

Given a codification, the problem is to write the first N terms of the sequence.

Input

The input file contains several test cases. For each of them, the program input is a single line containing the codification, without any space, followed by an integer N(2$\le$N$\le$50) .

Output

For each test case, the program output is a single line containing the list of first N terms of the sequence.

Sample Input

1 2	[2+[1]] 3 [2*[5+[-2]]] 7

Sample Output

1 2	2 3 4 10 30 30 -30 90 -450 3150

Solution

遞迴建造

#include <stdio.h> 
#include <string.h>
long long a[128];
void parsing(char s[]) {
    int sign = 1, i, m = 0;
    char pos;
    for(i = 1; s[i]; i++) {
        if(s[i] == '-')	sign = -1;
        else if(s[i] >= '0' && s[i] <= '9') 
            m = m * 10 + s[i] - '0';
        else {
            pos = s[i];
            break;
        }
    }
    m = sign * m;
    if(pos == '+') {
        parsing(s + i + 1);
        long long d = a[0];
        a[0] = m;
        for(int i = 1; i < 50; i++) {
            long long t = a[i];
            a[i] = a[i - 1] + d, d = t;
        }
    } else if(pos == '*') {
        parsing(s + i + 1);
        a[0] *= m;
        for(int i = 1; i < 50; i++)
            a[i] = a[i] * a[i-1];
    } else {
        for(int i = 0; i < 50; i++)
            a[i] = m;
    }
}
int main() {
    char s[1024];
    int n;
    while(scanf("%s %d", s, &n) == 2) {
        memset(a, 0, sizeof(a));
        parsing(s);
        for(int i = 0; i < n; i++)
            printf("%lld%c", a[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}
/*
[2+[1]] 3
[2*[5+[-2]]] 7
*/

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 995 - Super Divisible Numbers

Problem

For example, 22203014 is a base-4 super divisible number because 24 is divisible by 1, 224 is divisible by 2, 2224 is divisible by 3, 22204 is divisible by 4, 222034 is divisible by 5, 2220304 is divisible by 6, and 22203014 is divisible by 7.

Find the largest super divisible number of a given base which uses only digits from a given list of digits.

基底為 B 的數字 N 前綴長度 i 必需被 i 整除，找到一個最大符合條件的數字。同時會限用哪幾種 digit。

Sample Input

1 2	4 0123 10 010011

Sample Output

1 2	2220301 10

Solution

感謝天祥大大的指導，一度以為非常多解，因此逼不得以要用 dp 運行，但是仔細想想狀態太大，也無法計算。

根據窮舉的方式可以發現到，每一次窮舉時，假使前一次 mod i = X，則為了要使得 X + ? = 0 (mod i) 則 ? 的地方能填入的數字個數相當於 2 * i <= B 的解，因此答案的數量是相當少的，也就是說最多為 (B/i)! 種可能，撇開不可運行的分枝，其實符合這個條件的數字相當少。

#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int B, valid[16], path[128];
vector<string> ret[128];
void dfs(int idx) {
    for(int i = idx == 0; i < B; i++) {
        if(!valid[i])	continue;
        path[idx] = i;
        int f = 0;
        for(int j = 0; j <= idx; j++)
            f = (f * B + path[j])%(idx+1);
        if(f == 0) {
            string s = "";
            for(int j = 0; j <= idx; j++)
                s += (path[j] + '0');
            ret[s.length()].push_back(s);
            dfs(idx+1);
        }
    }
}
int main() {
    char s[1024];
    while(scanf("%d %s", &B, &s) == 2) {
        memset(valid, 0, sizeof(valid));
        for(int i = 0; i < 128; i++)
            ret[i].clear();
        for(int i = 0; s[i]; i++)
            valid[s[i]-'0'] = 1;
        dfs(0);
        for(int i = 127; i >= 0; i--) {
            if(ret[i].size()) {
                sort(ret[i].begin(), ret[i].end());
                printf("%s\n", ret[i][ret[i].size()-1].c_str());
                break;
            }
        }
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 979 - The Abominable Triangleman

Problem

簡化版本的 UVA 10206 - Stars，這一題只求三角形之間的情況，並且只需要考慮相同大小、可能會任意地旋轉或者是翻轉 (鏡射)。

找到一個解輸出即可。

Sample Input

Sample Output

1
2
3

5 17
10 5
15 20

Solution

窮舉一條三角形上的邊當作 AB 邊，利用向量旋轉找到 C 點位置，查閱 C 點位置是否有存在於輸入的點集合中。

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        if(fabs(y-a.y) > eps)
        	return y < a.y;
        return false;
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x /a, y /a);
    }
    Pt operator*(const double a) const {
        return Pt(x *a, y *a);
    }
    int in() {
    	return scanf("%lf %lf", &x, &y) == 2;
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int main() {
    Pt A, B, C, D[2048];
    int N, cases = 0;
    while(A.in() && B.in() && C.in()) {
        scanf("%d", &N);
        set<Pt> S;
        for(int i = 0; i < N; i++)
            D[i].in(), S.insert(D[i]);
        if(cases++)	puts("");
        double AB = dist2(A, B), BC = dist2(B, C), sqrAB = dist(A, B), sqrBC = dist(B, C);
        double aABC = angle(A - B, C - B);
        sort(D, D + N);
        
        vector<Pt> ret;
        for(int i = 0; i < N; i++) {
            for(int j = i+1; j < N; j++) {
                if(AB < (D[j].x - D[i].x) * (D[j].x - D[i].x))
                    break;
                if(fabs(AB - dist2(D[i], D[j])) < eps) {
//					printf("%lf %lf %lf %lf\n", D[i].x, D[i].y, D[j].x, D[j].y);
                    Pt vBC, tc;
                    vBC = rotateRadian(D[i] - D[j], +aABC) * (sqrBC/sqrAB);
                    tc = D[j] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                    
                    vBC = rotateRadian(D[i] - D[j], -aABC) * (sqrBC/sqrAB);
                    tc = D[j] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }					
                    
                    vBC = rotateRadian(D[j] - D[i], +aABC) * (sqrBC/sqrAB);
                    tc = D[i] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                    
                    vBC = rotateRadian(D[j] - D[i], -aABC) * (sqrBC/sqrAB);
                    tc = D[i] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                }
            }
        }
        if(ret.size()) {
            sort(ret.begin(), ret.end());
            for(int i = 0; i < 3; i++) {
                printf("%.0lf %.0lf\n", ret[i].x, ret[i].y);
            }
        }
    }
    return 0;
}
/*
5 15
8 5
20 10
6
5 17
5 20
20 5
10 5
15 20
15 10
*/

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 970 - Particles

Problem

化合物只會有有三種 X, Y, Z，並且兩兩化合最多也只會是這三種。每次化合只能拿相鄰的進行化合，求最後能化合出的最大化合物為何 Z > Y > X？

Sample Input

1
2

1
ZYX

Sample Output

Solution

使用矩陣鍊乘積的 dp 方法，將可以在 O(n^3) 時間內完成，但是由於測資量龐大，單純的 O(n^3) 很容易 TLE，利用剪枝的方式，若已經完成所有可能情況的化合則停止。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    int table[3][3] = { {1,0,2},{0,1,1},{2,1,0} };
    char s[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%s", s);
        int dp[128][128][3] = {}, n = strlen(s);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j + i < n; j++) {
                for(int k = j; k < j + i; k++) {
                    for(int p = 0; p < 3; p++) {
                        if(dp[j][k][p])
                        for(int q = 0; q < 3; q++) {
                            if(dp[k+1][j+i][q]) {
                                dp[j][j+i][table[p][q]] = 1;
                            }
                        }
                    }
                    if(dp[j][j+i][0] && dp[j][j+i][1] && dp[j][j+i][2])
                        break;
                }
                if(i == 0)
                    dp[j][j][s[j]-'X'] = 1;
            }
        }
        for(int i = 2; i >= 0; i--) {
            if(dp[0][n-1][i]) {
                printf("%c\n", i+'X');
                break;
            }
        }
    }
    return 0;
}
/*
1
ZYX
*/

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 946 - A Pile of Boxes

Problem

一個神祕的堆疊方式，假如燒杯大小大於要放入的燒杯，在不超過其原本的燒杯高度的情況下，則可以將其放入內部，放入內部後，可能掉入底層的燒杯中。

根據這樣的方式模擬最後堆疊的最大高度。

Sample Input

Sample Output

Solution

半夜爬起來寫的，總覺得檢查事件挺麻煩的事情，因此採用遞迴的方式建造，在退回的情況下查閱是否要疊在上方。

inner 表示內部底層的燒杯、outer 表示上方的燒杯，footer 表示下方的燒杯。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int inner[105], outer[105], footer[105];
int height[105], A[105];
int place(int i, int mxI, int limit) {
//	printf("down %d %d\n", A[mxI], mxI);
    if(A[mxI] < A[i]) {
        if(height[mxI] + A[i] <= limit) {
            outer[mxI] = i, footer[i] = mxI; 
            height[i] = height[mxI] + A[i];
        }
        return height[mxI] + A[i];
    }
    if(inner[mxI] == -1) {
        int h = place(i, footer[mxI], height[mxI] - A[mxI]);
        if(h <= height[mxI] - A[mxI]) // complete
            return h;
        inner[mxI] = i, footer[i] = footer[mxI];
        height[i] = height[mxI] - A[mxI] + A[i];
        return height[i];
    } else {
        mxI = inner[mxI];
        while(outer[mxI] != -1)
            mxI = outer[mxI];
        int h = place(i, mxI, height[mxI]);
        if(h == height[mxI] - A[mxI] + A[i]) {
            h = place(i, footer[mxI], height[mxI] - A[mxI]);
//			printf("check %d %d\n", h, height[mxI] - A[mxI]);
            if(h <= height[mxI] - A[mxI])
                return h;
            inner[mxI] = i, footer[i] = footer[mxI];
            height[i] = height[mxI] - A[mxI] + A[i];
            return height[i];
        } else if(h > height[mxI]) {
            if(height[mxI] + A[i] <= limit) {
                outer[mxI] = i, footer[i] = mxI;
                height[i] = height[mxI] + A[i];
            }
            return height[mxI] + A[i];
        } else {
//			puts("hello");
            return h;
        }
    }
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        for(int i = 0; i <= n; i++)
            inner[i] = outer[i] = footer[i] = height[i] = -1;
        A[0] = 0, height[0] = 0;
        for(int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        int mxH = 0, mxI = 0;
        for(int i = 1; i <= n; i++) {
            int h = place(i, mxI, mxH);
            if(h > mxH) {
                outer[mxI] = i, footer[i] = mxI; 
                height[i] = height[mxI] + A[i];
            }
            h = height[i];
//			printf("[%d] %d - %d mxH = %d mxI %d\n", i, A[i], h, mxH, mxI);
//			for(int j = 1; j <= i; j++)
//				printf("--------[%d] %2d * in %2d out %2d foot %2d\n", j, A[j], inner[j], outer[j], footer[j]);
            if(h > mxH)	mxH = h, mxI = i;
        }
        printf("%d\n", mxH);
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

uva 921 - A Word Puzzle in the Sunny Mountains

Problem

將一個數字對應一個字母，現在已經有一些字典的單字，先將 seed 字串對應到第一組加密數字。接著找到一種對應方式，使得每一組加密數字都可以對應到字典單字中。

Sample Input

1 
11
7
1 2 3 4 5 3 0
1 5 1 0
1 6 3 4 0
7 3 4 8 1 0
9 3 4 8 1 0
9 1 9 10 11 0
10 11 6 3 0
ADORNO
ADORNO
AMOR
ANA
ARLINDO
ANTUNES
HORTA
PORTA
PORTAO
PORTAL
PAPEL
PARVO
ELMO
ESTE
ESSE
ARMADURA
HELENA
ERGONOMICO
EVA
ERVA
CARMO
COUVE
*

Sample Output

1	ADORNMHTPEL

Solution

題目看起來挺嚇人，直接窮舉即可，保證只有一解。

#include <stdio.h>
#include <string.h>
using namespace std;
int match[105][105], msize[105];
char seed[105], dictionary[105][105];
int dlen[105];
int mp[52];
int N, M, D;
int dfs(int idx) {
    if(idx == N) {
        int f = 1;
        for(int i = 1; i <= M; i++)
            f &= mp[i] != -1;
        return f;
    }
    for(int i = 0; i < D; i++) {
        if(dlen[i] != msize[idx])	continue;
        int ok = 1;
        for(int j = 0; j < msize[idx] && ok; j++) {
            if(mp[match[idx][j]] != -1 && mp[match[idx][j]] != dictionary[i][j])
                ok = 0;
        }
        if(ok) {
            int cp[52];
            for(int i = 1; i <= M; i++)	cp[i] = mp[i];
            for(int j = 0; j < msize[idx] && ok; j++)
                mp[match[idx][j]] = dictionary[i][j];
            if(dfs(idx+1))	return 1;
            for(int i = 1; i <= M; i++)	mp[i] = cp[i];
        }
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &M, &N);
        for(int i = 0; i < N; i++) {
            int j;
            for(j = 0; scanf("%d", &match[i][j]) && match[i][j]; j++);
            msize[i] = j;
        }
        scanf("%s", seed);
        memset(mp, -1, sizeof(mp));
        for(int i = 0; seed[i]; i++)
            mp[match[0][i]] = seed[i];
        for(D = 0; scanf("%s", &dictionary[D]) && dictionary[D][0] != '*'; D++) {
            dlen[D] = strlen(dictionary[D]);
        }
        dfs(0);
        for(int i = 1; i <= M; i++)		
            printf("%c", mp[i]);
        puts("");
    }
    return 0;
}

Read More +