解題區►解題區 - UVa

UVa 12818 - Arc and Point

Problem

用三個點表示一弧，求一點到一弧最段距離。

Sample Input

1
2
0 0 1 1 2 0 1 -1
3 4 0 5 -3 4 0 1

Sample Output

1
2
Case 1: 1.414
Case 2: 4.000

Solution

Imgur

Imgur

先拉 AC 一線，計算 ABC 的外心 O，判斷 ABC 張角是否大於 180 度，利用 O、B 是否在 AC 同側或異側。

接著，分配兩側開始討論，參考方式如上圖。有三角形內部問題等 …

誤差問題仍然很嚴重，用三分解法肯定過不去，倒不如說卡在要怎麼三分參數。

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    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);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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 angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
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);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
int main() {
    Pt a, b, c, p;
    int cases = 0;
    while (scanf("%lf %lf", &a.x, &a.y) == 2) {
        scanf("%lf %lf", &b.x, &b.y);
        scanf("%lf %lf", &c.x, &c.y);
        scanf("%lf %lf", &p.x, &p.y);
        double ret = min(dist(p, a), dist(p, c));
        double a1, b1, c1;
        Pt o = circle(a, b, c);
        a1 = a.y - c.y, b1 = c.x - a.x, c1 = a1 * a.x + b1 * a.y; // line ac
//        printf("%lf %lf %lf\n", a1, b1, c1);
//        printf("%lf %lf\n", a1 * b.x + b1 * b.y - c1, a1 * p.x + b1 * p.y - c1);
//        printf("%lf %lf\n", o.x, o.y);
        if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * o.x + b1 * o.y - c1 > 0)) {
            double d = dist(o, p), r = dist(o, a);
            if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * p.x + b1 * p.y - c1 > 0)) {
                if (cross(a, c, p) * cross(a, o, p) < eps &&
                    cross(c, o, p) * cross(c, a, p) < eps &&
                    cross(o, a, p) * cross(o, c, p) < eps) {
                } else {
                    if (d > r)
                        d -= r;
                    else
                        d = r - d;
                    ret = min(ret, d);
                }
            } else {
                if (cross(o, a, p) * cross(o, c, p) > -eps) {
                    d = d - r;
                    ret = min(ret, d);
                }
            }
        } else {
            double d = dist(o, p), r = dist(o, a);
            if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * p.x + b1 * p.y - c1 > 0)) {
            	if (cross(o, a, p) * cross(o, c, p) < eps) {
	                if (d > r)
	                    d -= r;
	                else
	                    d = r - d;
	                ret = min(ret, d);
            	}
            } else {
                if (cross(a, c, p) * cross(a, o, p) < eps &&
                        cross(c, o, p) * cross(c, a, p) < eps &&
                        cross(o, a, p) * cross(o, c, p) < eps) {
                    d = r - d;
                    ret = min(ret, d);
                }
            }
        }
        assert(ret >= 0);
        printf("Case %d: %.3lf\n", ++cases, ret + eps);
    }
    return 0;
}
/*
 4 -2 -2 4 -4 -2 -1 3 
 4 -2 -2 4 -4 -2 1 3
 4 -2 -2 4 -4 -2 -3 5 
 4 -2 -2 4 -4 -2 3 5
 4 -2 -2 4 -4 -2 -3 1
 4 -2 -2 4 -4 -2 -5 1 
 4 -2 -2 4 -4 -2 -1 -1
 4 -2 -2 4 -4 -2 -1 -3 
 4 -2 -2 4 -4 -2 0 0 
 
 -4 3 0 5 4 3 9 4 
 -4 3 0 5 4 3 -9 4
 -4 3 0 5 4 3 10 3
 -4 3 0 5 4 3 -4 5
 -4 3 0 5 4 3 8 2
 -4 3 0 5 4 3 1 2
 -4 3 0 5 4 3 1 -2
 -4 3 0 5 4 3 2 1
 0 0 1 1 2 0 1 -1
 
 3 4 0 5 -3 4 0 1
 3 4 0 5 -3 4 0 4.5
 3 4 0 5 -3 4 1 3
 3 4 0 5 -3 4 -3 3
 3 4 0 5 -3 4 0 -1
 
 -1 -1 0 3 1 -1 1 1
 -1 -1 0 3 1 -1 -2 -1
 -1 -1 0 3 1 -1 0 0
 -1 -1 0 3 1 -1 0 -1
 -1 -1 0 3 1 -1 0 -2
 
 2 0 0 2 -2 0 0 0
*/
Read More +
解題區►解題區 - UVa

