[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;
}