【洛谷4424】[HNOI_AHOI2018]寻宝游戏（我也不知道括号里该写啥）

题目

洛谷 4424

分析

感觉思路比较神仙。

对于按位与和按位或两种运算，显然每一位是独立的，可以分开考虑。

对于某一位，「与 \(0\)」会将这一位变成 \(0\)，「或 \(1\)」会将这一位变成 \(1\) ，「与 \(1\)」和「或 \(0\)」不会改变这一位的值。前两种操作会改变这一位的值，而后两种不会。将前两种称为「关键操作」，那么某一位最终的值取决且仅取决于这一位的最后一次「关键操作」是「与 \(0\)」还是「或 \(1\)」。如果是前者或者不存在关键操作，最终的值就是 \(0\) ，否则是 \(1\) 。

接下来就比较魔幻了。对于每一位，把每个操作符的右操作数（即题目中给定的 \(a_i\)）从右到左 排成一个字符串。假定已经填入了操作符，把这些操作符中与视作 \(1\) ，或视作 \(0\) ，也 从右到左 排成一个字符串。那么，最后一个关键操作就是这两个字符串第一个不相等的地方。换句话说，比较这两个字符串，如果操作符的字符串大（即最后一个关键操作是与 \(0\) ），最终结果就是 \(0\) ，否则是 \(1\) 。

有了这个奇妙的结论，把每一位的右操作数字符串处理出来，从小到大排序（下文中位的「前」「后」是按照这个顺序排序的）。如果把操作符字符串放在某两位的右操作数字符串之间，那么前面的所有位都是 \(0\) ，后面的所有位都是 \(1\) 。如果 \(r_i\) 中最靠前的 \(1\) 在最靠前的 \(0\) 之前，则无解；否则可以确定合法的操作符字符串在哪两位之间，答案就是字典序在这两位的字符串之间的串的数量。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
using namespace std;

namespace zyt
{
    const int N = 1e3 + 10, M = 5e3 + 10, P = 1e9 + 7;
    int arr[N][M], val[M], id[M];
    basic_string<int> s[M];
    bool cmps(const int a, const int b)
    {
        return s[a] < s[b];
    }
    int work()
    {
        int n, m, q;
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%1d", &arr[i][j]);
        for (int i = 1; i <= m; i++)
        {
            id[i] = i;
            for (int j = n, tmp = 0, cnt = 0; j > 0; j--)
            {
                tmp = tmp * 2 + arr[j][i], ++cnt;
                if (j == 1 || cnt == 16)
                    s[i] += tmp, tmp = cnt = 0;
            }
        }
        sort(id + 1, id + m + 1, cmps);
        for (int i = 1; i <= m; i++)
            for (int j = n; j > 0; j--)
                val[i] = (val[i] * 2LL + arr[j][i]) % P;
        val[m + 1] = 1;
        for (int i = 1; i <= n; i++)
            val[m + 1] = val[m + 1] * 2LL % P;
        id[m + 1] = m + 1;
        while (q--)
        {
            bool flag = false, no_ans = false;
            static int r[M];
            for (int i = 1; i <= m; i++)
                scanf("%1d", r + i);
            for (int i = 1; i <= m; i++)
                if (r[id[i]] == 1)
                    flag = true;
                else
                    no_ans |= flag;
            if (no_ans)
                puts("0");
            else
            {
                bool flag = false;
                for (int i = 1; i <= m; i++)
                    if (r[id[i]] == 1)
                    {
                        flag = true;
                        printf("%d\n", (val[id[i]] - val[id[i - 1]] + P) % P);
                        break;
                    }
                if (!flag)
                    printf("%d\n", (val[id[m + 1]] - val[id[m]] + P) % P);
            }
        }
        return 0;
    }
}
int main()
{
    return zyt::work();
}