UVa 12685 - Binary Tree

Problem

根據第一行指令，在一個二元樹中走訪節點，最後停留的位置交給第二行繼續執行。然而第二行的每一個指令可以選擇忽略或者執行，最後停留的節點共計有多少個。

Sample Input

1
2
3
4
5
2
L
LU
L
L

Sample Output

1
2
Case 1: 3
Case 2: 2

Solution

一開始會發現最後停留的點，下次可能抵達的位置為其左子樹節點個數 1、右子樹節點個樹 1。

定義：可能在下一個走到的左子節點個數 l、右子節點個數 r。

當選擇往左前往還沒有走過的左子節點時，所有左子節點各會增加可能未走到的左子節點、右子節點，而已經消耗 l 個未走過的左節點，現在增加 l 個未走過的左節點、l 個未走過的右節點。反之，走到右子節點也是。

如果選擇往上時，只會根據一開始停留點到 root 之間的距離有關。

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
#include <stdio.h> 
#include <stack>
using namespace std;
char S[131072], T[131072];
const int mod = 21092013;
int main() {
	int testcase, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s %s", S, T);
		stack<char> stk;
		for (int i = 0; S[i]; i++) {
			if (S[i] == 'L' || S[i] == 'R')
				stk.push(S[i]);
			else if (!stk.empty())
				stk.pop();
		}
		int ret = 1, lson = 1, rson = 1;
		for (int i = 0; T[i]; i++) {
			if (T[i] == 'L')
				ret = (ret + lson)%mod, rson = (rson + lson)%mod;
			else if (T[i] == 'R')
				ret = (ret + rson)%mod, lson = (lson + rson)%mod;
			else {
				if (!stk.empty()) {
					ret = (ret + 1)%mod;
					if (stk.top() == 'L')
						rson++;
					else
						lson++;
					stk.pop();
				}
			}
		}
		printf("Case %d: %d\n", ++cases, ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11964 - Equation

Problem

$$x_{1} + 2 x_{2} + 4 x_{3} + 8 x_{4} + 16 x_{5} + ... + 2^{t} x_{t}= K \text{ where } x_{i} \geq 0$$

找到所有組合數並且 mod M 的結果，其中 M 可以拆成數個小於 150 的質因數分解。

Sample Input

1
2
3
4
3
15 99
101 123
1234 536870912

Sample Output

1
2
3
Case 1: 26
Case 2: 111
Case 3: 176223474

Solution

其中 M 可以拆成數個小於 150 的質因數分解。

這句話可說是暗藏玄機，由於測資組數太多，對於每次 mod 情況都建表太慢。不然這題單純套用硬幣問題就能計算個數收尾。

因此，先將 M 進行質因數分解 $M = \prod_{i} p_{i}^{x_{i}}$，之後用中國餘式定理求解。

由於質因數的個數可能大於 1，那其實也可以發現 $\text{count mod } p_{i}$ 和 $\text{count mod } p_{i - 1}$ 之間的關係，$\text{count mod } p_{i-1} = \text{count mod } p_{i} \text{ mod } p_{i-1}$。

這裡可以 O(1) 算出來，而在 150 以內總共有 35 個質數，分別對這些質數計算出 mod 盡可能大，$p_{i} \le 10^{15}$ 為準。

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 <vector>
using namespace std;
#define maxL (150>>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[150], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 150;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
long long mulmod(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 inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    return i ? (la%mod+mod)%mod : (ra%mod+mod)%mod;
}
long long chinese_remainder(int n, long long m[], long long a[]) {
    long long M = 1, ret = 0;
    for(int i = 0; i < n; i++)
        M *= m[i];
    for(int i = 0; i < n; i++) {
        ret += a[i] * inv(M/m[i], m[i]) %M * (M/m[i]);
        ret %= M;
    }
    return (ret%M + M)%M;
}
vector< pair<int, int> > factor(long long n) {
	vector< pair<int, int> > R;
	
	for(int i = 0, j; i < Pt && 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(P[i], j));
		}
	}
	if(n != 1)	R.push_back(make_pair(n, 1));
	return R;
}
long long mpow(long long x, long long y) {
	long long ret = 1;
	for (int i = 0; i < y; i++)
		ret *= x;
	return ret;
}
vector<long long> dp[37];
int main() {
	sieve();
	for (int i = 0; i < Pt; i++) {
		long long m = P[i];
		int p = 0;
		for (m = P[i], p = 0; m * P[i] <= 1e+15; p++, m *= P[i]);
		dp[i].resize(100005, 0);
		dp[i][0] = 1;
		for (int j = 1; j <= 100000; j <<= 1) {
			for (int k = j; k <= 100000; k++)
				dp[i][k] = (dp[i][k] + dp[i][k - j])%m;
		}
	}
	int testcase, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		int K;
		long long M;
		scanf("%d %lld", &K, &M);
		vector< pair<int, int> > f = factor(M);
		long long m[35], a[35];
		for (int i = 0; i < f.size(); i++) {
			for (int j = 0; j < Pt; j++)
				if (f[i].first == P[j])
					m[i] = mpow(P[j], f[i].second), a[i] = dp[j][K] % m[i];
		}
		long long ret = chinese_remainder(f.size(), m, a);
		printf("Case %d: %lld\n", ++cases, ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11972 - Round Trip

Problem

給一張圖，從起點 c 出發，每一條邊最多經過一次，最後回到 c。中間可以經過哪些節點。

Sample Input

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

Sample Output

1
2
Case 1: 2 3 4 5 6
Case 2: none

Solution

窮舉所有可能做最大流，從起點 c 到指定的點 v，如果存在最大流 maxflow >= 2 表示至少兩條，因此可以拉成一個環，表示 v 可以在環上。

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
140
141
142
143
144
145
146
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
#define MAXN 128
struct Node {
    int x, y;
	int cap, flow;// x->y, v
    int next;
} edge[10005];
int e, head[MAXN], prev[MAXN], record[MAXN];
int level[MAXN], visited[MAXN];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = v, edge[e].flow = 0;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].flow = 0;
    edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
    memset(level, 0, sizeof(level));
    queue<int> Q;
    Q.push(s), level[s] = 1;
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(int i = head[tn]; i != -1; i = edge[i].next) {
            int y = edge[i].y;
            if(edge[i].cap > edge[i].flow && level[y] == 0) {
                level[y] = level[tn] + 1;
                Q.push(y);
            }
        }
    }
    return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
    int ret = 0;
    stack<int> stk;
    memset(visited, 0, sizeof(visited));
    stk.push(s);
    while(!stk.empty()) {
        int now = stk.top();
        if(now != t) {
            for(int i = head[now]; i != -1; i = edge[i].next) {
                int y = edge[i].y;
                if(visited[y] || level[y] != level[now] + 1)
                    continue;
                if(edge[i].cap > edge[i].flow) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 0x3f3f3f3f, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].cap - edge[ri].flow);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].flow += flow;
                edge[ri^1].flow -= flow;
                if(edge[ri].cap - edge[ri].flow == 0)
                    bottleneck = prev[i];
            }
            while(!stk.empty() && stk.top() != bottleneck)
                stk.pop();
            ret += flow;
        }
    }
    return ret;
}
int maxflowDinic(int s, int t) {
    int flow = 0;
    while(buildLevelGraph(s, t))
        flow += constructBlockingFlow(s, t);
    return flow;
}
vector<int> maxflowCut(int s, int t, int n) {
	buildLevelGraph(s, t);
	vector<int> ret;
	for (int i = 1; i <= n; i++) {
		for (int j = head[i]; j != -1; j = edge[j].next) {
			if (level[edge[j].x] && !level[edge[j].y] && edge[j].cap > 0 && edge[j].cap == edge[j].flow)
				ret.push_back(j);
		}
	}
	return ret;
}
int clearflow() {
	for (int i = 0; i < e; i++)
		edge[i].flow = 0;
}
int main() {
    int n, m, c;
    int x, y, v;
    int cases = 0;
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d %d %d", &n, &m, &c);
        e = 0;
        memset(head, -1, sizeof(head));
        for(int i = 0; i < m; i++) {
        	scanf("%d %d", &x, &y);
        	addEdge(x, y, 1);
        	addEdge(y, x, 1);
        }
        printf("Case %d: ", ++cases);
        int f = 0;
        for (int i = 1; i <= n; i++) {
        	if (i == c)	continue;
        	clearflow();
        	int flow = maxflowDinic(c, i);
        	if (flow >= 2) {
        		if (f)	putchar(' ');
        		printf("%d", i);
        		f = 1;
        	}
        }
        if (f == 0)
        	puts("none");
        else
        	puts("");
    }
    return 0;
}
/*
2
6 7 1
1 2
1 3
2 6
4 6
2 5
5 3
4 2
2 1 2
1 2
*/
Read More +
解題區►解題區 - UVa

