UVa 12637 - 30 Minutes or Less

Problem

現在有 R 個 Pizza 店,同一個時間接收到 N 筆訂單,每一個店負責處理一筆訂單,發送的成本為店家到訂單的曼哈頓距離。

求所有訂單送達的總時間最小值為何?

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2 2
1 5
2 1
4 2
4 3
3 2
2 1
4 3
7 4
4 5
5 -1

Sample Output

1
2
8
7

Solution

一開始以為是要求最後一個送達的時間最小化,二分下去才發現連範測都過不了。

建圖之後,用 KM 算法找最大帶權匹配 (費用最小就取負號),用最少費用流解也是可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
#include <map>
#include <vector>
using namespace std;
struct KM {
int W[105][105], N;
int mx[105], my[105]; // match arr
int lx[105], ly[105]; // label arr
int x[105], y[105]; // used arr
int hungary(int nd) {
int i;
x[nd] = 1;
for(i = 0; i < N; i++) {
if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) {
y[i] = 1;
if(my[i] == -1 || hungary(my[i])) {
my[i] = nd;
return 1;
}
}
}
return 0;
}
int run() {
int i, j, k, d;
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
for (int i = 0; i < N; i++)
lx[i] = -0x3f3f3f3f, ly[i] = 0;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
for(i = 0; i < N; i++) {
while(1) {
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
if(hungary(i)) break;
d = 0x3f3f3f3f;
for(j = 0; j < N; j++) {
if(x[j]) {
for(k = 0; k < N; k++)
if(!y[k])
d = d < lx[j]+ly[k]-W[j][k] ?
d : lx[j]+ly[k]-W[j][k];
}
}
if(d == 0x3f3f3f3f) break;
for(j = 0; j < N; j++) {
if(x[j]) lx[j] -= d;
if(y[j]) ly[j] += d;
}
}
}
int res = 0;
for(i = 0; i < N; i++) {
if(my[i] != -1)
res += W[my[i]][i];
}
return res;
}
} km;
int dist(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
int N, R;
int x[256], y[256], cost[128][128];
while (scanf("%d %d", &R, &N) == 2) {
for (int i = 0; i < R; i++)
scanf("%d %d", &x[i], &y[i]);
for (int i = 0; i < N; i++)
scanf("%d %d", &x[i+R], &y[i+R]);
km.N = R;
for (int i = 0; i < R; i++) {
for (int j = 0; j < N; j++) {
cost[i][j] = dist(x[i], y[i], x[j+R], y[j+R]);
km.W[i][j] = -cost[i][j];
}
for (int j = N; j < R; j++)
km.W[i][j] = 0;
}
int ret = km.run();
printf("%d\n", -ret);
}
return 0;
}
/*
2 2
1 5
2 1
4 2
4 3
3 2
2 1
4 3
7 4
4 5
5 -1
*/
Read More +

UVa 12890 - Easy Peasy

Problem

給一串整數序列,請問有多少連續的區間,區間不包含重複的數字。

Sample Input

1
2
3
4
5
2
3
1 2 1
5
1 2 3 1 2

Sample Output

1
2
5
12

Solution

窮舉每一個點當作區間左端點,向左延伸的最遠的右端點必然非遞減。

掃描線計算右端點。效率 O(n log n)

掛上輸入優化、HASH 會來得更快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main() {
int testcase, n, x;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
map<int, int> R;
int low = 0;
long long ret = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
int &y = R[x];
if (y > low) low = y;
y = i;
ret += i - low;
// printf("[%d %d]\n", low + 1, i);
}
printf("%lld\n", ret);
}
return 0;
}
/*
9
3
1 2 1
5
1 2 3 1 2
4
1 2 2 1
*/
Read More +

UVa 11123 - Counting Trapizoid

Problem

給平面上 N 個不重複的點,有多少梯形可以由這幾個點構成?

  • 有四條邊
  • 一對平行、一對不平行
  • 面積為正

Sample Input

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

Sample Output

1
2
Case 1: 0
Case 2: 1

Solution

先窮舉任兩個點拉起的線段 (let N = n*(n-1)/2)。

針對線段斜率排序,接著將相同斜率放置在同一個 group。

對於每一個 group 的每一個元素計算有多少可以配對成梯形。

  • 防止共線
  • 防止線段具有相同長度 (防止兩對邊平行)

