解題區►解題區 - Zerojudge

b315. 紅圓茵可的考驗

內容 ：

身為魔法師的你，想讓自己變得更強大，於是前來膜拜紅圓茵可，同時想請教他學習魔法的秘訣。經過日復一日的嘗試，你終於通過了柏油路，並且來到茵可家。「看在你這麼努力的份上，我就稍微指導你一下吧。」茵可說道。「所謂魔法，跟程式設計很像，就是一堆指令的結合。將分子移動、放熱、發光等等基礎的小魔法結合在一起，就會變成強大的魔法(像是防護罩就是控制空氣分子的移動，並使其重新排列成為堅固的結構，達到防禦的效果。)。所以說，腦中運算的能力是很重要的。」語畢，茵可大大丟給你一個題目:

給你N個數字，挑出其中兩個數字可以得到一個數字差(非負)，而N個數字會有N*(N-1)/2個數字差，問第K大數字差是多少?
如範例輸入，數字差有6個，分別為9(10-1)、7(8-1)、5(10-5)、4(5-1)、3(8-5)、2(10-8)，其中第5大的是3。

「等你能在1秒內解完這個問題再來找我吧!」隨後茵可打開比較大的門走掉了。

輸入說明 ：

第一行有兩個正整數N,K
接下來有N個整數(0<=每個整數<=1,000,000,000)

測資

  1. N<=10，K<=N*(N-1)/2
  2. N<=1,000，K<=N*(N-1)/2
  3. N<=10,000，K<=10,000
  4. N<=100,000，K<=100,000
  5. N<=100,000，K<=1,000,000,000

輸出說明 ：

輸出第K大數字差

範例輸入 ：

1
2
4 5
1 5 8 10

範例輸出 ：

1
3

Solution

使用二分搜索答案，通常是查找第 K 小的元素，這題是換成第 K 大元素，那麼就反過來找，中間調校的時候要特別小心。

代碼效率是 O(n log^2 n)，事實上可以壓成 O(n 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
#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int kThDiff(int A[], int n, long long m) {
	int mx = A[0], mn = A[0];
	for (int i = 0; i < n; i++)
		mx = max(mx, A[i]), mn = min(mn, A[i]);
	int l = 0, r = mx - mn, mid, ret;
	m = (long long) n * (n-1)/2 - m + 1;
	long long cnt;
	sort(A, A+n);
	while (l <= r) {
		mid = (l + r)/2;
		cnt = 0;
		for (int i = 0; i < n; i++) {
			int pos = (int)(upper_bound(A+i, A+n, A[i] + mid) - A);
			cnt += pos - i - 1;
		}
		if (cnt >= m)
			r = mid - 1, ret = mid;
		else
			l = mid + 1;
	} 
	return ret;
}
int main() {
	int n, m, A[131072];
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		printf("%d\n", kThDiff(A, n, m));
	}
	return 0;
}
/*
9 4
4 6 3 7 7 5 0 8 9 
5 1
7 4 2 5 2 
10 3
4 6 9 8 7 1 1 4 2 0 
9 20
3 8 6 2 1 9 6 7 2 
2 1
2 6 
4 4
0 9 0 0 
5 7
4 0 9 1 8 
11 30
1 2 1 6 1 0 7 7 5 2 5 
4 3
4 7 5 8 
2 1
1 6 
10 40
7 5 5 0 2 9 4 9 6 2 
3 2
6 8 7 
10 28
3 5 0 8 1 1 7 9 2 1 
9 3
6 7 1 2 0 8 5 1 0 
8 22
0 3 1 9 1 8 4 7 
11 20
2 3 0 4 7 1 7 6 2 2 1 
3 1
7 3 9 
4 2
9 2 4 5 
10 39
6 5 2 3 6 1 1 8 1 9 
8 7
4 9 7 2 1 6 3 2 
*/
Read More +
解題區►解題區 - Zerojudge

b314. 紅圓茵可的煩惱

內容 ：

