2014-12-05

UVa 12871 - Landmine Cleaner

Problem

給予每一個格子的得分，分數為鄰近九格的 L 個數 (1 個 1 分) 加上自己是否為 L (3 分)，因此最低 0 分，最高 12 分。

保證只有唯一解。

Sample Input

Sample Output

1
2
3

-L--
L-LL
LL--

Solution

不斷地刷新已知的可能結果，慢慢從邊緣開始向內侵蝕已知解。

要做整數線性規劃看來是不可能，用刷新的方式看看是否可以噴出解。

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 1024
int A[MAXN][MAXN], solv[MAXN][MAXN];
int g[MAXN][MAXN];
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
int n, m;
int isplace(int x, int y) {
    int v = A[x][y], tx, ty;
    int unknown = 0, score = 0;
    for (int i = 0; i < 8; i++) {
        tx = x + dx[i], ty = y + dy[i];
        if (tx < 0 || ty < 0 || tx >= n || ty >= m)
            continue;
        if (solv[tx][ty])	score += g[tx][ty];
        else				unknown++;
    }
    if (v < 3)					return -1;
    if (v > 8)					return 1;
    if (score + unknown < v)	return 1;
    if (score + 4 > v)			return -1;
    return 0; // not sure.
}
int main() {
    int testcase;
    int t;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &A[i][j]);
            }
        }
        memset(solv, 0, sizeof(solv));
        int test = n * m;
        while (test) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (solv[i][j])	continue;
                    int t = isplace(i, j);
                    if (t) {
                        test--;
                        g[i][j] = t > 0;
                        solv[i][j] = 1;
                    }
                }
            }
            
        }
        for (int i = 0; i < n; i++, puts("")) {
            for (int j = 0; j < m; j++) {
                if (solv[i][j])
                    putchar(g[i][j] ? 'L' : '-');
                else {
                    assert(false);
                }
            }
        }
    }
    return 0;
}
/*
9999
3 4
2 6 3 2
7 5 7 5
6 7 3 2
3 3
7 9 7
9 12 9
7 9 7
3 1
0
0
0
*/

Read More +

2014-12-05

解題區/解題區 - UVa

UVa 12431 - Happy 10/9 Day

Problem

計算 base B 下，每一個 digit 都是 d 的情況，長度為 N，mod M 的結果為何？

Sample Input

1 2	1 3 10 2 10

Sample Output

Case 1: 2

Solution

找到

$$d B^{0} + d B^{1} + ... + d B^{N-1} \text{ mod } M \\ \Rightarrow d \frac{B - 1}{B^{N} - 1} \text{ mod } M$$

由於 M 超過 int，運算起來仍有機會 overflow，因此要使用模乘法，也就是相當於直式乘法的運算，防止 (a*b) mod M 溢位。

#include <stdio.h> 
long long mul(long long a, long long b, long long mod) { 
    long long ret = 0; 
    for( ; b != 0; b>>=1, (a<<=1)%=mod) 
        if(b&1) (ret += a) %= mod; 
    return ret; 
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = mul(ret, x, mod);
        y >>= 1, x = mul(x, x, mod);
    }
    return ret;
}
long long solve(long long n, long long b, long long d, long long m) {
    // d * (b^n - 1) / (b - 1) mod m
    long long ret;
    ret = mpow(b, n, (b - 1) * m); // b^n mod (b-1) * m
    ret = (ret + (b - 1) * m - 1)/ (b - 1);
    ret = mul(ret, d, m);
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n, b, d, m, ret;
        scanf("%lld %lld %lld %lld", &n, &b, &d, &m);
        ret = solve(n, b, d, m);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}

Read More +

2014-12-05

解題區/解題區 - UVa

UVa 12425 - Best Friend

Problem

給一個整數 N，接著詢問 x，有多少 gcd(i, N) <= x。

Sample Input

Sample Output

Case 1
8
16
28
Case 2
10
10

Solution

先把 N 的因數 f 全部找出，原則上不超過 2000 個，然後建出 phi(N/f[i])。

當要知道 gcd(i, N) = x 時，相當於找到 gcd(i/x, N/x) = 1，任何與 N/x 互質的個數。建造完後，對於每次詢問二分答案即可。