斜率相同,按照交 y 軸的大小由小到大排序。(左側到右側),由左側掃描到右側,依序把非共線的線段丟入,並且紀錄線段長度資訊。每一個能匹配的組合為 當前線段數 - 相同長度線段數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define eps 1e-9
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);
}
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 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);
}
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;
}
};
struct DOUBLE {
double v;
DOUBLE(double a = 0):
v(a) {}
bool operator<(const DOUBLE &other) const {
if (fabs(v - other.v) > eps)
return v < other.v;
return false;
}
};
Pt D[256];
Seg segs[65536], buf[65536];
int main() {
int cases = 0;
int n, m;
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%lf %lf", &D[i].x, &D[i].y);
sort(D, D + n);
m = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
segs[m++] = Seg(D[i], D[j]);
sort(segs, segs + m);
long long ret = 0;
for (int i = 0; i < m; ) {
int j = i, tn = 0;
while (j < m && fabs(segs[i].angle - segs[j].angle) < eps)
buf[tn++] = segs[j], j++;
i = j;
map<DOUBLE, int> LEN; // LEN[len] = count.
queue<Seg> Q;
int tmp = 0;
// for (int k = 0; k < tn; k++)
// printf("(%lf %lf) - (%lf %lf)\n", buf[k].s.x, buf[k].s.y, buf[k].e.x, buf[k].e.y);
// puts("--- same slope");
for (int k = 0; k < tn; k++) {
while (!Q.empty() && fabs(cross(buf[k].s, buf[k].e, Q.front().s)) > eps) {
Seg t = Q.front();
Q.pop();
tmp++, LEN[DOUBLE(dist(t.s, t.e))]++;
}
int comb = tmp - LEN[DOUBLE(dist(buf[k].s, buf[k].e))]; // remove same length
ret += comb;
Q.push(buf[k]);
}
}
printf("Case %d: %lld\n", ++cases, ret);
}
return 0;
}
/*
4
0 0
1 0
0 1
1 1
4
0 0
1 1
2 0
0 1
6
5 1
3 1
5 0
3 3
2 4
0 8
0
*/
Read More +

UVa 12452 - Plants vs. Zombies HD SP

Problem

給一個 N 個點的樹圖,在點上放置植物保護所有的邊,每個點上最多放置一個植物,請問最少花費為何?

  • 綠豆槍手:花費 100 元,保護相鄰一條邊。
  • 分裂碗豆:花費 175 元,保護相鄰兩條邊。
  • 楊桃:花費 500 元,保護相鄰所有邊。

Sample Input

1
2
3
4
5
6
2
2
0 1
3
0 1
1 2

Sample Output

1
2
$100
$175

Solution

將樹轉換成有根樹,對於每一個 node 當成 tree 去做考慮。

狀態 dp[node][1:protect edge from parent, 0:none]

以 node 以下作為一個 subtree 的最少花費,並且是否已經保護通往父親的邊。

效率 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 32767
vector<int> g[MAXN];
long long dp[MAXN][2]; // [node][1:protect edge from parent, 0:none]
#define INF (1LL<<50)
void dfs(int u, int p) {
dp[u][0] = dp[u][1] = INF;
long long cost[3] = {};
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == p) continue;
dfs(v, u);
cost[0] += dp[v][0];
cost[1] += dp[v][1];
cost[2] += min(dp[v][0], dp[v][1]);
}
dp[u][0] = min(dp[u][0], cost[1]);
dp[u][1] = min(dp[u][1], cost[1] + 100);
dp[u][1] = min(dp[u][1], cost[2] + 500);
long long c[2] = {INF, INF};
for (int i = 0; i < g[u].size(); i++) {// two edge with subnode and parent.
int v = g[u][i];
if (v == p) continue;
dp[u][1] = min(dp[u][1], cost[1] - dp[v][1] + dp[v][0] + 175);
if (-dp[v][1] + dp[v][0] < c[1]) {
c[1] = -dp[v][1] + dp[v][0];
if (c[0] > c[1]) swap(c[0], c[1]);
}
}
// two two edge with two subnodes
dp[u][0] = min(dp[u][0], cost[1] + c[0] + c[1] + 175);
}
int main() {
int testcase, n;
int u, v;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
g[i].clear();
for (int i = 1; i < n; i++) {
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0, -1);
printf("$%lld\n", min(dp[0][0], dp[0][1]));
}
return 0;
}
Read More +

UVa 12440 - Save the Trees

Problem