UVa 12812 - The Largest Diamond-Shaped Kite

Problem

找一個最大箏形於給定的地圖中。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3 3
.#.
###
.#.
8 10
..##...#..
.###..###.
..#.......
....##....
....######
...#####..
..########
.....#....

Sample Output

1
2
3
5

Solution

其實很像找一個最大正方形，可以參考 NPSC 營地的作法。而要求箏形事實上就是將地圖翻轉 45 度角。

參考 UVa 10593 - Kites 的做法可以完成。

以前寫的 代碼 真是萌哒。

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
#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;
char g[512][512];
int dp[512][512];
int main() {
    int testcase;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%s", g[i]);
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '#') {
                    int v1, v2, v3;
                    v1 = i-1 >= 0 && j-1 >= 0 ? dp[i-1][j-1] : 0;
                    v2 = i-2 >= 0 ? dp[i-2][j] : 0;
                    v3 = i-1 >= 0 && j+1 < m ? dp[i-1][j+1] : 0;
                    if (i-1 >= 0 && g[i-1][j] == '#')
                        dp[i][j] = min(v1, min(v2, v3)) + 1;
                    else
                        dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
                ret = max(ret, dp[i][j]);
            }
        }
        printf("%d\n", ret * 2 - 1 < 0 ? 0 : ret * 2 - 1);
    }
    return 0;
}
/*
 2
 3 3
 .#.
 ###
 .#.
 8 10
 ..##...#..
 .###..###.
 ..#.......
 ....##....
 ....######
 ...#####..
 ..########
 .....#....
 */
