Siehst, Vater, du den Erlkönig nicht?
Den Erlkönig mit Kron' und Schweif?
懵逼的 题目
[CTSC2007]数据备份Backup
种树
[POJ
Challenge]生日礼物
扯淡的 题解
我头一次感觉到智商是我做题(抄题解)的瓶颈(遭了 是脑死亡的感觉) = =
ZKY学长让我们做的种树 不会 遂抄黄学长博客 发现黄学长的做题顺序是
\(2288 \to 1150 \to
2151\)可是为什么我觉着\(2288\)明明是最难的呢...当然你先做完最难的就可以秒后面的题了
三个题的思路都是用一个堆记录当前的所有决策 越优的决策越靠近堆顶,
每次做决策就是取堆顶元素 然后取出堆顶元素之后 再考虑怎么处理影响
1150
就是选出\(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
|
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define INF ((MAXN << 1) - 1)
#define LINF (100000000000000000ll)
#define MAXN (100000 + 5)
#define int LL
#define LL long long
#define pii pair<int, int>
using namespace std;
struct cmp {
bool operator () (const pii x, const pii y) { return x.first > y.first; }
};
int n, m, a[MAXN], nex[MAXN << 1], pre[MAXN << 1];
LL ta[MAXN << 1], ans;
bool del[MAXN << 1];
priority_queue<pii, vector<pii>, cmp> q;
main() {
scanf("%lld%lld", &n, &m);
scanf("%lld", &a[1]);
for (int i = 2; i <= n; i++) scanf("%lld", &a[i]), ta[++ta[0]] = a[i] - a[i - 1];
for (int i = 1; i <= ta[0]; i++) pre[i] = i - 1, nex[i] = i + 1, q.push(make_pair(ta[i], i));
n = ta[0];
pre[1] = nex[n] = INF, pre[INF] = n, nex[INF] = INF;
ta[INF] = LINF;
while (m) {
while (del[q.top().second]) q.pop();
int dqz = q.top().first, dqx = q.top().second;
q.pop();
ans += dqz;
ta[++ta[0]] = ta[pre[dqx]] + ta[nex[dqx]] - dqz;
del[dqx] = del[pre[dqx]] = del[nex[dqx]] = true;
nex[ta[0]] = nex[nex[dqx]], pre[ta[0]] = pre[pre[dqx]];
pre[nex[ta[0]]] = ta[0], nex[pre[ta[0]]] = ta[0];
q.push(make_pair(ta[ta[0]], ta[0]));
--m;
}
printf("%lld", ans);
return 0;
}
|
2151
和上面的问题差不多 无非就是转成了环形 并且求的是点权和最大
双向链表的边界处理一下
再把cmp函数的大于号方向换一下就行了
顺便提一下当时zky学长讲这题的时候被烜爷爷用DP+FFT秒了
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
|
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (200000 + 5)
#define pii pair<int, int>
using namespace std;
struct cmp {
bool operator () (const pii x, const pii y) { return x.first < y.first; }
};
int n, m, ta[MAXN << 1], pre[MAXN << 1], nex[MAXN << 1], ans;
bool del[MAXN << 1];
priority_queue<pii, vector<pii>, cmp> q;
int main() {
scanf("%d%d", &n, &m);
if (m > n / 2) {
puts("Error!");
return 0;
}
for (int i = 1; i <= n; i++) scanf("%d", &ta[i]), pre[i] = i - 1, nex[i] = i + 1, q.push(make_pair(ta[i], i));
pre[1] = n, nex[n] = 1;
ta[0] = n;
while (m) {
while (q.size() && del[q.top().second]) q.pop();
int dqz = q.top().first, dqx = q.top().second;
q.pop();
ans += dqz;
ta[++ta[0]] = -dqz + ta[pre[dqx]] + ta[nex[dqx]];
del[dqx] = del[pre[dqx]] = del[nex[dqx]] = true;
pre[ta[0]] = pre[pre[dqx]], nex[ta[0]] = nex[nex[dqx]];
nex[pre[ta[0]]] = ta[0], pre[nex[ta[0]]] = ta[0];
q.push(make_pair(ta[ta[0]], ta[0]));
--m;
}
printf("%d", ans);
return 0;
}
|
2288
这题绝对难度不是一个档次的好吧... = =
首先 我们要把整个序列合并 让同号的区间变成一个点(把他们的点权加起来)
把0都舍去(对没影响)
然后我们发现这个序列现在变得正负交错了
考虑如果正数的个数小于等于\(m\)就不用做了直接输出他们的和就可以了
现在的情况是正数的个数大于\(m\)
我们就有了两个决策:
扔掉几个正数
加入一些负数 让这个负数的两边的正数连成一个
这两个决策都会让我们选的数的个数减少\(1\)
考虑怎么表示出这两个决策和他们对答案的影响反正我想不出来:
把所有数加到堆里 按照绝对值从小到大排序
是不是很妙?
对于正数 绝对值小就代表对答案的贡献小 可以扔掉ta
对于负数 绝对值小就代表用这个负数把两边的正数连起来"损失"最小
于是就用这个负数来连接ta两边的正数
当然还有喜闻乐见的边界问题
边界上的负数是不能选的(选了也不会减少答案选择的块数) (当然正数是可以选的
(就相当于扔掉了))
说道选数 选出来我们要干什么呢
我们知道了负数是用来连接旁边的两块正数的
我们可以直接把这个负数和两边的正数合一起放到堆里
那正数呢 其实正数也是连接两边的两块负数
就想到与把两边的负数和这个正数合在一起变成一大段负数(为什么是负数呢
因为这个正数的绝对值比旁边的两个负数都要小嘛)
还有就是选一个数对答案的影响 正数就是直接减去这个正数的值
负数就是加上负数的值 然后就喜闻乐见的可以统一为减去堆顶的绝对值
到这就算做完了
反正我觉得考场上想出这种做法的人...大概已经可以归为神了
当然gayge给我安利了一天他的线段树做法(虽然维护了18个值就跟一坨狗屎一样吧)(还有我很想吐槽他背景那个哒哒哒冒蓝火的加特林怎么办)
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
|
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define pii pair<int, int>
#define MAXN (100000 + 5)
#define INF ((MAXN << 1) - 1)
#define abs(x) (((x) > 0) ? (x) : (-(x)))
using namespace std;
struct cmp {
bool operator () (const pii x, const pii y) { return abs(x.first) > abs(y.first); }
};
int n, m, a[MAXN], ta[MAXN << 1], pre[MAXN << 1], nex[MAXN << 1], ans, cntz;
bool del[MAXN << 1];
priority_queue<pii, vector<pii>, cmp> q;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[++a[0]]), a[0] -= (!a[a[0]]);
n = a[0];
int dq = a[1];
for (int i = 2; i <= n; i++)
if (a[i] * a[i - 1] > 0) dq += a[i];
else {
if (dq > 0) ans += dq, ++cntz;
if (dq) ta[++ta[0]] = dq;
dq = a[i];
}
if (dq > 0) ans += dq, ++cntz;
if (dq) ta[++ta[0]] = dq;
if (cntz <= m) {
printf("%d", ans);
return 0;
}
n = ta[0];
for (int i = 1; i <= n; i++) pre[i] = i - 1, nex[i] = i + 1, q.push(make_pair(ta[i], i));
pre[1] = pre[0] = 0, nex[n] = nex[INF] = INF;
pre[INF] = n, nex[0] = 1;
while (cntz > m) {
while (del[q.top().second]) q.pop();
int dqz = q.top().first, dqx = q.top().second;
q.pop();
if (pre[dqx] == 0 || nex[dqx] == INF) {
if (dqz > 0)
ans -= dqz, --cntz;
del[dqx] = true;
if (pre[dqx]) nex[pre[dqx]] = INF;
else pre[nex[dqx]] = 0;
continue;
}
ans -= abs(dqz);
ta[++ta[0]] = dqz + ta[pre[dqx]] + ta[nex[dqx]];
pre[ta[0]] = pre[pre[dqx]], nex[ta[0]] = nex[nex[dqx]];
nex[pre[ta[0]]] = ta[0], pre[nex[ta[0]]] = ta[0];
del[dqx] = del[pre[dqx]] = del[nex[dqx]] = true;
q.push(make_pair(ta[ta[0]], ta[0]));
--cntz;
}
printf("%d", ans);
return 0;
}
|
By 准备退役旅游的 Cansult