Oct 17 2014

[ACM 題目] 單調測試

Problem

單調－這性質相當巧妙，可以在算法上好好地敲上一筆，處理速度跟你輸入的速度一樣快呢。

Background

這是計算幾何作業中的一環，但是找到一個 O(n) 算法果然不容易。

3.11 Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not necessarily a horizontal or vertical one.

到底有沒有可能用單調性質測試單調呢？ O(n log n) 就是極限？讓我們來挑戰挑戰。

Problem

假想一個二維平面，x 軸左右兩側將會射入雷射，現在要將一個簡單多邊形由上往下放入，雷射將會打在第一個碰觸的點上，請問有沒有一種放置方式，使得每一個邊都被雷射覆蓋到。

如上圖，假使這樣放置，位置 (0, 0), (2, 0) 將無法被雷射覆蓋，如果將此圖旋轉 90 度放入，就能覆蓋到所有邊了！因此，決定是否有一個角度放入，能覆蓋到所有邊。

Input

有多組測資，每一組測資第一行將會有一個整數 N，

接下來會有 N 行，每一行上會有一個座標 (x, y)，採用順時針或者逆時針順序。

Output

對於每組測資輸出一行，每一行輸出 yes/no。

Sample Input

Sample Output

1
2

yes
no

Solution

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
#define eps 1e-10
#define MAXN 32767
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 double &a) const {
        return Pt(x * a, y * a);
    }
    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 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);
}
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;
}
Pt getIntersect(Pt l1, Pt p1, Pt l2, Pt p2) {
	double a1, b1, c1, a2, b2, c2;
	double dx, dy, d;
	a1 = l1.y, b1 = -l1.x;
	c1 = a1 * p1.x + b1 * p1.y;
	a2 = l2.y, b2 = -l2.x;
	c2 = a2 * p2.x + b2 * p2.y;
	dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
	d = a1 * b2 - a2 * b1;
	return Pt(dx/d, dy/d);
}
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;
    }
};
struct CMP2 {
    bool operator()(const double &i, const double &j) const {
        if (fabs(i-j) > eps)
            return i < j;
        return false;
    }
};
Seg segs[MAXN];
Pt D[MAXN];
int testMonotone(int n, Pt D[]) {
    int m = 0, origin_n = n;
    D[n] = D[0], D[n+1] = D[1];
    for (int i = 1; i <= n; i++) {
        Pt v1 = D[i + 1] - D[i];
        Pt v2 = D[i - 1] - D[i];
        segs[m++] = Seg(v1, v2, i);
        segs[m++] = Seg(v1 * -1, v2 * -1, i);
    }
    n = m;
    Pt pos = Pt(0, 0);
    set<int> S;
    map<double, vector< pair<int, int> >, CMP2> angle;
    for (int i = 0; i < n; i++) {
        double v1 = atan2(segs[i].s.y - pos.y, segs[i].s.x - pos.x);
        double v2 = atan2(segs[i].e.y - pos.y, segs[i].e.x - pos.x);
        angle[v1].push_back(make_pair(i, 0));
        angle[v2].push_back(make_pair(i, 1));
    }
    double c;
    pair<int, int> u = angle.begin()->second[0];
    Pt fpt;
    if (u.second == 0)  fpt = segs[u.first].s;
    else                fpt = segs[u.first].e;
    for (int i = 0; i < n; i++) {
		if (cross(pos, fpt, segs[i].s) * cross(pos, fpt, segs[i].e) < 0) {
			Pt q = getIntersect(segs[i].s - segs[i].e, segs[i].s, fpt - pos, pos);
			if (dot(q - pos, fpt - pos) > 0)
				S.insert(segs[i].label);
		} 
    }
    for (map<double, vector< pair<int, int> >, CMP2>::iterator it = angle.begin();
         it != angle.end(); it++) {
        for (int i = 0; i < it->second.size(); i++) {
            pair<int, int> u = it->second[i];
            if (u.second == 0)
                c = cross(pos, segs[u.first].s, segs[u.first].e);
            else
                c = cross(pos, segs[u.first].e, segs[u.first].s);
            if (fabs(c) > eps) {
                if (c > 0)
                    S.insert(segs[u.first].label);
                else
                    S.erase(segs[u.first].label);
            }
        }
        if (S.size() >= origin_n - 2)
            return 1;
    }
    return 0;
}
int main() {
    int n;
    double x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        int flag = testMonotone(n, D);
        puts(flag ? "yes" : "no");
    }
    return 0;
}