相信大家都知道紅圓茵可是誰，就不多介紹了。最近他有一個煩惱，身為一位大魔法師，每天都有成千上萬的人來膜拜他<( )>。因為人數實在太多了，這麼多人跑到他家膜拜他，害他都無法好好練習魔法了。茵可家門前有一條柏油路，要到他家一定得經過這條柏油路，他決定把這條柏油路(長方形)切成N*M個格子，並且在其中某些格子設下陷阱，踩到陷阱的人會被傳送回柏油路的起點。「恩~這樣子就可以減少膜拜我的人了~」紅圓茵可心想。但是，為了讓jackyXX等人可以到達他家，也不能把柏油路封死，必須確保一定有條路徑可以走到茵可家。而你的任務是要提醒茵可大大<( )>，哪些點能放陷阱，而哪些點不能放陷阱(導致道路封死)。
柏油路的起點在左邊，而茵可家在柏油路的右邊。一個人在柏油路上只能往上下左右四個方向走，不能走斜對角。

一條3*10的柏油路

oooooooooo
oooooooooo
oooooooooo

一條被封死的柏油路

ooooxooooo
oooxoooooo
ooxooooooo

一條沒被封死的柏油路

xxxxxxoooo
oooooxoxxx
ooxxoooxoo

輸入說明 ：

第一行有3個正整數N、M、T，T為茵可接下來要放的陷阱數量(0<T<=N*M)。
接下來T行每行有2個非負整數x,y表示這個陷阱要放的位址。
縱軸為x軸，橫軸為y軸，左下角那格為(0,0)。
保證一個點只會被放最多一次。

測資

  1. N,M<=10
  2. N,M<=50
  3. N,M<=100
  4. N,M<=1000
  5. N,M<=1000

輸出說明 ：

對每一個要放的陷阱，若該點可放，請輸出一行”<( )>”(不含雙引號)，並且把陷阱放上去。
若該點不可放(會導致道路封死)，請輸出”>_<”(不含雙引號)，並且不放該陷阱。

範例輸入 ：

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

範例輸出 ：

1
2
3
4
5
<(_ _)>
<(_ _)>
>_<
>_<
<(_ _)>

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
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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int parent[1048576], weight[1048576];
int used[1024][1024];
const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
const int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};
int findp(int x) {
	return parent[x] == x ? parent[x] : parent[x] = findp(parent[x]);
}
int joint(int p, int q) {
	p = findp(p), q = findp(q);
	if (weight[p] > weight[q])
		weight[p] += weight[q], parent[q] = p;
	else
		weight[q] += weight[p], parent[p] = q;
	return 1;
}
int main() {
	int n, m, Q, cases = 0;
	int x, y, tx, ty;
	while (scanf("%d %d %d", &n, &m, &Q) == 3) {
		cases++;
		int N = n * m + 10, up = n * m + 1, down = n * m + 2;
		int p, q, A[8];
		for (int i = 0; i < N; i++)
			parent[i] = i, weight[i] = 1;
		for (int i = 0; i < Q; i++) {
			scanf("%d %d", &x, &y);
			p = x * m + y;
			up = findp(up), down = findp(down);
			int s = 0;
			for (int j = 0; j < 8; j++)	{
				tx = x + dx[j], ty = y + dy[j];
				if (ty < 0 || ty >= m)	{
					A[j] = p;
					continue;
				}
				if (tx < 0)			q = up;
				else if(tx >= n)	q = down;
				else {
					if (used[tx][ty] != cases) {
						A[j] = p;
						continue;
					}
					q = tx * m + ty;
				}
				if (findp(q) == up)		s |= 1;
				if (findp(q) == down)	s |= 2;
				A[j] = q;
			}
			if (s != 3) {
				puts("<(_ _)>");
				for (int j = 0; j < 8; j++) {
					joint(p, A[j]);
				}
				used[x][y] = cases;
			} else {
				puts(">_<");
			}
		}
	}
	return 0;
}
Read More +
解題區►解題區 - Zerojudge

a577. 高精度乘法

Problem

這題十分直接，就是要你計算兩個很大的數字的乘積。

Sample Input

1
2
3
4
5
0
5
11
12

Sample Output

1
2
0
132

Solution

快速傅立葉 FFT 對我來說也是一知半解，但是我能知道他計算旋積可以在 O(n log n) 完成 n 個答案結果。

旋積計算就是對於維度為 n 的兩個向量，相互作內積，其中一個向量不斷地作 rotate shift right 的操作，因此會有 n 個內積結果。