很多地方忘記用 long long，吃了不少 Runtime error。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define maxL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[100000], Pt = 0;
int phi[1048576];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for (i = 1; i <= n; i++)
    	phi[i] = i;
    for (i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            for (j = i; j <= n; j += i)
            	phi[j] = phi[j]/i * (i-1);
            P[Pt++] = i;
        }
    }
}
vector< pair<long long, int> > factor(long long n) {
    long long on = n;
    vector< pair<long long, int> > R;
    
    for(int i = 0, j; i < Pt && (long long)P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {		
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair((long long)P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, long long m, vector< pair<long long, int> > &v, vector<long long> &ret) {
    if(idx == v.size()) {
        ret.push_back(m);
        return;
    }
    long long a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v, ret), a *= b;
}
long long getPhi(long long n) {
    if (n < 1000000)	return phi[n];
    vector< pair<long long, int> > f = factor(n);
    for (int i = 0; i < f.size(); i++)
        n = n / f[i].first * (f[i].first - 1);
    return n;
}
int main() {
    sieve();
    int testcase, cases = 0, Q;
    long long N, X;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %d", &N, &Q);
        vector< pair<long long, int> > f = factor(N);
        vector<long long> fa;
        vector<long long> sum;
        make(0, N, 1, f, fa);
        sum.resize(fa.size(), 0);
        sort(fa.begin(), fa.end());
        for (int i = 0; i < fa.size(); i++) {
            if (i)
                sum[i] = sum[i-1] + getPhi(N / fa[i]);
            else
                sum[i] = getPhi(N / fa[i]);
        }
        printf("Case %d\n", ++cases);
        for (int i = 0; i < Q; i++) {
            scanf("%lld", &X);
            if (X <= 0) {
                puts("0");
                continue;
            }
            long long ret = 0;
            int pos = (int)(lower_bound(fa.begin(), fa.end(), X) - fa.begin());
            if (pos >= fa.size() || fa[pos] > X)	pos--;
            ret = sum[pos];
            printf("%lld\n", ret);
        }
    }
    return 0;
}
/*
2
30 3
1
2
10
11 5
0
1
2
11
15
*/

Read More +

2014-12-05

解題區/解題區 - UVa

UVa 12404 - Trapezium Drawing

Problem

給予梯形兩點座標、四個邊長。找到另外兩點座標。

Sample Input

1 2	1 0 0 20 0 10 14 8

Sample Output

1 2	Case 1: 14.00000000 8.00000000 0.00000000 8.00000000

Solution

向量旋轉找解。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
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);
    }
    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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.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;
}
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);
}
double solve(double a, double b, double c, double d) {
    // d^2 - x^2 = b^2 - (a - x - c)^2
    // d^2 - x^2 = b^2 - (a-c - x)^2
    // d^2 - x^2 = b^2 - ((a-c)^2 - 2(a-c)x + x^2)
    // d^2 - x^2 = b^2 - (a-c)^2 + 2(a-c)x - x^2
    // d^2 - b^2 + (a-c)^2 = 2(a-c)x
    double x;
    x = (pow(d, 2) - pow(b, 2) + pow(a-c, 2))/(2 * (a-c));
    return x;
}
int main() {
    int testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        Pt A, B, C, D;
        double a, b, c, d;
        scanf("%lf %lf", &x, &y);
        A = Pt(x, y);
        scanf("%lf %lf", &x, &y);
        B = Pt(x, y);
        scanf("%lf %lf %lf", &b, &c, &d);
        a = dist(A, B);
        x = solve(a, b, c, d);
        
        Pt vAB = (B - A) / a;
        double theta = atan2(sqrt(d*d - x*x), x);
        D = rotateRadian(vAB, theta) * d + A;
        C = D + vAB * c;
        printf("Case %d:\n", ++cases);
        printf("%.8lf %.8lf %.8lf %.8lf\n", C.x, C.y, D.x, D.y);
    }
    return 0;
}
/*
1
0 0 20 0 10 14 8
8
0 0 20 0 10 14 8
0 0 20 0 8 14 10
20 0 0 0 10 14 8
20 0 0 0 8 14 10
8 0 8 20 10 14 8
8 0 8 20 8 14 10
0 20 0 0 10 14 8
0 20 0 0 8 14 10
*/

Read More +

2014-12-05

解題區/解題區 - UVa

UVa 10397 - Connect the Campus

Problem

在現有的鋪設下，還有幾處建築物之間沒有連通。

找到花費最小的歐基里德距離生成樹

Sample Input

Sample Output

1
2

4.41
4.41

Solution

直接用 kruskal 就可以完成，但是建造邊最慘將會達到 O(n^2)，因此效率並不好，好幾年之後回過頭來寫這一題。