Read More +

Oct 17 2014

解題區►解題區 - Zerojudge

b327. 學姊日談

內容：

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』
Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

輸入說明：

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

輸出說明：

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行，保證總和可以在 signed 32 bits 內。

範例輸入：

範例輸出：

Solution 1

先將一棵樹壓平，壓平的方式為採用前序走訪。壓樹的另一個思考方式就是換成括弧表示法。(A (B) (C(D)(E))) 類似的情況。壓樹之後，每個節點對應一個左右括弧位置，當我們增加節點 v 權重時，相當於將所有區間的內數字加上 k (子樹的所有節點到根的花費)。

因此我們的問題變成

操作 [l, r]：將區間內的所有數字加上 k
詢問 x：詢問位置 x 元素的值。

下面使用 Binary indexed tree 示範區間調整，單點詢問。

對於 ADD [l, r] k 時，相當於 BIT[l] += k, BIT[r+1] -= k，單點詢問相當於找前綴和 [1, x] 的結果。

每個操作時間複雜度 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
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 bPos[MAXN], ePos[MAXN], inOrder[MAXN<<1], inIdx = 0;
void prepare(int u, int p) {
	bPos[u] = ePos[u] = ++inIdx, inOrder[inIdx] = u;
	for (int i = 0; i < tree.g[u].size(); i++) {
		int v = tree.g[u][i];
		if (v == p)	continue;
		prepare(v, u);
	}
	ePos[u] = ++inIdx, inOrder[inIdx] = u;
}
int bitTree[MAXN<<1];
void modify(int x, int N, int val) {
    while (x <= N) {
        bitTree[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += bitTree[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
	int n, q, x, y;
	char cmd[10];
	while (scanf("%d", &n) == 1) {
		tree.init(n);
		
		int on[MAXN] = {};
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			tree.addEdge(x, y);
		}
		
		inIdx = 0;
		prepare(tree.root = 0, -1);
		memset(bitTree, 0, sizeof(bitTree));
		scanf("%d", &q);
		for (int i = 0; i < q; i++) {
			scanf("%d %d", &x, &y);
			modify(bPos[x], inIdx, y);
            modify(ePos[x] + 1, inIdx, -y);
			printf("%d\n", query(bPos[x]));
		}
		puts("");
	}
	return 0;
}

Solution 2

這個解法直接使用樹鏈剖分，樹鏈剖分將子樹節點數量最大的當作重邊，其餘皆為輕邊。將以重邊相連的所有節點，看似一個鏈狀，當作一個 1D Array 看待。

保證每個點爬到 root，只會經過 log n 的輕邊，而中間鏈狀處理，可以使用 segment tree 等之類的樹來壓縮處理時間。

下面為樹鏈剖分的解法，詢問效率 O(log^2 n)，調整 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
	int p, pPos;
	vector<int> A;
	vector<int> BIT;
	void init() {
		A.clear(), BIT.clear();
		p = -1;
	}
} 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 prepare(int u, int p) {
	int sz = 1, mx = 0, 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 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);
		}
		nd.BIT.clear(), nd.BIT.resize(nd.A.size() + 10, 0);
		if (p != -1)	nd.p = iNode[p], nd.pPos = aPos[p];
	}
	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 queryBIT(vector<int> &BIT, int x) {
	int ret = 0;
	while (x)
		ret += BIT[x], x -= x&(-x);
	return ret;
}
void modifyBIT(vector<int> &BIT, int x, int val, int L) {
	while (x <= L)
		BIT[x] += val, x += x&(-x);
}
void search(int u) {
	int sum = 0;
	set< pair<int, int> >::iterator it, jt;
	for (int i = iNode[u], in = aPos[u]; i != -1; in = nodes[i].pPos, i = nodes[i].p)
		sum += queryBIT(nodes[i].BIT, in + 1);
	printf("%d", sum);
	puts("");
}
void modify(int u, int val) {
	Node &nd = nodes[iNode[u]];
	int pos = aPos[u];
	modifyBIT(nd.BIT, pos + 1, val, nd.A.size());
}
int main() {
	int n, q, x, y;
	char cmd[10];
	while (scanf("%d", &n) == 1) {
		tree.init(n);
		
		int on[MAXN] = {};
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			tree.addEdge(x, y);
		}
		
		prepare(tree.root = 0, -1);
		memset(used, 0, sizeof(used));
		nodesize = 0;
		build(tree.root = 0, -1);
		
		scanf("%d", &q);
		for (int i = 0; i < q; i++) {
			scanf("%d %d", &x, &y);
			modify(x, y);
			search(x);
		}
		puts("");
	}
	return 0;
}

