【洛谷P8160】[JOI 2022 Final] 星际蛋糕 (Intercastellar)
公开作品
lihl
咕咕咕,咕咕
2023-10-22 19:21:07
26
【洛谷P8160】[JOI 2022 Final] 星际蛋糕 (Intercastellar)
greenFlag
作品介绍

注意!在输入样例时需要一个一个输入而并非直接复制粘贴

[JOI 2022 Final] 星际蛋糕 (Intercastellar)

题目背景

在 30XX 年,由于科学家和工程师的不断努力,不同星球之间的互动变得非常活跃。比太郎是一只河狸,他现在是一项交流项目的大使。他的任务是向不同星球的居民介绍地球上的食物。他将在下午 1 点出发去 JOI 星球。

现在,比太郎正计划向 JOI 星球的居民介绍 castella。castella 已经被切成了若干段。castella 是一种由面粉、鸡蛋、糖和淀粉糖浆制成的烘烤海绵蛋糕。

题目描述

castella 的形状是一个在水平方向上很长的长方体。它被切成了 N 段,其中从左往右的第 i 段的长度为整数 A_i。

几分钟前,我们得知 JOI 星球的居民不喜欢偶数。为了解决此问题,你需要不断执行下列操作,直到不存在长度为偶数的段。

  1. 在长度为偶数的段中,你选择最靠右的一段。
  2. 你将选中的这一段切成两个长度相等的段。也就是说,假设选中的这一段的长度是 k,你将其切成长度为 k/2 的两段。你不改变其他段的位置。

为了确认操作是否被正确地执行了,比太郎让你回答 Q 个询问。第 j 个询问如下:

  • 当所有操作执行完毕后,从左往右的第 X_j 段的长度为多少?

给定 castella 的信息与询问,请写一个程序回答所有询问。

输入格式

第一行,一个正整数 N。

接下来 N 行,第 i 行一个正整数 A_i。

接下来一行,一个正整数 Q。

接下来 Q 行,第 j 行一个正整数 X_j。

输出格式

输出 Q 行,第 j 行一个数,表示第 j 个询问的答案。

样例 #1

样例输入 #1

4
14
9
8
12
6
2
3
5
7
11
13

样例输出 #1

7
9
1
1
1
3

样例 #2

样例输入 #2

13
1
4
1
4
2
1
3
5
6
2
3
7
3
8
2
10
11
13
15
17
18
20

样例输出 #2

1
1
1
1
5
3
1
3

样例 #3

样例输入 #3

16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704

样例输出 #3

5
1
7
57
1

提示

【样例解释 #1】

一开始,castella 从左到右的段的长度分别为 14, 9, 8, 12。

当所有操作执行完毕后,castella 被切成了 15 段。从左到右的段的长度分别为 7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3。

这个样例满足子任务 2, 3 的限制。

【样例解释 #2】

这个样例满足所有子任务的限制。

【样例解释 #3】

这个样例满足子任务 2, 3 的限制。


【数据范围】

本题采用捆绑测试。

对于 100% 的数据,1 ≤ N, Q ≤ 2x10^5,1 ≤ A_i ≤ 10^9,1 ≤ X_j ≤ 10^15,X_j ≤ X_j+1,保证当所有操作执行完毕后,castella 被切成了至少 X_Q 段。

  • 子任务 1(25 分):A_i ≤ 8。
  • 子任务 2(35 分):N, Q ≤ 1000。
  • 子任务 3(40 分):无特殊限制。

译自 JOI 2022 Final T1「インターカステラー / Intercastellar
lihl 手动取消Latex语法

转换题解:https://www.luogu.com.cn/blog/368355/solution-p8160
随便找了道lowbit
临时变量很好用,爱来自lihl

社区热门

评论

本项目不支持手机或可直接操作