Read More +
解題區►解題區 - UVa

UVa 12811 - The Turtle's Journey

Problem

  • left X
  • right X
  • forward X
  • repeat N [ INST ]

上述總共有四種指令架構，分別輸出前三個指令的 X 總和值。其中第四個為迴圈架構。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
begin
forward 10
left 90
forward 10
left 90
forward 10
left 90
forward 10
left 90
end
begin
forward 10
left 90
forward 10
left 90
forward 10
left 90
forward 10
left 90
end

Sample Output

1
2
360 0 40
360 0 40

Solution

由於輸入沒有迴圈，差點忘了有 repeat 指令。遞迴讀進輸入即可。

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
#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;
const long long mod = 1000003;
char s[128];
void dfs(long long cmd[]) {
    scanf("%s", s);
    if (s[0] == 'e' || s[0] == ']')    return;
    long long x, ncmd[3] = {};
    scanf("%lld", &x);
    if (s[0] == 'l')
        cmd[0] += x, dfs(ncmd);
    else if (s[0] == 'r' && s[1] == 'i')
        cmd[1] += x, dfs(ncmd);
    else if (s[0] == 'f')
        cmd[2] += x, dfs(ncmd);
    else if (s[0] == 'r' && s[1] == 'e'){
        scanf("%*s");
        dfs(cmd);
        for (int i = 0; i < 3; i++)
            cmd[i] = (cmd[i] * x) %mod;
        dfs(ncmd);
    }
    for (int i = 0; i < 3; i++)
        cmd[i] = (cmd[i] + ncmd[i]) %mod;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%*s");
        long long cmd[3] = {};
        dfs(cmd);
        printf("%lld %lld %lld\n", cmd[0], cmd[1], cmd[2]);
    }
    return 0;
}
/*
 2
 begin
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 end
 begin
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 end */
Read More +
解題區►解題區 - UVa

UVa 12810 - Sumthing

Problem

$$S(1) = \sum_{i=1}^{n} A[i] \\ S(2) = 2 \sum_{i=1}^{n} \sum_{j=i+1}^{n} A[i] A[j] \\ S(3) = 2^{2} \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} A[i] A[j] A[k] \\ ...$$