Read More +

Oct 17 2014

解題區►解題區 - Zerojudge

b322. 樹形鎖頭

內容：

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

輸入說明：

輸入有多組測資。

每一組測資第一行會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

輸出說明：

每組測資輸出一行，分別將節點權重輸出。

範例輸入：

範例輸出：

1	5 3 5 3 2 4 8

Solution

解說圖

A[] : 子樹總和
B[] : 節點權重

增加路徑 u 到 v 的權重為 k 時，路徑相當於 u 到某點 x 再到 LCA(u, v) 接著 y 最後 v。

那我們增加節點 u, v 的權重 B[u] += k, B[v] += k，減少其 LCA 的權重 B[LCA(u, v)] -= 2k，然後你會觀察 A[] 的部分，權重增加 k 的只會有 u-v 之間的所有節點。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
int visited[32767];
vector<int> tree[32767];
int parent[32767], weight[32767];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
// LCA
vector< pair<int, int> > Q[32767];// query pair, input index - node
int LCA[131072]; // [query time] input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
		int v = tree[u][i];
    	if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int dfs(int u, int p, int weight[]) {
	int sum = weight[u];
    for(int i = 0; i < tree[u].size(); i++) {//son node.
		int v = tree[u][i];
    	if(v == p)	continue;
        sum += dfs(v, u, weight);
    }
    return weight[u] = sum;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
	int n, m, x, y, u, v, k;
	int X[32767], Y[32767], K[32767];
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			tree[i].clear();
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			tree[x].push_back(y);
			tree[y].push_back(x);
		}
		
		int weight[32767] = {}, extra[32767] = {};
		for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &X[i], &Y[i], &K[i]);
			Q[X[i]].push_back(make_pair(i, Y[i]));
        	Q[Y[i]].push_back(make_pair(i, X[i]));
		}
		tarjan(0, -1);
		for (int i = 0; i < m; i++) {
			extra[LCA[i]] += K[i];
			weight[X[i]] += K[i];
			weight[Y[i]] += K[i];
			weight[LCA[i]] -= 2 * K[i];
		}
		dfs(0, -1, weight);
		for (int i = 0; i < n; i++)
			printf("%d%s", weight[i] + extra[i], i == n-1 ? "" : " ");
		puts("");
	}
	return 0;
}

Read More +

Oct 17 2014

解題區►解題區 - Zerojudge

b321. 河道分界

內容：

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

輸入說明：

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

輸出說明：

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

範例輸入：

8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

範例輸出：

[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

Solution

建造一個 BST，這裡使用內建 std::set 的紅黑樹，查找 lower_bound 即可。如果是靜態的河道，一開始對其排序即可，然後二分查找 lower_bound。

如果測資有錯，歡迎打我。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
#define eps 1e-6
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);
    }
};
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);
}
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;
	int label;
	seg(Pt a, Pt b):s(a), e(b) {}
};
struct CMP {
	static double y;
	
	double interpolate(const Pt& p1, const Pt& p2, double& y) {
        if (p1.y == p2.y) return p1.x;
        return p1.x + (double)(p2.x - p1.x) / (p2.y - p1.y) * (y - p1.y);
    }
    
