Oct 12 2014

建造二元搜尋樹 O(n log n)

Problem

參照 Zerojudge d526: Binary Search Tree (BST) 按照插入的順序，建造一棵二元搜尋樹，原則上很簡單，但是很容易遇到極端的偏斜情況，如果插入順序很接近已經排序過的順序，則複雜度最慘為 O(n^2)。

Sample Input

11
368 115 121 88 741 762 801 34 41 511 60
6
5 2 10 4 9 15

Sample Output

1 2	368 115 88 34 41 60 121 741 511 762 801 5 2 4 10 9 15

Solution

核心

先稍微認識一下笛卡爾樹 (一種二元樹)，每個節點為 <key, value>，只看 key 時，笛卡爾樹是一棵二元搜尋樹，而看 value 時，它是一個最大堆 (或者是最小堆)。

在建造前，先撇清一點，笛卡爾樹的深度可能到達 n，與一般平衡樹不同。

笛卡爾樹如何建造 ? 假使已經對於 key 值由小到大排序 (升排序)，那麼將點依序插入笛卡爾樹，能保證的是－由於要符合二元搜尋樹，新加入的點一定是這棵樹某個節點的右節點。知道這一點後，再往前考慮前一次插入的點(它原本也符合再某節點的右節點)，往這個節點往上爬，直到符合最大堆(性質 node.v > new_insert.v)，這時將這個節點的右子樹移到新加入節點的左子樹 (此時符合二元搜尋樹的性質，也保有原本堆的性質)。就這麼持續入點下去。

這麼發現，往上爬的次數不超過節點個數，因為每個節點只會從右子樹換到左子樹。均攤下 O(n) (每個節點只會從右子樹推到左子樹一次，因此最多 n 次)

我們接著將 “按照順序插入的 BST” 轉換成建造笛卡爾樹，key 值依舊為輸入的元素大小，而 value 則訂為輸入順序，根據 key 值為一個二元搜尋樹，根據 value 建造一個最小堆，那麼仔細思考可以得到與原本相同的二元搜尋樹。

建造笛卡爾樹只需要花 O(n) 時間，但建造前必須根據 key 排序 O(n log n)，所以複雜度為 O(n log n)。

在這樣的方式建造有一個缺點，並不知道途中插入的情況，只會在最後得到一樣的二元搜尋樹。假使要得到途中插入的情況，考慮離線處理，將所有操作儲存起來，而二元樹的節點位置並不會更動的情況下，事先建造一個靜態樹，隨後使用一個懶標記存在與否即可。

補充

如何利用這個笛卡爾樹解決最簡單的 RMQ 問題？
對於 <key, value> = <i, A[i]> 所建造的笛卡爾樹，可以利用 LCA 的 tarjan 算法(離線作法) 在 O(n) 時間內完成。RMQ 假使查找 [l, r] 的最小值，又因為我們根據 value 建造最小堆，則根據 tarjan 的搜索順序，拜訪右子樹時(對於區間的 r 來說)，左子樹將會跟其 LCA 合併，而 LCA 的 index 肯定比左子樹來得大 (大於等於 l)，又根據最小堆保證是大於等於 l 且小於等於 r 的最小值。
只有笛卡爾樹可以做到建造二元搜尋樹嗎？
其實並不然，還可以藉由一個額外的平衡樹來完成，效率一樣在 O (n log n)，但是親自撰寫平衡樹本身就本末倒置，如果藉由 STL 提供的平衡樹，代碼量會比笛卡爾樹好寫多。具體而言使用 lower_bound 查找當前插入的元素位在哪兩個元素之間，一定符合在右子樹或者是左子樹。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Node {
    int key, value;
    int lson, rson, parent;
};
Node D[65536];
void insertCartesianTree(int index, Node D[]) {
    int p = index - 1;
    while(D[p].value > D[index].value)
        p = D[p].parent;
    D[index].lson = D[p].rson;
    D[p].rson = index;
    D[index].parent = p;
}
void dfsPrint(int node) {
    if(node == 0)    return;
    printf("%d ", D[node].key);
    dfsPrint(D[node].lson);
    dfsPrint(D[node].rson);
}
int main() {
    int N, x;
    pair<int, int> A[65536];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &x);
			A[i] = make_pair(x, i);
        }
        sort(A+1, A+1+N);
        D[0].value = -1;
        D[0].lson = D[0].rson = D[0].parent = 0;
        for(int i = 1; i <= N; i++) {
            D[i].lson = D[i].rson = D[i].parent = 0;
            D[i].value = A[i].second, D[i].key = A[i].first;
        }
        for(int i = 1; i <= N; i++) {
            insertCartesianTree(i, D);
        }
        dfsPrint(D[0].rson);
        puts("");
    }
    return 0;
}

