2015-03-21

UVa 1462 - Fuzzy Google Suggest

Problem

模擬 Google 的模糊搜尋，使用編輯距離找到相符的前綴單詞數量。

編輯距離的限制小於等於 2。

Sample Input

4 
content 
common 
onganize 
case 
7 
c 0 
con 0 
con 2 
con 1 
com 1
comm 2 
cog 1

Sample Output

Solution

對於每一個詢問，沒辦法把每一個單字都拿出來嘗試過一次。

建造一個 trie，然後在 trie 上面進行編輯距離的 dp 規則，當搜尋到重覆的結果時，可以立刻返回，由於編輯距離小於等於 2，重複走訪的可能性低很多，因此用一個懶標記，如果前綴已經符合，則下次走訪就沒有必要搜索下去。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 26
#define MAXS (1024)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt, label;
        void init() {
            cnt = label = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c - 'a';
    }
    // merge trie
    void merge_dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt += v->cnt;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        	p->cnt += w;
        }
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    // fuzzy find
    void fuzzy_dfs(Node *u, int idx, const char s[], int fuzzy_edit) {
    	if (fuzzy_edit < 0)			return ;
        if (u->label == cases + 1)	return ;
    	if (s[idx] == '\0') {
    		u->label = cases + 1;
    		return ;
        }
            
        if (u->label < cases)
            u->label = cases;
        for (int i = 0; i < MAXCHAR; i++) {
            if (u->next[i]) {
                if (toIndex(s[idx]) == i)
                	fuzzy_dfs(u->next[i], idx+1, s, fuzzy_edit);
                else
                	fuzzy_dfs(u->next[i], idx+1, s, fuzzy_edit-1); // replace s[idx]
                fuzzy_dfs(u->next[i], idx, s, fuzzy_edit-1); // insert s[idx]
            }
        }
        fuzzy_dfs(u, idx+1, s, fuzzy_edit-1); // delete s[idx]
    }
    int fuzzy_count(Node *u) {
    	if (u->label == cases+1)
    		return u->cnt;
    	if (u->label < cases)
    		return 0;
        int ret = 0;
        for (int i = 0; i < MAXCHAR; i++) {
            if (u->next[i])
                ret += fuzzy_count(u->next[i]);
        }
        return ret;
    }
    int fuzzyFind(const char str[], int fuzzy_edit) {
    	cases += 2;
    	fuzzy_dfs(root, 0, str, fuzzy_edit);
    	return fuzzy_count(root);
    }
    
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
} tool;
char s[MAXS];
int main() {
    int N, Q, f;
    while (scanf("%d", &N) == 1 && N) {
    	tool.init();
    	while (getchar() != '\n');
    	
    	for (int i = 0; i < N; i++) {
    		gets(s);
    		tool.insert(s, 1);
    	}
    	scanf("%d", &Q);
    	for (int i = 0; i < Q; i++) {
    		scanf("%s %d", s, &f);
    		int ret = tool.fuzzyFind(s, f);
    		printf("%d\n", ret);
    	}
    	
    	tool.free();
    }
    return 0;
}
/*
4 
content 
common 
onganize 
case 
7 
c 0 
con 0 
con 2 
con 1 
com 1
comm 2 
cog 1
 */

Read More +

2015-03-21

解題區/解題區 - UVa

UVa 1113 - Multiple Morse Matches

Problem

給摩斯電碼的編碼方式，以及一串沒有切割的主字串，和可能使用的單字集，請問有多少不同的解析方式。

Sample Input

1
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK

Sample Output

Solution

這題很明顯地是一道 O(nm) 的動態規劃，dp[i] 表示長度為 i 的解析方法數，藉由 match S[i, j] 轉移成 dp[j] += dp[i]。

為了加速 match 的速度，先將字典集轉換成摩斯電碼，插入到 trie 中，當要做 match 時，相當於在 trie 走訪，可以高效地降低 O(m) 的嘗試。變成 O(nn)

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 2 
#define MAXS (4096)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt;
        void init() {
            cnt = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c == '.';
    }
    // merge trie
    void merge_dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt += v->cnt;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt += w;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
        
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
} tool;
char S[MAXS], T[MAXS], buf[MAXS];
string morse[] = {
    ".-", "-...", "-.-.", "-..",
    ".", "..-.", "--.", "....",
    "..", ".---", "-.-", ".-..",
    "--", "-.", "---", ".--.",
    "--.-", ".-.", "...", "-",
    "..-", "...-", ".--", "-..-",
    "-.--", "--.."};
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
    	tool.init();
    	
    	scanf("%s", S);
    	scanf("%d", &n);    	
    	for (int i = 0; i < n; i++) {
    		scanf("%s", T);
    		int m = 0;
    		for (int j = 0; T[j]; j++)
    			for (int k = 0; morse[T[j] - 'A'][k]; k++)
                    buf[m++] = morse[T[j] - 'A'][k];
            buf[m] = '\0';
            tool.insert(buf, 1);
    	}
    	
    	int len = (int) strlen(S);
    	int dp[MAXS] = {};
    	dp[0] = 1;
    	for (int i = 0; i < len; i++) {
    		Trie::Node *p = tool.root;
    		for (int j = i; j < len; j++) {
    			int u = tool.toIndex(S[j]);
    			if (p->next[u] == NULL)
                    break;
                p = p->next[u];
                dp[j+1] += dp[i] * p->cnt;
    		}
    	}
    	
    	printf("%d\n", dp[len]);	
    	if (testcase)
    		puts("");
        
        tool.free();    
    }
    return 0;
}
/*
 */

Read More +

2015-03-21

解題區/解題區 - UVa

UVa 1352 - Colored Cubes

Problem

給予最多 4 個骰子，修改最少的面，使得每個骰子同構。

Sample Input

