[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
")

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
", (a[pos1].ans + mod - a[pos1 + 1].ans) % mod);
    }
}