#P12641. 「OOI 2021 Day 1」跳跃橱柜

    ID: 11827 传统题 6000ms 512MiB 尝试: 4 已通过: 1 难度: 9 上传者: 标签>CF2600构造数学数据结构队列贪心差分

「OOI 2021 Day 1」跳跃橱柜

题目描述

在克罗什的家中,曾经有 nn 个橱柜排成一排,第 ii 个橱柜的高度为 hih_i。最近克罗什搬家了,但无法将这些橱柜一起带走。他希望购买 nn 个新橱柜,并尽量让它们与原来的橱柜相似。

克罗什不记得每个橱柜的具体高度,但他记得每三个连续橱柜中最高与最低橱柜之间的高度差。换句话说,如果橱柜的高度序列为 h1,h2,…,hnh_1, h_2, \ldots, h_n,那么克罗什记得的值为 $w_i = \max(h_{i}, h_{i + 1}, h_{i + 2}) - \min(h_{i}, h_{i + 1}, h_{i + 2})$,其中 1≤i≤n−21 \leq i \leq n - 2。

在新家中,克罗什希望购买 nn 个橱柜,使得一切如旧——所有的 wiw_i 值必须保持不变。请帮助克罗什确定他应该购买哪些橱柜以及如何排列它们,或者判断他是否记错了,因为这样的橱柜序列可能并不存在。

输入格式

第一行包含两个整数 nn 和 CC (3≤n≤106,0≤C≤1012(3 \leq n \leq 10^{6}, 0 \leq C \leq 10^{12}),分别表示橱柜的数量和对 wiw_i 的限制。

第二行包含 n−2n - 2 个整数 w1,w2,…,wn−2w_1, w_2, \ldots, w_{n - 2} (0≤wi≤C)(0 \leq w_i \leq C)。

输出格式

如果无法购买满足条件的 nn 个橱柜,则在单独一行中输出 No。

否则,在第一行输出 Yes,并在第二行输出 nn 个整数 h1′,h2′,…,hn′h'_1, h'_2, \ldots, h'_n (0≤hi′≤1018)(0 \leq h'_i \leq 10^{18}),表示要购买的橱柜的高度。

可以证明,如果存在解,则在给定高度限制下一定存在一个解。

如果存在多个正确解,可以输出其中任意一个。

6
2 1 5 2 7 4

YES
2 3 1 6

5
1 3 1 9 20

NO

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 00 是样例。

子任务 分值 附加限制 子任务依赖 备注
11 55 n≤20n \leq 20,C≤20C \leq 20 00
22 77 n≤200n \leq 200,C≤200C \leq 200 0,10, 1
33 1313 n≤2000n \leq 2000,C≤2000C \leq 2000 0∼20 \sim 2
44 55 n≤100000n \leq 100000,C≤20C \leq 20 0,10, 1
55 55 n≤20n \leq 20,C≤100000C \leq 100000 0,10, 1
66 55 n≤50n \leq 50 0,1,50, 1, 5
77 1515 n≤2000n \leq 2000 0∼3,5,60 \sim 3, 5, 6
88 1010 n≤100000n \leq 100000,C≤100000C \leq 100000 0∼50 \sim 5
99 1515 n≤100000n \leq 100000 0∼80 \sim 8
1010 2020 0∼90 \sim 9