UVa 13154 - Extreme XOR Sum

Problem

給一長度為 $N$ 的整數序列,詢問任意區間的極端異或和 Extreme XOR Sum。

定義 Extreme XOR Sum 為一系列操作的最後一個值

  • 當長度 $n>1$ 時,將陣列縮小為 $n-1$
  • $[a_0, a_1, a_2, \cdots, a_{n-1}]$,每一個元素與後一個元素運行互斥或,將會被轉換成 $[a_0 \oplus a_1, a_1\oplus a_2, a_2 \oplus a_3, \cdots, a_{n-2}\oplus a_{n-1}]$
  • 直到只剩下一個元素,即為 Extreme XOR Sum

Sample Input

1
2
3
4
5
6
7
1
5
1 4 6 7 8
3
0 0
0 1
2 4

Sample Output

1
2
3
4
Case 1:
1
5
14

Solution

這題詢問次數非常多,一般運行將對每一個詢問達到 $O(N)$ 的複雜度,這很容易得到 TLE。從大多的數據結構,如線段樹、塊狀表 … 等,他們提供高效率的查找效能,但也必須符合某些條件才能使用。因此,在此題若要符合結合律將變得相當困難。

觀察

假設要計算陣列 $[1, 4, 6, 7, 8]$ 的值時

  • 第一步,$[1 \oplus 4, 4 \oplus 6, 6 \oplus 7, 7 \oplus 8]$
  • 第二步,$[1 \oplus 4 \oplus 4 \oplus 6, \cdots]$
  • 如此類推下去,XOR 有結合律,我們發現到各別使用了 1 次 $a_0$、4 次 $a_1$、6 次 $a_2$、4 次 $a_3$ 和 1 次 $a_4$

對於不同的長度,我們發現到是二項係數的配對情況。由於偶數次的 XOR 會互消,只需要計算出現奇數次的即可,因此我們列出二項次數模二的情況,進而得到 Sierpinski triangle/Sierpinski sieve。即使知道 Sierpinski sieve 是二項係數模二的結果,我們仍不知道要怎麼套用結合律達到剖分加速的條件。

二項係數的公式如下

$$\begin{align*} \binom{n}{m} &= \binom{n-1}{m-1} + \binom{n-1}{m} \\ &= \frac{n!}{m!(n-m)!} \end{align*}$$

階層運算在數學運算上的性質並不多,逼得我們只好往碎形上觀察,以下列出前幾項的結果

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

發現它是一個很有趣的碎形,每個三角形大小都是以二的冪次的。我們按照 $2^3 = 8$ 切割一下上圖,並且把右邊斜的補上 0 得到下圖。

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
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
^---------------
1 0 0 0 0 0 0 0 |1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 |1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 |1 0 1 0 0 0 0 0
1 1 1 1 0 0 0 0 |1 1 1 1 0 0 0 0
1 0 0 0 1 0 0 0 |1 0 0 0 1 0 0 0
1 1 0 0 1 1 0 0 |1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0 |1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 |1 1 1 1 1 1 1 1
^----------------^--------------
1 0 0 0 0 0 0 0 |0 0 0 0 0 0 0 0 |1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 |0 0 0 0 0 0 0 0 |1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 |0 0 0 0 0 0 0 0 |1 0 1 0 0 0 0 0
1 1 1 1 0 0 0 0 |0 0 0 0 0 0 0 0 |1 1 1 1 0 0 0 0
1 0 0 0 1 0 0 0 |0 0 0 0 0 0 0 0 |1 0 0 0 1 0 0 0
1 1 0 0 1 1 0 0 |0 0 0 0 0 0 0 0 |1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0 |0 0 0 0 0 0 0 0 |1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 |0 0 0 0 0 0 0 0 |1 1 1 1 1 1 1 1
^ ^ ^
箭頭表示本身也是 Sierpinski sieve

區塊縮影得到 miniature pattern 也是 Sierpinski sieve
1
1 1
1 0 1

得到數個一模一樣的子圖,上述全零和非零的區塊,又恰好構成 Sierpinski sieve。這告訴我們任何操作全都要以二的冪次為基準,且合併區段時須以二項係數為係數。設定 pattern 大小為 $M=2^{\lceil \log_2 N\rceil}$,最後得到 miniature pattern。在同一層中,非零構成的條紋都是相同的模式,例如上述得圖中,最後一層的箭號組合必然是 101 或者是 000,最後得到下列公式計算條紋。

$A_{i, j} = A_{i-1}{j} \oplus A_{i-1,j+M}$

接下來,我們將需要確定每一個條紋 (stripe) 是否使用全零或者非零,只需要查找 miniature pattern 相應的係數即可。

