[HNOI2018]寻宝游戏(题解转载自别处)

题解(自别处转载):

Luogu
CSDN

这题关键是将运算符也替换成0,1

然后在运算符与原串混杂里找规律。

而且替换的方式也有所要求，考场上两种替换方式都要尝试。

#include <bitset>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <assert.h>

#include <algorithm>

using namespace std;

#define LL long long

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define GO debug("GO\n")

inline int rint() {

    register int x = 0, f = 1; register char c;

    while (!isdigit(c = getchar())) if (c == '-') f = -1;

    while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));

    return x * f;

}

template<typename T> inline void chkmin(T &a, T b) { a > b ? a = b : 0; }

template<typename T> inline void chkmax(T &a, T b) { a < b ? a = b : 0; }

const int maxN = 5e3 + 10, mod = 1e9 + 7;

char b[maxN][maxN];

int n, m, q;

int buc[maxN], rk[maxN];

struct xhc {

    int num[maxN]; int id; LL ans;

    friend bool operator< (xhc a, xhc b) {

        for (int i = 1; i <= n; ++ i)

            if (a.num[i] != b.num[i]) return a.num[i] > b.num[i];

        return 0;

    }

} a[maxN];

LL qpow(LL a, LL b) {

    LL res = 1;

    for (; b; b >>= 1, a = a * a % mod)

        if (b & 1) res = res * a % mod;

    return res;

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("xhc.in", "r", stdin);

    freopen("xhc.out", "w", stdout);

#endif

    ios::sync_with_stdio(0);

    cin >> n >> m >> q;

    for (int i = 1; i <= n; ++ i)

        cin >> (b[i] + 1);

    for (int i = 1; i <= m; ++ i) {

        a[i].id = i;

        for (int j = n; j >= 1; -- j) {

            a[i].num[n - j + 1] = b[j][i] - '0';

            a[i].ans = (1ll * (a[i].ans<<1ll) + (b[j][i] - '0')) % mod;

        }

    }

    sort(a + 1, a + m + 1);

    for (int i = 1; i <= m; ++ i)

        rk[a[i].id] = i;

    a[0].ans = qpow(2, n);

    while (q--) {

        static char str[maxN];

        cin >> str;

        for (int i = 1; i <= m; ++ i)

            buc[rk[i]] = str[i - 1] - '0';

        int pos0 = 0, pos1 = 0;

        for (int i = m; i >= 1; -- i)

            if (buc[i]) { pos1 = i; break; }

        for (int i = 1; i <= m; ++ i)

            if (!buc[i]) { pos0 = i; break; }

        if (pos0 and pos1 and pos0 < pos1) puts("0");

        else

            printf("%lld\n", (a[pos1].ans + mod - a[pos1 + 1].ans) % mod);

    }

}