Skip to content

「HEOI2014」南园满地堆轻絮

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

小 Z 是 ZRP(Zombies’ Republic of Poetry,僵尸诗歌共和国)的一名诗歌爱好者,最近他研究起了诗词音律的问题。在过去,诗词是需要编成曲子唱出来的,比如下面这首《菩萨蛮》,唱出来的话其对应 的音符就是这样的:

11 1{1} 55 5{5} 66 6{6} 55 44 4{4} 33 3{3} 22 2{2} 11

因而可以发现,1 1 5 5 6 6 5, 4 4 3 3 2 2 1 这串音符就成为了研究音律的关键。

小 Z 翻阅了众多史料发现,过去的一首曲子的音调是不下降的。小 Z 想要知道对于一首给定的曲子,如何通过提高音调或者降低音调,将它的音调修改得不下降,而且使得修改幅度最大的那个音符的修改幅度尽量小。

即如果把一个包含 nn 个音符的曲子看做是一个正整数数列 A1,,AnA_1, \ldots, A_n,那么目标是求另一个正整数数列 B1,,BnB_1, \ldots, B_n, 使得对于任意的 1i<n1 \leq i < nBiBi+1B_i \leq B_{i + 1},而且使得 ans=max1jn{AjBj}\mathit{ans} = \max_{1 \leq j \leq n} \{|A_j - B_j|\} 尽量小。

小 Z 很快就想清楚了做法,但是鉴于他还忙着写诗,所以这个任务就交给了你。

#输入格式

由于数据规模可能较大,因此采用如下方式生成数据。

每个数据包含六个数:n,Sa,Sb,Sc,Sd,A1,pn, S_a, S_b, S_c, S_d, A_1, p,意为共有 nn 个音符,第一个音符为 A1A_1

生成规则如下:定义生成函数 f(x)=Sax3+Sbx2+Scx+Sdf(x) = S_a x^3 + S_b x^2 + S_c x + S_d; 那么给出递推公式 Ai=f(Ai1)+f(Ai2)A_i = f(A_{i-1}) + f(A_{i-2}),此处规定 a0=0a_0 = 0

由于中间过程的数可能会特别大,所以要求每一步与 AA 中的每个数都对一个给定的数 pp 取模。

#输出格式

输出一行,包含一个正整数 ans\mathit{ans}

#输入输出样例

样例输入 #1

3 815 6901 3839 178 199 10007

样例输出 #1

1334

样例解释 #1

生成的数列为 199 4568 1901199 \ 4568 \ 1901,此时将 45684568 修改为 3234323419011901 也修改为 32343234 即可,代价为 13341334

#数据范围与约定

对于 100%100\% 的数据,n5000000n \leq 5000000Sa,Sb,Sc,Sd,A110000S_a, S_b, S_c, S_d, A_1 \leq 10000p1000000007p \leq 1000000007

#思路

看到最大值最小,自然而然地就想到了二分答案。

可以从贪心的角度来考虑,每次在满足条件的情况下让 bib_i 尽可能小更有利于后续处理。

如果 aibi>x|a_i - b_i| > x,则无论如何也无法满足条件,因此该情况不成立。

#代码

C++
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
#include <iostream>
#include <algorithm>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e6 + 5;

int n, s_a, s_b, s_c, s_d, a[N], b[N], mod, ans;

inline int f(int x) {
return (static_cast<long long>(s_a) % mod * x % mod * x % mod * x % mod
+ static_cast<long long>(s_b) % mod * x % mod * x % mod
+ static_cast<long long>(s_c) % mod * x % mod
+ s_d)
% mod;
}

bool check(int x) {
std::copy_n(a + 1, n, b + 1);

for (int i = 1; i <= n; i++) {
b[i] = std::max(b[i - 1], b[i] - x);

if (std::abs(a[i] - b[i]) > x) return false;
}

return true;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> s_a >> s_b >> s_c >> s_d >> a[1] >> mod;

for (int i = 2; i <= n; i++) {
a[i] = (f(a[i - 1]) + f(a[i - 2])) % mod;
}

int l = 0, r = mod;

while (l <= r) {
int mid = l + r >> 1;

if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}

cout << ans << endl;

return 0;
}