如何在 Sierpinski sieve 找到非零係數的位置

$\binom{n}{i} \mod 2 = 1$,必滿足 $n\&i = i$。其證明從數學歸納法來,由二冪次的長度碎形著手,移除最高位的 1 得到 $i'$,從 $i'$ 舊有位置集合,保留此集合,並對每一個元素增加二的冪次得到碎形的另一邊。

故可利用下述算法,準確地找到每一個非零的係數位置

1
2
for (int pos = n; pos; pos = (pos-1)&n)
C[n][pos] mod 2 = 1

最後附上優化後得到 Rank 1 的程序 0.040 s

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
#include <bits/stdc++.h>
using namespace std;

static const int M = (1<<7);
static const int MAXN = 10005;
static int A[M+1][MAXN];
void miniature(int n) {
for (int i = 1; i*M < n; i++) {
for (int j = 0; j+i*M < n; j++)
A[i][j] = A[i-1][j] ^ A[i-1][j+M];
}
}
int extract(int l, int r) {
const int n = r-l;
const int m = n/M;
const int o = n%M;
int ret = A[m][l];
for (int i = o; i; i = (i-1)&o)
ret ^= A[m][l+i];
return ret;
}
namespace MM {
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
class Print {
public:
static const int N = 1048576;
char buf[N], *p, *end;
Print() {
p = buf, end = buf + N - 1;
}
void printInt(int x, char padding) {
static char stk[16];
int idx = 0;
stk[idx++] = padding;
if (!x)
stk[idx++] = '0';
while (x)
stk[idx++] = x%10 + '0', x /= 10;
while (idx) {
if (p == end) {
*p = '\0';
printf("%s", buf), p = buf;
}
*p = stk[--idx], p++;
}
}
void flush() {
*p = '\0', p = buf;
printf("%s", buf);
}
static inline void online_printInt(int x) {
static char ch[16];
static int idx;
idx = 0;
if (x == 0) ch[++idx] = 0;
while (x > 0) ch[++idx] = x % 10, x /= 10;
while (idx)
putchar(ch[idx--]+48);
}
~Print() {
*p = '\0';
printf("%s", buf);
}
} bprint;
}
int main() {
int testcase, cases = 0;
int n, m;
// scanf("%d", &testcase);
MM::ReadInt(&testcase);
while (testcase--) {
// scanf("%d", &n);
MM::ReadInt(&n);
for (int i = 0; i < n; i++)
// scanf("%d", &A[0][i]);
MM::ReadInt(&A[0][i]);
miniature(n);
// scanf("%d", &m);
MM::ReadInt(&m);
printf("Case %d:\n", ++cases);
for (int i = 0; i < m; i++) {
int l, r;
// scanf("%d %d", &l, &r);
MM::ReadInt(&l), MM::ReadInt(&r);
// printf("%d\n", extract(l, r));
MM::bprint.printInt(extract(l, r), '\n');
}
MM::bprint.flush();
}
return 0;
}
/*
1
5
1 4 6 7 8
3
0 0
0 1
2 4
*/

Read More +

UVa 13100 - Painting the Wall

Problem

給一張 $N \times M$ 的圖,用最少筆畫勾勒出指定圖像,每一筆只能平行於兩軸,並且輸出任意一組解。

Sample Input

1
2
3
4
5
6
5 7
.*...*.
.*...*.
.*****.
.*...*.
.*...*.

Sample Output

1
2
3
4
3
vline 2 1 5
vline 6 1 5
hline 3 2 6

Solution

明顯地,要繪製的座標 $(x, y)$,可以視為一條邊 $x \Rightarrow y$,只要挑選某些點就可以覆蓋相鄰邊即可,在二分圖上找最少點集覆蓋是 P 多項式時間內可解的,並且最少點集大小為最大匹配數。但這一題要求要連續的筆畫,因此需要針對給定的圖形進行重新編號,將不連續的 x 和 y 座標重新定義。

這裡採用 Dinic’s algorithm 解決二分匹配,最後利用貪心回溯的方式可以找到一組解。

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#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;
assert(n < MAXV);
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++];
assert(e < MAXE);
}
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;
const int MAXN = 1024*1024;
int mx[MAXN], my[MAXN];
int X[MAXN], Y[MAXN];
int n, m, VX, VY;
int C[MAXN][3], R[MAXN][3];
void dfs(int u) {
if (X[u]) return ;
X[u] = 1;
for (Edge *p = g.adj[u]; p != NULL; p = p->next) {
if (p->v - VX >= 1 && p->v - VX <= VY) {
if (my[p->v - VX] != -1 && Y[p->v - VX] == 0) {
Y[p->v - VX] = 1;
dfs(my[p->v - VX]);
}
}
}
}
int main() {
static char s[1024][1024];
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 1; i <= n; i++)
scanf("%s", s[i]+1);

