注意！在输入样例时需要一个一个输入而并非直接复制粘贴
[JOI 2022 Final] 星际蛋糕 (Intercastellar)
题目背景
在 30XX 年，由于科学家和工程师的不断努力，不同星球之间的互动变得非常活跃。比太郎是一只河狸，他现在是一项交流项目的大使。他的任务是向不同星球的居民介绍地球上的食物。他将在下午 1 点出发去 JOI 星球。
现在，比太郎正计划向 JOI 星球的居民介绍 castella。castella 已经被切成了若干段。castella 是一种由面粉、鸡蛋、糖和淀粉糖浆制成的烘烤海绵蛋糕。
题目描述
castella 的形状是一个在水平方向上很长的长方体。它被切成了 N 段，其中从左往右的第 i 段的长度为整数 A_i。
几分钟前，我们得知 JOI 星球的居民不喜欢偶数。为了解决此问题，你需要不断执行下列操作，直到不存在长度为偶数的段。
- 在长度为偶数的段中，你选择最靠右的一段。
- 你将选中的这一段切成两个长度相等的段。也就是说，假设选中的这一段的长度是 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
社区热门
本项目不支持手机或可直接操作
Comment