[CodeForces1169E] And Reachability（思维，DP）

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://codeforces.com/contest/1169/problem/E

题意：给$n$个数$a_i$，$m$次询问，要求每次询问下标$x$的数能否一直与到下标为$y$的数，从$x$出发$a_x$与的每一个中间数$a_k$不能为$0$，问是否存在这样一个序列，能一直与到下标为$y$的数。

考虑DP，$f(i,j)$表示从$i$出发能走到$i$之后的最近的一个数的下标$p$，并且这两个数都有数位$j$. 于是我们可以枚举另一个数位$k$作为桥梁，看看是否可以连接$i$到$p$.

显然，我们需要维护一个$last_k$，表示第$i$个数后边的最近的数，并且这个数包括$k$位的下标。于是递推式为：
$$
f(i,j)=min(f(i,j),f(last(k),j))
$$
更新的时候实际上枚举的是是否可以做桥梁的$i$，并且倒序更新，这样才能保证之前的状态都已经计算过。

查询的时候可以询问$a_y$是否存在数位$i$，并且$f(x,i)$这个下标是否在$x$和$y$之间，如果在的话，这个数可以作为桥梁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int maxn = 300300;
const int maxm = 22;
int n, m, a[maxn];
int f[maxn][maxm], last[maxm];

signed main() {
  // freopen("in", "r", stdin);
  int x, y;
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for (int i = 0; i < maxn; i++) {
      for (int j = 0; j < maxm; j++) {
        f[i][j] = n + 1;
        last[j] = n + 1;
      }
    }
    for (int i = n; i >= 1; i--) {
      for (int j = 0; j < maxm; j++) {
        if ((1 << j) & a[i]) {
          for (int k = 0; k < maxm; k++) {
            f[i][k] = min(f[i][k], f[last[j]][k]);
          }
          last[j] = i;
          f[i][j] = i;
        }
      }
    }
    while (m--) {
      cin >> x >> y;
      bool ok = 0;
      for (int i = 0; i < maxm; i++) {
        if ((1 << i) & a[y]) {
          if (f[x][i] <= y) {
            ok = 1;
          }
        }
      }
      if (ok) cout << "Shi" << endl;
      else cout << "Fou" << endl;
    }
  }
  return 0;
}