static int xg[1024][1024] = {};
static int yg[1024][1024] = {};
memset(xg, 0, sizeof(xg));
memset(yg, 0, sizeof(yg));
VX = 0, VY = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i][j] == '*') {
if (xg[i][j] == 0) {
xg[i][j] = ++VX;
int k = j;
while (k <= m && s[i][k] == '*')
xg[i][k] = VX, k++;
C[VX][0] = i, C[VX][1] = j, C[VX][2] = k-1;
}
if (yg[i][j] == 0) {
yg[i][j] = ++VY;
int k = i;
while (k <= n && s[k][j] == '*')
yg[k][j] = VY, k++;
R[VY][0] = j, R[VY][1] = i, R[VY][2] = k-1;
}
}
}
}

int source = 0, sink = VX+VY+1;
g.Init(VX+VY+2);
for (int i = 1; i <= VX; i++)
g.Addedge(source, i, 1);
for (int i = 1; i <= VY; i++)
g.Addedge(VX+i, sink, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i][j] == '*') {
// printf("%d - %d\n", xg[i][j], yg[i][j]);
g.Addedge(xg[i][j], yg[i][j] + VX, 1);
}
}
}
int mxflow = g.Maxflow(source, sink);
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
memset(X, 0, sizeof(X));
memset(Y, 0, sizeof(Y));
int match = 0;
for (int i = 1; i <= VX; i++) {
for (Edge *p = g.adj[i]; p != NULL; p = p->next) {
int x = i, y = p->v, flow = p->flow;
if (flow == 0 && y - VX >= 1 && y - VX <= VY) {
// match x - (y - VX) in bipartite graph
int r = x, c = y - VX;
mx[r] = c;
my[c] = r;
match++;
}
}
}
assert(match == mxflow);

for (int i = 1; i <= VX; i++) {
if (mx[i] == -1)
dfs(i);
}

printf("%d\n", mxflow);
for (int i = 1; i <= VX; i++) {
if (!X[i] && mx[i] != -1) {
printf("hline %d %d %d\n", C[i][0], C[i][1], C[i][2]);
mxflow--;
}
}
for (int i = 1; i <= VY; i++) {
if (Y[i]) {
printf("vline %d %d %d\n", R[i][0], R[i][1], R[i][2]);
mxflow--;
}
}
assert(mxflow == 0);
}
return 0;
}
Read More +

UVa 13102 - Tobby Stones

Problem

$N$ 個石頭排成一列,一開始都是白色石頭,經過 $M$ 詢問,分別統計區間內的黑色、白色石頭個數。

操作分別有以下幾種:

1. 統計區間 [l, r] 的黑色、白色石頭個數。
2. 將區間 [l, r] 的石頭的排列反轉。
3. 將區間 [l, r] 的石頭的顏色反轉。
4. 將區間 [l, r] 的石頭的顏色全部改成 $c$

## Sample Input ##

1
2
3
4
5
6
7
8
9
10
10  7
0 0 9
3 0 4 0
0 0 4
1 0 9
0 5 9
2 5 9
0 3 9
100 1
0 0 50

Sample Output

1
2
3
4
5
0 10
5 0
5 0
0 7
0 51

Solution