Read More +

Oct 6 2014

解題區►解題區 - UVa

UVa 12424 - Answering Queries on a Tree

Problem

給一棵樹

調整某一個節點上的顏色
詢問兩個點路徑上，哪一個顏色數量最多，輸出數量即可。

Sample Input

Sample Output

Solution

由於顏色不大於 10，可以安妥建造 10 棵線段樹，利用樹鏈剖分的概念，重邊將會取子樹最大的那一邊，其他都是輕邊，隨後保證每一個點往上爬升，最多經過 log n 個輕邊。

因此時間複雜度調整 O(log n) 詢問 O(log^2 n)。

對於樹鏈剖分找 LCA 操作，針對兩個 (x, y) 所在的 node 而言，查看哪個 node 位置高低，調整到同高進行操作，保證爬的次數最多 log n，對於每一個 node 中建造一個線段樹，因此各自 query 也要 log n。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 131072
int color[MAXN];
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
	int p, pPos, dep;
	vector<int> A;
	vector<int> seg[10];
	void init() {
		A.clear();
		p = -1, dep = 0;
	}
} nodes[262144];
struct Tree {
	vector<int> g[MAXN];
	int root;	
	void init(int n) {
		for (int i = 0; i < n; i++)
			g[i].clear();
		root = 0;
	}
	void addEdge(int x, int y) {
		g[x].push_back(y);
		g[y].push_back(x);
	}
} tree;
int getSTsize(int n) {
	int ret = 1;
	for (ret = 1; ret < n; ret <<= 1);
	return ret<<1;
}
int prepare(int u, int p) {
	int sz = 1, mx = -1, hedge = -1;
	int v, t;
	for (int i = 0; i < tree.g[u].size(); i++) {
		v = tree.g[u][i], t;
		if (v == p)	continue;
		sz += (t = prepare(v, u));
		if (mx < t)
			mx = t, hedge = v;
	}
	hNext[u] = hedge;
	return sz;
}
void buildST(Node &nd, int k, int l, int r) {
	if (l > r)	return ;
	if (l == r) {
		nd.seg[color[nd.A[l]]][k] = 1;
		return;
	}
	int mid = (l + r)/2;
	buildST(nd, k<<1, l, mid);
	buildST(nd, k<<1|1, mid+1, r);
	for (int i = 0; i < 10; i++)
		nd.seg[i][k] = nd.seg[i][k<<1] + nd.seg[i][k<<1|1];
}
void build(int u, int p) {	
	if (used[u] == 0) {
		Node &nd = nodes[++nodesize];
		nd.init();
		for (int i = u; i != -1; i = hNext[i]) {
			used[i] = 1;
			iNode[i] = nodesize, aPos[i] = nd.A.size();
			nd.A.push_back(i);
		}
		for (int i = 0; i < 10; i++)
			nd.seg[i].clear(), nd.seg[i].resize(getSTsize(nd.A.size()), 0);
		buildST(nd, 1, 0, nd.A.size() - 1);
		if (p != -1) {
			nd.p = iNode[p], nd.pPos = aPos[p];
			nd.dep = nodes[nd.p].dep + 1;
		}
	}
	int v;
	for (int i = 0; i < tree.g[u].size(); i++) {
		v = tree.g[u][i];
		if (v == p)	continue;
		build(v, u);
	}
}
int colorsum[10];
void queryST(Node &nd, int k, int l, int r, int x, int y) {
	if (x <= l && r <= y) {
		for (int i = 0; i < 10; i++)
			colorsum[i] += nd.seg[i][k];
		return ;
	}
	int mid = (l + r)/2;
	if (x <= mid)
		queryST(nd, k<<1, l, mid, x, y);
	if (mid < y)
		queryST(nd, k<<1|1, mid+1, r, x, y);
	
}
void search(int u, int v) {
	memset(colorsum, 0, sizeof(colorsum));
	int x = iNode[u], y = iNode[v];
	u = aPos[u], v = aPos[v];
	while (x != y) {
		if (nodes[x].dep < nodes[y].dep)
			swap(x, y), swap(u, v);
		assert(u <= nodes[x].A.size());
		queryST(nodes[x], 1, 0, nodes[x].A.size() - 1, 0, u);
		u = nodes[x].pPos, x = nodes[x].p;
	}
	if (u > v)	swap(u, v);
	queryST(nodes[x], 1, 0, nodes[x].A.size() - 1, u, v);
	int ret = 0;
//	for (int i = 0; i < 10; i++)
//		printf("%d ", colorsum[i]);
//	puts("");
	for (int i = 0; i < 10; i++)
		ret = max(ret, colorsum[i]);
	printf("%d\n", ret);
}
void modifyST(Node &nd, int k, int l, int r, int x, int v) {
	if (l == r) {
		for (int i = 0; i < 10; i++)
			nd.seg[i][k] = 0;
		nd.seg[v][k]++;
		return ;
	}
	int mid = (l + r)/2;
	if (x <= mid)
		modifyST(nd, k<<1, l, mid, x, v);
	else
		modifyST(nd, k<<1|1, mid+1, r, x, v);
	for (int i = 0; i < 10; i++)
		nd.seg[i][k] = nd.seg[i][k<<1] + nd.seg[i][k<<1|1];
}
void modify(int u, int color) {
	int x = iNode[u];
	modifyST(nodes[x], 1, 0, nodes[x].A.size() - 1, aPos[u], color);
}
int main() {
//	freopen("in.txt","r+t",stdin);
//    freopen("out2.txt","w+t",stdout);
	int testcase;
	int n, q, x, y;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &q);
		for (int i = 0; i < n; i++)
			scanf("%d", &color[i]), color[i]--;
		tree.init(n);
		
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			x--, y--;
			tree.addEdge(x, y);
		}
		
		prepare(tree.root = 0, -1);
		memset(used, 0, sizeof(used));
		nodesize = 0;
		build(tree.root = 0, -1);
		