3 
scarlet green blue yellow magenta cyan 
blue pink green magenta cyan lemon 
purple red blue yellow cyan green 
2 
red green blue yellow magenta cyan 
cyan green blue yellow magenta red 
2 
red green gray gray magenta cyan 
cyan green gray gray magenta red 
2 
red green blue yellow magenta cyan 
magenta red blue yellow cyan green 
3 
red green blue yellow magenta cyan 
cyan green blue yellow magenta red 
magenta red blue yellow cyan green 
3 
blue green green green green blue 
green blue blue green green green 
green green green green green sea-green 
3 
red yellow red yellow red yellow 
red red yellow yellow red yellow 
red red red red red red 
4 
violet violet salmon salmon salmon salmon 
violet salmon salmon salmon salmon violet 
violet violet salmon salmon violet violet 
violet violet violet violet salmon salmon 
1 
red green blue yellow magenta cyan 
4 
magenta pink red scarlet vermilion wine-red 
aquamarine blue cyan indigo sky-blue turquoise-blue 
blond cream chrome-yellow lemon olive yellow 
chrome-green emerald-green green olive vilidian sky-blue 
0

Sample Output

Solution

由於每個骰子有 24 種同構排列，複雜度 O(24^4)。

將排列對齊後，使用貪心算法，將每一個 column 找到最多相同元素，剩餘的就是最少修改元素。

類似漢明距離的最少修改。順便將之前的代碼重新構造。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
struct DICE {
    int dice[6]; // front, right, up, back, left, down
    void rightTurn() {
    	static int t;
    	t = dice[0], dice[0] = dice[4];
    	dice[4] = dice[3], dice[3] = dice[1], dice[1] = t;
    }
    void upTurn() {
    	static int t;
    	t = dice[0], dice[0] = dice[5];
    	dice[5] = dice[3], dice[3] = dice[2], dice[2] = t;
    }
    void clockwise() {
        static int t;
        t = dice[2], dice[2] = dice[4];
        dice[4] = dice[5], dice[5] = dice[1], dice[1] = t;
    }
    void print() {
        for (int i = 0; i < 6; i++)
            printf("%d ", dice[i]);
        puts("");
    }
    vector<DICE> generate() {
        vector<DICE> ret;
        DICE tmp = *this;
        
        for (int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
            	ret.push_back(tmp);
                tmp.clockwise();
            }        
            tmp.rightTurn();
        }
        tmp.upTurn();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 4; j++) {
                ret.push_back(tmp);
                tmp.clockwise();
            }        
            tmp.upTurn(), tmp.upTurn();
        }
        return ret;
    }
    bool operator<(const DICE &x) const {
        for (int i = 0; i < 6; i++)
            if (dice[i] != x.dice[i])
                return dice[i] < x.dice[i];
        return false;
    }
    bool operator==(const DICE &x) const {
        for (int i = 0; i < 6; i++)
            if (dice[i] != x.dice[i])
                return false;
        return true;
    }
};
int path[8];
vector<DICE> kind[8];
vector<DICE> permutation;
int ret = 0x3f3f3f3f, N;
int counter[32];
void dfs(int idx) {
    if (idx == N) {
        int ch = 0;
        for (int i = 0; i < 6; i++) {
            int mx = 0;
            memset(counter, 0, sizeof(counter));
            for (int j = 0; j < N; j++)
                mx = max(mx, ++counter[kind[j][path[j]].dice[i]]);
            ch += N - mx;
            if (ch >= ret)	return ;
        }
        ret = min(ret, ch); 
        return ;
    }
    for (int i = 0; i < kind[idx].size(); i++) {
        path[idx] = i;
        dfs(idx+1);
    }
}
int main() {
    DICE p;
    for (int i = 0; i < 6; i++)
    	p.dice[i] = i;
    permutation = p.generate();
    
    char s[128];
    while (scanf("%d", &N) == 1 && N) {
    	map<string, int> colors;
    	for (int i = 0; i < N; i++) {
    		int v[6];
    		for (int j = 0; j < 6; j++) {
    			scanf("%s", s);
    			int &x = colors[s];
    			if (x == 0)	x = colors.size();
    			v[j] = x;
    		}
    		DICE D;
    		D.dice[0] = v[0], D.dice[1] = v[1], D.dice[2] = v[2];
    		D.dice[5] = v[3], D.dice[4] = v[4], D.dice[3] = v[5];
    		
    		kind[i] = D.generate();
    		sort(kind[i].begin(), kind[i].end());
    		kind[i].resize(unique(kind[i].begin(), kind[i].end()) - kind[i].begin());
//    		printf("%d\n", kind[i].size());
    	}
    	
    	ret = 0x3f3f3f3f;
    	dfs(0);
    	printf("%d\n", ret);
    }
    return 0;
}

Read More +

2015-03-21

解題區/解題區 - UVa

UVa 1364 - Knights of the Round Table

Problem

圓桌武士要圍一桌，由於騎士很多，他們彼此憎恨的關係也越來越複雜，梅林被聘請來計劃會議的圓桌位置，騎士們的座位必須符合下列條件，否則將會無法開會。

彼此憎恨的騎士不可相鄰
圓桌要恰好奇數個人，否則無法進行投票

由於是圓桌，每個騎士都恰好有兩個鄰居，梅林只想知道誰絕對沒有辦法參與圓桌，求出絕對無法參與圓桌會議的騎士個數，並不用最大化圓桌的最大人數。

Sample Input

Sample Output

Solution

首先，一個簡單的特性，二分圖如果存在環，則保證沒有奇環，因為從 X 集合出去到 Y 集合，再回到 X 集合，保證環的路徑一定經過偶數條邊。同時，存在奇環的圖，一定不是二分圖。

二分圖不存在奇環，存在奇環的圖一定不是二分圖

藉由這個道理，這題還需要點特性，如果這張圖存在奇環，對於一個 BCC (雙向連通元件)，則滿足所有點都可以在一個奇環上。有可能一個點同時在奇環或者是偶環。