用 Splay Tree 完成區間反轉,打個懶標記就可以完成,每個操作都可以在 $\mathcal{O}(\log 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
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 1048576;

class SPLAY_TREE { // Splay Tree
public:
static const int MAXN = 1048576;
struct Node {
static Node *EMPTY;
Node *ch[2], *fa;
char rev, set, inv, val;
int size;
int sumw, sumb;
Node() {
ch[0] = ch[1] = fa = NULL;
rev = set = inv = 0;
val = sumw = sumb = 0, size = 1;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
void pushdown() {
if (rev) {
if (ch[0] != EMPTY) ch[0]->rev ^= 1;
if (ch[1] != EMPTY) ch[1]->rev ^= 1;
swap(ch[0], ch[1]);
rev ^= 1;
}
if (set) {
if (ch[0] != EMPTY) ch[0]->set = set, ch[0]->inv = 0;
if (ch[1] != EMPTY) ch[1]->set = set, ch[1]->inv = 0;
if (set == 1) // white
val = 0, sumw = sumw + sumb, sumb = 0;
else
val = 1, sumb = sumw + sumb, sumw = 0;
set = 0, inv = 0;
}
if (inv) {
if (ch[0] != EMPTY) {
if (ch[0]->set)
ch[0]->set = 3 - ch[0]->set;
else
ch[0]->inv ^= 1;
}
if (ch[1] != EMPTY) {
if (ch[1]->set)
ch[1]->set = 3 - ch[1]->set;
else
ch[1]->inv ^= 1;
}
swap(sumw, sumb), val = !val;
inv = 0;
}
}
void pushup() {
if (ch[0] != EMPTY) ch[0]->pushdown();
if (ch[1] != EMPTY) ch[1]->pushdown();
sumw = sumb = 0;
if (val == 0) sumw++;
else sumb++;
sumw += ch[0]->sumw + ch[1]->sumw;
sumb += ch[0]->sumb + ch[1]->sumb;
size = 1 + ch[0]->size + ch[1]->size;
}
} _mem[MAXN];

int bufIdx;
SPLAY_TREE::Node *root;
SPLAY_TREE() {
Node::EMPTY = &_mem[0];
Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
Node::EMPTY->size = Node::EMPTY->val = 0;
bufIdx = 1;
}
void init() {
bufIdx = 1;
}
Node* newNode() {
Node *u = &_mem[bufIdx++];
*u = Node();
u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
y->pushup();
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
x->pushdown();
}
Node* find_rt(Node *x) {
for (; x->fa != Node::EMPTY; x = x->fa);
return x;
}
void splay(Node *x, Node *below) {
Node *y, *z;
deal(x);
while (!x->is_root() && x->fa != below) {
y = x->fa, z = y->fa;
if (!y->is_root() && y->fa != below) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
x->pushup();
if (x->fa == Node::EMPTY) root = x;
}
Node* build(int l, int r, Node *p, char s[]) {
if (l > r) return Node::EMPTY;
int mid = (l + r)/2;
Node *t = newNode();
t->val = s[mid], t->fa = p;
if (t->val == 0) t->sumw ++;
else t->sumb ++;
t->ch[0] = build(l, mid-1, t, s);
t->ch[1] = build(mid+1, r, t, s);
t->pushup();
if (p == Node::EMPTY) root = t;
return t;
}
void debug(Node *u){
if (u == Node::EMPTY) return;
u->pushdown();
debug(u->ch[0]);
printf("%d", u->val);
debug(u->ch[1]);
}
Node* kthNode(int pos) {
Node *u = root;
for (int t; u != Node::EMPTY;) {
u->pushdown();
t = u->ch[0]->size;
if (t+1 == pos) return u;
if (t >= pos)
u = u->ch[0];
else
pos -= t+1, u = u->ch[1];
}
return Node::EMPTY;
}
void insert(int pos, int val) {
Node *p, *q, *r;
p = kthNode(pos), q = kthNode(pos+1);
r = newNode();
splay(p, Node::EMPTY);
splay(q, root);
r->val = val, q->ch[0] = r, r->fa = q;
splay(r, Node::EMPTY);
}
void erase(int pos) {
Node *p, *q;
p = kthNode(pos-1), q = kthNode(pos+1);
splay(p, Node::EMPTY), splay(q, root);
q->ch[0] = Node::EMPTY;
splay(q, Node::EMPTY);
}
void reverse(int l, int r) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
q->ch[0]->rev ^= 1;
splay(q->ch[0], Node::EMPTY);
}
void inverse(int l, int r) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
q->ch[0]->inv ^= 1;
splay(q->ch[0], Node::EMPTY);
}
void reset(int l, int r, int c) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
if (c == 1) {
q->ch[0]->set = 1;
} else {
q->ch[0]->set = 2;
}
splay(q->ch[0], Node::EMPTY);
}
pair<int, int> stat(int l, int r) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
return make_pair(q->ch[0]->sumb, q->ch[0]->sumw);
}

} tree;
SPLAY_TREE::Node *SPLAY_TREE::Node::EMPTY;

int main() {
static char s[1048576] = {}; // white
int n, m, cmd, l, r, c;
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 0; i <= n+1; i++)
s[i] = 0;
tree.init();
tree.build(0, n+1, SPLAY_TREE::Node::EMPTY, s);
pair<int, int> ret;
for (int i = 0; i < m; i++) {
scanf("%d", &cmd);
if (cmd == 0) {
scanf("%d %d", &l, &r);
ret = tree.stat(l+1, r+1);
printf("%d %d\n", ret.first, ret.second);
} else if (cmd == 1) {
scanf("%d %d", &l, &r);
tree.reverse(l+1, r+1);
} else if (cmd == 2) {
scanf("%d %d", &l, &r);
tree.inverse(l+1, r+1);
} else if (cmd == 3) {
scanf("%d %d %d", &l, &r, &c);
tree.reset(l+1, r+1, c);
}
}
}
return 0;
}
Read More +

UVa 13101 - Tobby on Tree

