题目翻译

给定 $x=(00001111)_2,y=(00110011)_2,z=(01010101)_2$。

你有二元运算符『与』和『或』，以及一元运算符『取反』。

与：表示二进制下按位与，字符是 &。

或：表示二进制下按位或，字符是 |。

取反：表示二进制下按位取反，字符是 !。

优先级从大到小排列是：取反，与，或。

给出 $n(1\leq n\leq 10^4)$ 个询问，每次给出长度为 $8$ 的二进制串，求其在使用 $x,y,z$ 和以上三种操作后得到该二进制串的最优答案。

对于『最优答案』的解释：优先取长度小的，长度一样优先取字典序小的。

题目思路

首先，$n\leq 10^4$ 的数据范围是假的，只有 $256$ 个输入串。

二进制串改成十进制数状压也是显然的。

考虑设计 $f_i$ 表示凑到 $i$ 的『最优答案』。

但是因为优先级会有很多括号的事情，所以加入一位 $f_{i,k}$ 表示凑到 $i$ 当前优先级为 $k$ 得到的『最优答案』。

转移十分显然，这里从自己转移到别人比较方便，分两大类：

1. 一元运算符

那么就是给自己前面加上 ! 即可。

2. 二元运算符

转移暴力枚举 $i,j\in [0,256)$，之后枚举 $i$ 和 $j$ 的优先级，再枚举两个二元运算符进行转移。

关于实现，这里不推荐大家写若干循环，我直接手动循环展开转移的。不然优先级加括号要判挺多东西。

但是，这个做法还有个问题。你转移一次不一定是对的啊。

然后你会发现，你一共 $255$ 个值的状态，其实状态很少，多跑几轮总能转移结束。那么你就类似图论最短路多跑几次，直到所有的“松弛操作”都没有进行再结束。

也就是说，状态设计成 $f_{r,i,k}$ 表示第 $r$ 轮转移凑到 $i$ 当前优先级为 $k$ 得到的『最优答案』。

实现的时候注意优先级问题要加括号！取『最优答案』的时候要注意不要从空串开始转移。关于转移次数，我转移了 $6$ 轮就过了。

完整代码

CF submission 254456293

#include <bits/stdc++.h>
using namespace std;
const int a[] = {0b00001111, 0b00110011, 0b01010101};
const char ch[] = {'x', 'y', 'z'};
const char op[] = {'|', '&', '!'}; // 低 ~ 高，单值 和 括号 也算 2 级，高级 外面可以套 低级
const int R = 6;
const int n = 1 << 8;
string Min(string &a, string &b) { return a.size() ^ b.size() ? (a.size() < b.size() ? a : b) : (a < b ? a : b); }
void chkmn(string &a, string b)
{
    if (a.empty())
        a = b;
    else
        a = Min(a, b);
}
int StB(string &s)
{
    int ret = 0;
    for (char c : s)
        ret = ret << 1 | c ^ '0';
    return ret;
}
int inv(int x) { return 0b11111111 ^ x; }
string f[R + 1][n][3];
string ans[n];
int t;
void solve()
{
    string s;
    cin >> s;
    cout << ans[StB(s)] << '\n';
}
int main()
{
    for (int i = 0; i < 3; i++)
        f[0][a[i]][2] = ch[i];
    for (int r = 0; r < R; r++)
    {
        // 单值修改
        for (int i = 0; i < n; i++)
        {
            // 继承原始
            if (!f[r][i][0].empty())
                chkmn(f[r + 1][i][0], f[r][i][0]);
            if (!f[r][i][1].empty())
                chkmn(f[r + 1][i][1], f[r][i][1]);
            if (!f[r][i][2].empty())
                chkmn(f[r + 1][i][2], f[r][i][2]);
            // 取反
            if (!f[r][i][0].empty())
                chkmn(f[r + 1][inv(i)][2], "!(" + f[r][i][0] + ")");
            if (!f[r][i][1].empty())
                chkmn(f[r + 1][inv(i)][2], "!(" + f[r][i][1] + ")");
            if (!f[r][i][2].empty())
                chkmn(f[r + 1][inv(i)][2], "!" + f[r][i][2]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // 0 | 0
                if (!f[r][i][0].empty() && !f[r][j][0].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][0] + "|" + f[r][j][0]);
                // 0 | 1
                if (!f[r][i][0].empty() && !f[r][j][1].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][0] + "|" + f[r][j][1]);
                // 0 | 2
                if (!f[r][i][0].empty() && !f[r][j][2].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][0] + "|" + f[r][j][2]);
                // 0 & 0
                if (!f[r][i][0].empty() && !f[r][j][0].empty())
                    chkmn(f[r + 1][i & j][1], "(" + f[r][i][0] + ")&(" + f[r][j][0] + ")");
                // 0 & 1
                if (!f[r][i][0].empty() && !f[r][j][1].empty())
                    chkmn(f[r + 1][i & j][1], "(" + f[r][i][0] + ")&" + f[r][j][1]);
                // 0 & 2
                if (!f[r][i][0].empty() && !f[r][j][2].empty())
                    chkmn(f[r + 1][i & j][1], "(" + f[r][i][0] + ")&" + f[r][j][2]);

                // 1 | 0
                if (!f[r][i][1].empty() && !f[r][j][0].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][1] + "|" + f[r][j][0]);
                // 1 | 1
                if (!f[r][i][1].empty() && !f[r][j][1].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][1] + "|" + f[r][j][1]);
                // 1 | 2
                if (!f[r][i][1].empty() && !f[r][j][2].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][1] + "|" + f[r][j][2]);
                // 1 & 0
                if (!f[r][i][1].empty() && !f[r][j][0].empty())
                    chkmn(f[r + 1][i & j][1], f[r][i][1] + "&(" + f[r][j][0] + ")");
                // 1 & 1
                if (!f[r][i][1].empty() && !f[r][j][1].empty())
                    chkmn(f[r + 1][i & j][1], f[r][i][1] + "&" + f[r][j][1]);
                // 1 & 2
                if (!f[r][i][1].empty() && !f[r][j][2].empty())
                    chkmn(f[r + 1][i & j][1], f[r][i][1] + "&" + f[r][j][2]);

                // 2 | 0
                if (!f[r][i][2].empty() && !f[r][j][0].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][2] + "|" + f[r][j][0]);
                // 2 | 1
                if (!f[r][i][2].empty() && !f[r][j][1].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][2] + "|" + f[r][j][1]);
                // 2 | 2
                if (!f[r][i][2].empty() && !f[r][j][2].empty())
                    chkmn(f[r + 1][i | j][0], f[r][i][2] + "|" + f[r][j][2]);
                // 2 & 0
                if (!f[r][i][2].empty() && !f[r][j][0].empty())
                    chkmn(f[r + 1][i & j][1], f[r][i][2] + "&(" + f[r][j][0] + ")");
                // 2 & 1
                if (!f[r][i][2].empty() && !f[r][j][1].empty())
                    chkmn(f[r + 1][i & j][1], f[r][i][2] + "&" + f[r][j][1]);
                // 2 & 2
                if (!f[r][i][2].empty() && !f[r][j][2].empty())
                    chkmn(f[r + 1][i & j][1], f[r][i][2] + "&" + f[r][j][2]);
            }
        }
        // cerr << r << endl;
        // for (int i = 0; i < n; i++)
        //     for (int j = 0; j < 3; j++)
        //         cerr << f[r][i][j] << " \n"[j == 2];
        // cerr << endl;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            chkmn(ans[i], f[R][i][j]);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}