對於 EMST 可以使用 Delaunay triangulation 完成。Delaunay triangulation 原則上可以在 O(n log n) 時間內完成。由於 EMST 是 Delaunay 的 subgraph，而 Delaunay 保證 edge 數最多為 3n - 6。套用 kruskal 的 O(E log E) 算法就能保證在 O(n log n) 時間內完成。

Delaunay triangulation 目前實作有 D&C 和 random 兩種。

計算幾何資料請參照 morris821028/Computational-Geometry 下載。

廣泛的比較下，兩者期望都在 O(n log n) 完成，而實際結果 D&C 普遍速度快很多。random 作法很吃機率期望，原因是要支持動態的 point location 操作，沒有一個好的資料結構來保證每一步的搜索效率，教科書上給予一個類似可持久化結構的 DG structure，深度是期望的 O(log n)，實作起來只會比 O(n) 快個常數倍。但 random increase algorithm 對於演算法的證明的確是比較容易，而且步驟相當好說明。

當效率不好去學 D&C algorithm，一開始要對座標進行排序，也就是不支持動態 (離線操作)，接著針對 x 座標剖半，兩個完成 Delaunay triangulation 的凸包進行合併，接著需要將中間縫隙穿針引線地縫起來。因此要找到兩個凸包的下公切線，然後開始攀爬上去，保證一開始的下公切線一定是 Delaunay edge，然後開始窮舉下一個 Delaunay edge，過程中也不斷地移除不適的邊。

有相當不錯的資料結構可以快速地搜索公切線、圍繞凸包的頂點 … 等，但是根據教科書給予的計算，每一個點的 degree 期望值不超過 9，意即偷偷地窮舉攀爬不影響效率。

關於三點共圓，詢問一點是否在圓內的操作，投影到拋物面上，三點在投影結果上拉出一個平面，若點在圓內，則保證該點在平面的下方。求出外心計算，會造成誤差 (無法儲存除法運算結果)，換成拋物面的思路魯棒性高。

下附 D&C algorithm 的做法，關於 random 就放在 github repo 封存了。