如果要套用在這一題，相當於操作多項式乘法的計算，舉個例子來說

123 x 456

相當於下面兩個向量作旋積

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 4, 5, 6)
dot = 0
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 4, 5, 6, 0)
dot = 0
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 4, 5, 6, 0, 0)
dot = 0
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 4, 5, 6, 0, 0, 0)
dot = 4
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 4, 5, 6, 0, 0, 0, 0)
dot = 13

如此類推，不過 FFT 只能使用 double 運算，因此在儲存精度上不是很好拿捏，誤差大概在 1e-1 ~ 1e-2 之間。

感謝 liouzhou_101 的誤差指導

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
#include <complex>
#include <cmath>
using namespace std;
#define for if (0); else for
using namespace std;
const int MaxFastBits = 16;
int **gFFTBitTable = 0;
int NumberOfBitsNeeded(int PowerOfTwo) {
	for (int i = 0;; ++i) {
		if (PowerOfTwo & (1 << i)) {
			return i;
		}
	}
}
int ReverseBits(int index, int NumBits) {
	int ret = 0;
	for (int i = 0; i < NumBits; ++i, index >>= 1) {
		ret = (ret << 1) | (index & 1);
	}
	return ret;
}
void InitFFT() {
    gFFTBitTable = new int *[MaxFastBits];
    for (int i = 1, length = 2; i <= MaxFastBits; ++i, length <<= 1) {
        gFFTBitTable[i - 1] = new int[length];
        for (int j = 0; j < length; ++j) {
            gFFTBitTable[i - 1][j] = ReverseBits(j, i);
		}
    }
}
inline int FastReverseBits(int i, int NumBits) {
    return NumBits <= MaxFastBits ? gFFTBitTable[NumBits - 1][i] : ReverseBits(i, NumBits);
}
void FFT(bool InverseTransform, vector<complex<double> >& In, vector<complex<double> >& Out) {
    if (!gFFTBitTable) { InitFFT(); }
    // simultaneous data copy and bit-reversal ordering into outputs
	int NumSamples = In.size();
    int NumBits = NumberOfBitsNeeded(NumSamples);
    for (int i = 0; i < NumSamples; ++i) {
		Out[FastReverseBits(i, NumBits)] = In[i];
    }
    // the FFT process
    double angle_numerator = acos(-1.) * (InverseTransform ? -2 : 2);
    for (int BlockEnd = 1, BlockSize = 2; BlockSize <= NumSamples; BlockSize <<= 1) {
        double delta_angle = angle_numerator / BlockSize;
        double sin1 = sin(-delta_angle);
        double cos1 = cos(-delta_angle);
        double sin2 = sin(-delta_angle * 2);
        double cos2 = cos(-delta_angle * 2);
        for (int i = 0; i < NumSamples; i += BlockSize) {
			complex<double> a1(cos1, sin1), a2(cos2, sin2);
            for (int j = i, n = 0; n < BlockEnd; ++j, ++n) {
				complex<double> a0(2 * cos1 * a1.real() - a2.real(), 2 * cos1 * a1.imag() - a2.imag());
				a2 = a1;
				a1 = a0;
				complex<double> a = a0 * Out[j + BlockEnd];
				Out[j + BlockEnd] = Out[j] - a;
				Out[j] += a;
            }
        }
        BlockEnd = BlockSize;
    }
    // normalize if inverse transform
    if (InverseTransform) {
        for (int i = 0; i < NumSamples; ++i) {
			Out[i] /= NumSamples;
        }
    }
}
vector<double> convolution(vector<double> a, vector<double> b) {
	int n = a.size();
	vector<complex<double> > s(n), d1(n), d2(n), y(n);
    for (int i = 0; i < n; ++i) {
        s[i] = complex<double>(a[i], 0);
	}
    FFT(false, s, d1);
    s[0] = complex<double>(b[0], 0);
    for (int i = 1; i < n; ++i) {
		s[i] = complex<double>(b[n - i], 0);
	}
    FFT(false, s, d2);
    for (int i = 0; i < n; ++i) {
		y[i] = d1[i] * d2[i];
    }
    FFT(true, y, s);
	vector<double> ret(n);
	for (int i = 0; i < n; ++i) {
		ret[i] = s[i].real();
	}
	return ret;
}
struct Polynomial {
    vector<double> v;
    Polynomial operator*(const Polynomial &other) const {
        int n = (int) max(v.size(), other.v.size()) * 2, m;
        for (m = 2; m < n; m <<= 1);
        vector<double> na, nb;
        na.resize(m, 0), nb.resize(m, 0);
        for (int i = 0; i < v.size(); i++)
            na[i] = v[i];
        for (int i = 0, j = m - 1; i < other.v.size(); i++, j--)
            nb[j] = other.v[i];
        Polynomial ret;
        ret.v = convolution(na, nb);
        for (int i = 1; i < ret.v.size(); i++)
            ret.v[i - 1] = ret.v[i];
        ret.v[ret.v.size() - 1] = 0;
        return ret;
    }
};
char sa[1<<18], sb[1<<18];
long long ret[1<<19];
int main() {
    while (scanf("%s %s", sa, sb) == 2) {
        Polynomial a, b, c;
        for (int i = (int)strlen(sa) - 1; i >= 0; i--)
            a.v.push_back(sa[i] - '0');
        
        for (int i = (int)strlen(sb) - 1; i >= 0; i--)
            b.v.push_back(sb[i] - '0');
        c = a * b;
        
        memset(ret, 0, sizeof(ret));
        int f = 0;
        double eps = 1.5e-1;
        for (int i = 0; i < c.v.size(); i++)
            ret[i] = (long long) (c.v[i] + eps);
        int n = (int)c.v.size();
        for (int i = 0; i < n; i++) {
            if (ret[i] >= 10) {
                ret[i + 1] += ret[i]/10;
                ret[i] %= 10;
            }
        }
        for (int i = n; i >= 0; i--) {
            if (ret[i])
                f = 1;
            if (f)
                printf("%lld", ret[i]);
        }
        if (!f)
            printf("0");
        puts("");
    }
    return 0;
}
/*
 0
 5
 
 11
 12
 */