這個證明也很簡單，BCC 在元件中，定義拿走任一條邊 e(u, v)，u 和 v 之間仍然存在一條路徑。那麼可以知道對於一個奇環上的點 x 和 y，以及奇環外一點 u，若 e(x, u) 存在，則 e(u, y) 也存在，則會產生兩個環，其中一個環一定是奇數。擴散下去，所有在 BCC 元件的點，都會在一個奇環上。

BCC 存在奇環，每一個點都至少在一個奇環上

很久沒寫 BCC，一直以來寫 cut point (關節點) 和 cut edge (bridge) 的機會比較高，都忘了 BCC 的寫法。一張圖，拆成 BCC 時，每一個節點可能存在數個 BCC 元件中。

// BCC
#include <stdio.h> 
#include <string.h>
#include <vector> 
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1024;
class BCC {
public:
    vector<int> g[MAXN], bcc[MAXN];
    stack< pair<int, int> > stk;
    int n;
    int vfind[MAXN], findIdx;
    int visited[MAXN];
    int bcc_tmp[MAXN], bccCnt, cutPt[MAXN];
    int dfs(int u, int p) {
        visited[u] = 1;
        vfind[u] = ++findIdx;
        
        int mn = vfind[u], branch = 0, t;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (!visited[v]) {
                stk.push(make_pair(u, v));
                t = dfs(v, u);
                mn = min(mn, t), branch++;
                if (t >= vfind[u]) {
                    pair<int, int> e;
                    bcc[++bccCnt].clear();
                    do {
                        e = stk.top(), stk.pop();
                        if (bcc_tmp[e.first] != bccCnt)
                            bcc[bccCnt].push_back(e.first), bcc_tmp[e.first] = bccCnt;
                        if (bcc_tmp[e.second] != bccCnt)
                            bcc[bccCnt].push_back(e.second), bcc_tmp[e.second] = bccCnt;
                    } while (e != make_pair(u, v));
                    cutPt[u] = 1;
                }
            } else if (vfind[v] < vfind[u] && v != p) {
                stk.push(make_pair(u, v));
                mn = min(mn, vfind[v]);
            }
        }
        if (p < 0 && branch == 1)	cutPt[u] = 0;
        return mn;
    }
    void findBCC() {
        while (!stk.empty())	stk.pop();
        memset(visited, 0, sizeof(visited));
        memset(bcc_tmp, 0, sizeof(bcc_tmp));
        bccCnt = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                findIdx = 0;
                dfs(i, -1);
            }
        }
    }
    void addEdge(int x, int y) {
        g[x].push_back(y), g[y].push_back(x);
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear();
    }
} g;
int A[MAXN][MAXN];
int belong[MAXN], color[MAXN];
int isBipartite(int u) {
    for (int i = 0; i < g.g[u].size(); i++) {
        int v = g.g[u][i];
        if (belong[u] != belong[v])	
            continue;
        if (color[v] == color[u])
            return false;
        if (!color[v]) {
            color[v] = 3 - color[u];
            if (!isBipartite(v))
                return false;
        }
    }
    return true;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        memset(A, 0, sizeof(A));
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y), x--, y--;
            A[x][y] = A[y][x] = 1;
        }
        
        g.init(n);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!A[i][j]) {
                    g.addEdge(i, j);
//					printf("%d %d --\n", i, j);
                }
            }
        }
        
        g.findBCC();
        
        memset(belong, 0, sizeof(belong));
        int onOddCycle[MAXN] = {};
        for (int i = 1; i <= g.bccCnt; i++) {
            for (int j = 0; j < g.bcc[i].size(); j++) {
                belong[g.bcc[i][j]] = i, color[g.bcc[i][j]] = 0;
//				printf("%d ", g.bcc[i][j]);
            }
//			puts("");
            memset(color, 0, sizeof(color));
            color[g.bcc[i][0]] = 1;
            if (!isBipartite(g.bcc[i][0])) { // 
                for (int j = 0; j < g.bcc[i].size(); j++)
                    onOddCycle[g.bcc[i][j]] = 1;
            }
        }
        
        int ret = n;
        for (int i = 0; i < n; i++)
            ret -= onOddCycle[i];
        printf("%d\n", ret);
    }
    return 0;
}
/*
7 9
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
4 5
1 2
2 3
3 4
4 1
2 4
4 4
1 2
2 3
3 1
1 4
5 5
1 4
1 5
2 5
3 4
4 5
12 3
8 7
2 3
4 2
7 12
4 7
5 6
1 7
2 1
1 3
2 7
5 1
6 3
6 7
3 7
3 4
4 1
0 0
*/

Read More +

2015-03-08

解題區/解題區 - UVa

UVa 11214 - Guarding the Chessboard

Problem

用最少的皇后，覆蓋盤面中所有的 ‘X’。皇后之間的相互攻擊可以忽略不理。

Sample Input

8 8
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
8 8
X.......
.X......
..X.....
...X....
....X...
.....X..
......X.
.......X
0

Sample Output

1 2	Case 1: 5 Case 2: 1

Solution