#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 1024
struct Point {
    double x, y;
    int id;
    Point(double a = 0, double b = 0, int c = -1):
    	x(a), y(b), id(c) {}	
    Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y);
    }
    Point operator+(const Point &a) const {
        return Point(x + a.x, y + a.y);
    }
    Point operator*(const double a) const {
        return Point(x * a, y * a);
    }
    Point operator/(const double a) const {
        return Point(x / a, y / a);
    }
    bool operator<(const Point &a) const {
        if (fabs(x - a.x) > eps)	return x < a.x;
        if (fabs(y - a.y) > eps)	return y < a.y;
        return false;
    }
    bool operator==(const Point &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Point &a) const {
        return !(fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    } 
    void read(int id = -1) {
        this->id = id;
    }
    double dist(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    double dist2(Point b) {
        return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
    }
    void print() {
        printf("point (%lf, %lf)\n", x, y);
    }
};
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
        x(a), y(b), z(c) {}
    Point3D(Point p) {
        x = p.x, y = p.y, z = p.x * p.x + p.y * p.y;
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    double dot(Point3D a) {
    	return x * a.x + y * a.y + z * a.z;
    }
};
struct Edge {
    int id;
    list<Edge>::iterator twin;
    Edge(int id = 0) {
        this->id = id;
    }
};
int cmpZero(double v) {
    if (fabs(v) > eps)	return v > 0 ? 1 : -1;
    return 0;
}
double cross(Point o, Point a, Point b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
Point3D cross(Point3D a, Point3D b) { // normal vector
    return Point3D(a.y * b.z - a.z * b.y 
                 , -a.x * b.z + a.z * b.x
                 , a.x * b.y - a.y * b.x);
}
int inCircle(Point a, Point b, Point c, Point p) {
    if (cross(a, b, c) < 0)
        swap(b, c);
    Point3D a3(a), b3(b), c3(c), p3(p);
//	printf("%lf %lf %lf\n", a3.x, a3.y, a3.z);
//	printf("%lf %lf %lf\n", b3.x, b3.y, b3.z);
//	printf("%lf %lf %lf\n", c3.x, c3.y, c3.z);
//	printf("%lf %lf %lf\n", p3.x, p3.y, p3.z);
    b3 = b3 - a3, c3 = c3 - a3, p3 = p3 - a3;
    Point3D f = cross(b3, c3); // normal vector
    return cmpZero(p3.dot(f)); // check same direction, in: < 0, on: = 0, out: > 0
}
int intersection(Point a, Point b, Point c, Point d) { // seg(a, b) and seg(c, d)
    return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0 
        && cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
class Delaunay {
    public:
    list<Edge> head[MAXV]; // graph
    Point p[MAXV];
    int n, rename[MAXV];
    void init(int n, Point p[]) {
        for (int i = 0; i < n; i++)
            head[i].clear();
        for (int i = 0; i < n; i++)
            this->p[i] = p[i];
        sort(this->p, this->p + n);
        for (int i = 0; i < n; i++)
            rename[p[i].id] = i;
        this->n = n;
        divide(0, n - 1);
    }
    void addEdge(int u, int v) {
        head[u].push_front(Edge(v));
        head[v].push_front(Edge(u));
        head[u].begin()->twin = head[v].begin();
        head[v].begin()->twin = head[u].begin();
    }
    void divide(int l, int r) {
        if (r - l <= 1) { // #point <= 2
            for (int i = l; i <= r; i++)
                for (int j = i+1; j <= r; j++)
                    addEdge(i, j); 
            return;
        }
        int mid = (l + r) /2;
        divide(l, mid);
        divide(mid + 1, r);
        
        list<Edge>::iterator it;
        int nowl = l, nowr = r;
        
//		printf("divide %d %d\n", l, r);
        for (int update = 1; update; ) { // find left and right convex, lower common tangent
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptR, ptL, t);
                if (cmpZero(v) > 0 || (cmpZero(v) == 0 && ptR.dist2(t) < ptR.dist2(ptL))) {
                    nowl = it->id, update = 1;
                    break;
                }
            }
            if (update)	continue;
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptL, ptR, t);
                if (cmpZero(v) < 0 || (cmpZero(v) == 0 && ptL.dist2(t) < ptL.dist2(ptR))) {
                    nowr = it->id, update = 1;
                    break;
                }
            }
        }
        
        addEdge(nowl, nowr); // add tangent
//		printf("add base %d %d\n", nowl, nowr);
        for (int update = 1; true;) {
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            int ch = -1, side = 0;
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
//				ptL.print(), ptR.print(), p[it->id].print();
                if (cmpZero(cross(ptL, ptR, p[it->id])) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = -1;
//				printf("test L %d %d %d\n", nowl, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                if (cmpZero(cross(ptR, p[it->id], ptL)) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = 1;
//				printf("test R %d %d %d\n", nowr, it->id, inCircle(ptL, ptR, p[ch], p[it->id])); 
            }
            if (ch == -1)	break; // upper common tangent
//			printf("choose %d %d\n", ch, side);
            if (side == -1) {
                for (it = head[nowl].begin(); it != head[nowl].end(); ) {
                    if (intersection(ptL, p[it->id], ptR, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowl].erase(it++);
                    } else
                        it++;
                }
                nowl = ch;
                addEdge(nowl, nowr);
            } else {
                for (it = head[nowr].begin(); it != head[nowr].end(); ) {
                    if (intersection(ptR, p[it->id], ptL, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowr].erase(it++);
                    } else
                        it++;
                }
                nowr = ch;
                addEdge(nowl, nowr);
            }
        }
    }
    
    vector< pair<int, int> > getEdge() {
        vector< pair<int, int> > ret;
        list<Edge>::iterator it;
        for (int i = 0; i < n; i++) {
            for (it = head[i].begin(); it != head[i].end(); it++) {
                if (it->id < i)
                    continue;
//				printf("DG %d %d\n", i, it->id);
                ret.push_back(make_pair(p[i].id, p[it->id].id));
            }
        }
        return ret;
    }
} tool;
struct edge {
    int x, y, v;
    edge(int a = 0, int b = 0, int c = 0):
        x(a), y(b), v(c) {}
    bool operator<(const edge &a) const {
        return v < a.v;
    }
};
int parent[1024], weight[1024];
void init(int n) {
    for(int i= 0; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
int findp(int x) {
    return x == parent[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;
}
int main() {
    int n, m, cases = 0;
    Point p[MAXV];
    while (scanf("%d", &n) == 1) {
        init(n);
        int x, y;
        int e = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            p[i] = Point(x, y, i);
        }
        
        tool.init(n, p);
            
        vector<edge> E;
        vector< pair<int, int> > DG = tool.getEdge();
        for (int i = 0; i < DG.size(); i++) {
            x = DG[i].first, y = DG[i].second;
            int v = (p[x].x - p[y].x) * (p[x].x - p[y].x) + 
                        (p[x].y - p[y].y) * (p[x].y - p[y].y);
            E.push_back(edge(x, y, v));
//			printf("DG %d %d %d\n", x, y, v);
        }
        
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            e += joint(x, y);
        }
        
        sort(E.begin(), E.end());
        double ret = 0;
        for (int i = 0; i < E.size(); i++) {
            x = E[i].x, y = E[i].y;
            if (joint(x, y)) {
                ret += sqrt(E[i].v);
                e++;
                if (e == n - 1)
                    break;
            }
        }
        printf("%.2lf\n", ret);
    }
    return 0;
}
/*
2
1 1
2 2
0
1
1 1
0
4
103 104
104 100
104 103
100 100
1
4 2
4
3 4
4 0
4 3
0 0
1
4 2
*/

Read More +

2014-12-02

學校課程/通識課程

[通識] 文明的進程小組報告

主題

跨國的文明競逐與衝突－原住民的文化問題

報告核心－文明的傲慢

「原住民」稱呼為何而來？

誠心臣服在我太陽帝國之下

正因為我們是侵略者！他們才是 真‧台灣人 。

AcFun 線上看－《賽德克巴萊》

在評論中大陸人這麼說

「為什麼他們不說國語？」
「一隻豬發生的血案？」
「他們才是真台灣人啊。」

都已經被我們給文明化了

要求弱勢族群做出相同的行為－那就是一種傲慢。

文化差異

漢人文化需要競爭，做任何事情都需要競爭，而原住民只要在工作上能夠溫飽就能快樂過活，藉由唱歌舞蹈等表現方式來闡述他們的快樂，及時行樂整是他們的天性，說他們懶惰不上進才是我們的傲慢。相較於競爭，他們是互助合作的生命共同體，在那種生存環境下，農耕、狩獵都要互相幫忙，你說競爭下的快樂帶給多少回饋？

把我的尊嚴還給我！

如何表現自己的英勇事蹟？奮勇殺敵、狩獵得到的骸骨作為一個能力階層。即使如此，敬老尊賢是重要的文化，年齡階層而非能力階層。做為一個活在漢人社會的人而言，能力若決定一生，而談快樂？雖然能力不如人，難道就培養不出比自己厲害的人？也許虎媽就是這麼來的。

還敢帶刀 ... 混蛋！

佩刀難道錯了嗎？佩刀是因為生活所需，也是我們地位的象徵。憑什麼要求不能帶刀，那你們帶刀又是什麼意思，相比中古世紀騎士可以制裁的對象，低層社會人們只能對自己以下的對象進行攻擊。

融入現代社會

第一階段－原住民成年人
從成年人開始步入社會，雖然一開始會接受很殘酷的生活適應，還必須使用漢姓，論名字對自尊的重要性，即使謀求到工作，並且逐漸適應生活所需。(有多少人能失去自己的名字？)
第二階段－孩子教育
由於長時間活在漢人社會，孩子學習也就必須上小學，然而文化的成長背景不同下，做為父母能教導什麼給孩子？就因為環境不同，知識理解的差異所引來歧視，難道就是錯的嗎？
第三階段－傳統繼承
村落沒有新血、沒有傳承，不就是鼓勵他們進入漢人社會的原因嗎？

什麼樣背景的人用什麼方式學，不是比較好理解嗎？學習成績不好沒什麼好擔心，只是規格面向不同。不懂不是問題，只是要換的方式。

保有精神

也改變不了這張不被文明認同的臉

我們的信仰、精神，藉由血緣牽連在一起。

巴萬，你的獵場在哪裡？

矛盾所在

用很多補償條款鼓勵原住民進入我們漢人社會，但又希望他們保有他們自己的文化？

鼓勵改變，但卻又希望不變？(你們這群人到底想怎樣！)

武力較強的文明使得我們成功掠奪這塊土地，而這種文明真的是文明嗎？難道不就是個野蠻人？
想想印地安原住民的文化，真的是所謂低於來自被歐洲驅逐的人們所擁有的嗎？
如果你們所說小七是文明的象徵？想要成為你們所說的文明文化有錯嗎？

反問小朋友：「沒有漢堡和薯條，你們都吃什麼？」小朋友答說，就吃海裡抓的九孔和龍蝦。

蘭嶼小孩要吃薯條www.chinatimes.com/newspapers/20140721000704-260109

文章中見到蘭嶼小孩吃山珍海味，那豈不是反了？依照生活的飲食水準，到底是誰過得奢侈？

世界原住民

當年英國統治的殖民地眾多，要不是他們可以退回祖國，那群人也是相當龐大的原住民。然而我們仗著人數眾多，無法退出的處境，厚臉皮地活在這片土地。不是中國對待少數民族的方式，他們在同一個文化脈絡下分支成長，即使不能理解，也能知道自己是同一脈人，已經磨得相當長久的時間。

縱使看著別國對待本國原住民的方式，例如：規劃保護區、歸還土地… 等，同時也表明了曾經使用過的暴力，他們的處境與我們台灣不同，他們有原本的家可以回，而我們必須對抗其他國家的勢力，必須與原住民站在同一條船上，也許對待他們的方式相比別國來說殘酷，一旦我們的立場被別國 (如中國，他們又會怎麼對待原住民？) 取代，那到底是誰殘酷？

被消費的文化

文明化造就觀光行為

觀光是大多數人的娛樂，也因此造就服務業的產生。談談服務業與文明化的關係

這個新的公民身分的尊貴性，首先意味著華人社會本來以長幼輩分及遠近
親疏為基礎的傳統人際關係階序必須被鬆動，好讓尊貴的自豪自信得以越過這
些差異位置所包含的舉止規範和情感限制，而成為所有主體都可以近用的現代
情感特質。在這方面，第一個重要的結構性發展就是台灣產業結構劇變後的服
務業人際互動模式，以及隨之在日常生活中不斷重複的互動消費實踐，它們都
使得新規訓不再只是外加的強制和要求，而得以徹底融入主體的生活活動與內
在自我情感。

情感嬌貴化：變化中的台灣性佈局sex.ncu.edu.tw/members/Ho/paper/20120620%20%E4%B8%8A%E5%A4%A7%E6%96%87%E5%8C%96%E7%A0%94%E7%A9%B6%EF%BC%8D%E6%83%85%E6%84%9F%E5%AC%8C%E8%B2%B4%E5%8C%96%EF%BC%88%E7%B9%81%EF%BC%89.pdf

這深入探討可能要問一下何春蕤老師，總之身處服務業的情感，肯定是原住民們所無法理解的，一開始覺得他們好客，不知不覺地商業化他們，直到他們的好心被利用，才逐漸地被厭惡。

反思

當我們對外說出「我們台灣人」到底是指那些人？是活在這片土地上的所有人？那接下來的話就是共同意識嗎？正因為要對外證明我們是個國，才急切地想要讓所有活在這片土地上的人，至少有一個共同意志？

我們用更殘酷的方式生存，剝奪那些活在幕後的人的生存條件與資源，真的有比原住民文明嗎？追求文明結果，竟是雙面刃？

探討

在各國文化的核心目標不同時，它們對待原住民的方式也有所不同，到底是給予相同地位？還是給予空間適性發展？我想這牽涉到－到底有沒有必要活在「社會」牢籠，他們明明不用看處在強勢文化人們的臉色，自給自足活得很好，為何他們要踏入我們的文化？

也許以前原住民的人數與文化有關係，為了生存不得不離開原本的文化，背負著必須學習更多文化知識的壓力。這種不對稱的學習，真的造就我們欺壓原住民了嗎？

文化模式與人口承載量

造成必要的出走的主因。根據人口普查統計，至今原住民已經從日治時代的七萬多人暴增到五十多萬人，它們的生活習性支撐這麼多人嗎？

看待偏見

偏見有時也是一種讚美 。即使是你所認為不文明的舉動，不就是正因為做了你做不到的事情？

文化分工

唱歌、表演真的是唯一生存之道？原住民未來若要發展特色，難道唱歌表演就是唯一了嗎？在很多原住民歌手的興起下，就只能朝著同一個方向嗎？

學校教育

窮鄉僻壤的村落，書上這麼多內容壓根沒見過，為何而學？遵守什麼規矩？

補償條例

一個跨世代的心態，但要知道強勢文化下也有弱勢成員，而生存的價值是因為他們的需求而存在，有時給予環境正表示處於文明的鑑賞期。

生活教育

生活就是最好的教育，有人走得出去，也一定會有人走不出去，為了部落而走的民族精神？

器具演進

從人工到電動－難道有人畫畫一開始就學電繪嗎？沒什麼大驚小怪的，會電腦打字就不會寫字了嗎？

Read More +

2014-12-02

解題區/解題區 - UVa

UVa 1674 - Lightning Energy Report

Problem

給一棵樹，接著有數次操作將路徑 (u, v) 上的所有節點權重加上 k。

請問最後每一個點帶有的權重為何？

Sample Input

Sample Output

Solution

參照 zerojudge b322. 樹形鎖頭的解法。

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;
#define MAXV 65536
int visited[MAXV];
vector<int> tree[MAXV];
int parent[MAXV], weight[MAXV];
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[MAXV];// 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;
    int testcase, cases = 0;
    int X[MAXV], Y[MAXV], K[MAXV];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        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[MAXV] = {}, extra[MAXV] = {};
        for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
        scanf("%d", &m);
        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);
        
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < n; i++)
            printf("%d\n", weight[i] + extra[i]);
    }
    return 0;
}

