CF1168C And Reachability 题解 线性dp

题目链接

https://codeforces.com/problemset/problem/1168/C

题目大意

给定一个数组 \(a\)，从下标 \(x\) 能够转移到下标 \(y\) 要满足 \(x \lt y\) 且 \(a_{p_i}\, \&\, a_{p_{i+1}} > 0\)，其中 \(\&\) 表示逻辑与。多次询问，每次询问给出 \(x\) 和 \(y\)，你需要回答出能够通过若干次转移从下标 \(x\) 到达下标 \(y\)。

解题思路

定义 \(go_{i, k}\) 表示从下标 \(i\) 能够到达的最小的下标 \(j\)，且满足 \(a_j\) 的第 \(k\) 位为 \(1\)（这里 \(j \ge i\)）。

如何计算它呢？再定义一个 \(last_{i,k}\) 表示满足 \(j \gt i\) 且 \(a_j\) 的第 \(k\) 位为 \(1\) 的最小下标 \(j\)。

可以证明 \(go_{i,k}\) 等于 \(i\) 或者 \(\min{(go_{last_{i,j},k})}\) （其中 \(j\) 对应的是 \(a_i\) 为 \(1\) 的所有那些位）。

所以在 \(O(n \log \max\{a_i\})\) 时间复杂度只能能够求出所有的状态 \(go_{i, k}\)。然后只要对于 \(a_y\) 中为 \(1\) 的任意一位 \(j\) 来说，只要满足 \(go_{x, j} \leq y\) 就能从下标 \(x\) 转移到下标 \(y\)。

示例程序

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;

int n, q, a[maxn], last[19], go[maxn][19];

bool check(int x, int y) {
    for (int i = 0; i < 19; i++)
        if (go[x][i] <= y && (a[y] & (1 << i)))
            return true;
    return false;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", a+i);
    for (int i = 0; i < 19; i++) go[n+1][i] = last[i] = n+1;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < 19; j++)
            go[i][j] = n + 1;
        for (int j = 0; j < 19; j++) {
            if (a[i] & (1 << j)) {
                for (int k = 0; k < 19; k++) {
                    go[i][k] = min(go[i][k], go[ last[j] ][k]);
                }
                last[j] = i;
                go[i][j] = i;
            }
        }
    }
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        puts(check(x, y) ? "Shi" : "Fou");
    }
    return 0;
}

参考资料

https://codeforces.com/blog/entry/67241