小信的特工行动题解

经验分享区
1

朴素做法（45pts）

直接暴力 dfs， 时间复杂度 O(2^n) 明显的，当 n = 45 的时候， TLE

正解

注意到模数为 2^{64} 注意到 unsigned long long 类型时，由于没有符号位， 累加超出范围时会自然溢出，不需要取模。

由于直接 dfs 的时间复杂度难以接受， 所以我们考虑折中搜索， 把原本在一个线性空间的是数组拆成两个 dfs 分别搜索， 这样我们的时间复杂的降到了 2^{\frac{n}{2}} + 2 ^ {\frac{n}{2}} 当 n = 45 时 运算约 10^7 次， 在 c++ 中可以接受（毕竟巅峰时期的信友队测评机可是可以一秒跑 10^9 ） 的

void dfs1(int p, ULL sum)
{
    if(p == n / 2)
    {
        mp[sum] = res.substr(0, n / 2);
        return;
    }
    res[p] = '0';
    dfs1(p + 1, sum);

    res[p] = '1';
    dfs1(p + 1, sum + b[p]);
}

void dfs2(int p, ULL sum)
{
    if(p == n)
    {
        if(mp.count(s - sum))
        {
            cout << mp[s - sum] << res.substr(n / 2, n - n / 2) << endl;
        }
        return;
    }
    res[p] = '0';
    dfs2(p + 1, sum);

    res[p] = '1';
    dfs2(p + 1, sum + b[p]);
}
1 个赞