Chlience

【题解】LOJ 2494. 「AHOI / HNOI2018」寻宝游戏
Problem给你 $n$ 个长度为 $m$ 的 $0101$ 串你可以在每个串前面加一个运算符 $\land$ ...
扫描右侧二维码阅读全文
14
2018/12

【题解】LOJ 2494. 「AHOI / HNOI2018」寻宝游戏

Problem

给你 $n$ 个长度为 $m$ 的 $0101$ 串

你可以在每个串前面加一个运算符 $\land$ 或 $\lor$,分别表示 $and$ 和 $or$ 运算

每次询问一个长度为 $m$ 的 $01$ 串,问有多少总操作序列能得到这个串

Solution

先考虑每个串只有一个字符的情况
询问:给定一个 $01$ 串,在其中加入 $\land$ 和 $\lor$ ,有多少种方式得到 $0$ 或 $1$

因为第一位是 $0$ ,那么当且仅当某一位为 $\lor1$ 并且之后没有 $\land 0$ 才能使得最后为 $1$
考虑将第 $i$ 位(为$1$) 作为最后一个 $\lor 1$ 的位置,那么前面序列就可以任意放 $\land,\lor$ 而后面序列需要 $\lor 0,\land1$

如果将其反向过来,就是 $1$ 的后面必须接 $\land$,$0$ 的后面必须接 $\lor$ ,直到第 $i$ 位接 $\lor$ 后就可以随便接了
如果将 $\land$ 看做 $1$,$\lor$ 看做 $0$ ,从右向左将操作序列连起来形成一个二进制串 $x$,原串从右往左连起来形成一个二进制串 $b$,那么使得最终答案为 $1$,当且仅当 $x<b$

当然也可以使用归纳法

若在最后加入一个新串 $0$,那么只能是 原答案 序列加上 $\lor 0$
若在最后加入一个新串 $1$,那么既可以是 原答案 序列加上 $\lor 1$ ,也可以是 任意 序列加上 $\land 1$

反过来看仍然满足 $x<b$ 的条件

考虑每个串多字符的情况,也就是对于每一位都满足单字符的条件

那么现在的问题就是找到区间 $x\in [L,R)$
对于某个特定答案序列 $r$,其区间范围如此确定:
$L = max(b_j)\quad r_j==0$
$R = min(b_j)\quad r_j==1$

所以我们对 $b_j$ 进行一次 基数排序 ,每次扫一下得到 $L,R$ 的值,然后相减取膜

注意最后判断是否无解的情况是需要额外设立变量

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int M = 5010;
const int mod = 1000000007;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n , m , q;
char str[N][M];
char r[M];
bool s[M][N];
int a[M] , b[M];
int sum[M];
int Count[2];
int main() {
    n = read(); m = read(); q = read();
    for(int i = 1 ; i <= n ; ++ i)
        scanf("%s" , str[i]);
    for(int i = 1 ; i <= m ; ++ i)
        for(int j = n ; j ; -- j) {
            s[i][j] = str[j][i - 1] - '0';
            sum[i] = (sum[i] * 2 + str[j][i - 1] - '0') % mod;
        }
    for(int i = 1 ; i <= m ; ++ i) a[i] = i;
    for(int i = 1 ; i <= n ; ++ i) {
        Count[0] = Count[1] = 0;
        for(int j = 1 ; j <= m ; ++ j)
            Count[s[a[j]][i]] ++;
        Count[1] += Count[0];
        for(int j = m ; j >= 1 ; -- j)
            b[Count[s[a[j]][i]] --] = a[j];
        for(int j = 1 ; j <= m ; ++ j)
            a[j] = b[j];
    }
    sum[m + 1] = 1;
    for(int i = 1 ; i <= n ; ++ i) sum[m + 1] = sum[m + 1] * 2 % mod;
    for(int i = 1 ; i <= q ; ++ i) {
        scanf("%s" , r + 1);
        int L = 0 , R = m + 1 , LL = 0 , RR = m + 1;
        for(int j = 1 ; j <= m ; ++ j) {
            if(r[a[j]] == '1') {
                R = a[j];
                RR = j;
                break;
            }
        }
        for(int j = m ; j >= 1 ; -- j) {
            if(r[a[j]] == '0') {
                L = a[j];
                LL = j;
                break;
            }
        }
        if(LL >= RR) puts("0");
        else printf("%d\n" , (sum[R] - sum[L] + mod) % mod);
    }
    return 0;
}
Last modification:February 11th, 2019 at 08:28 am

Leave a Comment