直接套 DLX 最小重複覆蓋的模板，但是單純使用會狂 TLE。額外加上初始貪心，找到搜索的第一把剪枝條件，這一個貪心使用每次找盤面上能覆蓋最多 ‘X’ 的位置，進行放置皇后的工作。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXV 0x3f3f3f3f
#define MAXE 1048576
#define MAXC 1048576
#define MAXR 65536
class DLX {
public:
    struct DacingLinks {
        int left, right;
        int up, down;
        int ch, rh;
        int data; // extra info
    } DL[MAXE];
    int s[MAXC], o[MAXR], head, size, Ans, findflag;
    void Remove(int c) {
        static int i;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            DL[DL[i].right].left = DL[i].left;
            DL[DL[i].left].right = DL[i].right;
            s[DL[i].ch]--;
        }
    }
    void Resume(int c) {
        static int i;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            DL[DL[i].right].left = i;
            DL[DL[i].left].right = i;
            s[DL[i].ch]++;
        }
    }
    int used[MAXC] = {};
    int H() {
        static int c, ret, i, j, time = 0;
        for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
            if(used[c] != time) {
                ret ++, used[c] = time;
                for(i = DL[c].down; i != c; i = DL[i].down)
                    for(j = DL[i].right; j != i; j = DL[j].right)
                        used[DL[j].ch] = time;
            }
        }
        return ret;
    }
    void DFS(int k) {
        if(k + H() >= Ans) return;
        if(DL[head].right == head) {
            Ans = min(Ans, k);
            return;
        }
        int t = MAXV, c = 0, i, j;
        for(i = DL[head].right; i != head; i = DL[i].right) {
            if(s[i] < t) {
                t = s[i], c = i;
            }
        }
        for(i = DL[c].down; i != c; i = DL[i].down) {
            o[k] = i;
            Remove(i);
            for(j = DL[i].right; j != i; j = DL[j].right) Remove(j);
            DFS(k+1);
            for(j = DL[i].left; j != i; j = DL[j].left) Resume(j);
            Resume(i);
            if (findflag) break;
        }
    }
    int new_node(int up, int down, int left, int right) {
        assert(size < MAXE);
        DL[size].up = up, DL[size].down = down;
        DL[size].left = left, DL[size].right = right;
        DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
        return size++;
    }
    void addrow(int n, int Row[], int data) {
        int a, r, row = -1, k;
        for(a = 0; a < n; a++) {
            r = Row[a];
            DL[size].ch = r, s[r]++;
            DL[size].data = data;
            if(row == -1) {
                row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
                DL[row].rh = a;
            }else {
                k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
                DL[k].rh = a;
            }
        }
    }
    void init(int m) {
        size = 0;
        head = new_node(0, 0, 0, 0);
        int i;
        for(i = 1; i <= m; i++) {
            new_node(i, i, DL[head].left, head);
            DL[i].ch = i, s[i] = 0;
        }
    }
} dlx;
const int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};
int greedy(int n, int m, char g[][16]) {
    int ret = 0;
    while (true) {
        int has = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'X') {
                    has = 1;
                }
            }
        }
        if (!has)   break;
        int mx = 0, bx = 0, by = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = 0;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    while (x >= 0 && x < n && y >= 0 && y < m) {
                        if (g[x][y] == 'X')
                            cnt++;
                        x += dx[k], y += dy[k];
                    }
                }
                if (g[i][j] == 'X')
                    cnt++;
                if (cnt > mx)
                    mx = cnt, bx = i, by = j;
            }
        }
        for (int k = 0; k < 8; k++) {
            int x = bx + dx[k], y = by + dy[k];
            while (x >= 0 && x < n && y >= 0 && y < m) {
                if (g[x][y] == 'X')
                    g[x][y] = '.';
                x += dx[k], y += dy[k];
            }
        }
        if (g[bx][by] == 'X')
            g[bx][by] = '.';
        ret++;
    }
    return ret;
}
int main() {
    int cases = 0;
    int n, m;
    char g[16][16];
    while (scanf("%d %d", &n, &m) == 2 && n) {
        int cover_col = 0, A[16][16] = {};
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'X') {
                    A[i][j] = ++cover_col;
                }
            }
        }
        dlx.init(cover_col);
   
        int row[2028], rowSize = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                rowSize = 0;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    while (x >= 0 && x < n && y >= 0 && y < m) {
                        if (g[x][y] == 'X')
                            row[rowSize++] = A[x][y];
                        x += dx[k], y += dy[k];
                    }
                }
                if (g[i][j] == 'X')
                    row[rowSize++] = A[i][j];
                sort(row, row + rowSize);
                if (rowSize) {
                    dlx.addrow(rowSize, row, i * m + j);
                }
            }
        }
        dlx.Ans = greedy(n, m, g);
        dlx.DFS(0);
        printf("Case %d: %d\n", ++cases, dlx.Ans);
    }
    return 0;
}

Read More +

2015-03-08

解題區/解題區 - UVa

UVa 1683 - In case of failure

Problem

對平面上，每一個點找到最鄰近點的距離，輸出歐幾里得距離的平方即可。

Sample Input

Sample Output

Solution

KD Tree

計算幾何中的資料結構 KD-tree，雖然不算完美，一開始先進行 random search，先找到基礎的剪枝條件，隨後掛上啟發式進行搜索。

