题解：CF2156B Strange Machine

首先看到

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

，所以特判即可通过。

代码：

CPP

#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;
}

题解：CF2156B Strange Machine

文章操作

相关推荐

评论

题解：CF2156B Strange Machine