Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


「BZOJ 4654」「UOJ 223」「NOI2016」国王饮水记

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. explanation
  7. 7. Solution

Description

跳蚤国有 n 个城市,伟大的跳蚤国王居住在跳蚤国首都中,即 1 号城市中。跳蚤国最大的问题就是饮水问题,由于首都中居住的跳蚤实在太多,跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用,这导致跳蚤国王也经常喝不上水。于是,跳蚤国在每个城市都修建了一个圆柱形水箱,这些水箱完全相同且足够高。一个雨天后,第 i 个城市收集到了高度为 hi 的水。由于地理和天气因素的影响,任何两个不同城市收集到的水高度互不相同。跳蚤国王也请来蚂蚁工匠帮忙,建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时,可以指定任意多的城市,将这些城市的水箱用地下连通系统连接起来足够长的时间之后,再将地下连通系统关闭。由连通器原理,这些城市的水箱中的水在这次操作后会到达同一高度,并且这一高度等于指定的各水箱高度的平均值。由于地下连通系统的复杂性,跳蚤国王至多只能使用 k 次地下连通系统。跳蚤国王请你告诉他,首都 1 号城市水箱中的水位最高能有多高?

Input

输入的第一行包含 3 个正整数 n,k,p分别表示跳蚤国中城市的数量,跳蚤国王能使用地下连通系统的最多次数,以及你输出的答案要求的精度。p 的含义将在输出格式中解释。接下来一行包含 n 个正整数,描述城市的水箱在雨后的水位。其中第 i 个 正整数 hi 表示第 i 个城市的水箱的水位。保证 hi 互不相同,1≤hi≤10^5对于所有数据,满足3≤p≤3000,1≤n≤8000,1≤k≤10^9

Output

仅一行一个实数,表示 1 号城市的水箱中的最高水位。这个实数只可以包含非负整数部分、小数点和小数部分。其中非负整数部分为必需部分,不加正负号。若有小数部分,则非负整数部分与小数部分之间以一个小数点隔开。若无小数部分,则不加小数点。你输出的实数在小数点后不能超过 2p 位,建议保留至少 p 位。数据保证参考答案与真实答案的绝对误差小于 10^-2p。你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 10^-p

Sample Input

1
2
3 1 3
1 4 3

Sample Output

1
2.666667

explanation

由于至多使用一次地下连通系统,有以下 5 种方案:

  1. 不使用地下连通系统:此时 1 号城市的水箱水位为 1。

  2. 使用一次连通系统,连通 1、2 号:此时 11 号城市的水箱水位为 5/2。

  3. 使用一次连通系统,连通 1、3 号:此时 1 号城市的水箱水位为 2/2。

  4. 使用一次连通系统,连通 2、3号:此时 1 号城市的水箱水位为 1。

  5. 使用一次连通系统,连通 1、2、3号:此时 11 号城市的水箱水位为 8/3。

Solution

首先去掉所有比 h[1] 还要小的 h[i];

然后如果没有 k 的限制,每次就总是取最小的两个数合并;

但现在有 k 的限制,因此有可能某些步骤必须合并多个 h。

有一个结论:h[i] 排序后,每次必然是合并从 h[1] 开始的连续区间。

那么我们可以用 f[i][j] 表示用了 j 次连通器,合并了 1~i 的节点后的最高水量。

$p_i$ 表示 h 的前缀和,则 $f_{i,j}=\max_{k<i}\{\frac{f_{k,j-1}+p_i-p_k}{i-k+1}\}$

这是一个斜率方程的形式(注意,不是斜率优化,只是满足斜率的形式),设 $P(x)=(x-1, p_x-f_{x,j-1})$,我们就是要维护它在 $(i, p_i)$ 处的最大斜率。

这个方程满足决策单调性,因此可以用一个单调队列维护凸壳,每个元素 O(1) 计算。

由于 h[i] 互不相同,「一次合并多余 2 个节点」的操作,不会超过 14 次,而且这些操作一定是最开始的连续操作。

