#2104. 倾诉

    ID: 2104 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest1898来源:qoj.ac数据:公开样例贪心

倾诉

倾诉

题目描述

第一试倾诉(confide) IOI2025 中国国家队选拔 倾诉(confide) 【题目描述】 “在我们倾诉的时候,烦恼衰减了。倾诉者的难过一半交给了对方,另一半随着声 波还给了世界。烦恼就这样在人群里越传越弱,直到随风而逝。” 小I 的小圈子里有n 个人,第i (1 ≤i ≤n) 个人初始有.正.整.数ai 的烦恼。 为了减轻大家的烦恼,小I 组织了一次聊天活动,活动中n 个人按照编号从小到大 的顺序从左往右坐成一排。 时间有限,小I 可以在活动中组织.不.超.过k 次倾诉。每次倾诉中,某个倾诉者 p (1 ≤p ≤n−1) 向右手边的人p+1 倾诉,这首先导致ap+1 ←ap+1 + 1 2ap,然后ap ←0, 其中←表示赋值。小I 可以任意选择每次倾诉的倾诉者。注意编号为n 的人不会向其 他人倾诉。 小I 希望大家的烦恼尽可能少,于是他想知道:在活动过后,所有人最终烦恼的最 大值最小是多少。 S 你需要输出答案的精确值。具体地,答案总能写成 2n 的形式,其中S 是一个不超 过2n × (maxn i=1 ai) 的正整数。你需要输出S 的二进制表示。 【输入格式】 从文件confide.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行一个整数T,表示测试数据组数,接下来依次 描述每组测试数据。 对于每组数据,第一行两个整数n, k,分别表示人数和倾诉次数上限;第二行n 个 正整数a1, a2, · · · , an 描述初始每个人的烦恼值。 【输出格式】 输出到文件confide.out 中。 对于每组数据输出一行一个01 字符串,从高位到低位描述S 的二进制表示。你的 输出不应该有前导零。 【样例1 输入】 3 1 3 1 2 5 2 1 3 3 2 4 5 2 1 5 第2 页 共9 页 第一试倾诉(confide) IOI2025 中国国家队选拔 3 3 6 5 2 1 7 【样例1 输出】 100100 1 10100 2 10100 3 【样例1 解释】 对于第一组测试数据,最优策略为让第一个人倾诉。最终烦恼值为(0, 4.5, 1),故输 出4.5 × 23 = 36 的二进制表示100100。 对于第二和第三组测试数据,最优策略为先让第二个人倾诉,再让第一个人倾诉。 最终烦恼值为(0, 2.5, 2),故输出2.5 × 23 = 20 的二进制表示10100。 【样例2】 见选手目录下的confide/confide2.in 与confide/confide2.ans。 【样例2 解释】 该组样例七个测试数据的答案分别为10, 10, 8, 5, 3.5, 2.75, 2.5。 【子任务】 设! n 表示单个测试点中所有测试数据的n 的和。对于所有测试数据,保证 • 1 ≤T ≤2 × 104, • 1 ≤n, ! n ≤2 × 104,1 ≤k ≤109, • ∀1 ≤i ≤n, 1 ≤ai ≤106。 ! n ≤ 子任务编号 分值 ai ≤ k ≥ 1 2 30 2 10 200 106 3 13 750 1 4 20 2,500 5 17 104 104 6 16 109 2 ×104 106 7 22 1 第3 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
3 1
5 2 1
3 2
5 2 1
3 3
5 2 1
100100
10100
10100

样例 2

7
10 1
10 9 8 7 6 5 4 3 2 1
10 3
10 9 8 7 6 5 4 3 2 1
10 5
10 9 8 7 6 5 4 3 2 1
10 7
10 9 8 7 6 5 4 3 2 1
10 9
10 9 8 7 6 5 4 3 2 1
10 11
10 9 8 7 6 5 4 3 2 1
10 13
10 9 8 7 6 5 4 3 2 1
10100000000000
10100000000000
10000000000000
1010000000000
111000000000
101100000000
101000000000