KD-tree 的效能在 D 度空間，區間詢問 (回報區域中的所有點或求區域極值) 的效能約為 O(n^(1-1/d))。我不會估算找鄰近點對的效能。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 262144
#define MAXD 2
#define INF (1LL<<60)
class kdTree {
public:
    struct PointD {
        long long d[MAXD];
        int label;
    };
    struct Node {
        Node *lson, *rson;
        int label;
    };
    struct cmp {
        bool operator()(const PointD* x, const PointD* y) const {
            if (x->d[sortDidx] != y->d[sortDidx])
                return x->d[sortDidx] < y->d[sortDidx];
            return x->label < y->label;
        }
    };
    struct pQcmp {
        bool operator() (pair<long long, int> &a, pair<long long, int> &b) const {
            if (a.first != b.first)	return a.first < b.first;
            return a.second < b.second;
        }
    };
    static int sortDidx;
    priority_queue<pair<long long, int>, vector< pair<long long, int> >, pQcmp> pQ; // <dist, label>
    Node buf[MAXN], *root;
    PointD pt[MAXN], *A[MAXN];
    int bufsize, K, qM, n;
    long long Q[MAXD], max_dist;
    void prepare(int n) {
        this->n = n;
        bufsize = 0;
        for (int i = 0; i < n; i++)
            A[i] = &pt[i];
        root = build(0, 0, n - 1);
    }
    Node* build(int k, int l, int r) {
        if(l > r)	return NULL;
        int m = (l + r)/2;
        Node *ret = &buf[bufsize++];
        sortDidx = k;
        nth_element(A + l, A + m, A + r + 1, cmp());
        ret->label = A[m]->label, ret->lson = ret->rson = NULL;
        if(l != r) {
            ret->lson = build((k+1)%K, l, m-1);
            ret->rson = build((k+1)%K, m+1, r);
        }
        return ret;
    }
    long long dist(int idx) {
        long long ret = 0;
        for(int i = 0; i < K; i++)
            ret += (long long)(pt[idx].d[i] - Q[i]) * (pt[idx].d[i] - Q[i]);
        return ret;
    }
    long long h_func(long long h[]) {
        long long ret = 0;
        for(int i = 0; i < K; i++)	ret += h[i];
        return ret;
    }
    void findNearest(Node *u, int k, long long h[]) {
        if(u == NULL || h_func(h) >= max_dist)
            return;
        long long d = dist(u->label);
        if (d <= max_dist) {
            pQ.push(make_pair(d, u->label));
            while (pQ.size() >= qM + 1)
                max_dist = pQ.top().first, pQ.pop();
        }
        long long old_hk = h[k];
        if (Q[k] <= pt[u->label].d[k]) {
            if (u->lson != NULL)
                findNearest(u->lson, (k+1)%K, h);
            if (u->rson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->rson, (k+1)%K, h);
                h[k] = old_hk;
            }
        } else {
            if(u->rson != NULL)
                findNearest(u->rson, (k+1)%K, h);
            if (u->lson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->lson, (k+1)%K, h);
                h[k] = old_hk;
            }
        }
    }
    void randomSearch(int ban) {
        max_dist = INF;
        long long d;
        for (int i = 0; i < 100; i++) {
            int x = rand()%n;
            if (x == ban)	continue;
            d = dist(x);
            if (d <= max_dist) {
                pQ.push(make_pair(d, x));
                while (pQ.size() >= qM + 1)
                    max_dist = pQ.top().first, pQ.pop();
            }
        }
    }
    void query(long long p[], int M, int ban) {
        for (int i = 0; i < K; i++)
            Q[i] = p[i];
        max_dist = INF, qM = M;
        long long h[MAXD] = {};
        randomSearch(ban);
        findNearest(root, 0, h);
        vector<int> ret;
        while (!pQ.empty())
            ret.push_back(pQ.top().second), pQ.pop();
        for (int i = (int) ret.size() - 1; i >= 0; i--) {
            if (ret[i] == ban)	continue;
            printf("%lld\n", dist(ret[i]));
            break;
        }
    }
};
int kdTree::sortDidx;
kdTree tree;
int main() {
    int n;
    long long p[MAXD];
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        tree.K = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++)
                scanf("%lld", &tree.pt[i].d[j]);
            tree.pt[i].label = i;
        }
        tree.prepare(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++)
                p[j] = tree.pt[i].d[j];
            tree.query(p, 2, i);
        }
    }
    return 0;
}
/*
 2
 10
 17 41
 0 34
 24 19
 8 28
 14 12
 45 5
 27 31
 41 11
 42 45
 36 27
 15
 0 0
 1 2
 2 3
 3 2
 4 0
 8 4
 7 4
 6 3
 6 1
 8 0
 11 0
 12 2 
 13 1 
 14 2 
 15 0
 */

Delaunay

關於 Delaunay triangulation 在此就不說明，由於是 Voronoi Diagram，就可以找到所有相鄰的點。

