【CF1661B】Getting Zero（位运算，搜索）

【题目描述】
假设有一个数 v v v，对于每次操作，你都有以下两种选择：

• 将 v v v变成 ( v + 1 ) % 32768 (v+1)%32768 (v+1)%32768；
• 将 v v v变成 ( v ∗ 2 ) % 32768 (v*2)%32768 (v∗2)%32768。

现在给你 n n n个整数 a 1 , a 2 , … , a n a_1,a_2,dots, a_n a1​,a2​,…,an​，请问使得每个数变为 0 0 0的最少操作次数分别是多少？

【输入格式】
第一行输入一个整数 n ( 1 ≤ n ≤ 32768 ) n(1le nle 32768) n(1≤n≤32768)，表示整数的数量。
第二行输入 n n n个整数 a 1 , a 2 , … , a n ( 0 ≤ a i < 32768 ) a_1,a_2,dots, a_n(0le a_i<32768) a1​,a2​,…,an​(0≤ai​<32768)。

【输出格式】
输出 n n n个整数，第 i i i个数表示将 a i a_i ai​变为 0 0 0所需的最少操作次数。

【输入样例】

4
19 32764 10240 49

【输出样例】

14 4 4 15 

【分析】

由于 32768 = 2 15 32768=2^{15} 32768=215，因此最多将一个数乘以 15 15 15次 2 2 2后对 32768 32768 32768取模即为 0 0 0，因为 ( v ∗ 2 15 ) % 2 15 = 0 (v*2^{15})%2^{15}=0 (v∗215)%215=0，所以答案最大为 15 15 15。
假设需要进行 i i i次加法操作， j j j次减法操作，那么需要满足 i ≤ 15 , j ≤ 15 ile 15,jle 15 i≤15,j≤15，最后的结果即为 i + j i+j i+j。
在进行若干次乘法操作后得到的值为偶数，不能再加上一个奇数，因为那样就不可能做到模 32768 32768 32768等于 0 0 0，而如果再加上一个偶数，则一定不如先加后乘更优，例如 v → v + 1 → 2 ( v + 1 ) vrightarrow v+1rightarrow 2(v+1) v→v+1→2(v+1)优于 v → 2 v → 2 v + 1 → 2 v + 2 vrightarrow 2vrightarrow 2v+1rightarrow 2v+2 v→2v→2v+1→2v+2。因此可以证明一定是先进行 i i i次加法操作，之后再进行 j j j次乘法操作，即 ( v + i ) ∗ 2 j % 32768 = 0 (v+i)*2^j%32768=0 (v+i)∗2j%32768=0。
本题使用BFS也可以过，从当前数开始，搜索出转变成 0 0 0所需的最少步数，如果步数超过 15 15 15则剪枝。

【代码】

#include 
#include 
#include 
using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int x, res = 15;
        cin >> x;
        for (int i = 0; i <= 15; i++)
            for (int j = 0; j <= 15; j++)
                if (((x + i) << j) % 32768 == 0)
                    res = min(res, i + j);
        cout << res << ' ';
    }
    return 0;
}

【BFS代码】

#include 
#include 
#include 
#include 
using namespace std;

const int N = 33000;
int dis[N];

void bfs(int s)
{
    memset(dis, -1, sizeof dis);
    dis[s] = 0;
    queue Q;
    Q.push(s);
    while (Q.size())
    {
        int t = Q.front();
        Q.pop();
        if (!t) break;
        int u = (t + 1) % 32768, v = (t << 1) % 32768;
        if (!~dis[u] && dis[t] + 1 <= 15) dis[u] = dis[t] + 1, Q.push(u);
        if (!~dis[v] && dis[t] + 1 <= 15) dis[v] = dis[t] + 1, Q.push(v);
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int x;
        cin >> x;
        bfs(x);
        cout << dis[0] << ' ';
    }
    return 0;
}