有一排樹,每個樹分別有 typeheight,現在要將其分團,

  • 每一團內不允許有相同的 type
  • 每一團的花費是最高的 height

計算總花費最小為何?

Sample Input

1
2
3
4
5
6
7
1
5
3 11
2 13
1 12
2 9
3 13

Sample Output

1
Case 1: 26

Solution

藉由掃描線的思路,可以得知每一個樹的位置 i,往左延伸最大多少內不會有重複的 type。詳見 12890 - Easy Peasy 的技巧。

因此會得到公式$dp([i]) = min(dp[j - 1] + max(height[k])), j \geq f(i), j \le k \le i$

dp[i]:將前 i 個樹分團的最少費用。

計算這個公式需要 O(n^2),由於 n 很大,必須找一個優化將其降下來。

首先知道 f(i) 是非遞減函數 (會一直增加),單純看 i 時,dp[j - 1] 是固定的,但
max(height[k]) 會逐漸增加,如果能在 O(log n) 時間進行更新、詢問,複雜度將可以降至 O(n log n)

每個元素有兩個屬性 (a, b)

  • query(f(i), i) : return min(A[k].a + A[k].b), f(i) <= k <= i
  • update(f(i), i, height[i]) : A[k].b = max(A[k].b, height[i])

左思右想仍然沒有辦法用線段樹完成它,至少是一個很 tricky 的花費計算。

有一個貪心的思路,考慮區間內的計算時,只需要找到嚴格遞減的高度進行更新即可,並非所有的可能進行嘗試。用一個單調隊列,只記錄 [f(i), i] 之間的嚴格遞減的高度資訊,接著每次需要窮舉單調隊列內的所有元素。

複雜度最慘還是 O(n^2),隨機測資下速度是快非常多的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int type[MAXN], height[MAXN];
long long dp[MAXN];
int dQ[MAXN];
int main() {
// freopen("in.txt", "r+t", stdin);
// freopen("out.txt", "w+t", stdout);
int testcase, cases = 0;
int n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d %d", &type[i], &height[i]);
map<int, int> R;
int L = 0;
dp[0] = 0;
int head = 0, rear = -1;
for (int i = 1; i <= n; i++) {
int &y = R[type[i]];
L = max(L, y);
y = i;
while (head <= rear && dQ[head] <= L)
head++;
while (head <= rear && height[dQ[rear]] <= height[i])
rear--;
dQ[++rear] = i;
dp[i] = 1LL<<60;
for (int j = head; j <= rear; j++) {
if (j != head)
dp[i] = min(dp[i], dp[dQ[j-1]] + height[dQ[j]]);
else
dp[i] = min(dp[i], dp[L] + height[dQ[j]]);
}
}
printf("Case %d: %lld\n", ++cases, dp[n]);
}
return 0;
}
/*
1
5
3 11
2 13
1 12
2 9
3 13
30
10
4 13
2 18
7 20
1 16
1 14
10 5
5 11
7 19
8 12
2 16
9999
10
10 16
3 5
8 11
8 2
5 3
6 2
10 19
6 10
6 16
6 4
9999
10
3 6
10 5
2 9
5 2
9 3
3 8
6 10
4 17
7 10
6 11
*/
Read More +

UVa 1382 - Distant Galaxy

Problem

給平面上 N 個點,找一個最大矩形,使得矩形邊上有最多點個數。

Sample Input

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

Sample Output

1
Case 1: 7

Solution

UVa 1382

先離散化處理,將所有點放置在 grid[100][100] 內。

接著窮舉上下兩條平行線,由左而右開始掃描,邊緣的個數為 V[U1] + V[U2] + H[R] - V[U3] + V[U4] + H[L],掃描時維護 V[U3] + V[U4] - H[L] 的最小值。

特別小心矩形的四個頂點的排容,上述的公式仍然不太夠。由於題目沒有特別要求正面積矩形,必須考慮共線上最多的點個數。