所以我们可以只算出 DP 方程的前 14 层,剩下的都贪心处理。

一个小 trick:先用 double 计算转移路径,然后再用高精度小数类计算精确答案。

这可能是我正经写过的最长的代码了……(虽然绝大部分不是我写的 233)

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
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
#include <bits/stdc++.h>
namespace std {
const int PREC = 3050;
class Decimal {
public:
Decimal();
Decimal(const std::string &s);
Decimal(const char *s);
Decimal(int x);
Decimal(long long x);
Decimal(double x);
bool is_zero() const;
std::string to_string(int p) const;
double to_double() const;
friend Decimal operator+(const Decimal &a, const Decimal &b);
friend Decimal operator+(const Decimal &a, int x);
friend Decimal operator+(int x, const Decimal &a);
friend Decimal operator+(const Decimal &a, long long x);
friend Decimal operator+(long long x, const Decimal &a);
friend Decimal operator+(const Decimal &a, double x);
friend Decimal operator+(double x, const Decimal &a);
friend Decimal operator-(const Decimal &a, const Decimal &b);
friend Decimal operator-(const Decimal &a, int x);
friend Decimal operator-(int x, const Decimal &a);
friend Decimal operator-(const Decimal &a, long long x);
friend Decimal operator-(long long x, const Decimal &a);
friend Decimal operator-(const Decimal &a, double x);
friend Decimal operator-(double x, const Decimal &a);
friend Decimal operator*(const Decimal &a, int x);
friend Decimal operator*(int x, const Decimal &a);
friend Decimal operator/(const Decimal &a, int x);
friend bool operator<(const Decimal &a, const Decimal &b);
friend bool operator>(const Decimal &a, const Decimal &b);
friend bool operator<=(const Decimal &a, const Decimal &b);
friend bool operator>=(const Decimal &a, const Decimal &b);
friend bool operator==(const Decimal &a, const Decimal &b);
friend bool operator!=(const Decimal &a, const Decimal &b);
Decimal &operator+=(int x);
Decimal &operator+=(long long x);
Decimal &operator+=(double x);
Decimal &operator+=(const Decimal &b);
Decimal &operator-=(int x);
Decimal &operator-=(long long x);
Decimal &operator-=(double x);
Decimal &operator-=(const Decimal &b);
Decimal &operator*=(int x);
Decimal &operator/=(int x);
friend Decimal operator-(const Decimal &a);
friend Decimal operator*(const Decimal &a, double x);
friend Decimal operator*(double x, const Decimal &a);
friend Decimal operator/(const Decimal &a, double x);
Decimal &operator*=(double x);
Decimal &operator/=(double x);
private:
static const int len = PREC / 9 + 1;
static const int mo = 1000000000;
static void append_to_string(std::string &s, long long x);
bool is_neg;
long long integer;
int data[len];
void init_zero();
void init(const char *s);
};
Decimal::Decimal() { this->init_zero(); }
Decimal::Decimal(const char *s) { this->init(s); }
Decimal::Decimal(const std::string &s) { this->init(s.c_str()); }
Decimal::Decimal(int x) {
this->init_zero();
if (x < 0) {
is_neg = true;
x = -x;
}
integer = x;
}
Decimal::Decimal(long long x) {
this->init_zero();
if (x < 0) {
is_neg = true;
x = -x;
}
integer = x;
}
Decimal::Decimal(double x) {
this->init_zero();
if (x < 0) {
is_neg = true;
x = -x;
}
integer = (long long)x;
x -= integer;
for (int i = 0; i < len; ++i) {
x *= mo;
if (x < 0) x = 0;
data[i] = (int)x;
x -= data[i];
}
}
void Decimal::init_zero() {
is_neg = false;
integer = 0;
memset(data, 0, len * sizeof(int));
}
bool Decimal::is_zero() const {
if (integer) return false;
for (int i = 0; i < len; ++i) if (data[i]) return false;
return true;
}
void Decimal::init(const char *s) {
this->init_zero();
is_neg = false;
integer = 0;
while (*s != 0) {
if (*s == '-') {
is_neg = true;
++s;
break;
} else if (*s >= 48 && *s <= 57) break;
++s;
}
while (*s >= 48 && *s <= 57) {
integer = integer * 10 + *s - 48;
++s;
}
if (*s == '.') {
int pos = 0;
int x = mo / 10;
++s;
while (pos < len && *s >= 48 && *s <= 57) {
data[pos] += (*s - 48) * x;
++s;
x /= 10;
if (x == 0) {
++pos;
x = mo / 10;
}
}
}
}
void Decimal::append_to_string(std::string &s, long long x) {
if (x == 0) {
s.append(1, 48);
return;
}
char _[30];
int cnt = 0;
while (x) {
_[cnt++] = x % 10;
x /= 10;
}
while (cnt--) s.append(1, _[cnt] + 48);
}
std::string Decimal::to_string(int p) const {
std::string ret;
if (is_neg && !this->is_zero()) ret = "-";
append_to_string(ret, this->integer);
ret.append(1, '.');
for (int i = 0; i < len; ++i) {
int x = mo / 10;
int tmp = data[i];
while (x) {
ret.append(1, 48 + tmp / x);
tmp %= x;
x /= 10;
if (--p == 0) break;
}
if (p == 0) break;
}
if (p > 0) ret.append(p, '0');
return ret;
}
double Decimal::to_double() const {
double ret = integer;
double k = 1.0;
for (int i = 0; i < len; ++i) {
k /= mo;
ret += k * data[i];
}
if (is_neg) ret = -ret;
return ret;
}
bool operator<(const Decimal &a, const Decimal &b) {
if (a.is_neg != b.is_neg) return a.is_neg && (!a.is_zero() || !b.is_zero());
else if (!a.is_neg) {
if (a.integer != b.integer) return a.integer < b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] < b.data[i];
return false;
} else {
if (a.integer != b.integer) return a.integer > b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] > b.data[i];
return false;
}
}
bool operator>(const Decimal &a, const Decimal &b) {
if (a.is_neg != b.is_neg) return !a.is_neg && (!a.is_zero() || !b.is_zero());
else if (!a.is_neg) {
if (a.integer != b.integer) return a.integer > b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] > b.data[i];
return false;
} else {
if (a.integer != b.integer) return a.integer < b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] < b.data[i];
return false;
}
}
bool operator<=(const Decimal &a, const Decimal &b) {
if (a.is_neg != b.is_neg) return a.is_neg || (a.is_zero() && b.is_zero());
else if (!a.is_neg) {
if (a.integer != b.integer) return a.integer < b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] < b.data[i];
return true;
} else {
if (a.integer != b.integer) return a.integer > b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] > b.data[i];
return true;
}
}
bool operator>=(const Decimal &a, const Decimal &b) {
if (a.is_neg != b.is_neg) return !a.is_neg || (a.is_zero() && b.is_zero());
else if (!a.is_neg) {
if (a.integer != b.integer) return a.integer > b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] > b.data[i];
return true;
} else {
if (a.integer != b.integer) return a.integer < b.integer;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return a.data[i] < b.data[i];
return true;
}
}
bool operator==(const Decimal &a, const Decimal &b) {
if (a.is_zero() && b.is_zero()) return true;
if (a.is_neg != b.is_neg) return false;
if (a.integer != b.integer) return false;
for (int i = 0; i < Decimal::len; ++i) if (a.data[i] != b.data[i]) return false;
return true;
}
bool operator!=(const Decimal &a, const Decimal &b) { return !(a == b); }
Decimal &Decimal::operator+=(long long x) {
if (!is_neg) {
if (integer + x >= 0) integer += x;
else {
bool last = false;
for (int i = len - 1; i >= 0; --i) {
if (last || data[i]) {
data[i] = mo - data[i] - last;
last = true;
} else last = false;
}
integer = -x - integer - last;
is_neg = true;
}
} else {
if (integer - x >= 0) integer -= x;
else {
bool last = false;
for (int i = len - 1; i >= 0; --i) {
if (last || data[i]) {
data[i] = mo - data[i] - last;
last = true;
} else last = false;
}
integer = x - integer - last;
is_neg = false;
}
}
return *this;
}
Decimal &Decimal::operator+=(int x) { return *this += (long long)x; }
Decimal &Decimal::operator-=(int x) { return *this += (long long)-x; }
Decimal &Decimal::operator-=(long long x) { return *this += -x; }
Decimal &Decimal::operator/=(int x) {
if (x < 0) {
is_neg ^= 1;
x = -x;
}
int last = integer % x;
integer /= x;
for (int i = 0; i < len; ++i) {
long long tmp = 1LL * last * mo + data[i];
data[i] = tmp / x;
last = tmp - 1LL * data[i] * x;
}
if (is_neg && integer == 0) {
int i;
for (i = 0; i < len; ++i) if (data[i] != 0) break;
if (i == len) is_neg = false;
}
return *this;
}
Decimal &Decimal::operator*=(int x) {
if (x < 0) {
is_neg ^= 1;
x = -x;
} else if (x == 0) {
init_zero();
return *this;
}
int last = 0;
for (int i = len - 1; i >= 0; --i) {
long long tmp = 1LL * data[i] * x + last;
last = tmp / mo;
data[i] = tmp - 1LL * last * mo;
}
integer = integer * x + last;
return *this;
}
Decimal operator-(const Decimal &a) {
Decimal ret = a;
if (!ret.is_neg && ret.integer == 0) {
int i;
for (i = 0; i < Decimal::len; i++) if (ret.data[i] != 0) break;
if (i < Decimal::len) ret.is_neg = true;
} else ret.is_neg ^= 1;
return ret;
}
Decimal operator+(const Decimal &a, int x) {
Decimal ret = a;
return ret += x;
}
Decimal operator+(int x, const Decimal &a) {
Decimal ret = a;
return ret += x;
}
Decimal operator+(const Decimal &a, long long x) {
Decimal ret = a;
return ret += x;
}
Decimal operator+(long long x, const Decimal &a) {
Decimal ret = a;
return ret += x;
}
Decimal operator-(const Decimal &a, int x) {
Decimal ret = a;
return ret -= x;
}
Decimal operator-(int x, const Decimal &a) { return -(a - x); }
Decimal operator-(const Decimal &a, long long x) {
Decimal ret = a;
return ret -= x;
}
Decimal operator-(long long x, const Decimal &a) { return -(a - x); }
Decimal operator*(const Decimal &a, int x) {
Decimal ret = a;
return ret *= x;
}
Decimal operator*(int x, const Decimal &a) {
Decimal ret = a;
return ret *= x;
}
Decimal operator/(const Decimal &a, int x) {
Decimal ret = a;
return ret /= x;
}
Decimal operator+(const Decimal &a, const Decimal &b) {
if (a.is_neg == b.is_neg) {
Decimal ret = a;
bool last = false;
for (int i = Decimal::len - 1; i >= 0; --i) {
ret.data[i] += b.data[i] + last;
if (ret.data[i] >= Decimal::mo) {
ret.data[i] -= Decimal::mo;
last = true;
} else last = false;
}
ret.integer += b.integer + last;
return ret;
} else if (!a.is_neg) return a - -b;
else return b - -a;
}
Decimal operator-(const Decimal &a, const Decimal &b) {
if (!a.is_neg && !b.is_neg) {
if (a >= b) {
Decimal ret = a;
bool last = false;
for (int i = Decimal::len - 1; i >= 0; --i) {
ret.data[i] -= b.data[i] + last;
if (ret.data[i] < 0) {
ret.data[i] += Decimal::mo;
last = true;
} else last = false;
}
ret.integer -= b.integer + last;
return ret;
} else {
Decimal ret = b;
bool last = false;
for (int i = Decimal::len - 1; i >= 0; --i) {
ret.data[i] -= a.data[i] + last;
if (ret.data[i] < 0) {
ret.data[i] += Decimal::mo;
last = true;
} else last = false;
}
ret.integer -= a.integer + last;
ret.is_neg = true;
return ret;
}
} else if (a.is_neg && b.is_neg) return -b - -a;
else if (a.is_neg) return -(-a + b);
else return a + -b;
}
Decimal operator+(const Decimal &a, double x) { return a + Decimal(x); }
Decimal operator+(double x, const Decimal &a) { return Decimal(x) + a; }
Decimal operator-(const Decimal &a, double x) { return a - Decimal(x); }
Decimal operator-(double x, const Decimal &a) { return Decimal(x) - a; }
Decimal &Decimal::operator+=(double x) {
*this = *this + Decimal(x);
return *this;
}
Decimal &Decimal::operator-=(double x) {
*this = *this - Decimal(x);
return *this;
}
Decimal &Decimal::operator+=(const Decimal &b) {
*this = *this + b;
return *this;
}
Decimal &Decimal::operator-=(const Decimal &b) {
*this = *this - b;
return *this;
}
}
using namespace std;
const int maxn = 8005;
int n, k, p, h[maxn];
int layer, q[maxn], ql, qr;
int trans[17][maxn], method[17];
double dp[17][maxn], y[maxn];
Decimal ans;
double slope(int a, int b) { return (y[b] - y[a]) / (b - a); }
int main() {
scanf("%d%d%d", &n, &k, &p);
int tot = 1;
scanf("%d", h + 1);
for (int i = 2, x; i <= n; ++i) {
scanf("%d", &x);
if (x > h[1]) h[++tot] = x;
}
sort(h + 1, h + tot + 1);
n = tot;
for (int i = 2; i <= n; ++i) h[i] += h[i - 1];
k = min(k, n - 1);
layer = min(k, 14);
for (int i = 1; i <= n; ++i) dp[0][i] = h[1];
for (int i = 1; i <= layer; ++i) {
ql = 1, qr = 0;
for (int j = 2; j <= n; ++j) {
y[j - 1] = h[j - 1] - dp[i - 1][j - 1];
while (ql < qr && slope(q[qr], j - 1) < slope(q[qr - 1], q[qr])) --qr;
q[++qr] = j - 1;
y[j + 1] = h[j];
while (ql < qr && slope(q[ql], j + 1) < slope(q[ql + 1], j + 1)) ++ql;
trans[i][j] = q[ql];
dp[i][j] = slope(q[ql], j + 1);
}
}
method[layer] = n - k + layer;
for (int i = layer; i; --i) method[i - 1] = trans[i][method[i]];
ans = h[1];
for (int i = 1; i <= layer; ++i) {
int j = method[i], k = method[i - 1];
ans = (ans + h[j] - h[k]) / (j - k + 1);
}
for (int i = method[layer] + 1; i <= n; ++i) ans = (ans + h[i] - h[i - 1]) / 2;
puts(ans.to_string(p + 1).c_str());
return 0;
}
最近的文章

「BZOJ 4012」「HNOI2015」开店

Description风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共…

BZOJ, 主席树, 树链剖分 继续阅读
更早的文章

「BZOJ 2759」一个动态树好题

Description有N个未知数x[1..n]和N个等式组成的同余方程组: x[i]=k[i]*x[p[i]]+b[i] mod 10007 其中,k[i],b[i],x[i]∈[0,10007)∩Z 你要应付Q个事务,每个是两种情况之一: 一.询问当前x[a]的解 A a 无解输出-1 x[a]…

BZOJ, Link-Cut Tree, 基环树 继续阅读