//		for (int i = 0; i < n; i++)
//			printf("[%d] %d\n", i, hNext[i]);
		int cmd, u, v;
		for (int i = 0; i < q; i++) {
			scanf("%d %d %d", &cmd, &u, &v);
			if (cmd == 0) {
				u--, v--;
				modify(u, v);
			} else {
				u--, v--;
				search(u, v);
			}
		}
	}
	return 0;
}

Read More +

Oct 6 2014

解題區►解題區 - UVa

UVa 12783 - Weak Links

Problem

是否存在 weak link，使得兩個 component 會因為 weak link 斷掉而無法連通。

Sample Input

Sample Output

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

Solution

找橋 bridge！利用 back edge 的深度進行判斷。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int visited[1024], depth[1024];
vector< pair<int, int> > bridge;
int findBridge(int u, int p, int dep) {
	visited[u] = 1, depth[u] = dep;
	int back = 0x3f3f3f3f;
	for(int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if(v == p)	continue;
		if(!visited[v]) {
			int b = findBridge(v, u, dep+1);
			if(b > dep)
				bridge.push_back(make_pair(u, v));
			back = min(back, b);
		} else {
			back = min(back, depth[v]);
		}
	}
	return back;
}
int main() {
	int n, m, q, x, y;
	while(scanf("%d %d", &n, &m) == 2 && n+m) {
		for(int i = 0; i < n; i++)
			g[i].clear();
		for(int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			g[x].push_back(y);
			g[y].push_back(x);
		}
		
		bridge.clear();
		memset(visited, 0, sizeof(visited));
		for(int i = 0; i < n; i++) {
			if(!visited[i]) {
				findBridge(i, -1, 0);
			}
		}
		for (int i = 0; i < bridge.size(); i++)
			if (bridge[i].first > bridge[i].second)
				swap(bridge[i].first, bridge[i].second);
		sort(bridge.begin(), bridge.end());
		printf("%d", bridge.size());
		for (int i = 0; i < bridge.size(); i++)
			printf(" %d %d", bridge[i].first, bridge[i].second);
		puts("");
	}
	return 0;
}

Read More +

Oct 6 2014

解題區►解題區 - UVa

UVa 12784 - Don't Care

Problem

問是否計算順序會影響結果，給一個有向圖，請問是否每一個操作都會 reduce 到同一個項目。

Sample Input

Sample Output

Solution

如果裡面有環肯定是不行的，因此需要偵測環是否存在。

在這之後，必須檢查是否會 reduce 到同一個項目，因此我們將每個 node reduce 的結果保存，之後取聯集，如果發現 reduce 項目超過一個則直接回傳失敗。