	bool operator()(const seg &i, const seg &j) {
		double v1 = interpolate(i.s, i.e, y), v2 = interpolate(j.s, j.e, y);
		if (fabs(v1 - v2) > eps)
			return v1 < v2;
		return false;
	}
};
double CMP::y = 0;
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
	int n;
	double x, y, up, down;
	char cmd[10];
	while (scanf("%d", &n) == 1) {
		set<seg, CMP> S;
		for (int i = 0, k = 1; i < n; i++) {
			scanf("%s", cmd);
			if (cmd[0] == 'A') {
				scanf("%lf %lf", &up, &down);
				seg tmp = seg(Pt(up, 1), Pt(down, 0));
				tmp.label = k;
				S.insert(tmp), k++;
			} else {
				scanf("%lf %lf", &x, &y);
				CMP::y = y;
				set<seg>::iterator it = S.lower_bound(seg(Pt(x, 1), Pt(x, 1))), jt;
				if (it != S.end()) {
					if (onSeg(it->s, it->e, Pt(x, y))) {
						puts("[?, ?]");
						continue;
					}
				}
				int l = -1, r = -1;
				if (it != S.begin()) {
					jt = it, jt--;
					l = jt->label;
					if (onSeg(jt->s, jt->e, Pt(x, y))) {
						puts("[?, ?]");
						continue;
					}
				}
				if (it != S.end())
					r = it->label;
				if (l == -1)
					printf("[S, ");
				else
					printf("[%d, ", l);
				if (r == -1)
					printf("M]");
				else
					printf("%d]", r);
				puts("");
			}
		}
	}
	return 0;
}

Read More +

Oct 12 2014

解題區►出題解題

[ACM 題目] 少女與戰車

Problem

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

一面走著，一面唱著歌兒。唱道草原上空的蒼鷹，唱道她衷心喜愛的男孩。他的來信封封都珍藏。

啊！歌兒，女孩悠揚的歌聲，請跟隨著光明的太陽，飛翔到遙遠前方的戰士，為喀秋莎來向他致意。

願他還記得純情的女孩，願她的歌聲能被聽聞。願他保衛著祖國的大地，而喀秋莎守護著愛情。

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

姑娘唱著美妙的歌曲，她在歌唱草原的雄鷹，她在歌唱心愛的人兒，她還藏著愛人的書信。

啊，這歌聲姑娘的歌聲，跟著光明的太陽去飛吧，去向遠方邊疆的戰士，把喀秋莎的問候傳達。

駐守邊疆年輕的戰士，心中懷念遙遠的姑娘，勇敢戰鬥保衛祖國，喀秋莎愛情永遠屬於他。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

現在有 N 台戰車平行奔馳在雪地上，在時間 $t = 0$ 時，分別位於 $x_{i}$，並且每戰車都維持等速度 $v_{i}$，請問有哪幾台曾經在奔馳的過程中當過領先者。

Input

輸入有多組測資，每組第一行會有一個整數 N (N < 32767)。

接著會有 N 行戰車資訊，每一行上會有兩個實數 $(x_{i}, v_{i})$，其中 $-100,000\le x_{i} \le 100,000$、$-100\le v_{i} \le 100$。

Output

對於每組輸出一行，按照輸入順序輸出是否曾經當過領先者，參閱範例輸出。

Sample Input

Sample Output

1 1 0
1 1 1 1 0 0
1 0 1
1 1 1 0

hint

Javascript Animation Click It !

example 1
example 2
example 3
example 4

Solution

Read More +

Oct 12 2014

解題區►解題區 - UVa

UVa 12806 - Grand Tichu

Problem

增加 4 張牌到撲克牌中，每名玩家將會獲得 14 張牌，而在有 8 張的時候，可以預估是否會湊到 4 種類型的手牌，如果可以組合出其中一種的機率大於 0.25，則喊出 Grand Tichu!。

Sample Input

D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0

Sample Output