Read More +

2014-12-02

解題區/解題區 - UVa

UVa 1659 - Help Little Laura

Problem

平面上有 N 個點，並且給定數條有向邊，在這個遊戲中，必須從某個點出發，沿著邊回到起點。每一條邊最多經過一次，而點可以重複走。

每經過一條邊，可以獲益每單位長 X 的利益，但是使用一條邊的成本為 Y。

請問最大獲益為何？

Sample Input

4 5 1 
0 0 2 3 0 
1 0 3 4 0 
1 1 4 0 
0 1 1 0 
1 2 1 
0 0 0 
10 7 2 
0 0 2 4 0 
5 0 3 0 
5 10 4 10 0 
2 3 5 0 
7 5 6 0 
0 11 1 0 
8 0 10 5 0 
18 3 7 0 
14 5 8 1 0 
12 9 9 0 
0

Sample Output

1
2
3

Case 1: 16.00 
Case 2: 0.00 
Case 3: 522.18

Solution

目標將每一個點調整 indeg = outdeg，要將多餘的邊捨去，只要滿足 indeg = outdeg，則可以表示平面上有數個尤拉環道。

接著建造最少費用流的模型，來捨去掉多餘的邊。當存有邊 e(i->j) 時，outdeg[i]++, indeg[j]++，一開始選擇所有 cost(e(i->j)) > 0 的邊，作為初始盤面，對於 cost(e(i->j)) < 0 先不選，選擇獲益為負的結果並不好。

