算法期末复习小记

很久不写题,手法生疏.. 做个简短记录吧,或是卡的比较久的题,或是手生忘记怎么写的题.

  • Dynamic Median:堆
  • Ultra-QuickSort:线段树+离散化/树状数组+离散化/归并
  • 重要逆序对:归并/线段树+离散化/树状数组+离散化

Dynamic Median

http://algorithm.openjudge.cn/19exfinalsim/C

不算困难的题目… 用对顶堆解决:建一个最大堆 max_heap 和一个最小堆 min_heap,保持:

  1. max_heap 的堆顶始终小于等于 min_heap 的堆顶;
  2. 两个堆的元素个数差不超过 \(1\). 事实上,保持 max_heap 元素更多,且比 min_heap 多不超过 \(1\) 个元素即可.

写完之后先 TLE 一发,稍作优化之后便是 RE + WA…???经过多次修改尝试(炸OJ)之后,发现是 unsigned int 的问题…负数的情况会和 int 有所不同…

简单总结一下:priority_queuesize() 方法返回值是 unsigned int,所以不要乱做减法…

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

int main()
{
int t;
scanf("%d", &t);
while (t--)
{
std::priority_queue<int, vector<int>, greater<int>> min_heap;
std::priority_queue<int, vector<int>, less<int>> max_heap;
int N;
scanf("%d", &N);
while (N--)
{
char op[5];
scanf("%s", op);
if (op[0] == 'I')
{
int x;
scanf("%d", &x);
if (max_heap.empty())
max_heap.push(x);
else
{
if (x < max_heap.top())
max_heap.push(x);
else
min_heap.push(x);
}
// 之前写的是 max_heap.size() - min_heap.size() >= 2
// 因此在把 if 改成 while 后会反复执行非常多次... 提交结果会是 MLE.
// 但正常情况下,这里的 if 改成 while 是没有任何问题的.
if (max_heap.size() >= min_heap.size() + 2)
{
min_heap.push(max_heap.top());
max_heap.pop();
}

if (max_heap.size() < min_heap.size())
{
max_heap.push(min_heap.top());
min_heap.pop();
}
}

if (op[0] == 'D')
{
max_heap.pop();
if (max_heap.size() < min_heap.size())
{
max_heap.push(min_heap.top());
min_heap.pop();
}
}

if (op[0] == 'Q')
printf("%d\n", max_heap.top());
}
}

return 0;
}

Ultra-QuickSort

http://bailian.openjudge.cn/practice/2299/

求逆序…数字范围很大,因此需要离散化. 因为结果可能爆 int 而 WA 很多发…(当然,也有树状数组的做法,以及归并的做法)

线段树做法

严格来说这份代码采取的思路并不能算作真正的离散化. 这里的做法是对每个 \(a_i\),把下标 \(i\) 与值 \(a_i\) 都存下来,存到 \((val,idx)\) 这样结构的二元组中,那么初始状况下,所有二元组是按照 \(idx\) 排序的,我们需要求 \(val\) 序列的逆序数. 这等价于将 \(val\) 排序后,求 \(idx\) 序列的逆序数. 而 \(idx\) 的取值范围就是 \([1,n]\),因此只需要开规模为 \(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
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define root 1, n, 1

const int maxn = 500005;

int sum[maxn << 2];
vector<pair<int, int>> v;

void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void build(int l, int r, int rt)
{
if (l == r)
{
sum[rt] = 0;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}

void update(int x, int l, int r, int rt)
{
if (l == r)
{
sum[rt]++;
return;
}
int m = (l + r) >> 1;
if (x <= m) update(x, lson);
else update(x, rson);
pushup(rt);
}

int query(int l, int r, int rt, int ll, int rr)
{
if (ll <= l && rr >= r) return sum[rt];

int ret = 0;
int m = (l + r) >> 1;

if (ll <= m) ret += query(lson, ll, rr);
if (rr > m) ret += query(rson, ll, rr);
return ret;
}

int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
if (n == 0) break;

memset(sum, 0, sizeof(sum));
v.clear();

for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
v.push_back(make_pair(x, i));
}
stable_sort(v.begin(), v.end());
long long res = 0;
for (int i = 0; i < v.size(); i++)
{
update(v[i].second, 1, maxn, 1);
res += query(1, maxn, 1, v[i].second + 1, maxn);
}
printf("%lld\n", res);
}

return 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
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

const int maxn = 500005;
int n, x[maxn], f[maxn];

long long Merge_Sort(int l, int r, int *a, int *b)
{
if (r - l == 1)
return 0;

int m = (l + r) >> 1;
long long ans = Merge_Sort(l, m, a, b) + Merge_Sort(m, r, a, b);
int p = l, q = m, c = l;
while (p < m || q < r)
{
if (q >= r || (p < m && a[p] <= a[q]))
b[c++] = a[p++];
else
{
ans += m - p;
b[c++] = a[q++];
}
}
for (int i = l; i < r; i++)
a[i] = b[i];
return ans;
}