Grand Tichu!
Grand Tichu!
Grand Tichu!
...
...
...

Solution

搜索順序的重要性，由於 4 種組合牌中，只與 ADPMd 有關，剩下的類型可以直接利用組合去計算，只要窮舉 ADPMd 出現在手牌的組合情況即可。

如果按照一般的 23456789TJQKADPMd 效率不彰，耗費時間太久，再多剪枝都不夠。

一開始誤以為是 4 種機率加總大於 0.25 就輸出，不管怎麼樣連範測都會錯，後來發現是湊出其中一種的機率必須大於 0.25。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long C[50][50];
const char kind[20] = "ADPMd23456789TJQK";
int ihand[20], ohand[20], mhand[20];
int suffix[20];
long long va[10], vb;
void dfs(int idx, int card, long long ways) {
	if (idx > 4) {
		ways = ways * C[suffix[idx]][14 - card];
		int hh = 0;
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
			hh = 1, va[hh] += ways;// D P A
		if (ohand[1] > 0 && ohand[0] >= 2)
			hh = 2, va[hh] += ways;// D A A
		if (ohand[2] > 0 && ohand[0] >= 3)
			hh = 3, va[hh] += ways; // P A A A
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
			hh = 4, va[hh] += ways; // D P M d
		vb += ways;
		return ;
	}
	if (card == 14) {
		int hh = 0;
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
			hh = 1, va[hh] += ways;// D P A
		if (ohand[1] > 0 && ohand[0] >= 2)
			hh = 2, va[hh] += ways;// D A A
		if (ohand[2] > 0 && ohand[0] >= 3)
			hh = 3, va[hh] += ways; // P A A A
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
			hh = 4, va[hh] += ways; // D P M d
		vb += ways;
		return ;
	}
	if (idx == 17 || card + suffix[idx] < 14)	return ;
	for (int i = 0; i <= ihand[idx] && card + i <= 14; i++) {
		ohand[idx] += i;
		dfs(idx+1, card + i, ways * C[ihand[idx]][i]);
		ohand[idx] -= i;
	}
}
int main() {
	for (int i = 0; i < 50; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++)
			C[i][j] = C[i-1][j-1] + C[i-1][j];
	}
	char hand[64];
	while (scanf("%s", &hand) == 1 && hand[0] != '0') {
		memset(ihand, 0, sizeof(ihand));
		memset(ohand, 0, sizeof(ohand));
		for (int i = 4; i < 17; i++)
			ihand[i] = 4, mhand[i] = 4;
		ihand[0] = 4, mhand[0] = 4;
		for (int i = 1; i <= 4; i++)
			ihand[i] = 1, mhand[i] = 1;
		for (int i = 0; i < 8; i++) {
			int p = find(kind, kind + 17, hand[i]) - kind;
			ihand[p]--, ohand[p]++;
		}
		memset(suffix, 0, sizeof(suffix));
		for (int i = 17; i >= 0; i--)
			suffix[i] = suffix[i+1] + ihand[i];
		memset(va, 0, sizeof(va));
		vb = 0;
		dfs(0, 8, 1);
		int ok = 0;
		for (int i = 0; i < 4; i++) {
			double p = (double)va[i] / vb;
			if (p > 0.25)	ok = 1;
		}
		if (ok)
			puts("Grand Tichu!");
		else
			puts("...");
	}
	return 0;
}
/*
D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0
D23468AA
0.000000
0.125000
1.000000
0.025439
Grand Tichu
D2P4688K
0.000000
0.424761
0.070768
0.004394
Grand Tichu
D23468KA
0.000000
0.125000
0.336263
0.003315
Grand Tichu
D2233889
0.000000
0.046558
0.070768
0.000298
...
PdM2345T
0.000000
0.046558
0.006332
0.004394
...
PdM234AA
0.000000
0.125000
0.125000
0.236702
...
*/

Read More +

Oct 12 2014

解題區►解題區 - UVa

UVa 12804 - The Necronomicon of Computing

Problem

給一段簡單的組合語言，有三種指令。