效能是 O(n log n)，而平面上的邊為線性 O(n)，但這種做法必須離線。

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
using namespace std;
#define eps 1e-8
#define MAXN (1048576)
#define MAXV 262144
struct Point {
    double x, y;
    int id;
    Point(double a = 0, double b = 0, int c = -1):
    x(a), y(b), id(c) {}
    Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y);
    }
    Point operator+(const Point &a) const {
        return Point(x + a.x, y + a.y);
    }
    Point operator*(const double a) const {
        return Point(x * a, y * a);
    }
    Point operator/(const double a) const {
        return Point(x / a, y / a);
    }
    bool operator<(const Point &a) const {
        if (fabs(x - a.x) > eps)	return x < a.x;
        if (fabs(y - a.y) > eps)	return y < a.y;
        return false;
    }
    bool operator==(const Point &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Point &a) const {
        return !(fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    }
    void read(int id = -1) {
        this->id = id;
    }
    double dist(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    double dist2(Point b) {
        return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
    }
    void print() {
        printf("point (%lf, %lf)\n", x, y);
    }
};
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
    x(a), y(b), z(c) {}
    Point3D(Point p) {
        x = p.x, y = p.y, z = p.x * p.x + p.y * p.y;
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    double dot(Point3D a) {
        return x * a.x + y * a.y + z * a.z;
    }
};
struct Edge {
    int id;
    list<Edge>::iterator twin;
    Edge(int id = 0) {
        this->id = id;
    }
};
int cmpZero(double v) {
    if (fabs(v) > eps)	return v > 0 ? 1 : -1;
    return 0;
}
double cross(Point o, Point a, Point b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
Point3D cross(Point3D a, Point3D b) { // normal vector
    return Point3D(a.y * b.z - a.z * b.y
                   , -a.x * b.z + a.z * b.x
                   , a.x * b.y - a.y * b.x);
}
int inCircle(Point a, Point b, Point c, Point p) {
    if (cross(a, b, c) < 0)
        swap(b, c);
    Point3D a3(a), b3(b), c3(c), p3(p);
    //	printf("%lf %lf %lf\n", a3.x, a3.y, a3.z);
    //	printf("%lf %lf %lf\n", b3.x, b3.y, b3.z);
    //	printf("%lf %lf %lf\n", c3.x, c3.y, c3.z);
    //	printf("%lf %lf %lf\n", p3.x, p3.y, p3.z);
    b3 = b3 - a3, c3 = c3 - a3, p3 = p3 - a3;
    Point3D f = cross(b3, c3); // normal vector
    return cmpZero(p3.dot(f)); // check same direction, in: < 0, on: = 0, out: > 0
}
int intersection(Point a, Point b, Point c, Point d) { // seg(a, b) and seg(c, d)
    return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0
    && cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
class Delaunay {
public:
    list<Edge> head[MAXV]; // graph
    Point p[MAXV];
    int n, rename[MAXV];
    void init(int n, Point p[]) {
        for (int i = 0; i < n; i++)
            head[i].clear();
        for (int i = 0; i < n; i++)
            this->p[i] = p[i];
        sort(this->p, this->p + n);
        for (int i = 0; i < n; i++)
            rename[p[i].id] = i;
        this->n = n;
        divide(0, n - 1);
    }
    void addEdge(int u, int v) {
        head[u].push_front(Edge(v));
        head[v].push_front(Edge(u));
        head[u].begin()->twin = head[v].begin();
        head[v].begin()->twin = head[u].begin();
    }
    void divide(int l, int r) {
        if (r - l <= 1) { // #point <= 2
            for (int i = l; i <= r; i++)
                for (int j = i+1; j <= r; j++)
                    addEdge(i, j);
            return;
        }
        int mid = (l + r) /2;
        divide(l, mid);
        divide(mid + 1, r);
        
        list<Edge>::iterator it;
        int nowl = l, nowr = r;
        
        //		printf("divide %d %d\n", l, r);
        for (int update = 1; update; ) { // find left and right convex, lower common tangent
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptR, ptL, t);
                if (cmpZero(v) > 0 || (cmpZero(v) == 0 && ptR.dist2(t) < ptR.dist2(ptL))) {
                    nowl = it->id, update = 1;
                    break;
                }
            }
            if (update)	continue;
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptL, ptR, t);
                if (cmpZero(v) < 0 || (cmpZero(v) == 0 && ptL.dist2(t) < ptL.dist2(ptR))) {
                    nowr = it->id, update = 1;
                    break;
                }
            }
        }
        
        addEdge(nowl, nowr); // add tangent
        //		printf("add base %d %d\n", nowl, nowr);
        for (int update = 1; true;) {
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            int ch = -1, side = 0;
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                //				ptL.print(), ptR.print(), p[it->id].print();
                if (cmpZero(cross(ptL, ptR, p[it->id])) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = -1;
                //				printf("test L %d %d %d\n", nowl, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                if (cmpZero(cross(ptR, p[it->id], ptL)) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = 1;
                //				printf("test R %d %d %d\n", nowr, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            if (ch == -1)	break; // upper common tangent
            //			printf("choose %d %d\n", ch, side);
            if (side == -1) {
                for (it = head[nowl].begin(); it != head[nowl].end(); ) {
                    if (intersection(ptL, p[it->id], ptR, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowl].erase(it++);
                    } else
                        it++;
                }
                nowl = ch;
                addEdge(nowl, nowr);
            } else {
                for (it = head[nowr].begin(); it != head[nowr].end(); ) {
                    if (intersection(ptR, p[it->id], ptL, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowr].erase(it++);
                    } else
                        it++;
                }
                nowr = ch;
                addEdge(nowl, nowr);
            }
        }
    }
    
    vector< pair<int, int> > getEdge() {
        vector< pair<int, int> > ret;
        list<Edge>::iterator it;
        for (int i = 0; i < n; i++) {
            for (it = head[i].begin(); it != head[i].end(); it++) {
                if (it->id < i)
                    continue;
                //				printf("DG %d %d\n", i, it->id);
                ret.push_back(make_pair(p[i].id, p[it->id].id));
            }
        }
        return ret;
    }
} tool;
#define INF (1LL<<60)
Point p[MAXV];
long long ret[MAXV];
int main() {
    int testcase, n;
    long long x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld %lld", &x, &y);
            p[i] = Point(x, y, i);
        }
        tool.init(n, p);
        vector< pair<int, int> > DG = tool.getEdge();
        for (int i = 0; i < n; i++) {
            ret[i] = INF;
        }
        for (int i = 0; i < DG.size(); i++) {
            x = DG[i].first, y = DG[i].second;
            long long v = (long long) (p[x].x - p[y].x) * (long long) (p[x].x - p[y].x) +
            (long long) (p[x].y - p[y].y) * (long long) (p[x].y - p[y].y);
            ret[x] = min(ret[x], v);
            ret[y] = min(ret[y], v);
        }
        for (int i = 0; i < n; i++) {
            printf("%lld\n", ret[i]);
        }
    }
    return 0;
}
/*
 2
 10
 17 41
 0 34
 24 19
 8 28
 14 12
 45 5
 27 31
 41 11
 42 45
 36 27
 15
 0 0
 1 2
 2 3
 3 2
 4 0
 8 4
 7 4
 6 3
 6 1
 8 0
 11 0
 12 2
 13 1
 14 2
 15 0
 */

Read More +

2015-03-08

解題區/解題區 - UVa

UVa 1679 - Easy Geometry

Problem

在凸多邊形內部找一最大空白矩形 (平行兩軸)。多邊形頂點數最多 10 萬個。

Sample Input

Sample Output

1 2	3.5 2.5 5.5 4.5 1 1 7 4

Solution

三分內嵌三分再內嵌二分，幾何算法從函數觀點下手的有趣題目。

首先，觀察矩形在 x 軸的情況，觀察矩形左側 left.x，最大空白矩形面積呈現凸性，而在 left.x 下，right.x 分布也呈現凸性。