#include <stdio.h> 
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> g[1024];
set<int> A[1024];
int used[1024];
int instk[1024];
int dfs(int u) {
	used[u] = 1, instk[u] = 1;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (instk[v])
			return 1;
		if (!used[v]) {
			if(dfs(v))
				return 1;
			A[u].insert(A[v].begin(), A[v].end());
			if (A[u].size() > 1)
				return 1;
		}
	}
	if (g[u].size() == 0)
		A[u].insert(u);
	instk[u] = 0;
	return A[u].size() > 1;
}
int main() {
	int n, m, x, y;
	while (scanf("%d %d", &n, &m) == 2 && n) {
		for (int i = 0; i < n; i++)
			g[i].clear(), used[i] = 0, A[i].clear(), instk[i] = 0;
		int indeg[1024] = {};
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			g[x].push_back(y);
			indeg[y]++;
		}
		
		int err = 0;
		for (int i = 0; i < n && !err; i++) {
			if (used[i] == 0 && indeg[i] == 0)
				err |= dfs(i);
		}
		for (int i = 0; i < n; i++) // cycle
			if (used[i] == 0)
				err = 1;
		printf("%d\n", !err);
	}
	return 0;
}
/*
3 2
0 1
1 2
2 2
0 1
0 1
2 2
0 1
1 0
3 2
0 1
0 2
0 0
*/

Read More +

Oct 6 2014

解題區►解題區 - Zerojudge

b317. 紅圓茵可的野望

內容：

紅圓茵可最近隱居在板擦山研究魔法師的夢想，傳說中的魔法－「召喚蘿莉」。
只要成功練就這個魔法，茵可就可以召喚出一堆蘿莉，然後跟一堆蘿莉一起……嘿嘿嘿…..
目前茵可已經研究出N種可能可以成功魔法陣，接下來就是要測試這些魔法陣能不能成功召喚蘿莉，因為數量實在太多了，所以他決定先測試其中K種。為了測試魔法陣，茵可需要先開一個異次元空間，並且在裡面做測試(因為召喚蘿莉是個極大的魔法，發動時可能會造成空間扭曲，不小心毀掉可茵城就不好了。)。魔法陣都是圓形的，半徑為r，發動一個魔法陣需要以魔法陣為底高度為h的圓柱體空間。而茵可只能開出長方體的異次元空間，一個異次元空間有其長、寬、高，而魔法陣只能放置在該空間的地板上(長 x 寬那一面)，所以要發動一個半徑為r，高度為h的魔法陣，茵可需要開一個長2r寬2r高h的異次元空間(體積2r x 2r x h)。現在茵可想要開一個異次元空間，而這個空間至少要能發動K個魔法陣(不必同時發動)，這個空間的體積至少是多少。

輸入說明：

第一行有兩個正整數 N,K(K<=N)
接下來N行每行有兩個正整數r,h代表一個魔法陣的半徑及發動需要高度(r,h<=100)

測資

N<=100
N<=100
N<=100
N<=100000
N<=100000

輸出說明：

輸出要發動其中K個魔法陣所需最小的異次元空間的體積是多少

範例輸入：

範例輸出：

提示：

範測所需體積為 224=16

可發動第1、2、5個魔法陣

Solution

這一題有兩種做法，直接窮舉 O(100 * 100) 的針對 [r, h] 找到 [0, r] x [0, h] 的數量是否大於 K，那麼可以在線性時間內完成。

而下面的做法，算是多此一步，原本想說能不能用 O(n log n) 時間內完成，但是會缺少部分調整資訊，也就是單純排序，以掃描線的基準會漏到資訊。

如果這一題的 r, h 很大的話，窮舉還是會耗費 O(n^2 log n)，套用當前最佳解剪枝應該快上很多。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int BIT[256];
int query(int x) {
	int ret = 0;
	for (; x; x -= x&(-x))
		ret += BIT[x];
	return ret;
}
void modify(int x, int L) {
	for (; x <= L; x += x&(-x))
		BIT[x]++;
}
int main() {
	int N, K, r, h, w;
	while (scanf("%d %d", &N, &K) == 2) {
		vector<pair<int, int> > D;
		for (int i = 0; i < N; i++) {
			scanf("%d %d", &r, &h);
			assert(r <= 100 && h <= 100 && r > 0 && h > 0);
			D.push_back(make_pair(r * 2, h));
		}
		int ret = 0x3f3f3f3f;
		sort(D.begin(), D.end());
		memset(BIT, 0, sizeof(BIT));
		for (int i = 0; i < N; i++) {
			modify(D[i].second, 255);
			for (int j = D[i].second; j <= 100; j++) {
				int q = query(j);
				w = D[i].first, h = j;
				if (q >= K)
					ret = min(ret, w*w*h);
			}
		}
		if (K == 0)	ret = 0;
		printf("%d\n", ret);
	}
	return 0;
}