如果 cost(e(i->j)) > 0，建造邊 i->j, flow: 1, cost: cost(e(i->j))，假使在最少費用流中選擇這一條邊時，就會將 deg 數量減少。對於 cost(e(i->j)) < 0 一開始並沒有在盤面上，如果流經這一條邊，則說明將會增加這一條邊。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[1000005];
int e, head[600], prev[600], record[600], inq[600];
double dis[600];
void addEdge(int x, int y, int cap, double 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++;
}
double mincost(int s, int t, int n) {
    double mncost = 0;
    int flow, totflow = 0;
    int i, x, y;
    double oo = 1e+30;
    while(1) {
    	for (int i = 0; i <= n; i++)
    		dis[i] = oo;
        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;
                    prev[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 = 0x3f3f3f3f;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[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 mncost;
}
int main() {
    int cases = 0;
    int N, X, Y;
    int x[128], y[128], u;
    while (scanf("%d %d %d", &N, &X, &Y) == 3 && N) {
    	vector<int> g[128];
    	for (int i = 1; i <= N; i++) {
    		scanf("%d %d", &x[i], &y[i]);
    		while (scanf("%d", &u) == 1 && u)
    			g[i].push_back(u);
        } 
        
    	e = 0;
        memset(head, -1, sizeof(head));	
        int deg[128] = {};
        double sumCost = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < g[i].size(); j++) {
                u = g[i][j];
                double d = hypot(x[i] - x[u], y[i] - y[u]);
                double cost = d * X - Y;
                if (cost < 0) {
                    addEdge(u, i, 1, -cost);
                } else {
                    sumCost += cost;
                    addEdge(i, u, 1, cost);
                    deg[u]--, deg[i]++;
                }
            }
        }
        int source = 0, sink = N + 1;
        for (int i = 1; i <= N; i++) {
            if (deg[i] > 0)	addEdge(source, i, deg[i], 0);
            if (deg[i] < 0)	addEdge(i, sink, -deg[i], 0);
        }
        double mncost = mincost(source, sink, N+1);
        printf("Case %d: %.2lf\n", ++cases, sumCost - mncost + eps);
    }
    return 0;
}
/*
4 5 1 
0 0 2 3 0 
1 0 3 4 0 
1 1 4 0 
0 1 1 0 
1 2 1 
0 0 0 
10 7 2 
0 0 2 4 0 
5 0 3 0 
5 10 4 10 0 
2 3 5 0 
7 5 6 0 
0 11 1 0 
8 0 10 5 0 
18 3 7 0 
14 5 8 1 0 
12 9 9 0 
0
*/

Read More +

2014-12-02

解題區/解題區 - UVa

UVa 1649 - Binomial coefficients

Problem

組合的反函數，現在給定組合數，輸出是由哪幾種組合可以配出組合數。

Sample Input

1
2
3

2
2
15

Sample Output

1
(2,1)
4
(6,2) (6,4) (15,1) (15,14)

Solution

先預見表，完成前幾項的結果。

看著巴斯卡三角形單純看 i，對於 C(n, i) 是一個嚴格遞增的函數。因此窮舉 i，針對組合數進行二分搜索。

為防止越界，在整數計算上可以利用除法進行比大小。

#include <stdio.h>
#include <map> 
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1024
const long long MAXVAL = 1e+16, MAXVAL2 = 1e+15;
long long C[MAXN][MAXN] = {};
map<long long, vector< pair<long long, long long> > > R;
int testCombination(long long n, long long m, long long Cnm) { // test C(n, m), m < 10
    long long ret = 1;
    m = min(m, n-m);
    for (long long i = 1; i <= m; i++) {
        if (Cnm * i / (n + 1 - i) / ret  < 1)
            return 1;
        ret = ret * (n + 1 - i) / i;
    }
    return ret == Cnm ? 0 : -1;
}
vector< pair<long long, long long> > invCombination(long long n) {
    vector< pair<long long, long long> > ret;
    ret = R[n];
    for (int i = 1; i < 10; i++) {
        long long l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r)/2;
            int f = testCombination(mid, i, n); // {-1, 0, 1}
            if (f == 0) {
                ret.push_back(make_pair(mid, i));
                ret.push_back(make_pair(mid, mid - i));
                break;
            }
            if (f < 0)
                l = mid + 1;
            else
                r = mid - 1;
        }
    }
    sort(ret.begin(), ret.end());
    ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
    return ret;
}
int main() {
//	printf("%d\n", testCombination(5000, 2, 12497500));
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] = min(C[i][j], MAXVAL);
            if (j != i && C[i][j] <= MAXVAL2)
                R[C[i][j]].push_back(make_pair(i, j));
        }
    }