將 S(1) … S(n) 加總後 mod 1000000009 輸出。

Sample Input

1
2
3
4
5
2
3
1 2 3
5
2 3 5 7 11

Sample Output

1
2
52
66412

Solution

特別發現到 1000000009 是質數，對於任意一個數字都存在乘法反元素，那麼將總和定義為

$$(1 + 2 A[0])(1 + 2 A[1])(1 + 2 A[2]) ... (1 + 2 A[n])/2 \text{ mod } 1000000009$$

/2 部分利用乘上 2 在 mod 1000000009 下的反元素即可。

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
#include <stdio.h> 
const long long mod = 1000000009LL;
long long mpow(long long x, long long y, long long mod) {
	long long ret = 1;
	while (y) {
		if (y&1)
			ret = (ret * x)%mod;
		y >>= 1, x = (x * x)%mod;
	}
	return ret;
} 
int main() {
	int testcase, n;
	long long div2 = mpow(2, mod-2, mod);
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		long long p = 1, x;
		for (int i = 0; i < n; i++) {
			scanf("%lld", &x);
			p *= (1 + x * 2);
			p %= mod;
		}
		p = ((p - 1) * div2)%mod;
		printf("%lld\n", p);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12809 - Binary Search Tree

Problem

類似 UVa 10304 - Optimal Binary Search Tree，給每個節點的拜訪頻率，建造一個二元樹，使得詢問次數最小化。

Sample Input

1
2
3
4
5
6
3
0.33 0.34 0.33
3
0.8 0.15 0.05
4
0.23 0.4 0.17 0.2

Sample Output

1
2
3
1.6600
1.2500
1.7700

Solution

套用四邊形不等式進行優化。

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
#include <stdio.h> 
#include <string.h> 
double f[128];
double sum[128], w[128][128];
double dp[128][128];
int arg[128][128];
int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		for (int i = 1; i <= n; i++)
			scanf("%lf", &f[i]);
		sum[0] = 0;
		for (int i = 1; i <= n; i++)
			sum[i] = sum[i-1] + f[i];
		for (int i = 1; i <= n; i++)
			for (int j = i; j <= n; j++)
				w[i][j] = sum[j] - sum[i - 1];
		for (int i = 0; i <= n; i++)
			dp[i][i] = 0, arg[i][i] = i;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; i + j <= n; j++) {
				double mn = 1e+30;
				int idx = -1;
				for (int k = arg[j][i+j-1]; k <= arg[j+1][i+j]; k++) {
					double t = dp[j][k-1] + dp[k+1][i+j] + w[j][k-1] + w[k+1][i+j];
					if (t < mn)
						mn = t, idx = k;
				}
				dp[j][i+j] = mn, arg[j][i+j] = idx;
			}
		}
		printf("%lf\n", dp[1][n] + 1);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12786 - Friendship Networks

Problem

類似 UVa 10720 - Graph Construction，給一個無向圖的每一個節點 degree，請問是否能構成圖。

Sample Input

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

Sample Output

1
2
3
1
0
1

Solution

使用公式加二分。