Problem

一場遊戲有 $N$ 個數,每一次挑兩個不同的數,將大的數字扣除小的數字,直到沒辦法挑出任何不同的數,亦即所有數皆相同,遊戲結果就是最後的數字值。

現在給予一棵樹,操作有兩種:

  • 詢問樹上兩點 $u$$v$ 的路徑上的數字,遊戲結果為何。
  • 改變樹上某個節點 $u$ 的值為 $c$

Sample Input

1
2
3
4
5
6
7
8
9
10
5
5 15 20 15 9
0 2
0 3
3 1
3 4
3
1 2 1
2 3 3
1 1 4

Sample Output

1
2
5
3

Solution

明顯地答案就是路徑上所有數字的最大公因數,充分利用 Link/Cut Tree 的特性,解決樹上詢問的詢問即可。

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
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <bits/stdc++.h> 
using namespace std;

class LCT { // Link-Cut Tree
public:
static const int MAXN = 262144;
struct Node {
static Node *EMPTY;
Node *ch[2], *fa;
int rev;
int val, size;
int gcd;
Node() {
ch[0] = ch[1] = fa = NULL;
rev = 0;
val = 0;
gcd = 1, size = 1;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
void pushdown() {
if (rev) {
ch[0]->rev ^= 1, ch[1]->rev ^= 1;
swap(ch[0], ch[1]);
rev ^= 1;
}
}
void pushup() {
if (this == EMPTY) return ;
gcd = this->val, size = 1;
if (ch[0] != EMPTY) {
gcd = __gcd(gcd, ch[0]->gcd);
size += ch[0]->size;
}
if (ch[1] != EMPTY) {
gcd = __gcd(gcd, ch[1]->gcd);
size += ch[1]->size;
}
}
} _mem[MAXN];

int bufIdx;
LCT() {
Node::EMPTY = &_mem[0];
Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
Node::EMPTY->size = 0;
bufIdx = 1;
}
void init() {
bufIdx = 1;
}
Node* newNode() {
Node *u = &_mem[bufIdx++];
*u = Node();
u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
y->pushup(), x->pushup();
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
x->pushdown();
}
void splay(Node *x) {
Node *y, *z;
deal(x);
while (!x->is_root()) {
y = x->fa, z = y->fa;
if (!y->is_root()) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
x->pushup();
}
Node* access(Node *u) {
Node *v = Node::EMPTY;
for (; u != Node::EMPTY; u = u->fa) {
splay(u);
u->ch[1] = v;
v = u;
v->pushup();
}
return v;
}
void mk_root(Node *u) {
access(u)->rev ^= 1, splay(u);
}
void cut(Node *x, Node *y) {
mk_root(x);
access(y), splay(y);
y->ch[0] = x->fa = Node::EMPTY;
}
Node* _cut(Node *rt, Node *x) {
Node *u, *v;
mk_root(rt);
access(x), splay(x);
for (v = x->ch[0]; v->ch[1] != Node::EMPTY; v = v->ch[1]);
x->ch[0]->fa = x->fa;
x->fa = x->ch[0] = Node::EMPTY;
return v;
}
void link(Node *x, Node *y) {
mk_root(x);
x->fa = y;
}
Node* find(Node *x) {
for (x = access(x); x->pushdown(), x->ch[0] != Node::EMPTY; x = x->ch[0]);
return x;
}
//
int gcdPath(Node *x, Node *y) {
mk_root(x);
access(y), splay(y);
return y->gcd;
}
//
void changeNode(Node *x, int c) {
mk_root(x);
x->val = c;
}
void debug(int n) {
}
} tree;
LCT::Node *LCT::Node::EMPTY;
LCT::Node *A[262144];

int W[131072];
int main() {
int n, m, cmd, x, y;
while (scanf("%d", &n) == 1) {
for (int i = 0; i < n; i++)
scanf("%d", &W[i]);
tree.init();
for (int i = 0; i < n; i++) {
A[i] = tree.newNode();
A[i]->val = W[i];
}
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
tree.link(A[x], A[y]);
}
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &cmd, &x, &y);
if (cmd == 1) {
printf("%d\n", tree.gcdPath(A[x], A[y]));
} else {
tree.changeNode(A[x], y);
}
}
}
return 0;
}
/*
5
5 15 20 15 9
0 2
0 3
3 1
3 4
9999
1 2 1
1 1 3
2 3 3
1 1 4
1 1 3
*/

Read More +

UVa 13000 - VIP Treatment

Problem

$N$ 個工人和 $M$ 種工作,每一種工作分成兩種工作量 VIP 以及 Regular,有一些工作只能指派給特定工人完成。每名工人有各自的完成速度,請問最小化所有工作完成的最大時間為何?