Read More +
解題區►解題區 - Zerojudge

b278. 说话不算话的区间求和

Problem

一个长度为n的数组a[1..n]，初始值为0,。要求你维护三种操作：

1 x v ：把数组的第x个元素改为v；(1≤x≤n,1≤v≤100,000,000)

2 x y ：询问数组元素a[x],a[x+1],…,a[y]之和；(1≤x≤y≤n)

0 k ：撤销最近的k次操作(注意，撤销操作本身也是操作，询问也算一次操作)。(1≤k≤当前操作次数)

Sample Input

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

Sample Output

1
2
3
1

Solution

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

這一題最麻煩的是對於版本回溯，對於撤銷操作而言，撤銷操作可以撤銷 “撤銷操作”，因此會不斷地展開原本被撤銷的相關操作，然後又將部分操作撤銷 … 反反覆覆，後來發現只要根據當前的版本號減去要撤銷操作的總數即可返回，因此必須記錄每一次操作的線段樹結果。

套用函數式線段樹就相當簡單了！

感謝 liouzhou_101 的題意指導

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 <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
#define MAXBUF 8388608
struct Node {
    int lson, rson;
    long long sum;
} node[MAXBUF + 50];
int nodesize = 0;
int root[524288];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int l, int r, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    if (l == r) {
        node[k].sum = val;
        return k;
    }
    int m = (l + r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, l, m, x, val);
    else
        node[k].rson = change(node[p].rson, m+1, r, x, val);
    node[k].sum = node[node[k].lson].sum + node[node[k].rson].sum;
    return k;
}
long long query(int k, int l, int r, int x, int y) {
    if (x <= l && r <= y)
        return node[k].sum;
    int m = (l + r)/2;
    long long sum = 0;
    if (x <= m) {
        sum += query(node[k].lson, l, m, x, y);
    }
    if (y > m) {
        sum += query(node[k].rson, m+1, r, x, y);
    }
    return sum;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        
        root[0] = build(1, n);
        
        int pre_ver = 0, cmd, x = 0, y = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &cmd, &x);
            if (cmd == 0) {
                y = 0;
                root[i] = root[i - x - 1];
                pre_ver = i;
            } else if (cmd == 1) {
                scanf("%d", &y);
                root[i] = change(root[pre_ver], 1, n, x, y);
                pre_ver = i;
            } else if (cmd == 2){
                scanf("%d", &y);
//                printf("query root = %d\n", root[pre_ver]);
                printf("%lld\n", query(root[pre_ver], 1, n, x, y));
                root[i] = root[pre_ver];
                pre_ver = i;
            }
            if (nodesize > MAXBUF) {
                return 0;
            }
        }
    }
    return 0;
}
/*
 2 5
 1 1 1
 1 2 2
 2 1 2
 0 2
 2 1 2
 */