因此，三分左端點再三分右端點，最後二分查找兩條平行線交凸邊形的兩點，找到空白矩形的面積。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    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);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    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;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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 cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
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);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
#define MAXN 131072
#define INF 1e+30
Pt D[MAXN];
double ret;
Pt retLpt, retRpt;
double getArea(vector<Pt> &upper, vector<Pt> &lower, double lx, double rx) {
    int p, q;
    Pt a, b, c, d;
    p = (int) (lower_bound(upper.begin(), upper.end(), Pt(lx, INF)) - upper.begin());
    q = (int) (lower_bound(lower.begin(), lower.end(), Pt(lx, INF)) - lower.begin());
    assert(p > 0 && q > 0);
    a = getIntersect(Seg(Pt(lx, 1), Pt(lx, -1)), Seg(upper[p], upper[p-1]));
    b = getIntersect(Seg(Pt(lx, 1), Pt(lx, -1)), Seg(lower[q], lower[q-1]));
    p = (int) (lower_bound(upper.begin(), upper.end(), Pt(rx, INF)) - upper.begin());
    q = (int) (lower_bound(lower.begin(), lower.end(), Pt(rx, INF)) - lower.begin());
    assert(p > 0 && q > 0);
    c = getIntersect(Seg(Pt(rx, 1), Pt(rx, -1)), Seg(upper[p], upper[p-1]));
    d = getIntersect(Seg(Pt(rx, 1), Pt(rx, -1)), Seg(lower[q], lower[q-1]));
    double area = (rx - lx) * (min(a.y, c.y) - max(b.y, d.y));
    if (area > ret) {
        ret = area;
        retLpt = Pt(lx, max(b.y, d.y));
        retRpt = Pt(rx, min(a.y, c.y));
    }
    return area;
}
double search(vector<Pt> &upper, vector<Pt> &lower, double lx) {
    double l = lx, r = upper[upper.size()-1].x, mid, midmid, md, mmd;
    double ret = 0;
    for (int it = 0; it < 100; it++) {
        mid = (l + r)/2;
        midmid = (mid + r)/2;
        md = getArea(upper, lower, lx, mid);
        mmd = getArea(upper, lower, lx, midmid);
        ret = max(ret, md);
        if (md < mmd)
            l = mid;
        else
            r = midmid;
    }
    return ret;
}
double findMaxRectangle(vector<Pt> upper, vector<Pt> lower) {
    double mnx, mxx;
    mnx = upper[0].x, mxx = upper[upper.size()-1].x;
    double l = mnx, r = mxx, mid, midmid, md, mmd;
    double ret = 0;
    for (int it = 0; it < 100; it++) {
        mid = (l + r)/2;
        midmid = (mid + r)/2;
        md = search(upper, lower, mid);
        mmd = search(upper, lower, midmid);
        ret = max(ret, md);
        if (md < mmd)
            l = mid;
        else
            r = midmid;
    }
    return ret;
}
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            D[i].read(); // clockwise order
        double mnx = INF, mxx = -INF;
        for (int i = 0; i < N; i++) {
            mnx = min(mnx, D[i].x);
            mxx = max(mxx, D[i].x);
        }
        vector<Pt> upper, lower;
        Pt Lpt = Pt(mnx, -INF), Rpt = Pt(mxx, INF);
        int lst, rst;
        for (int i = 0; i < N; i++) {
            if (cmpZero(D[i].x - mnx) == 0) {
                if (Lpt < D[i]) {
                    Lpt = D[i], lst = i;
                }
            }
            if (cmpZero(D[i].x - mxx) == 0) {
                if (D[i] < Rpt) {
                    Rpt = D[i], rst = i;
                }
            }
        }
        while (true) {
            upper.push_back(D[lst]);
            if (cmpZero(D[lst].x - mxx) == 0)
                break;
            lst = (lst + 1)% N;
        }
        while (true) {
            lower.push_back(D[rst]);
            if (cmpZero(D[rst].x - mnx) == 0)
                break;
            rst = (rst + 1)% N;
        }
        reverse(lower.begin(), lower.end());
        ret = 0;
        double area = findMaxRectangle(upper, lower);
//		printf("%lf\n", area);
        printf("%lf %lf %lf %lf\n", retLpt.x, retLpt.y, retRpt.x, retRpt.y);
    }
    return 0;
}
/*
4
5 1
2 4
3 7
7 3
5
1 1
1 4
4 7
7 4
7 1
*/

Read More +

2015-03-08

解題區/解題區 - UVa

UVa 1676 - GRE Words Revenge

Problem

操作有二種，學習單詞以及給一篇文章，詢問學習單詞出現總次數。

輸入有經過加密，其加密的位移量為上一次詢問答案。

Sample Input

Sample Output

Case #1:
2
Case #2:
1
0

Solution

如果是靜態，則可以想到 AC 自動機自然可以解決，但是 AC 自動機卻不支持動態建造。

為了滿足操作，可以利用快取記憶體的方式，進行分層，將小台 AC 自動機不斷重新建造，當小台 AC 自動機的節點總數大於某個值時，將其與大台 AC 自動機合併。合併操作必須是線性的，不要去重新插入每一個單詞。

特別小心有重複的單詞出現的小台或者是大台的操作，如果有重複必須忽略。雖然在理論上，分兩層操作的總複雜度高於倍增分層 (2, 4, 6, 8, …)，但是實作後，倍增分層一直 TLE。