int main()
{
while (scanf("%d", &n) != EOF)
{
if(n == 0) break;
for (int i = 0; i < n; i++)
scanf("%d", &x[i]);
printf("%lld\n", Merge_Sort(0, n, x, f));
}
return 0;
}

重要逆序对

http://algorithm.openjudge.cn/201919191919/18xlyB/

归并做法

一直不会的归并排序…学♂习一下..

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;

const int maxn = 2e5 + 5;

int n, a[maxn], b[maxn];
long long res;

int Binary_Search(int l, int r, int val)
{
int ret = r + 1;
while (l <= r)
{
if (l == r)
{
if (a[l] > val) ret = l;
break;
}
int m = (l + r) >> 1;
if (a[m] > val)
{
ret = m;
r = m;
}
else l = m + 1;
}
return ret;
}

void merge(int l, int m, int r)
{
int i = l, j = m + 1, cnt = 0;
while (cnt < r - l + 1)
{
if (i > m) b[cnt++] = a[j++];
else if (j > r) b[cnt++] = a[i++];
else if (a[i] > a[j])
{
res += m - Binary_Search(i, m, 2 * a[j]) + 1;
b[cnt++] = a[j++];
}
else b[cnt++] = a[i++];
}
for (int k = 0; k < cnt; k++)
a[l + k] = b[k];
}

void Merge_Sort(int l, int r)
{
if (l == r) return;
int m = (l + r) >> 1;
Merge_Sort(l, m);
Merge_Sort(m + 1, r);
merge(l, m, r);
}

int main()
{
while (scanf("%d", &n) != EOF)
{
if(n == 0) break;

res = 0;
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
Merge_Sort(0, n - 1);
printf("%lld\n", res);
}
return 0;
}

线段树做法

夏令营和算法期末考试都写挂的题…(都写的是线段树,但甚至没有过样例Orz)一定要用线段树写过…

一开始妄想直接从 Ultra-Quicksort 的代码改,但 val 序列的重要逆序很难转换为 idx 序列的逆序(也可能是我没想到). 因此转而考虑将序列 \(a_1,\ldots,a_n\) 直接离散化,依次将其插入线段树,对每个 \(i\) 都查询比 \(2a_i\) 大的个数,并存到答案中.

但是这样会出问题:\(2a_i\) 可能超过原先 \(a\) 的取值范围,从而导致一些问题. 解决办法很简单,倒序插入,然后查询小于 \(a_i/2\) 的数即可. 随后因为 \(a_i/2\) 可能不是整数的情况费了一番功夫…然后才成功 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
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define root 1, maxn, 1

const int maxn = 400005;

int origional_a[maxn], a[maxn], uniqued_a[maxn], half_a[maxn];
int sum[maxn << 2];

void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void build(int l, int r, int rt)
{
if (l == r)
{
sum[rt] = 0;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}

void update(int x, int l, int r, int rt)
{
if (l == r)
{
sum[rt]++;
return;
}
int m = (l + r) >> 1;
if (x <= m) update(x, lson);
else update(x, rson);
pushup(rt);
}

long long query(int l, int r, int rt, int ll, int rr)
{
if (ll <= l && rr >= r) return sum[rt];

long long ret = 0;
int m = (l + r) >> 1;

if (ll <= m) ret += query(lson, ll, rr);
if (rr > m) ret += query(rson, ll, rr);
return ret;
}

int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
if(n == 0) break;
memset(sum, 0, sizeof(sum));

for (int i = 1; i <= n; i++)
{
scanf("%d", &origional_a[i]);
origional_a[i] *= 2; // 保证除以2还是整数
a[i] = origional_a[i];
uniqued_a[i] = origional_a[i];
}

sort(uniqued_a + 1, uniqued_a + 1 + n);
int sz = unique(uniqued_a + 1, uniqued_a + 1 + n) - uniqued_a - 1;
for(int i = 1; i <= n; i++)
{
a[i] = lower_bound(uniqued_a + 1, uniqued_a + sz + 1, origional_a[i]) - uniqued_a;
a[i] *= 2; // 变成整数
half_a[i] = lower_bound(uniqued_a + 1, uniqued_a + sz + 1, origional_a[i] / 2) - uniqued_a;
half_a[i] = 2 * half_a[i] - 1; // 保证顺序
}

long long res = 0;
for (int i = n; i >= 1; i--)
{
update(a[i], root);
res += query(root, 1, half_a[i]);
}
printf("%lld\n", res);
}

return 0;
}