题解：CF2156B Strange Machine

linjinkun · 2025-11-13 16:20:19 · 题解

首先看到 n \le 20，虽然 a_i \le 10^9，但是你会发现当 1 \sim n 中只要有一台 B 机器，那么这一次轮回至少除以 2，所以复杂度最多是 O(qn \log V)，V 是值域，但你会发现如果 1 \sim n 中全都是 A 机器，那么这么做，复杂度就是 O(qV) 的，会 T 得飞起，但是你会发现如果 1 \sim n 中全都是 A 机器的话，那对于任意 a_i 答案显然是 a_i，所以特判即可通过。

代码：

#include<bits/stdc++.h>
using namespace std;
char s[25];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> _;
    while(_--)
    {
        int n,q;
        cin >> n >> q;
        cin >> s+1;
        int A = 0,B = 0;
        for(int i = 1;i<=n;++i)
        {
            A+=s[i] == 'A';
            B+=s[i] == 'B';
        }
        while(q--)
        {
            int x;
            cin >> x;
            if(B == 0)
            {
                cout << x << '\n';
            }
            else
            {
                int num = 0;
                while(x)
                {
                    for(int i = 1;i<=n;++i)
                    {
                        if(!x)
                        {
                            break;
                        }
                        ++num;
                        if(s[i] == 'A')
                        {
                            --x;
                        }
                        else
                        {
                            x>>=1;
                        }
                    }
                }
                cout << num << '\n';
            }
        }
    }
    return 0;
}