Read More +
解題區►解題區 - Zerojudge

a331. K-th Number

Problem

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i…j] segment, if this segment was sorted?”
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Sample Input

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

Sample Output

1
2
3
5
6
3

Solution

之前使用過塊狀鏈表、歸併樹來完成這一題，其中速度快 歸併樹 > 函數式線段樹 > 塊狀鏈表，空間消耗大小 函數式線段樹 > 歸併樹 > 塊狀鏈表。

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

為了找到區間 K 大，使用函數式線段樹有點類似於掃描線算法，對於某個時間點依序將數字放進去，然後對於區間查詢 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[2097152];
int nodesize = 0;
int A[131072], B[131072], root[131072];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
int main() {
    int n, m, x, y, k;
    while (scanf("%d %d", &n, &m) == 2) {
        map<int, int> R;
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), R[A[i]] = 0;
        
        int size = 0;
        for (map<int, int>::iterator it = R.begin(); it != R.end(); it++) {
            it->second = ++size;
            B[it->second] = it->first;        
        }
        
        nodesize = 1;
        root[0] = build(1, size);
        
        for (int i = 1; i <= n; i++) {
            A[i] = R[A[i]];
            root[i] = change(root[i-1], A[i], 1);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &k);
            printf("%d\n", B[query(root[y], root[x-1], k)]);
        }
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */
Read More +
解題區►解題區 - Zerojudge

a858. 數三角形

題目

內容：

你有一個大小為N的完全圖，這N(N-1)/2條邊可能是紅色或黑色。任三個不同的點都形成一個三角形，請問三邊同色的三角形有幾個？

輸入說明：

第一行輸入一個正整數N，其中N<=1,000。接下來的N行，每行有N個數字，其中第i行的第j個數字代表邊(i,j)的顏色，紅色用1表示，黑色用2表示，i=j時則用0表示。

輸出說明：

請輸出同色三角形的數目。

範例輸入：

4
0 1 2 1
1 0 1 1
2 1 0 2
1 1 2 0

範例輸出：

1

解法

  • 作法：
    分治，將輸入 n 個劃分成兩堆，分別窮舉所有可能，採用合併的方式去運算。
a858.cpp 
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
/**********************************************************************************/
/*  Problem: a858 "數三角形" from                                             */
/*  Language: CPP (462 Bytes)                                                     */
/*  Result: AC(0.1s, 264KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-17 11:06:20                                     */
/**********************************************************************************/
#include <stdio.h>
int main() {
    int n, x;
    while (scanf("%d", &n) == 1) {
        int p = (n) * (n-1) * (n-2) / 6;
        int s = 0;
        for (int i = 0; i < n; i++) {
            int b = 0, r = 0;
            for(int j = 0; j < n; j++) {
                scanf("%d", &x);
                r += x == 1;
                b += x == 2;
            }
            s += r * b;
        }
        printf("%d\n", p - s/2);
    }
    return 0;
}
Read More +
解題區►解題區 - Zerojudge

a007. 判斷質數

題目

內容：

請判斷某數是否為質數

輸入說明：

輸入有多組測試資料（以EOF結尾），每組測試資料占一行，只包含一個整數x, 2 ≦ x ≦ 2147483647。

輸出說明：

對於每組測試資料，如果輸入的x為質數，則輸出一行「質數」（不含引號）；否則輸出一行「非質數」（不含引號）。詳見範例測試資料。

範例輸入：

13
14

範例輸出：

質數
非質數

解法

  • 作法：
    Miller-Rabin Algorithm