//	for (int i = 0; i < 10; i++)
//		printf("%lld\n", C[MAXN-1][i]);
    int testcase;
    long long n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld", &n);
        vector< pair<long long, long long> > r = invCombination(n);
        printf("%d\n", (int) r.size());
        for (int i = 0; i < r.size(); i++)
            printf("(%lld,%lld)%c", r[i].first, r[i].second, i == r.size()-1 ? '\n' : ' ');
    }
    return 0;
}

Read More +

2014-12-02

解題區/解題區 - UVa

UVa 1614 - Hell on the Markets

Problem

金融交易，它們希望賣出、買進交易結束後的差為零。

意即將數字分兩堆的結果相同。

Sample Input

Sample Output

1
2
3

No
Yes
1 -1 -1 1

Solution

由於保證 0 < a[i] <= i，基於這一點，可以發現到只考慮一個數字 a[1] 時，必然可以湊出 1 - a[1]，當考慮第 i 大數字時，保證前 i - 1 個數字可以湊出 1 ~ (i-1)，加上第 i 個數字必然可以湊出 1 ~ (i-1)+a[i] (1, 2, 3, ..., i-1, a[i], 1+a[i], ..., i-1+a[i])。

而事實上，可以湊出所有的 1 ~ sum[i]，根據遞歸是可以證明的。只要總和是偶數，必然可以劃分成總和相同的兩堆。排序一下，從大的數字開始挑，貪心去完成目標的總和。

#include <stdio.h>
#include <algorithm>
using namespace std;
    
pair<int, int> A[100000];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        long long sum = 0;
        int ret[100000] = {};
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i].first);
            A[i].second = i;
            sum += A[i].first;
        } 
        if (sum%2) {
            puts("No");
        } else {
            puts("Yes");
            sum /= 2;
            sort(A, A+n);
            for (int i = n-1; i >= 0; i--) {
                if (sum >= A[i].first)
                    sum -= A[i].first, ret[A[i].second] = 1;
                else
                    ret[A[i].second] = -1;
            }
            for (int i = 0; i < n; i++)
                printf("%d%c", ret[i], i == n-1 ? '\n' : ' ');
        }
    }
    return 0;
}

Read More +