效率 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main() {
int n, x[128], y[128];
int cases = 0;
while (scanf("%d", &n) == 1 && n) {
map<int, int> Rx, Ry;
for (int i = 0; i < n; i++) {
scanf("%d %d", &x[i], &y[i]);
Rx[x[i]] = 0, Ry[y[i]] = 0;
}
int size, R, C;
size = 0;
for (map<int, int>::iterator it = Rx.begin();
it != Rx.end(); it++) {
it->second = size++;
}
R = size;
size = 0;
for (map<int, int>::iterator it = Ry.begin();
it != Ry.end(); it++) {
it->second = size++;
}
C = size;
int g[128][128] = {}, ret = 0;
for (int i = 0; i < n; i++) {
int r, c;
r = Rx[x[i]], c = Ry[y[i]];
g[r][c]++;
}
for (int i = 0; i < R; i++) {
int sum[128] = {}, s1, s2, mn;
for (int j = i; j < R; j++) {
s1 = s2 = 0, mn = 0;
for (int k = 0; k < C; k++) {
// printf("[%d %d] %d\n", i, j, k);
sum[k] += g[j][k];
s1 += g[i][k], s2 += g[j][k];
if (i != j) {
// printf("%d %d %d %d = %d\n", s1, s2, mn, sum[k], s1 + s2 - mn + sum[k]);
ret = max(ret, s1 + s2 - mn + sum[k] - g[i][k] - g[j][k]);
mn = min(mn, s1 + s2 - sum[k]);
}
}
}
}
for (int i = 0; i < R; i++) {
int sum = 0;
for (int j = 0; j < C; j++)
sum += g[i][j];
ret = max(ret, sum);
}
for (int i = 0; i < C; i++) {
int sum = 0;
for (int j = 0; j < R; j++)
sum += g[j][i];
ret = max(ret, sum);
}
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}
/*
10
2 3
9 2
7 4
3 4
5 7
1 5
10 4
10 6
11 4
4 6
3
1 1
2 1
3 1
3
1 1
1 2
1 3
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
*/
Read More +

[通識] 文明的進程 Week 11

主題-攻擊欲的轉變

不知何時開始,人們對於暴力行為開始無法容忍,逐漸地喪失對於暴力的經驗。曾經也打過架,恨不得把對方殺了,即使捶得再大力也弄不出傷口來,也許被馴化的怒火無法傷害任何人,只剩下精神上的威嚇。拿刀殺人的場景不是在電視情節中,就只能在夢裡、幻想裡去想這些。

同類相互攻擊在大自然中常見不過的事,為什麼在人類身上卻逐漸消失?沒錯!因為我們有穿越好幾世代的外部記憶體-文化。

攻擊欲

曾經的人們為了生活,長久時間的定居,明天在哪都不曉得。只要一戰爭,贏了高興,輸了什麼都沒,生命就是這麼地短暫,中古世紀曾有一段話「看見死亡才能安心、吃得好、睡得好」那是在什麼樣的生存條件下,活著不是殺死對方,又是被殺、被壓迫的日子。面對死亡才能安心,這才是真正的活著!「 未知死,焉知生 」古人說得有道理。

為什麼至今仍有黑道白道之分?當白道無法解決的事情,黑道顯得更有威震力,看看「日本黑道山口組」在許多電影情節中,黑道的存在反而凸顯了到底是傾聽社會聲音做事?還是聽從自己的本能。社會給予的牢籠,促使我們不做暴力的行為,隱藏自己的情感,然而這些情感去哪了?

沒有暴力的行為,如何表示自己的不滿?敵意?產生出的無力感、關係冷漠、義憤,用另外一種方式宣洩自己的攻擊欲,「 如果這些世界不接受我,那就摧毀這個世界吧! 」沒了直來直往的暴力世界,卻產生出兩個極端的世界,被壓抑著暴力的人們何時會爆發呢?

殘暴的必要性-對敵人寬厚,就是壯大對方,未來必有危害,「斬草不除根,春風吹又生」不殺行嗎?用仁慈看那個世界,你就是找死!然而現今的攻擊欲,單純的攻擊欲也傷不了任何人,用武器所需要的技術越來越高,沒有技術也殺不死人,這片高牆越來越高厚呢。

陽剛

起初所謂的陽剛只得是什麼?不正是那殘暴的事實嗎?現今看看那些陽剛的定義,早已經被陰柔化,受到捧吹的帥哥又是在古時的男人嗎?追求性別平等的代價,造成暴力的消失,如果還要展現自己的暴力,只能迂迴表達自己那一身的肌肉。

行刑

既然沒法殺人,公開行刑正是大眾娛樂,一個人被處刑,整座城市的人都在看,這是為什麼?在電影情節中,殺人的血腥畫面是否令人振奮?追求安心才是本能!

現在有很多不殺人的行刑,例如剝奪尊嚴,相當於利用羞恥感、價值觀的攻擊,文化的禁忌-身體的隱蔽性,這還不讓人精神崩潰嗎?讓一個人不成人形的方式很多,精神是如此地脆弱。

死亡

過去人們很難活長,活到三、四十歲就算有幸,也因為戰爭死亡相當常見,如果人們對死亡感到悲傷,豈不是沒辦法過生活?整年都要哭天喊地的,你能說他們無情嗎?不行,他們本應該這麼做,否則沒辦法前進。

古人很容易 認命 ,對於前途未卜的不安,明天還能活著嗎?戰爭就在那麼一夕之間開打,生計被土地綁著,想走也走不了。有一夜沒一夜的的恐懼,「 今宵有酒今宵醉 」死了就什麼都沒了,為何不現在享用?總是 盤算未來 ,那是你們現代人的奢侈。

血濃於水,資產階級興起後,家族之間的私鬥相當常見,衝突一來,不少家族因此滅絕。信得過的人只有血緣關係的人,不要說為何當官的都想找自己人,找不同處境的人,不怕在背後被人捅一刀嗎?(不論豬隊友)

活在當下,並非沒有遠見、逃避現實 ,誰知道明天在哪?那等絕望,你還有盤算未來的本錢嗎?

剝奪

如何表示對別人的不滿?當下只剩下視覺的攻擊,作為一個活在現代的人,動手動腳就已經輸一半,觸覺已被作為侵略他人身體的領域,嗅覺則不能作為認識人的方法 (因為那如野獸一樣)。

視覺已成為唯一攻擊欲的發揮。觀賞球類運動也是如此,作為球迷欣賞支持的隊伍侵略,但自己除了看,什麼事情都不能做,一旦做了就是不文明的舉動。

暴力遊戲會使得人暴力嗎?愚蠢的人們啊,在怎麼轉換情感,也不可能百分百的宣洩。

魅力化

論吸血鬼、狼人的暴力魅力化,腐女們準備好了嗎?

以下開放暴動。本文 … 略。

Read More +

自然語言處理 論文研讀 2

著重目標

即使 Unigram 效果已經相當不錯,基於人類日常對話的模式,絕非單詞相依無關,藉由好幾個連詞表示出不同的意思是常有的事情,探討 n-grams (n > 3) 對於當前的語意分類器的強化、優化。

已知問題

當 n-grams (n > 3) 時,語意的模糊性質會提高,可能同時把正反兩面的詞放置在一起,如此一來這一組的利用價值並不高,在計算分類上會將精準度稀釋,同時對於記憶體的負荷也會增加 (必須記錄各種組合,例如化學元素與化合物的數量大小關係)。

接著 n-grams 通常是用在英文處理精準度比較好,因為 單詞分明 (藉由空白隔開),對於機器而言中文句子並不存在詞 (token),都是一堆字元 (character)。

研究顯示: 漢字順序並不一定影響閱讀

請看下述文字-研究顯示:漢字序順並不定一影閱響讀。

對於中文自然語言處理,斷詞的重要性、語意處理上有額外的研究領域,在這裡暫時不談論這些。也許可以談談看不考慮順序的 n-grams,型態從 tuple 變成 dag。

分類器

分類器分成線上訓練、離線訓練,就已知得到目前 SVM 仍然在實務上的效果是最好的,在這裡不談論 SVM,一部分原因是 SVM 太慢。

下面是在不同領域的分類器構思,線上訓練、線性調整。大多數的分類器都必須定義特徵,對於每一個要分辨的項目是否存有這一個特徵 (boolean),而在部分可允許模糊的模型,可以利用權重 (float) 表示特徵強弱。

類神經網路

Passive-Aggressive Algorithm

對於感知機的內容所知不多,每加入一筆結果,將劃分的依準疊加上預期的法向量,成為新的劃分依準線。大多依靠數學的微積分來完成,並非完全相信新加入的結果,因此會有一個計算的權重,來權衡影響的大小。

訓練流程:

$$\begin{align} & \text{INITIALIZE : } w_{1} = (0 ... 0) \text{ as parameters of the classifier} \\ & \text{For } t = 1, 2, ... \\ & \text{receive instance : } x_{t} \in R^{n} \\ & \text{predict : } \hat{y_{t}} = sign(w_{t}, x_{t}) \\ & \text{receive correct label : } y_{t} \in {-1, +1} \\ & \text{suffer loss : } l_{t} = max\left \{ 0, 1 - y_{t}(w_{t} \cdot x_{t}) \right \} \\ & \text{update-1: set : } \tau_{t} = \frac{l_{t}}{\left \| x_{t} \right \|^{2}} \\ & \text{update-2: update : } w_{t+1} = w_{t} + \tau_{t} y_{t} x_{t} \end{align}$$

自然語言

Language Modeling

就如上課內容所講的

$$\begin{align} P(s) = \prod_{i = 1}^{l} P(w_{i}|w_{1}^{i-1}) \end{align}$$

用 Good Turing 的方式去 smoothing 那些從未在模型中出現的詞語,它們是有機會的,絕非是機率 0。

機器學習

Winnow algorithm

設定一個閥值作為是否存在此分類的依據,隨後根據閥值調整相關數據的參數大小。

$h(x) = \sum_{w \in V}^{} f_{w}c_{w}(x)$ $f_{w}$ 是需要調整的參數$c_{w}(x)$ 為資料在每一個特徵的權重向量,運算內積值為$h(x)$

訓練流程:

$$\begin{align} & \text{Initialize all } f_{w} \text{ to 1.} \\ & \text{For each labeled revies x in the training set : } \\ & \text{Step 1. Calculate } h(x) \\ & \text{Step 2-1. If the revies is positive but Winnow predicts it as negative } \\ & h(x) < V \text{ , update the weight} f_{w} \text{ where } c_{w}(x) = 1 \text{ by } f'_{w} = f_{w} \times 2 \\ & \text{Step 2-2. If the revies is negative but Winnow predicts it as positive } \\ & h(x) > V \text{ , update the weight} f_{w} \text{ where } c_{w}(x) = 1 \text{ by } f'_{w} = f_{w} / 2 \\ \end{align}$$

簡單來說,當判斷錯誤時,將相關的 (它有的) 特徵係數權重調整,將其變大使得納入分類中、或者將其變小踢出分類中。

調和

為了加入 n-grams (n > 3) 的機制,必然要學習 忘記 無視 的才能,才能將垃圾訊息給捨去掉。同時也是降低記憶體的耗存的方法,這裡無法像人類有辦法根據時間將單詞組合抽象化,等到哪天 HTM 腦皮質學習算法 成功實作,相信在取捨上會更為流暢。

對於每一個特徵給予分數,保留前 K 好的特徵進行訓練,其餘特徵捨去,至於要保留的 K 大小將由實驗結果進行測試。

分數計算:

  • A:同一分類下,該屬性使用的資料筆數
  • B:在其他分類下,該屬性被使用的資料筆數
  • C:同一分類下,該屬性不使用的資料筆數
  • D:在其他分類下,該屬性不被使用的資料筆數
  • t:屬性
  • c:分類
$$\begin{align} x^{2}(t, c) = \frac{N \times (AD - CB)^{2} }{(A+C)\times (B + D) \times (A + B) \times (C + D)} \end{align}$$

結論

論文中提到,分別去了 50K、100K、200K 個分數高的 n-grams,又分別在 n = 3, 4, 5, 6 下進行測試,效果有那麼一點點地提升。

接著就是考驗我們期末 Project 要怎麼體現這篇論文的思路、擴充。

Read More +

UVa 12873 - The Programmers

Problem

給 P 個隊伍、S 個賽區,每隊分別都有可以去的賽區,而每一個賽區最多容納 C 個隊伍。

請問參加的總隊伍數量最大為何?

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
2 2 1 4
1 1
1 2
2 1
2 2
4 3 1 12
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
4 1
4 2
4 3

Sample Output

1
2
2
3

Solution

建造 maxflow 模型,source - team - site - sink 即可完成。

不是說好 maxflow 不太會考的嗎?結果還是在泰國賽區出來了,雖然之前也噴過 mincost 最少費用流 …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
int v, cap, flow;
Edge *next, *re;
} Edge;
class MaxFlow {
public:
Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
void Init(int x) {
n = x, e = 0;
for (int i = 0; i < n; ++i) adj[i] = NULL;
}
void Addedge(int x, int y, int flow){
edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
edge[e].re = &edge[e+1], adj[x] = &edge[e++];
edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
edge[e].re = &edge[e-1], adj[y] = &edge[e++];
}
void Bfs(int v){
int front = 0, rear = 0, r = 0, dis = 0;
for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
level[v] = 0, ++lvCnt[0];
Q[rear++] = v;
while (front != rear){
if (front == r) ++dis, r = rear;
v = Q[front++];
for (Edge *i = adj[v]; i != NULL; i = i->next) {
int t = i->v;
if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
}
}
}
int Maxflow(int s, int t){
int ret = 0, i, j;
Bfs(t);
for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
i = s;
while (level[s] < n){
while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow))
arc[i] = arc[i]->next;
if (arc[i]){
j = arc[i]->v;
pre[j] = arc[i];
i = j;
if (i == t){
int update = INF;
for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
if (update > p->flow) update = p->flow;
ret += update;
for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
p->flow -= update, p->re->flow += update;
i = s;
}
}
else{
int depth = n-1;
for (Edge *p = adj[i]; p != NULL; p = p->next)
if (p->flow && depth > level[p->v]) depth = level[p->v];
if (--lvCnt[level[i]] == 0) return ret;
level[i] = depth+1;
++lvCnt[level[i]];
arc[i] = adj[i];
if (i != s) i = pre[i]->re->v;
}
}
return ret;
}
} g;
int main() {
int testcase;
scanf("%d", &testcase);
while (testcase--) {
int P, S, C, m, x, y;
scanf("%d %d %d %d", &P, &S, &C, &m);
g.Init(P + S + 2);
int source = 0, sink = P + S + 1;
for (int i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
g.Addedge(x, P + y, 1);
}
for (int i = 1; i <= P; i++)
g.Addedge(source, i, 1);
for (int i = 1; i <= S; i++)
g.Addedge(P + i, sink, C);
int ret = g.Maxflow(source, sink);
printf("%d\n", ret);
}
return 0;
}
/*
2
2 2 1 4
1 1
1 2
2 1
2 2
4 3 1 12
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
4 1
4 2
4 3
*/
Read More +