判斷指令：有可能跳到第 x 個指令，不然就會執行下一行指令。
計算指令：計算完，執行下一行指令。
跳躍指令：直接跳躍到第 x 個指令。

判斷這支程式是否有機會停止、或者是進入無限迴圈、還是一直都會結束。

Sample Input

3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A

Sample Output

1
2
3

NEVER
ALWAYS
SOMETIMES

Solution

知道指令與指令之間的關係，不仿建造一個有向圖，判斷使否存在一個環，根據 BFS 若沒有辦法抵達終點，

沒有辦法抵達終點，有環，保證程式會進入無限迴圈。
有辦法抵達終點，有環，有機會停止。
其他－總會停止。

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAXN 1024
vector<int> g[MAXN];
char cmd[MAXN][16];
int N[MAXN], used[MAXN], instk[MAXN];
int loopflag, endflag;
void dfs(int u) {
	instk[u] = 1, used[u] = 1;
	for (int i = 0; i < g[u].size(); i++) {
		if (used[g[u][i]] == 0)
			dfs(g[u][i]);
		if (instk[g[u][i]] == 1)
			loopflag = 1;
	}
	instk[u] = 0;
}
int main() {
	int testcase, L;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &L);
		for (int i = 0; i <= L + 1; i++)
			g[i].clear();
		for (int i = 1; i <= L; i++) {
			scanf("%s", cmd[i]);
			if (cmd[i][0] == 'A') {
				g[i].push_back(i+1);
			} else if (cmd[i][0] == 'J') {
				scanf("%d", &N[i]);
				g[i].push_back(N[i]);
			} else if (cmd[i][0] == 'C') {
				scanf("%d", &N[i]);
				g[i].push_back(N[i]);
				g[i].push_back(i+1);
			}
		}
		memset(used, 0, sizeof(used));
		memset(instk, 0, sizeof(instk));
		loopflag = 0, endflag = 0;
		dfs(1);
		endflag = used[L + 1];
		if (loopflag == 0 && endflag == 1)
			puts("ALWAYS");
		else if (loopflag == 1 && endflag == 0)
			puts("NEVER");
		else
			puts("SOMETIMES");
	}
	return 0;
}
/*
3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A
*/

Read More +

Oct 12 2014

解題區►解題區 - UVa

UVa 12803 - Arithmetic Expressions

Problem

給一個浮點數的五則運算表達式，計算其值。

Sample Input

3
( 3.00 + 4.50 )
( 5.00 - ( 2.50 * 3.00 ) )
( ( 7.00 / 3.00 ) + ( 4.00 - ( 3.00 * 7.00 ) ) )

Sample Output

1
2
3

7.50
-2.50
-14.67

Solution

中序表達轉換成後序表達，隨後再使用 stack 完成計算。