Sample Input

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

Sample Output

1
2
3
Case 1: 48
Case 2: 18
Case 3: 6

Solution

二分時間,利用 maxflow 流滿的情況判定是否可以讓所有工人在限時內合作完成所有工作。

source - worker - job - sink,其中 source - worker 為工人能運作的最大工作量 time/W[i],worker - job 根據指派工人的配置,job - sink 為工作的 VIP 和 Regular 量。

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
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const long long LLINF = 1LL<<62;
typedef struct Edge {
int v;
long long 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, long long 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];
}
}
}
long long Maxflow(int s, int t){
long long ret = 0;
int 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){
long long update = LLINF;
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, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int M, N, K;
int W[64], V[64], R[64];
vector<int> WR[64];
int sumVIP = 0, maxW = 0;
scanf("%d %d %d", &M, &N, &K);
for (int i = 0; i < N; i++)
scanf("%d", &W[i]), maxW = max(maxW, W[i]);
for (int i = 0; i < M; i++) {
int n, x;
scanf("%d %d %d", &V[i], &R[i], &n);
WR[i].clear();
for (int j = 0; j < n; j++) {
scanf("%d", &x), x--;
WR[i].push_back(x);
}
sumVIP += V[i];
}

long long l = 0, r = (long long) maxW * (sumVIP + K), mid, ret = 0;
while (l <= r) {
mid = (l + r)/2;

long long time = mid;
int source = N + 2*M;
int sink1 = N + 2*M + 1; // VIP
int sink2 = N + 2*M + 2; // Regular
int sink = N + 2*M + 3;
g.Init(N + 2*M + 5);
for (int i = 0; i < N; i++) {
g.Addedge(source, i, time / W[i]);
// printf("e %d %d %d\n", source, i, time / W[i]);
}
g.Addedge(sink1, sink, sumVIP);
g.Addedge(sink2, sink, K);
// printf("e %d %d %d\n", sink1, sink, sumVIP);
// printf("e %d %d %d\n", sink2, sink, K);
for (int i = 0; i < M; i++) {
int u1 = N + 2*i, u2 = N + 2*i + 1;
g.Addedge(u1, sink1, V[i]);
g.Addedge(u2, sink2, R[i]);
// printf("e %d %d %d\n", u1, sink1, V[i]);
// printf("e %d %d %d\n", u2, sink2, R[i]);
for (int j = 0; j < WR[i].size(); j++) {
int v = WR[i][j];
// printf("e %d %d %d\n", v, u1, INF);
// printf("e %d %d %d\n", v, u2, INF);
g.Addedge(v, u1, LLINF);
g.Addedge(v, u2, LLINF);
}
}

long long flow = g.Maxflow(source, sink);
// printf("time %d: %d\n", time, flow);
if (flow == sumVIP + K)
r = mid - 1, ret = time;
else
l = mid + 1;
}
printf("Case %d: %lld\n", ++cases, ret);
}
return 0;
}
Read More +

UVa 13070 - Palm trees in the snow

Problem

給一排棕梠樹的樹高 $H_i$,經過大雪後,高度 $H_i \ge W$ 的樹都會攤倒,挑選一個區間滿足最多五棵屹立不搖的情況下,請問區間長度最長為何?

Sample Input

1
2
3
4
5
6
7
8
9
10
3
30
10
10 30 50 20 40 60 30 40 50 36
40
10
10 30 50 20 40 20 10 10 20 36
20
3
40 10 15

Sample Output

1
2
3
7
10
3

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
#include <bits/stdc++.h>
using namespace std;

int main() {
int testcase;
scanf("%d", &testcase);
while (testcase--) {
int W, N, x;
scanf("%d %d", &W, &N);
vector<int> A;
A.push_back(-1);
for (int i = 0; i < N; i++) {
scanf("%d", &x);
if (x >= W)
A.push_back(i);
}
A.push_back(N);
int ret = 0;
for (int i = 1; i < A.size()-1; i++) {
int x = A[min(i+5, (int)A.size()-1)];
ret = max(ret, x - A[i-1]-1);
}
if (A.size() == 2) ret = N;
printf("%d\n", ret);
}
return 0;
}
Read More +

UVa 13036 - Birthday Gift to SJ - 2

Problem

問在區間 $[a, b]$ 之中最大的 interesting number,所謂的 interesting number 就是分解成數個費波納契數的乘積。

Sample Input

1
2
3
4
3
1 7
1 10
1 1000000000000000000

Sample Output

1
2
3
6
10
1000000000000000000

Solution

