Codeforces 1168C（二进制、dp）

81 阅读 0 评论 54 点赞

我是靠谱客的博主受伤季节，这篇文章主要介绍Codeforces 1168C（二进制、dp），现在分享给大家，希望可以做个参考。

要点

‘&’操作暗示二进制上按位思考
对于y为1的位，要求x和y之间要至少有两个此位为1的（包含x、y），这样&起来才不是0.而这些位中只要存在一个是ok的即可
dp去求每个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
const int maxn = 3e5 + 5, Log = 20;
int n, q, a[maxn];
int go[maxn][Log + 5], Last[Log + 5];

int main() {
    read(n), read(q);
    rep(i, 1, n)    read(a[i]);

    rep(j, 0, Log) {
        Last[j] = n + 1;
        rep(i, 1, n + 1)//注意这里，因为Last设的是这里
            go[i][j] = n + 1;
    }
    per(i, n, 1) {
        rep(j, 0, Log) {
            if ((a[i] >> j) & 1) {
                go[i][j] = i;
                rep(k, 0, Log)
                    go[i][k] = min(go[i][k], go[Last[j]][k]);
                Last[j] = i;
            }
        }
    }

    for (int x, y; q; q--) {
        read(x), read(y);
        bool yes = 0;
        rep(j, 0, Log)
            yes |= ((a[y] >> j) & 1) && (go[x][j] <= y);
        puts(yes ? "Shi" : "Fou");
    }
    return 0;
}