Educational Codeforces Round 134 (Rated for Div. 2)

• Educational Codeforces Round 134 (Rated for Div. 2)
  • D. Maximum AND
  • E. Prefix Function Queries

D. Maximum AND

给定两个数组\(a\)和\(b\)，可以对\(b\)进行任意排列，定义\(c_i = a_i \oplus b_i\)，定义\(d = c_1 \& c_2 \& \cdots c_n\)，求最大的\(d\)。

这种求按位操作之后的最值，基本上就是从高位往低位枚举即可。

显然，最高位特别好计算，我们只需要判断\(a\)中\(1\)的数量和\(b\)中0的数量是否一致即可，如果一致则最高位可以为\(1\)，但是如果最高位为\(1\)，在求解次高位时就不能以这种方式去处理了，因为我们得考虑上一位的限制。

因此，我们可以维护一个mask代表上一位的限制，那么显然有\(a_i \& mask \oplus b_i \& mask = mask\)的情况。实际上，我们维护mask就是用来限定每个\(a\)能与哪些\(b\)进行匹配，注意，对于\(b\)来说，我们需要按位取反（考虑到异或操作）。

最后，我们可以用个map类似的数据结构来进行维护，代码如下，时间复杂度为：\(\mathcal{O}(n\log n \log (\max(a,b))\)

constexpr int B = 29;
void solve(){
    int n;
    std::cin >> n;;

    vt<int> a(n), b(n);
    R1V(a, n);
    R1V(b, n);

    auto check = [&](int bits){
        map<int, int> hsh;
        for (int x: a) ++ hsh[x & bits];
        for (int x: b) -- hsh[~x & bits];

        int ok = 1;
        for (auto &e: hsh) ok &= e.second == 0;
        return ok;
    };

    int ans = 0;
    for (int i = B; ~i; -- i){
        if (check(ans | (1 << i)))
            ans |= 1 << i;
    }
    wpr(ans);
}

E. Prefix Function Queries

给定一个字符串 \(s\)，以及\(q(\le1e5)\)个查询。每次查询给出一个字符串\(t(|t|<=10)\)，输出\(s + t\)的前缀函数在末尾\(|t|\)个位置的值。

这题容易想到首先计算出前\(|s|\)个的fail数组，然后基于此再对于后面这\(|t|\)个进行计算，但是在最坏的情况下可能需要跳转\(\mathcal{O}(n)\)次，所以我们需要进行优化。

这里需要用到可持久化KMP，但是目前我连KMP都没有做专题，所以我暂时放弃对于这部分的理解，补上几个链接：

• KMP1
• KMP2

好了 目前的任务先是把《算法导论》中的字符串部分全部学习完，再来补这个。