同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1163_折叠

2022-5-16 18:17| 发布者: Hocassian| 查看: 77| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503709555200-Problem List-采集的数据-后羿采集器.html

Pro.ID

1163

Title

折叠

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1163

AC

262

Submit

680

Ratio

38.53%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

给出一个数组，共N有个整数。N是2的k次幂。

将数组首尾折叠起来，数组长度减少一半。具体做法是把尾部向上向前翻，使得尾压在头的上面。

在第奇数次折叠时，新数组元素是折叠后上下对应位置的元素之和。

在第偶数次折叠时，新数组元素是折叠后上下对应位置的元素之差，即“尾”减“头”。

进行p次（p<k）折叠后，从头到尾输出最终折叠后的数组。

详见样例。

输入

单测试用例。

第一行是两个正整数n和p，表示共数组共有n个元素( n ≤ 65536 )，以及要进行p次折叠。

其中，n=2^k ， 2 < k ≤ 16 ， 0 < p < k

第二行是n个数组元素，全部元素均在int表示范围内。

输出

Description

给出一个数组，共N有个整数。N是2的k次幂。

将数组首尾折叠起来，数组长度减少一半。具体做法是把尾部向上向前翻，使得尾压在头的上面。

在第奇数次折叠时，新数组元素是折叠后上下对应位置的元素之和。

在第偶数次折叠时，新数组元素是折叠后上下对应位置的元素之差，即“尾”减“头”。

进行p次（p<k）折叠后，从头到尾输出最终折叠后的数组。

详见样例。

Input

单测试用例。

第一行是两个正整数n和p，表示共数组共有n个元素( n ≤ 65536 )，以及要进行p次折叠。

其中，n=2^k ， 2 < k ≤ 16 ， 0 < p < k

第二行是n个数组元素，全部元素均在int表示范围内。

Output

输出p次折叠后的数组。

Sample Input

16 2
1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1

Sample Output

14 10 6 2

Hint

开始前： 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1
第一次折叠后：
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
做加法，得到： 2 4 6 8 10 12 14 16
第二次折叠后：
16 14 12 10
2 4 6 8
做减法，得到： 14 10 6 2
这个例子是说明“折叠”操作是怎样的。