a007.cpp 
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
/**********************************************************************************/
/*  Problem: a007 "判斷質數"                                                  */
/*  Language: CPP (715 Bytes)                                                     */
/*  Result: AC(0.2s, 224KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 20:25:42                                     */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Pow(long long x, int n, long long mod) {
    long long Ans = 1, t = x;
    while(n) {
        if(n&1)
            Ans *= t, Ans %= mod;
        t *= t, t %= mod, n >>= 1;
    }
    return (int)Ans;
}
int JudgePrime(int n) {
    if(n == 2 || n == 3)    return 1;
    if(n == 1)    return 0;
    if(!(n&1))    return 0;
    int a, x, flag = 1, t;
    for(a = 0; a < 2; a++) {
        x = rand()%(n-4)+2;
        t = Pow(x, n-1, n);
        if(t != 1)    return 0;
    }
    return 1;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        if(JudgePrime(n))    puts("質數");
        else    puts("非質數");
    }
    return 0;
}
Read More +
解題區►解題區 - Zerojudge

a576. No Cheating

題目

內容：

有個學校想辦一場考試，提供了 T 間教室。每間教室的座位都是 M×N 的矩陣(不同教室的 M, N 可以不一樣)，而有的座位壞掉了不能坐。此外，為了避免學生作弊，如下圖，對任何一個學生而言，他的左方、左前方、右方、右前方都不可以有人坐。請問每間教室所能容納的學生數最多為何？

輸入說明：

第一行有一個數字 T，代表學校有 T 間教室。接下來會有每個教室的資料，每筆資料會有在同一行兩個正整數 M, N，代表座位的配置是 M×N。接下來的 M 行，每行有 N 個字元，’.’代表那個座位是好的，而’x’則代表那個座位壞了。

輸出說明：

對於每間教室，輸出”Case #X: Y”, 其中 X 代表這是第幾間教室，而 Y 則代表這間教室能容納的學生數最大值。

範例輸入：

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

範例輸出：

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46

解法

  • 作法：
    按列黑白染色，會發現不能連的位置恰好可以化成二分圖，求最大獨立集即可。
    最大獨立集 = 點個數 - 最大匹配數
a576.cpp 
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
/**********************************************************************************/
/*  Problem: a576 "No Cheating" from GCJ 2008 Round 3 C                           */
/*  Language: CPP (3826 Bytes)                                                    */
/*  Result: AC(0.1s, 1.2MB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 18:09:46                                     */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[65536];
int e, head[6500], prev[6500], record[6500];
int level[6500], visited[6500];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 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].v > 0 && 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].v > 0) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 1e+9, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].v);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].v -= flow;
                edge[ri^1].v += flow;
                if(edge[ri].v == 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;
}
int main() {
    int n, m;
    int testcase, cases = 0;
    int i, j, k, x, y;
    char g[128][128];
    int id[128][128];
    scanf("%d", &testcase);
    while(testcase--) {
        e = 0;
        memset(head, -1, sizeof(head));
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int ST[2] = {0, 0};
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(g[i][j] == '.') {
                    id[i][j] = ST[j&1]++;
                } else {
                    id[i][j] = -1;
                }
            }
        } 
        int source = ST[0] + ST[1];
        int sink = source + 1;
        for(int i = 0; i < ST[0]; i++)
            addEdge(source, i, 1);
        for(int i = 0; i < ST[1]; i++)
            addEdge(i + ST[0], sink, 1);
        int dx[] = {-1, -1, 0, 0, 1, 1};
        int dy[] = {-1, 1, -1, 1, 1, -1};
        int tx, ty, u, v;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j += 2) {
                if(id[i][j] == -1)  
                    continue;
                v = id[i][j];
                for(int k = 0; k < 6; k++) {
                    tx = i + dx[k];
                    ty = j + dy[k];
                    if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    u = id[tx][ty];
                    if(u == -1)
                        continue;
                    addEdge(v, u + ST[0], 1);
                }
            }
        }
        int ret = maxflowDinic(source, sink);
        printf("Case #%d: %d\n", ++cases, ST[0] + ST[1] - ret);
    }
    return 0;
}
Read More +
解題區►解題區 - Zerojudge

a962. 新專輯

題目

內容：

給定正整數N，請求出(N除以1的餘數)+(N除以2的餘數)+(N除以3的餘數)+…+(N除以N的餘數)。

輸入說明：

輸入只有一個正整數N，其中1<=N<=1014。

輸出說明：