然而這一題還有一種更困難的作法，詳見劉汝佳那本書，估計是一個動態後綴樹自動機 …

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 2
#define MAXS (5000005)
#define MAXNODE 526288
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val;
        void init() {
            fail = NULL;
            cnt = val = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
        return c - '0';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
char s[MAXS];
void decodeString(char s[], int L) {
    static char buf[MAXS];
    int n = (int) strlen(s);
    L %= n;
    for (int i = L, j = 0; i < n; i++, j++)
        buf[j] = s[i];
    for (int i = 0, j = n - L; i < L; i++, j++)
        buf[j] = s[i];
    for (int i = 0; i < n; i++)
        s[i] = buf[i];
}
ACmachine cache, disk;
int main() {
    int testcase, cases = 0;
    int N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        printf("Case #%d:\n", ++cases);
        int L = 0; // encrypted key
        int cFlag = 0, dFlag = 0;
        cache.init(), disk.init();
        for (int i = 0; i < N; i++) {
            scanf("%s", s);
            decodeString(s+1, L);
            //            printf("%s\n", s);
#define THRESHOLD 4096
            if (s[0] == '+') {
                if (disk.find(s+1) || cache.find(s+1))
                    continue;
                cache.insert(s+1), cFlag = 0;
                if (cache.size > THRESHOLD) {
                    disk.merge(cache), dFlag = 0;
                    cache.free();
                    cache.init(), cFlag = 0;
                }
            } else {
                if (!cFlag) cache.build();
                if (!dFlag) disk.build();
                int ret = disk.query(s+1) + cache.query(s+1);
                printf("%d\n", ret);
                L = ret;
            }
        }
        disk.free(), cache.free();
    }
    return 0;
}
/*
 99999
 10
 +01
 +110
 ?010
 +110
 +00
 +0
 ?001001
 ?001001
 +110110
 ?1101001101
 
 6
 +01
 +110
 +110
 +00
 +0
 ?001001
 
 20
 +101001011
 ?110100
 +11010100
 ?0011001101
 +111011
 ?00010011
 +0111010110
 +0000101
 +0
 +11000
 ?1
 +1010101
 +0001
 +0110
 +0111101111
 ?1100
 +0111
 +1001
 ?0110111011
 ?1010010100
 
 10
 +00
 ?010110100
 +0100000100
 +111
 +000000
 ?0000110
 +110
 +00
 +0011
 ?101001
 
 5
 +0
 +1000100
 +01
 +0
 ?1110010011
 
 2
 3
 +01
 +01
 ?01001
 3
 +01
 ?010
 ?011
 */

Read More +

2015-03-08

解題區/解題區 - UVa

UVa 1349 - Optimal Bus Route Design

Problem

每一條公車路線都是環狀，要求每一個站只在一條公車路線上，給定站與站之間的連通花費，求公車路線最少為何。

Sample Input

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

Sample Output

1
2
3

7 
25 
N

Solution

看起來先拆點，要求每一個點變成出點跟入點，要求每一個出點都能配對一個入點，這麼一來能保證每一個點都能走出去，進而形成環狀。

那麼這就是一題完美帶權二分匹配判定。

#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM 1048576
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], dis[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0, flow, totflow = 0;
        int i, x, y;
        while(1) {
            memset(dis, 63, sizeof(dis));
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = oo;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int main() {
    int n, x, y, v;
    while (scanf("%d", &n) == 1 && n) {
        g.init(2 * n + 2);
        int source = 2 * n, sink = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            x = i;
            while (scanf("%d", &y) == 1 && y) {
                scanf("%d", &v);
                y--;
                g.Addedge(2*x, 2*y+1, 1, v);
            }
            g.Addedge(source, 2*i, 1, 0);
            g.Addedge(2*i+1, sink, 1, 0);
        }
        pair<int, int> ret = g.mincost(source, sink);
        if (ret.second == n)
            printf("%d\n", ret.first);
        else
            puts("N");
    }
    return 0;
}

Read More +

2015-03-08

解題區/解題區 - UVa

UVa 1343 - The Rotation Game

Problem

一款很神秘的遊戲，盤面上只會有 1, 2, 3 三種數字，可以藉由八種轉動方式，目標是將中間的八格變成都是相同數字。

求最少步數。

Sample Input

1
2
3

1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

Sample Output

AC
2
DDHH
2

Solution

一開始設想，直接將三個分開討論，只考慮目標為 1 或 2 或 3，將狀態只變成 0/1，但分開計算的結果再取最小值可能會太慢，利用 BFS 很容易造成 TLE。

藉由 IDA* 的思路，啟發函數為中間位置還差多少個目標才能湊滿八個，因為每一次轉動，至多增加某一個數字在中間的個數。

#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string.h>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXSTATE 1048576
#define MAXN (20000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXN];
// 24! / (8! 16!) = 735471
int shift[8][8] = {
    {0, 2, 6, 11, 15, 20, 22},      // A
    {1, 3, 8, 12, 17, 21, 23},      // B
    {10, 9, 8, 7, 6, 5, 4},         // C
    {19, 18, 17, 16, 15, 14, 13},   // D
    {23, 21, 17, 12, 8, 3, 1},      // E
    {22, 20, 15, 11, 6, 2, 0},      // F
    {13, 14, 15, 16, 17, 18, 19},   // G
    {4, 5, 6, 7, 8, 9, 10}          // H
};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int invShift[8] = {5, 4, 7, 6, 1, 0, 3, 2};
void shiftStrip(int A[], int dir) {
    int tmp = A[shift[dir][0]];
    for (int i = 0; i < 6; i++)
        A[shift[dir][i]] = A[shift[dir][i+1]];
    A[shift[dir][6]] = tmp;
}
int H(int A[]) {
    int K[4] = {};
    for (int i = 0; i < 8; i++) {
        K[A[center[i]]]++;
    }
    return 8 - max(K[1], max(K[2], K[3]));
}
int ida_depth, solved;
int path[128];
int IDA(int A[], int dep, int hv) {
    if (hv == 0) {
        solved = 1;
        if (dep == 0) {
            puts("No moves needed");
        } else {
            for (int i = 0; i < dep; i++)
                printf("%c", path[i] + 'A');
            puts("");
        }
        printf("%d\n", A[center[0]]);
        return dep;
    }
    if (dep + hv > ida_depth)
        return dep + hv;
    int back = 0x3f3f3f3f, shv, tmp;
    for (int i = 0; i < 8; i++) {
        shiftStrip(A, i);
        shv = H(A), path[dep] = i;
        tmp = IDA(A, dep + 1, shv);
        back = min(back, tmp);
        shiftStrip(A, invShift[i]);
        if (solved) return back;
    }
    return back;
}
int main() {
    while (true) {
        int A[32];
        for (int i = 0; i < 24; i++) {
            scanf("%d", &A[i]);
            if (A[i] == 0)  return 0;
        }
        solved = 0;
        for (ida_depth = 0; solved == 0;)
            ida_depth = IDA(A, 0, H(A));
    }
    return 0;
}
/*
 
*/

Read More +