UVa 12872 - Hidden Plus Signs

Problem

盤面上放置許多 + 展開,保證寬高相同並且不會超出格子外部,同時每一個大小不超過 11。而十字中心不會被其他十字覆蓋,每一格會顯示被覆蓋幾次。

找到一種放置方法,復原盤面結果,如果有種放置方法,選擇一種字典順序最小的輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0
10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0

Sample Output

1
2
3
4
2
3 3
9
8 10

Solution

論窮舉順序的重要性,將會導致速度的快慢。

原則上先把所有 1 的位置挑出,依序窮舉每一個 1 是否可以進行放置。每一次選擇放置時,先從最大的寬高開始嘗試,先塞掉大多數的盤面結果,否則速度會被拉下。

不確定這一題是否有很正統的作法,求指導。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <algorithm>
using namespace std;
int g[32][32], n, m;
int A[900][2], N, SUM = 0;
int isEmpty() {
return SUM == 0;
}
void remove(int x, int y, int w) {
for (int i = x - w; i <= x + w; i++)
g[i][y]--, SUM--;
for (int i = y - w; i <= y + w; i++)
g[x][i]--, SUM--;
g[x][y]++, SUM++;
}
void resume(int x, int y, int w) {
for (int i = x - w; i <= x + w; i++)
g[i][y]++, SUM++;
for (int i = y - w; i <= y + w; i++)
g[x][i]++, SUM++;
g[x][y]--, SUM--;
}
int place(int x, int y, int w) {
for (int i = x - w; i <= x + w; i++)
if (!g[i][y])
return 0;
for (int i = y - w; i <= y + w; i++)
if (!g[x][i])
return 0;
return 1;
}
int dfs(int idx, int used, int LX, int LY) {
if (isEmpty()) {
printf("%d\n%d %d\n", used, LX + 1, LY + 1);
return 1;
}
if (idx == N)
return 0;
int t = min(min(A[idx][0], A[idx][1]), min(n - 1 - A[idx][0], m - 1 - A[idx][1]));
for (int i = t; i >= 1; i--) {
if (place(A[idx][0], A[idx][1], i)) {
remove(A[idx][0], A[idx][1], i);
if (dfs(idx+1, used + 1, A[idx][0], A[idx][1]))
return 1;
resume(A[idx][0], A[idx][1], i);
}
}
if (dfs(idx+1, used, LX, LY))
return 1;
return 0;
}
int main() {
int testcase;
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", &g[i][j]), SUM += g[i][j];
N = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == 1)
A[N][0] = i, A[N][1] = j, N++;
dfs(0, 0, -1, -1);
}
return 0;
}
/*
2
5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0
10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0
*/
Read More +