Read More +

Oct 6 2014

解題區►解題區 - Zerojudge

b316. 紅圓茵可的消失

內容：

「哇!我終於解出來啦!咦?茵可呢?」剛解完K大數字差的你，在茵可家到處尋找，卻始終不見紅圓茵可的身影。
四處打聽之下，得知茵可前往神秘之山－「板擦山」修練神秘的魔法去了。板擦山本身有天然的結界，只有法力高強的魔法師才有辦法進入山中。「這下子我該怎麼找到茵可呢?」你苦思著，「想找茵可嗎?我可以告訴你怎麼找到茵可!」似乎是剛好路過的長頸鹿這麼說道。
板擦山的山腳下有好幾間便利商店，這些便利商店剛好開在結界外，茵可每天都會到山下的其中一間購買民生用品，而且到哪家便利商店是可以預測的。板擦山上有N個點，每個點有各自的編號，越高的點編號越小，點跟點之間有道路連接，茵可所在的山頂為編號0的點，便利商店也是其中的一個點。茵可每天會由山頂出發，經過一些點後到山下的便利商店買東西。當茵可走到一個點x後，他會先走跟x有連接的點中，編號比x大(當然要往山下走阿)的點中，編號最小的那一個。而下一次又到x時就走第二小的，直到編號比x大的點都走過一次，就會回到最小的點繼續走。(假設 3號點連到 1,4,5，第一次到3時，茵可會走向4。下一次到3時，茵可會走向5。再下一次到3時，茵可會走向4。)若一個點沒有連到編號比它大的點，則該點為便利商店。
你從長頸鹿手中的到了板擦山的地圖，你就可以預測茵可在第K天時會走到哪一家便利商店了!

輸入說明：

第一行有兩個正整數N,M,K，表示有N個點(編號0~N-1)、M條邊(M<=N*(N-1)/2)及詢問第K天茵可會到哪個點。
接下來M行每行有兩個整數a,b表示a跟b間有一條邊(保證同樣兩個點間只會有一條邊)。

測資

N<=10,K<=100
N<=10,K<=100
N<=1000,K<=1000
N<=1000,K<=1000000000，整張圖為一棵樹
N<=1000,K<=1000000000

輸出說明：

輸出第K天時茵可會走到哪個點。

範例輸入：

範例輸出：

提示：

範例測資
第一天 0→1→2→3
第二天 0→2→3
第三天 0→4
第四天 0→1→4

Solution

一開始曲解題目了，不過沒關係。

首先讓我們來了解多久一循環，根據公式 $cycle(u) = \sum cycle(v) | u \rightarrow v$，這個很容易理解的，事實上 cycle(0) 可能很大派不上用場。

如果試圖用週期 M 天，則期望用模擬迭代到 M 天是否與第一天相同，則很容易在 M + 1 天不會與第二天相同，因為路徑相同不代表狀態相同。

藉此我們利用動態規劃的概念，來找尋狀態的基底位置。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int main() {
	int N, M, K;
	int x, y;
	while (scanf("%d %d %d", &N, &M, &K) == 3) {
		for (int i = 0; i < N; i++)
			g[i].clear();
		for (int i = 0; i < M; i++) {
			scanf("%d %d", &x, &y);
			if (x > y)	swap(x, y);
			g[x].push_back(y);
		}
		for (int i = 0; i < N; i++)
			sort(g[i].begin(), g[i].end());
		int pass[1024] = {};
		int now = 0, x, sum = 0;
		pass[0] = --K;
		for (int i = 0; i < N; i++) {
			if (g[i].size() == 0)	continue;
			int u = i, v, div = pass[u] % g[i].size();
			for (int j = 0; j < g[i].size(); j++) {
				v = g[i][j];
				pass[v] += pass[u] / g[i].size();
				if (j < div)
					pass[v]++;
			} 
		}
		for (; g[now].size(); ) {
			x = pass[now]%g[now].size();
			now = g[now][x];
//			printf("-> %d\n", now);
		}
		printf("%d\n", now);
	}
	return 0;
}
/*
5 6 1
0 1
0 2
1 2
2 3
0 4
1 4
5 6 2
0 1
0 2
1 2
2 3
0 4
1 4
5 6 3
0 1
0 2
1 2
2 3
0 4
1 4
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4
*/

Read More +

