题解：CF2156B Strange Machine

Lucas_Fan_2013 · 2026-11-10 08:25:50 · 题解

思路

模拟。

把 n 个数理解为一个环，一遍一遍扫，直到 x 为 0。

优化

因为 x\le10^9，所以当 n 台机器都是 A 类型时，一个一个减一，太慢，会 TLE。

特判一下，答案显然为所给的 a_i。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N = 3e1+10;
int t;
int n,q;
char a[N];
int ans;
int main(){
    cin>>t;
    while (t--){
        cin>>n>>q;
        for (int i=1;i<=n;i++) cin>>a[i];
        while (q--){
            ans=0;
            int A;cin>>A;
            bool b=false;
            for (int i=1;i<=n;i++) if (a[i]=='B'){b=true;break;}
            if (b==false){ // 特判
                cout<<A<<endl;
                continue;
            }
            for (int i=1;;i++){
                if (a[i]=='A'){
                    A-=1;
                }
                else A=(A>>1);
                ans++;
                if (A==0){
                    cout<<ans<<endl;
                    break;
                }
                if (i==n) i=0;
            }
        }
    }
    return 0;
}