由於費波納契數成長速度非常快,用不著擔心會有好幾種不同數構成,因此可以採用中間相遇法,將前幾個小的費波納契數任意組合,後半則是剩餘的組合。至於要從哪裡開始拆團,必須手動測一下。

而這一題詢問次數非常多,儘管建好表,$\mathcal{O}(N \log N)$ 的搜索相當慢,甚至會 TLE,最好使用一次二分搜尋,或者利用單調性質降到 $\mathcal{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
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
// Algorithm: Meet in Middle
const int MAXN = 85;
const long long MAXV = 1e+18;
long long F[100] = {2, 3};
vector<long long> S1, S2;
void bfs(int begin, int end, vector<long long> &S) {
S.push_back(1);
for (int i = begin; i < end; i++) {
long long x = F[i];
vector<long long> next(S);
for (auto e : S) {
while (MAXV / e / x) {
e *= x;
next.push_back(e);
}
}
S = next;
}
sort(S.begin(), S.end());
S.resize(unique(S.begin(), S.end()) - S.begin());
}

int main() {
for (int i = 2; i < MAXN; i++) {
F[i] = F[i-1] + F[i-2];
assert(F[i] / MAXV == 0);
}
int split = 9;
bfs(0, split, S1);
bfs(split, MAXN, S2);
int testcase;
scanf("%d", &testcase);
while (testcase--) {
long long a, b;
long long ret = -1;
scanf("%lld %lld", &a, &b);
int idx1 = 0, idx2 = S2.size()-1;
for (; idx1 < S1.size(); idx1++) {
if (S1[idx1] > b) break;
long long e = S1[idx1];
while (idx2 > 0 && b / S2[idx2] / e == 0)
idx2--;
long long t = S2[idx2] * e;
if (t >= a)
ret = max(ret, t);
}
vector<long long>::iterator it = lower_bound(S1.begin(), S1.end(), b);
if (it == S1.end() || it != S1.begin() && *it > b) it--;
if (it != S1.end() && b / *it) {
long long t = *it;
if (t >= a)
ret = max(ret, t);
}
it = lower_bound(S2.begin(), S2.end(), b);
if (it == S2.end() || it != S2.begin() && *it > b) it--;
if (it != S2.end() && b / *it) {
long long t = *it;
if (t >= a)
ret = max(ret, t);
}
printf("%lld\n", ret);
}
return 0;
}
/*
1
5231711 13073137
*/

Read More +

UVa 13057 - Prove Them All

Problem

這家公司有自動推論引擎,請問至少要證明幾個基礎定理後,剩餘的都可以藉由推論引擎得到?

Sample Input

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

Sample Output

1
Case 1: 2

Solution

把這張圖的所有 SCC 元件全部縮成一點,變成 DAG 後,計算有幾個節點的 indegree 等於零,其零的個數就是答案。

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
#include <bits/stdc++.h>
using namespace std;
// similar as UVa 11504 - Dominos
// algorithm: SCC
const int MAXN = 32767;
class SCC {
public:
int n;
vector<int> g[MAXN], dag[MAXN];
// <SCC begin>
int vfind[MAXN], findIdx;
int stk[MAXN], stkIdx;
int in_stk[MAXN], visited[MAXN];
int contract[MAXN];
int scc_cnt;
// <SCC end>
int scc(int u) {
in_stk[u] = visited[u] = 1;
stk[++stkIdx] = u, vfind[u] = ++findIdx;
int mn = vfind[u], v;
for(int i = 0; i < g[u].size(); i++) {
v = g[u][i];
if(!visited[v])
mn = min(mn, scc(v));
if(in_stk[v])
mn = min(mn, vfind[v]);
}
if(mn == vfind[u]) {
do {
in_stk[stk[stkIdx]] = 0;
contract[stk[stkIdx]] = scc_cnt;
} while(stk[stkIdx--] != u);
scc_cnt++;
}
return mn;
}
void addEdge(int u, int v) { // u -> v
g[u].push_back(v);
}
void solve() {
for (int i = 0; i < n; i++)
visited[i] = in_stk[i] = 0;
scc_cnt = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
stkIdx = findIdx = 0;
scc(i);
}
}
void make_DAG() {
int x, y;
for (int i = 0; i < n; i++) {
x = contract[i];
for (int j = 0; j < g[i].size(); j++) {
y = contract[g[i][j]];
if (x != y)
dag[x].push_back(y);
}
}
for (int i = 0; i < scc_cnt; i++) {
sort(dag[i].begin(), dag[i].end());
dag[i].resize(unique(dag[i].begin(), dag[i].end()) - dag[i].begin());
}
}
void init(int n) {
this->n = n;
for (int i = 0; i < n; i++)
g[i].clear(), dag[i].clear();
}
} g;