Oct 6 2014

解題區►解題區 - Zerojudge

b315. 紅圓茵可的考驗

內容：

身為魔法師的你，想讓自己變得更強大，於是前來膜拜紅圓茵可，同時想請教他學習魔法的秘訣。經過日復一日的嘗試，你終於通過了柏油路，並且來到茵可家。「看在你這麼努力的份上，我就稍微指導你一下吧。」茵可說道。「所謂魔法，跟程式設計很像，就是一堆指令的結合。將分子移動、放熱、發光等等基礎的小魔法結合在一起，就會變成強大的魔法(像是防護罩就是控制空氣分子的移動，並使其重新排列成為堅固的結構，達到防禦的效果。)。所以說，腦中運算的能力是很重要的。」語畢，茵可大大丟給你一個題目:

給你N個數字，挑出其中兩個數字可以得到一個數字差(非負)，而N個數字會有N*(N-1)/2個數字差，問第K大數字差是多少?
如範例輸入，數字差有6個，分別為9(10-1)、7(8-1)、5(10-5)、4(5-1)、3(8-5)、2(10-8)，其中第5大的是3。

「等你能在1秒內解完這個問題再來找我吧!」隨後茵可打開比較大的門走掉了。

輸入說明：

第一行有兩個正整數N,K
接下來有N個整數(0<=每個整數<=1,000,000,000)

測資

N<=10，K<=N*(N-1)/2
N<=1,000，K<=N*(N-1)/2
N<=10,000，K<=10,000
N<=100,000，K<=100,000
N<=100,000，K<=1,000,000,000

輸出說明：

輸出第K大數字差

範例輸入：

1 2	4 5 1 5 8 10

範例輸出：

Solution

使用二分搜索答案，通常是查找第 K 小的元素，這題是換成第 K 大元素，那麼就反過來找，中間調校的時候要特別小心。

代碼效率是 O(n log^2 n)，事實上可以壓成 O(n log n)，因為中間的索引值肯定是單調的，不過要考慮組合問題，特別要小心同一個元素自減的結果。由於懶得判斷，複雜度高了點還是過了。

#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int kThDiff(int A[], int n, long long m) {
	int mx = A[0], mn = A[0];
	for (int i = 0; i < n; i++)
		mx = max(mx, A[i]), mn = min(mn, A[i]);
	int l = 0, r = mx - mn, mid, ret;
	m = (long long) n * (n-1)/2 - m + 1;
	long long cnt;
	sort(A, A+n);
	while (l <= r) {
		mid = (l + r)/2;
		cnt = 0;
		for (int i = 0; i < n; i++) {
			int pos = (int)(upper_bound(A+i, A+n, A[i] + mid) - A);
			cnt += pos - i - 1;
		}
		if (cnt >= m)
			r = mid - 1, ret = mid;
		else
			l = mid + 1;
	} 
	return ret;
}
int main() {
	int n, m, A[131072];
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		printf("%d\n", kThDiff(A, n, m));
	}
	return 0;
}
/*
9 4
4 6 3 7 7 5 0 8 9 
5 1
7 4 2 5 2 
10 3
4 6 9 8 7 1 1 4 2 0 
9 20
3 8 6 2 1 9 6 7 2 
2 1
2 6 
4 4
0 9 0 0 
5 7
4 0 9 1 8 
11 30
1 2 1 6 1 0 7 7 5 2 5 
4 3
4 7 5 8 
2 1
1 6 
10 40
7 5 5 0 2 9 4 9 6 2 
3 2
6 8 7 
10 28
3 5 0 8 1 1 7 9 2 1 
9 3
6 7 1 2 0 8 5 1 0 
8 22
0 3 1 9 1 8 4 7 
11 20
2 3 0 4 7 1 7 6 2 2 1 
3 1
7 3 9 
4 2
9 2 4 5 
10 39
6 5 2 3 6 1 1 8 1 9 
8 7
4 9 7 2 1 6 3 2 
*/

Read More +

Oct 5 2014

解題區►解題區 - Zerojudge

b314. 紅圓茵可的煩惱

內容：