Erdős–Gallai theorem

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
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int n, i, k;
long long sum[1005], d[1005];
int main() {
    while(scanf("%d", &n) == 1 && n) {
        sum[0] = 0;
        for(i = 0; i < n; i++)
            scanf("%lld", &d[i]);
        sort(d, d+n, greater<int>());
        for(i = 0; i < n; i++)
            sum[i+1] = sum[i] + d[i];
        long long left = 0, right;
        int ret = 1;
        if(sum[n]&1)    ret = 0;
        for(k = 0; k < n; k++) {
            left += d[k];
            right = (long long)k * (k+1);
            int l =  lower_bound(d , d + n, k+1, greater<int>()) - d;
            if(l < k+1)
                right += sum[n] - sum[k+1];
            else
                right += sum[n] - sum[l] + (long long)(k+1)*(l - k - 1);
            if(left > right)	ret = 0;
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12776 - Query for Divisor-free Numbers

Problem

給一個序列 A，請問在 A[l:r] 中 A[i] 不被 A[j] 整除的個數為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3

Sample Output

1
2
3
4
5
6
7
8
9
10
Case 1:
4
3
4
4
4
Case 2:
1
2
1

Solution

首先先貪心 A[i]，找到左側最鄰近的因數、右側最鄰近的因數的位置找出 L[i], R[i]。

以下使用 binary indexed tree 進行區域操作。

然後對於詢問 [l, r] 事先讀進來，加入掃描線算法，確保能夠詢問 [l, r] 時，找尋 BIT[r] 的值為何。

掃描時，當我們遇到某個因數所展開的區間 [L[i], R[i]] 的左端點

  • 對於 BIT[i, R[i]] 範圍元素都加上 1，而在遇到區間對應的 A[i] 位置進行移除區間 (不用等到右端點，必須在中間就移除掉，確保查詢的時 A[i] 還在裡面)，BIT[i, R[i]] 範圍元素都減去 1。
  • 對於遇到詢問 [l, r] 的左端點時，詢問 BIT[r] 的值為何。

因此資料結構要維護

  • 將一個區間內的元素都加上 k
  • 詢問某個元素值
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
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define maxL (50000>>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[32767], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
vector< pair<int, int> > factor(int n) {
	int on = n;
	vector< pair<int, int> > R;
	
	for(int i = 0, j; i < Pt && 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(P[i], j));
		}
	}
	if(n != 1)	R.push_back(make_pair(n, 1));
	return R;
}
void make(int idx, int n, int m, vector< pair<int, int> > &v, vector<int> &ret) {
	if(idx == v.size()) {
		ret.push_back(m);
		return;
	}
	int a = m, b = v[idx].first;
	for(int i = v[idx].second; i >= 0; i--)
		make(idx + 1, n, a, v, ret), a *= b;
}
int A[131072], L[131072], R[131072];
vector<int> Af[131072], RM[131072];
vector< pair<int, int> > Q[131072], QL[131072];
int OUT[131072];
int BIT[131072];
void modify(int x, int val, int L) {
	while (x <= L) {
		BIT[x] += val;
		x += (x)&(-x);
	}
}
int query(int x) {
	int ret = 0;
	while (x) {
		ret += BIT[x];
		x -= (x)&(-x);
	}
	return ret;
}
int main() {
//		freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
	sieve();
	int testcase, cases = 0;
	int n, m, x, y;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &A[i]);
			vector< pair<int, int> > f = factor(A[i]);
			Af[i].clear();
			make(0, A[i], 1, f, Af[i]);
		}
		for (int i = 0; i < n + 20; i++)
			Q[i].clear(), QL[i].clear(), RM[i].clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			Q[x].push_back(make_pair(y, i));
		}
		map<int, int> mp;
		map<int, int>::iterator mpit;
		for (int i = 1; i <= n; i++) {
			x = 0;
			for (int j = 0; j < Af[i].size(); j++)
				x = max(x, mp[Af[i][j]]);
			mp[A[i]] = i;
			L[i] = x + 1;
		}
		mp.clear();
		for (int i = n; i >= 1; i--) {
			x = n + 1;
			for (int j = 0; j < Af[i].size(); j++) {
				mpit = mp.find(Af[i][j]);
				if (mpit != mp.end())
					x = min(x, mpit->second);
			}
			mp[A[i]] = i;
			R[i] = x - 1;
		}
		for (int i = 1; i <= n; i++) {
			QL[L[i]].push_back(make_pair(R[i], i));
			RM[i].push_back(R[i]);
		}
		for (int i = 1; i <= n + 20; i++)
			BIT[i] = 0;
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j < QL[i].size(); j++) {
				modify(QL[i][j].second, 1, n + 20);
				modify(QL[i][j].first + 1, -1, n + 20);
//				printf("add [%d %d]\n", QL[i][j].second, QL[i][j].first);
			}
			if (i)
			for (int j = 0; j < RM[i-1].size(); j++) {
				modify(i-1, -1, n + 20);
				modify(RM[i-1][j] + 1, 1, n + 20);
//				printf("rm [%d %d]\n", i-1, RM[i][j]);
			}
			for (int j = 0; j < Q[i].size(); j++) {
				int v = query(Q[i][j].first);
				OUT[Q[i][j].second] = v;
//				printf("%d %d - %d\n", Q[i][j].first, Q[i][j].second, v);
			}
//			puts("--");
		}
		printf("Case %d:\n", ++cases);
		for (int i = 0; i < m; i++)
			printf("%d\n", OUT[i]);
	}
	return 0;
}
/*
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3
*/
Read More +