NOIP2016 Day2 T2(堆/单调队列)

25分水法:
直接模拟,增加$q$直接暴力把堆中的元素取出来加完放进去

65分水法:
直接按照题意模拟,但是堆里面存当前蚯蚓长度与 增加量$q$ 的差值(具体看代码),来避免每次使蚯蚓增加$q$.

90分水法:
发现很多数据$q=0$,那么等于蚯蚓不会再加了,考虑单调性。
用三个队列$q_1,q_2,q_3$,分别代表原始数据,切分第一部分,切分第二部分。
然后每次从三个队列里取最大值出来切,然后结果分别放进$q_2,q_3$。
这样做是对的,因为这样做数据是单调递减的,前面切的两部分一定比后面切的两部分分别大于。
然后加上65分的程序分段,这样就有90分了,注意分段程序千万别打错,不然白打前65分。

100分正解:
根据上一个90分做法,我们被暗示了——单调性。
$q≠0$也是单调的吗?是的。
我们通过反证可以知道:设$a_i$为当前被切割的蚯蚓的原长,$a_j$为$a_i$之前隔了$n$时段被切割的蚯蚓的原长
那么假设不单调,即出现:
$a_i \times p + n \times q \leq (a_j + n \times q) \times p$
那么就是
$a_i \times p + n \times q \leq a_j \times p + n \times q \times p$
因为$a_j \leq a_i, 0 < p < 1$,那么
$a_i \times p + n \times q > a_j \times p + n \times q \times p$成立
与之前的假设矛盾,因此是单调的
NOIP的部分分都是在暗示正解的方向,不过以后或者其他比赛可能回不会。所以尽可能往部分分想会暗示什么,但是也不要完全依赖部分分提示。
上述算法虽然难以证明,但是在想到90分做法以后,联想到$q≠0$,那就可以作一个假设,之后用暴力对拍即可验证正确性(你的暴力肯定要对)。

下面代码给出了3个分数档次(65,90,100)的代码:

65分堆水法:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
struct data {
LL len;
bool operator < (const data &b) const {
return len < b.len;
}
};
LL n, m, q, t, add;
db pi;
priority_queue<data> pq;
void clean() {
add = 0;
}
void solve() {
clean();
for (LL x, i = 1; i <= n; i++) scanf("%lld", &x), pq.push((data){x});
data p;
for (int i = 1; i <= m; i++) {
p = pq.top(); pq.pop();
LL len = p.len + add;
if (i % t == 0) printf("%lld ", len);
LL fir = (LL)((db)len * pi);
LL sec = len - fir;
add += q;
pq.push((data){fir - add}), pq.push((data){sec - add});
}
printf("\n");
int tot = 0;
while (!pq.empty()) {
p = pq.top(); pq.pop();
tot++;
LL len = p.len + add;
if (tot % t == 0) printf("%lld ", len);
}
printf("\n");
}
int main() {
LL u, v;
scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t), pi = (db)u / (db)v, solve();
return 0;
}

90分水法:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
struct data {
LL len;
bool operator < (const data &b) const {
return len < b.len;
}
};
LL n, m, q, t, add;
db pi;
priority_queue<data> pq;
void clean() {
add = 0;
}
void solve() {
clean();
for (LL x, i = 1; i <= n; i++) scanf("%lld", &x), pq.push((data){x});
data p;
for (int i = 1; i <= m; i++) {
p = pq.top(); pq.pop();
LL len = p.len + add;
if (i % t == 0) printf("%lld ", len);
LL fir = (LL)((db)len * pi);
LL sec = len - fir;
add += q;
pq.push((data){fir - add}), pq.push((data){sec - add});
}
printf("\n");
int tot = 0;
while (!pq.empty()) {
p = pq.top(); pq.pop();
tot++;
LL len = p.len + add;
if (tot % t == 0) printf("%lld ", len);
}
printf("\n");
}
LL q1[10000000 + 5], q2[10000000 + 5], q3[10000000 + 5];
LL h1 = 0, h2 = 0, h3 = 0, t1 = 0, t2 = 0, t3 = 0;
bool cmp(const int &a, const int &b) {
return a > b;
}
void solve2() {
for (int i = 1; i <= n; i++) scanf("%lld", &q1[i]);
sort(q1 + 1, q1 + 1 + n, cmp);
t1 = n;
for (int i = 1; i <= m; i++) {
LL maxd = -1, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
if (i % t == 0) printf("%lld ", maxd);
q2[++t2] = (LL)((db)maxd * pi);
q3[++t3] = maxd - (LL)((db)maxd * pi);
}
printf("\n");
for (int i = 1; i <= n + m; i++) {
LL maxd = -1, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
if (i % t == 0) printf("%lld ", maxd);
}
printf("\n");
}
int main() {
LL u, v;
scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t), pi = (db)u / (db)v;
if (q != 0) solve(); else solve2();
return 0;
}

100分正解:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
LL n, m, q, t, add;
db pi;
void clean() {
add = 0;
}
bool cmp(const int &a, const int &b) {
return a > b;
}
LL q1[10000000 + 5], q2[10000000 + 5], q3[10000000 + 5];
LL h1 = 0, h2 = 0, h3 = 0, t1 = 0, t2 = 0, t3 = 0;
void solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%lld", &q1[i]);
sort(q1 + 1, q1 + 1 + n, cmp);
t1 = n;
for (int i = 1; i <= m; i++) {
LL maxd = -1000000000, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
maxd += add;
if (i % t == 0) printf("%lld ", maxd);
add += q;
q2[++t2] = (LL)((db)maxd * pi) - add;
q3[++t3] = maxd - (LL)((db)maxd * pi) - add;
}
printf("\n");
for (int i = 1; i <= n + m; i++) {
LL maxd = -1000000000, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
if (i % t == 0) printf("%lld ", maxd + add);
}
printf("\n");
}
int main() {
LL u, v;
scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t), pi = (db)u / (db)v, solve();
return 0;
}

------ 本文结束 ------