相信大家都知道紅圓茵可是誰，就不多介紹了。最近他有一個煩惱，身為一位大魔法師，每天都有成千上萬的人來膜拜他<( )>。因為人數實在太多了，這麼多人跑到他家膜拜他，害他都無法好好練習魔法了。茵可家門前有一條柏油路，要到他家一定得經過這條柏油路，他決定把這條柏油路(長方形)切成N*M個格子，並且在其中某些格子設下陷阱，踩到陷阱的人會被傳送回柏油路的起點。「恩~這樣子就可以減少膜拜我的人了~」紅圓茵可心想。但是，為了讓jackyXX等人可以到達他家，也不能把柏油路封死，必須確保一定有條路徑可以走到茵可家。而你的任務是要提醒茵可大大<( )>，哪些點能放陷阱，而哪些點不能放陷阱(導致道路封死)。
柏油路的起點在左邊，而茵可家在柏油路的右邊。一個人在柏油路上只能往上下左右四個方向走，不能走斜對角。

一條3*10的柏油路

oooooooooo
oooooooooo
oooooooooo

一條被封死的柏油路

ooooxooooo
oooxoooooo
ooxooooooo

一條沒被封死的柏油路

xxxxxxoooo
oooooxoxxx
ooxxoooxoo

輸入說明：

第一行有3個正整數N、M、T，T為茵可接下來要放的陷阱數量(0<T<=N*M)。
接下來T行每行有2個非負整數x,y表示這個陷阱要放的位址。
縱軸為x軸，橫軸為y軸，左下角那格為(0,0)。
保證一個點只會被放最多一次。

測資

N,M<=10
N,M<=50
N,M<=100
N,M<=1000
N,M<=1000

輸出說明：

對每一個要放的陷阱，若該點可放，請輸出一行”<( )>”(不含雙引號)，並且把陷阱放上去。
若該點不可放(會導致道路封死)，請輸出”>_<”(不含雙引號)，並且不放該陷阱。

範例輸入：

範例輸出：

<(_ _)>
<(_ _)>
>_<
>_<
<(_ _)>

Solution

這一題相當活用并查集的概念，雖然題目問說是否能左右相連，但是反過來則是上下邊界是否會從不相連變成相連。

多設兩個虛點，我們假想所有上界點都與虛上點相連，下界點都與虛下點相連，每次一次加入一個障礙物時，檢查九宮格內是否會造成上下虛點相連，這裡必須先偷看并查集的結果，隨後在考慮是否將其相連。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int parent[1048576], weight[1048576];
int used[1024][1024];
const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
const int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};
int findp(int x) {
	return parent[x] == x ? parent[x] : parent[x] = findp(parent[x]);
}
int joint(int p, int q) {
	p = findp(p), q = findp(q);
	if (weight[p] > weight[q])
		weight[p] += weight[q], parent[q] = p;
	else
		weight[q] += weight[p], parent[p] = q;
	return 1;
}
int main() {
	int n, m, Q, cases = 0;
	int x, y, tx, ty;
	while (scanf("%d %d %d", &n, &m, &Q) == 3) {
		cases++;
		int N = n * m + 10, up = n * m + 1, down = n * m + 2;
		int p, q, A[8];
		for (int i = 0; i < N; i++)
			parent[i] = i, weight[i] = 1;
		for (int i = 0; i < Q; i++) {
			scanf("%d %d", &x, &y);
			p = x * m + y;
			up = findp(up), down = findp(down);
			int s = 0;
			for (int j = 0; j < 8; j++)	{
				tx = x + dx[j], ty = y + dy[j];
				if (ty < 0 || ty >= m)	{
					A[j] = p;
					continue;
				}
				if (tx < 0)			q = up;
				else if(tx >= n)	q = down;
				else {
					if (used[tx][ty] != cases) {
						A[j] = p;
						continue;
					}
					q = tx * m + ty;
				}
				if (findp(q) == up)		s |= 1;
				if (findp(q) == down)	s |= 2;
				A[j] = q;
			}
			if (s != 3) {
				puts("<(_ _)>");
				for (int j = 0; j < 8; j++) {
					joint(p, A[j]);
				}
				used[x][y] = cases;
			} else {
				puts(">_<");
			}
		}
	}
	return 0;
}

Read More +

Oct 5 2014

解題區►解題區 - UVa

UVa 225 - Golygons

Problem

每一步轉角九十度，並且第 i 次要走 i 長單位，回到原點且沿途不經過障礙物，同時轉角不可重複。

Sample Input

Sample Output

wsenenws
Found 1 golygon(s).
Found 0 golygon(s).

Solution

沿途經過障礙物，同時轉角不重複。一開始曲解了經過的轉角點，以為他也不能在隨後中經過，但實際上是可以的，因此拿了不少 WA。