int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int n, m, u, v;
scanf("%d %d", &n, &m);
g.init(n);
for (int i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
u--, v--;
g.addEdge(u, v);
}
g.solve();
g.make_DAG();

int indeg[MAXN] = {}, ret = 0;
for (int i = 0; i < g.scc_cnt; i++) {
for (auto &e : g.dag[i]) {
indeg[e]++;
}
}
for (int i = 0; i < g.scc_cnt; i++)
ret += indeg[i] == 0;
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}
Read More +

UVa 13015 - Promotions

Problem

$N$ 名員工,他們彼此之間會推薦、相互提拔對方,因此站在公司的角度來看,提拔順序不能違反這張圖的上下關係,亦即若要提拔某人,其推薦他的人全部都要被提拔。請問若要提拔 $A$ 個人,有哪些人一定會被提拔,同樣的,回答提拔 $B$ 個人的情況,最後回答,若提拔 $B$ 個人,誰一定不會被提拔?

Sample Input

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

Sample Output

1
2
3
2
4
3

Solution

一定是張 DAG,否則不能處理。對於輸入多存一張反向圖,接著每一次都去找其下屬節點有多少個,藉此構造出任何提拔方案中,最好和最差排名為多少。處理全部排名計算 $\mathcal{O}(V^2 E)$

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
#include <bits/stdc++.h>
using namespace std;
// O(VE)
const int MAXN = 5005;
int A, B, E, P;
vector<int> G[MAXN], invG[MAXN];
int used[MAXN] = {}, cases = 0;
int dfs(int u, vector<int> g[]) {
if (used[u] == cases) return 0;
used[u] = cases;
int ret = 1;
for (auto v : g[u])
ret += dfs(v, g);
return ret;
}
int main() {
int x, y;
while (scanf("%d %d %d %d", &A, &B, &E, &P) == 4) {
for (int i = 0; i < E; i++)
G[i].clear(), invG[i].clear();
// Must DAG
for (int i = 0; i < P; i++) {
scanf("%d %d", &x, &y);
G[x].push_back(y), invG[y].push_back(x);
}

int retA = 0, retB = 0, retN = 0;
for (int i = 0; i < E; i++) {
int worst, best;
cases++;
worst = E - dfs(i, G) + 1;
cases++;
best = dfs(i, invG);
if (worst <= A) retA++;
if (worst <= B) retB++;
if (best > B) retN++;
}
printf("%d\n%d\n%d\n", retA, retB, retN);
}
return 0;
}
Read More +

UVa 13024 - Saint John Festival

Problem

給予 $N$ 個大天燈的所在位置,隨後有 $Q$ 個小天燈位置,施放天燈後,請問有多少小天燈處於任三個天燈構成的三角形內部?

Sample Input

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

Sample Output

1
3

Solution

由於只詢問任意三個點構成的三角形內部,貪心就能想到一定是挑選凸包上的三點,只需要判定某點是不是在凸包內部,由於所有天燈已經給定,只需要跑一次 $\mathcal{O}(N \log N)$ 凸包算法,接著詢問一點是否在凸包內,只需要 $\mathcal{O}(\log 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
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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
#define eps 1e-10
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;
}
bool operator==(const Pt &a) const {
return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
}
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 val) const {
return Pt(x / val, y / val);
}
Pt operator*(const double val) const {
return Pt(x * val, y * val);
}
};
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 monotone(int n, Pt p[], Pt ch[]) {
sort(p, p+n);
int i, m = 0, t;
for (i = 0; i < n; i++) {
while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
for (i = n-1, t = m+1; i >= 0; i--) {
while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
return m-1;
}

double g(Pt a, Pt b, double x) {
Pt vab = b - a;
return a.y + vab.y * (x - a.x) / vab.x;
}
int inside_convex(const Pt &p, Pt ch[], int n) {
if (n < 3)
return false;
if (cross(ch[0], p, ch[1]) > eps)
return false;
if (cross(ch[0], p, ch[n-1]) < -eps)
return false;

int l = 2, r = n-1;
int line = -1;
while (l <= r) {
int mid = (l + r)>>1;
if (cross(ch[0],p, ch[mid]) > -eps) {
line = mid;
r = mid - 1;
} else l = mid + 1;
}
return cross(ch[line-1], p, ch[line]) < eps;
}
Pt D[131072], ch[262144];
int main() {
int testcase, n, m;
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);
}
n = monotone(n, D, ch);
scanf("%d", &m);
int ret = 0;
for (int i = 0; i < m; i++) {
scanf("%lf %lf", &x, &y);
int f = inside_convex(Pt(x, y), ch, n);
ret += f;
}
printf("%d\n", ret);
}
return 0;
}
Read More +