Mar 21 2015

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 +

Mar 21 2015

解題區►解題區 - 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 +

Mar 21 2015

解題區►解題區 - 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 +

Mar 21 2015

解題區►解題區 - 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 +

Mar 10 2015

解題區►解題區 - 其他題目

HDU 5097 - Page Rank

Problem

配合上一篇巨量資料的學習，利用馬可夫過程找到 Page Rank。

Sample Input

Sample Output

1	0.15 1.49 0.83 1.53

Solution

然而 Page Rank 計算主要分成兩種，一種是指派所有的 Page Rank 總合為 S，如果加起來不足 S，則把不足的部分平攤給所有節點，這麼一來計算誤差就可以被碾平，但這樣會會因為太多網頁，而導致單一 Rank 過小。

另外一種，則單純倚靠隨機的全局擴散，雖然會有計算誤差，持續做下去一樣會收斂。

為了加快速度，將公式的 $1 - \beta$ 提出，沒有必要將一個稀疏矩陣變成稠密矩陣，如果每一個矩陣元素都加上 $\frac{1 - \beta}{N}$ 會導致整個矩陣不存在非 0 的元素，而事實上 0 的元素是相當多的。這麼一來每次迭代的效率為 $O(E)$，而非 $O(N^{2})$。

#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
using namespace std;
// Markov process, math
const int MAXN = 4096;
const int MAXIT = 9999;
class PageRank {
public:
    const double eps = 1e-10;
    vector<int> g[MAXN], invg[MAXN];
    vector<double> r;
    int N;
    double beta, S;
    void init(int n, double beta) {
        this->N = n;
        this->beta = beta;
        for (int i = 0; i < n; i++)
            g[i].clear(), invg[i].clear();
    }
    void addEdge(int u, int v) {
        g[u].push_back(v);
        invg[v].push_back(u);
    }
    bool isComplete(vector<double> &a, vector<double> &b) {
        double e = 0;
        for (int i = (int) a.size() - 1; i >= 0; i--) {
            e += (a[i] - b[i]) * (a[i] - b[i]);
        }
        return e < eps;
    }
    void compute() {
        vector<double> next_r(N, 0);
        r.resize(N, 1.0);
        
        for (int it = 0; it < MAXIT; it++) {
            for (int i = 0; i < N; i++) {
                double tmp = 0;
                for (int j = 0; j < invg[i].size(); j++) {
                    int x = invg[i][j];
                    tmp += r[x] / g[x].size();
                }
                next_r[i] = tmp * beta + (1.0 - beta);
            }
            if (isComplete(r, next_r)) {
                r = next_r;
                return ;
            }
            r = next_r;
        }
    }
} g;
char s[MAXN][MAXN];
int main() {
    const double beta = 0.85f;
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%s", s[i]);
        
        g.init(N, beta);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (s[i][j] == '1') {
                    g.addEdge(i, j);
                }
            }
        }
        
        g.compute();
        
        for (int i = 0; i < N; i++) {
            printf("%.2lf%c", g.r[i], i == N - 1 ? '\n' : ' ');
        }
    }
    return 0;
}

Read More +

Mar 8 2015

解題區►解題區 - 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 +

Mar 8 2015

解題區►解題區 - 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 <= 2) { // #point <= 3
            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 +

Mar 8 2015

解題區►解題區 - 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 +

Mar 8 2015

解題區►解題區 - 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 +

Mar 8 2015

解題區►解題區 - 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 +