先说一下:代码仅供参考,有20%会TLE!!!

比太郎（ビ太郎 / Bi-tarō） 这道JOI 2022 Final T1《Intercastellar》故事里的主角。

日文原名：ビ太郎，中文翻译有的版本直接写成比太郎。

故事背景（原题开头）

30XX年，比太郎是个外星交流大使，要给JOI星球的外星人介绍地球美食——卡斯提拉蛋糕（就是长崎蛋糕）。 他准备了一长条蛋糕，要按照规则切开，别人来问切完之后第X块蛋糕多长，就是咱们这道题要解决的事。

就像国内题的“小明”，这道题的小明就叫比太郎！ 他不参与任何计算，只是故事里的人物，代码完全不用管他，只是用来包装题目的小故事。

补充小细节

日文「太郎」就是最经典的男生名字，前面加个ビ（Bi），拼成ビ太郎。 JOI好多题都会造这种小故事，太郎、花子、健太轮番出场，纯用来讲故事，算法和人名没关系。

题解:

JOI 2022 Final（正式名字是 JOI2021/2022 本选，2022年2月举办）

整套一共5道题，难度梯度很大。**T1 Intercastellar（卡斯提拉蛋糕）**是唯一适合水平的，剩下T2~T5难度远超GESP五级。

T1 Intercastellar 题意

有一串蛋糕块，每块长度是$A_i$。 规则：反复操作，直到没有偶数长度的蛋糕。

1. 在所有偶数长度块里，挑最右边那一块
2. 把它对半切开，变成两块长度相等的小块（比如长度4切成2、2）

切完之后，所有蛋糕全变成奇数长度。 给Q个询问，每次问：切完之后，从左数第$X_j$块蛋糕的长度是多少。

重点：绝对不能真的模拟切割！数字会爆炸。 思路：对每一块原始蛋糕$A_i$，算出它能切多少次。 比如$A_i=12$：$12 \to 6,6 \to 3,3,3,3$，最后变成4块，每块长度3。 也就是：不断除以2直到变成奇数，得到最终单块长度val，能分裂出来cnt块。 我们顺着原始蛋糕，累加块数，找到询问的$X_j$落在哪个原始蛋糕分裂出来的区间，答案就是对应的val。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<long long> val,cnt;
    for(int i=0;i<n;++i){
        long long a;
        cin>>a;
        long long c=1;
        while(a%2==0){
            a/=2;
            c*=2;
        }
        val.push_back(a);
        cnt.push_back(c);
    }
    int q;
    cin>>q;
    for(int i=0;i<q;++i){
        long long x;
        cin>>x;
        long long sum=0;
        for(int j=0;j<n;++j){
            if(sum+cnt[j]>=x){
                cout<<val[j]<<endl;
                break;
            }
            sum+=cnt[j];
        }
    }
    return 0;
}

简单例子

输入：

2
12 7
2
3
4

12最后分裂成4块，每块3；7本身奇数，1块7。 全部序列：3,3,3,3,7 询问3 → 3；询问4 →3。

这题坑：千万别开数组模拟切割，$A_i$最大能到$2^{60}$。

※T2难度会明显上一个台阶。