CF1168C And Reachability
And Reachability - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
目录题目大意
给定一个长度为 \(n\) 的数组 \(a\) 。
你可以选择一个长度为 \(k\) 的数组 \(p\)
\(p_1 = x , p _k = y\)
当 \(x<y\) 且 \(a_{p_i} \& a_{p_{i + 1}} > 0\) 时，我们称 \(x , y\) 为可到达的
现在给你 \(q\) 组询问，每个询问问你 \(x , y\) 是否可以到达
思路
\(dp\)
设 \(c_{i , j}\) 为二进制下的 \(a_i\) 的第 \(j\) 位是否为 \(1\)
设 \(g_{i , j}\) 为 \([1,{i- 1}]\) 中第 \(j\) 位为 \(1\) 且离 \(i\) 最近的点
那么
\[g_{i , j} = (c_{i - 1 , j} = 1) ? i - 1 : g_{i - 1 , j} \]设 \(f_{i , j}\) 为 \([1 , i -1]\) 中第 \(j\) 位为 \(1\) 且能够到达 \(i\) 的最近的一个点
-
需要中转站
\[f_{i , j} = max (f_{i , j} , f_{g_{i , k} , j}) (c_{i , k} = 1) \] -
不需要中转站
\[f_{i , j} = max (f_{i , j} , f_{i , k}) (c_{i , k} == 1 \ and \ c_{g_{i , k} , j} = 1 ) \]
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 3e5 + 5;
int n , q;
int a[N] , f[N][25] , g[N][25] , c[N][25];
int read () {
int val = 0;
char ch = getchar ();
while (ch > '9' || ch < '0') ch = getchar ();
while (ch >= '0' && ch <= '9') {
val = val * 10 + (ch - '0');
ch = getchar();
}
return val;
}
void pre (int i , int x) {
fu (j , 1 , 20) {
if (x & 1) c[i][j] = 1;
x >>= 1;
}
}
int main () {
freopen ("and.in" , "r" , stdin);
freopen ("and.out" , "w" , stdout);
n = read () , q = read ();
fu (i , 1 , n) {
a[i] = read ();
pre (i , a[i]);
}
fu (i , 1 , n) {
fu (j , 1 , 20) {
if (c[i - 1][j]) g[i][j] = i - 1;
else g[i][j] = g[i - 1][j];
}
}
fu (i , 1 , n) {
fu (j , 1 , 20) {
fu (k , 1 , 20) {
if (!c[i][k]) continue;
int x = g[i][k];
if (c[x][j]) f[i][j] = max (f[i][j] , x);
else f[i][j] = max (f[i][j] , f[x][j]);
}
}
}
int l , r , flg = 0;
while (q --) {
flg = 0;
scanf ("%d%d" , &l , &r);
fu (i , 1 , 20) {
if (c[l][i] && f[r][i] >= l) {
puts ("Shi");
flg = 1;
break;
}
}
if (flg) continue;
puts ("Fou");
}
return 0;
}