#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
int n, m, golygons;
set< pair<int, int> > ban;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char sdir[] = "nsew";
char path[1024];
char g[2048][2048] = {}, g2[2048][2048];
vector<string> ways;
#define BASE 1024
void dfs(int x, int y, int dir, int step) {
	if (abs(x - 0) + abs(y - 0) > (step + n) * (n - step + 1)/2) {
		return;
	}
	if (step == n + 1) {
		if (x == 0 && y == 0) {
			path[step - 1] = '\0';
//			puts(path);
			ways.push_back(path);
			golygons++;
		}
		return ;
	}
	if (dir != 0) {
		for (int i = 0; i < 2; i++) {
			int tx = x, ty = y, ok = 1;
			for (int j = 0; j < step; j++) {
				tx = tx + dx[i], ty = ty + dy[i];
				assert(BASE + tx >= 0 && BASE + ty >= 0);
				assert(BASE + tx < 2048 && BASE + ty < 2048);
				if (g[BASE + tx][BASE + ty]) {
					ok = 0;
					break;
				}
			}
			if (ok && g2[BASE + tx][BASE + ty] == 0) {
				g2[BASE + tx][BASE + ty] = 1;
				path[step - 1] = sdir[i];
				dfs(tx, ty, 0, step + 1);
				g2[BASE + tx][BASE + ty] = 0;
			}
		}
	}
	if (dir != 1) {
		for (int i = 2; i < 4; i++) {
			int tx = x, ty = y, ok = 1;
			for (int j = 0; j < step; j++) {
				tx = tx + dx[i], ty = ty + dy[i];
				assert(BASE + tx >= 0 && BASE + ty >= 0);
				assert(BASE + tx < 2048 && BASE + ty < 2048);
				if (g[BASE + tx][BASE + ty]) {
					ok = 0;
					break;
				}
			}
			if (ok && g2[BASE + tx][BASE + ty] == 0) {
				g2[BASE + tx][BASE + ty] = 1;
				path[step - 1] = sdir[i];
				dfs(tx, ty, 1, step + 1);
				g2[BASE + tx][BASE + ty] = 0;
			}
		}
	}
}
int main() {
	int testcase, x[64], y[64];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		ban.clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x[i], &y[i]);
			ban.insert(make_pair(x[i], y[i]));
			g[BASE + x[i]][BASE + y[i]] = 1;
		}
		ways.clear();
		dfs(0, 0, -1, 1);
		sort(ways.begin(), ways.end());
		for (int i = 0; i < ways.size(); i++)
			puts(ways[i].c_str());
		printf("Found %d golygon(s).\n\n", ways.size());
		for (int i = 0; i < m; i++)
			g[BASE + x[i]][BASE + y[i]] = 0;
	}
	return 0;
}
/*
2
8
2
-2 0
6 -2
8
2
2 1
-2 0
1000
16
0
*/

Read More +

Oct 5 2014

解題區►解題區 - UVa

UVa 12785 - Emacs Plugin

Problem

每個 * 位置，可以任意替換成任何字串或者是空字串，是問是否有可能匹配主字串。

Sample Input

4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x

Sample Output

yes
no
yes
yes
no

Solution

以 * 劃分，將其切割成好幾個 token，根據貪心原則只要按照順序出現這些 token 即可，因此盡可能靠左。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
#define MAXN 100005
char P[MAXN], T[MAXN];
int kmpTable[MAXN];
void KMPtable(const char *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(const char *T, int tlen, const char *P, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1)
        	return i;
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int n, plen, tlen;
	string token;
	while (scanf("%d", &n) == 1) {
		while (getchar() != '\n');
		gets(P);
		plen = strlen(P);
		for (int i = 0; i < n; i++) {
			gets(T);
			for (int j = 0; T[j]; j++) {
				if (T[j] == '*')
					T[j] = ' ';
			}
			stringstream sin(T);
			int start = 0;
			while (sin >> token) {		
				KMPtable(token.c_str(), token.length());
				int test = KMPmatching(P + start, plen - start, token.c_str(), token.length());
//				printf("%s %d %s\n", token.c_str(), test, P + start);
				if (test == -1)	 {start = -1; break;}
				start += test + 1;
			}
			puts(start == -1 ? "no" : "yes");
		}
	}
	return 0;
}
/*
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x
10
rwoeyhtdvtswftfguuujqxdxdqylkyqaahianzbejckxbgeybq
oexktdvtswftf*w*n*q*rvdloll*qr
kdd*ts*ftv**ur**cdx*qi
*dtlk
**q**g****a**n
*/

Read More +

Problem

Sample Input

Sample Output

Solution

核心

補充

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：