#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return 0;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
    	if (infix[i] == ' ')	continue;
        if(infix[i] >= '0' && infix[i] <= '9' || 
			(infix[i] == '-' && infix[i+1] >= '0' && infix[i+1] <= '9')) {
			while (infix[i] >= '0' && infix[i] <= '9' || 
				(infix[i] == '-' && infix[i+1] >= '0' && infix[i+1] <= '9') || infix[i] == '.') {
            	sprintf(ptr, "%c", infix[i]), i++;
            	while(*ptr)    ptr++;
        	}
        	sprintf(ptr, " ");
            while(*ptr)    ptr++;
        	i--;
        }else {
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(')
                while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
int isOper(char c) {
    switch(c) {
        case '(':return 1;
        case '+': case '-':return 1;
        case '*': case '/':return 1;
    }
    return 0;
}
double calcPostfix(char postfix[]) {
	stringstream sin(postfix);
	string token;
    stack<double> stk;
    double a, b, c;
    while (sin >> token) {
    	if (token.length() == 1 && isOper(token[0])) {
            b = stk.top(), stk.pop();
            a = stk.top(), stk.pop();
            switch(token[0]) {
                case '+': a = a+b;break;
                case '-': a = a-b;break;
                case '*': a = a*b;break;
                case '/': a = a/b;break;
            }
            stk.push(a);
    	} else {
    		stringstream cc(token);
    		cc >> c;
    		stk.push(c);
    	}
    }
    return stk.top();
}
char infix[262144], postfix[262144];
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (getchar() != '\n');
	while (testcase--) {
		gets(infix);
		trans(infix, postfix);
		printf("%.2lf\n", calcPostfix(postfix));
	}
	return 0;
}
/*
3
( 3.00 + 4.50 )
( 5.00 - ( 2.50 * 3.00 ) )
( ( 7.00 / 3.00 ) + ( 4.00 - ( 3.00 * 7.00 ) ) )
*/

Read More +

Oct 12 2014

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

ZJOI 2012 DAY2 灾难

Problem

阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：
一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。
这个图没有环。
图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存；而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了，它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。
举个例子：在一个草场上，生物之间的关系是：

如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以，草的灾难值是4。
给定一个食物网，你要求出每个生物的灾难值。

Input

第一行是一个正整数N，表示生物的种数。生物从1标号到N。
接下来N行，每行描述了一个生物可以吃的其他生物的列表，格式为用空格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是0表示列表的结束。

Output

包含N行，每行一个整数，表示每个生物的灾难值。

Sample Input

Sample Output

Solution

解法參照網路各位大神，效率為 O(E log V)，必須為 DAG 圖。

题目大意 ：给你一个有向可拓扑图，入度为零的点成为源点，然后考虑每一个点，假若删掉了他以及对应的边，那么除他外有多少个点不可达源点。

算法：按拓扑序遍历N个点，将距每个点最近的必须通过的点设为它的父亲，构造出一棵树。对于每个点，若向它连边的点只有一个，其父亲就是向它连边的点；若向它连边的点不只一个，其父亲是向它连边的所有点的最近公共祖先。删掉每个点后不可达点个数就是其子树的节点个数。

wzj_123wzjoier.blog.163.com/blog/…

這個做法接近貪婪思路，建造一個瓶頸樹，建造的過程找到最鄰近的瓶頸，而瓶頸的找法根據 LCA 完成。

建造完，利用 dfs 計算子樹大小，發生 stackoverflow，系統恰好沒有抓到，改用 bfs 計算就 A 過。

#include <stdio.h> 
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
// http://oi.nks.edu.cn/showproblem?problem_id=2646 
#define MAXN 65536
#define LOGMAXN 17
vector<int> g[MAXN], invg[MAXN], tree[MAXN];
int indeg[MAXN] = {};
vector<int> toposort(vector<int> g[], int n) {
	vector<int> ret;
	queue<int> Q;
	int u, v;
	for (int i = 0; i <= n; i++)
		indeg[i] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < g[i].size(); j++)
			indeg[g[i][j]]++;
	}
	for (int i = 1; i <= n; i++) {
		if (indeg[i] == 0)
			Q.push(i);
	}
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		ret.push_back(u);
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			if (--indeg[v] == 0)
				Q.push(v);
		}
	}
	return ret;
}
int depth[MAXN], parent[MAXN][LOGMAXN];
int getLCA(int x, int y) {
	int dist, i;
	if (depth[x] < depth[y])	swap(x, y);
	dist = depth[x] - depth[y];
	for (int i = 0; dist; i++, dist /= 2) {
		if (dist&1)	x = parent[x][i];
	}
	for (i = 0; x != y;) {
		if (parent[x][i] != parent[y][i] || (i == 0 && parent[x][i] == parent[y][i])) {
			x = parent[x][i];
			y = parent[y][i];
			i++;
		} else {
			i--;
		}
	}
	return x;
}
void buildTree(vector<int> &topo, vector<int> g[], int n) {
	for (int i = 1; i <= n; i++)
		tree[i].clear();
	int u, v;
	parent[0][0] = -1, depth[0] = 0;
	for (int i = 0; i < topo.size(); i++) {
		u = topo[i];
		if (g[u].size() == 0) {
			depth[u] = 1, parent[u][0] = 0;
			continue;
		}
		int lca = g[u][0];
		for (int j = 0; j < g[u].size(); j++)
			v = g[u][j], lca = getLCA(lca, v);
		depth[u] = depth[lca] + 1;
		parent[u][0] = lca;
		tree[lca].push_back(u);
		for (int i = 0; parent[u][i]; i++) {
			parent[u][i+1] = parent[parent[u][i]][i];
		}
	}
}
int used[MAXN], subtree[MAXN];
void sumTree(int n) {
	queue<int> Q;
	int u, v;
	for (int i = 1; i <= n; i++) {
		subtree[i] = 1;
		indeg[i] = tree[i].size();
		if (tree[i].size() == 0)	Q.push(i);
	}
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		v = parent[u][0];
		indeg[v]--;
		subtree[v] += subtree[u];
		if (indeg[v] == 0)
			Q.push(v);
	}
}
int main() {	
	int n, x, y, u, v;
	while(scanf("%d", &n) == 1) {
		for (int i = 0; i <= n; i++)
			g[i].clear(), invg[i].clear();
		for (int i = 1; i <= n; i++) {
			while (scanf("%d", &x) == 1 && x) {
				g[i].push_back(x);
				invg[x].push_back(i);
			}
		}
		vector<int> topo = toposort(invg, n);
		buildTree(topo, g, n);
		sumTree(n);
		for (int i = 1; i <= n; i++)
			printf("%d\n", subtree[i] - 1);
	}
	return 0;
}