為了避免要寫大數，你只要輸出這個奇怪的和除以1000000009的餘數就好了。

範例輸入：

10

範例輸出：

13

解法

  • 作法：
    各種方式要避免 mod 運算。
a962.cpp 
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
/**********************************************************************************/
/*  Problem: a962 "新專輯" from TIOJ 1674                                      */
/*  Language: CPP (1612 Bytes)                                                    */
/*  Result: AC(0.8s, 272KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 20:11:19                                     */
/**********************************************************************************/
#include <stdio.h>
#include <math.h>
#define MOD 1000000009LL
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;
    }
    if(i)
        return (la%mod+mod)%mod;
    return (ra%mod+mod)%mod;
}
int main() {
    long long inv2 = inv(2, MOD);
    long long n;
    while(scanf("%lld", &n) == 1) {
        long long ret = 0, hret = 0;
        long long half = (long long)sqrt(n)/5;
        long long u = -1, v = 0;
        for(half = 1; u != v; half++, u = v, v = n/half) {
            hret += n%half;
        }
        hret -= n%(half - 1);
        hret %= MOD;
        long long l = half - 1, r, div;
        long long a0, d, tn, buff;
        while(l <= n) {
            div = n / l;
            r = n / div;
            a0 = n % l, d = -div, tn = r - l + 1;
            if(tn >= MOD)   tn %= MOD;
            if(d >= MOD)    d %= MOD;
            if(a0 >= MOD)   a0 %= MOD;
            buff = (a0 * 2 + (tn - 1)*d);
            if(buff < 0 || buff >= MOD) buff %= MOD;
            buff *= tn;
            if(buff < 0 || buff >= MOD) buff %= MOD;
            ret += buff;
            l = r + 1;
        }
        ret %= MOD;
        ret = (ret * inv2)%MOD;
        ret = (ret + hret + MOD)%MOD;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
100000000000000
*/
Read More +
解題區►解題區 - Zerojudge

a981. 求和問題

題目

內容：

給你N個正整數, 試求哪幾個之和剛好為M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入說明：

n m (1<=n<=30, 1<=m<=100000000) n個正整數, 全部以空格分開

輸出說明：

  • 其和剛好等於m的數, 如果有多組解則按由小到大全部印出, 如果無解則印出 -1

範例輸入：

10 100
10 20 40 30 50 80 60 70 5 15

範例輸出：

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解法

  • 作法：
    分治，將輸入 n 個劃分成兩堆，分別窮舉所有可能，採用合併的方式去運算。
a981.cpp 
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 <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
	int n, m;
	int A[35];
	while(scanf("%d %d", &n, &m) == 2) {
		for(int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		sort(A, A + n, greater<int>());
		int h1Cnt = n / 2, h2Cnt = n - h1Cnt;
		map<long long, vector<int> > h1, h2;
		for(int i = (1<<h1Cnt)-1; i >= 0; i--) {
			long long sum = 0;
			for(int j = 0; j < h1Cnt; j++) {
				if((i>>j)&1)	sum += A[j];
			}
			h1[sum].push_back(i);
		}
		for(int i = (1<<h2Cnt)-1; i >= 0; i--) {
			long long sum = 0;
			for(int j = 0; j < h2Cnt; j++) {
				if((i>>j)&1)	sum += A[j + h1Cnt];
			}
			h2[sum].push_back(i<<h1Cnt);
		}
		set<int> ret;
		for(map<long long, vector<int> >::iterator it = h1.begin();
			it != h1.end(); it++) {
			long long f = (long long)m - it->first;
			map<long long, vector<int> >::iterator jt = h2.find(f);
			if(jt != h2.end()) {
				for(vector<int>::iterator iv = it->second.begin();
					iv != it->second.end(); iv++) {
					for(vector<int>::iterator jv = jt->second.begin();
						jv != jt->second.end(); jv++) {
						ret.insert(*iv| *jv);
					}
				}
			}
		}
		if(ret.size() == 0)
			puts("-1");
		for(set<int>::reverse_iterator it = ret.rbegin();
			it != ret.rend(); it++) {
			for(int i = n-1; i >= 0; i--) {
				if(((*it)>>i)&1) {
					printf("%d ", A[i]);
				}
			}
			puts("");
		}
	}
	return 0;
}
Read More +