Read More +

Oct 12 2014

解題區►解題區 - UVa

UVa 1629 - Cake slicing

Problem

切割長方形蛋糕，使得每一塊上恰好有一個莓果，每一次切割的花費即線長，求最小花費。

Sample Input

Sample Output

Case 1: 5

Solution

利用 DP 精神，考慮每一個地方都去切割，定義 dp[x][y][w][h] 為左上角座標 (x, y)，其長寬 (w, h) 的長方形蛋糕的最小花費。

沒有辦法對於連續空白之間只取一次切割，如果只切一次縱切的，切著左右兩側的橫切個數將會影響很大，所以每個位置都要嘗試。

#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
int N, M, K;
int g[32][32], sum[32][32];
int dp[32][32][32][32], used[32][32][32][32], testcase = 0;
int getArea(int x, int y, int w, int h) {
	return sum[x + w-1][y + h-1] - sum[x-1][y + h-1] - sum[x + w-1][y-1] + sum[x-1][y-1];
}
int dfs(int x, int y, int w, int h) {
	if (used[x][y][w][h] == testcase)
		return dp[x][y][w][h];
	if (getArea(x, y, w, h) < 2)
		return 0;
	used[x][y][w][h] = testcase;
	int &ret = dp[x][y][w][h];
	ret = 0x3f3f3f3f;
	for (int i = 1; i < w; i++) {
		if (getArea(x, y, i, h) > 0 && getArea(x+i, y, w-i, h) > 0)
			ret = min(ret, dfs(x, y, i, h) + dfs(x+i, y, w-i, h) + h);
	}
	for (int i = 1; i < h; i++) {
		if (getArea(x, y, w, i) > 0 && getArea(x, y+i, w, h-i) > 0)
			ret = min(ret, dfs(x, y, w, i) + dfs(x, y+i, w, h-i) + w);
	}
	return ret;
}
int main() {
	while (scanf("%d %d %d", &N, &M, &K) == 3) {
		memset(g, 0, sizeof(g));
		memset(sum, 0, sizeof(sum));
		int x, y;
		for (int i = 0; i < K; i++) {
			scanf("%d %d", &x, &y);
			g[x][y]++;
		}
		for (int i = 1; i <= N; i++) {
			int x = 0;
			for (int j = 1; j <= M; j++) {
				x += g[i][j];
				sum[i][j] = sum[i-1][j] + x;
			}
		}
		testcase++;
		printf("Case %d: %d\n", testcase, dfs(1, 1, N, M));
	}
	return 0;
}

Read More +

Problem

Input

Output

Sample Input

Sample Output

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution 1

Solution 2

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

Problem

Input

Output

Sample Input

Sample Output

hint

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Input

Output

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：