还是倒着讲吧，上周末约好一起打周赛的朋友摸了，加上周末有别的事儿于是我也摸了。今晚不想再接着摸就virtual participation了一下。总的来说这套题目质量还是不错的，C tle了四次，大概是1:23左右AK的。Profile Here。

Question D Subsequence With the Minimum Score

题意

给两个串s和t，把t去掉一个连续串t[l:r]（这个部分我已经手动简化了，题目说的是去掉若干字符，使代价为这些字符的最右端点与最左端点的差，那么我就直接去掉一个连续子串，多去掉一些字母也不会影响子串的性质）使t成为s的子串（空串是任何串的子串，因此保证一定有解），尽量使去掉的这个串t[l:r]尽量短，求去掉的这个串长度。

题解

这个我们实际上就是需要预处理一下t[1:i]和t[j:n]，即t的前缀和t的后缀是s的子串的长度，这个我们可以分别用双指针来预处理实现。最后我们利用上面处理的结果二分一下答案即可。

class Solution {
public:
    int minimumScore(string s, string t) {
        int m = s.size(), n = t.size();
        int f[n + 2], g[n + 2];
        f[0] = 0;
        for (int i = 1, j = 1; i <= n; i++) {
            while (j <= m && s[j - 1] != t[i - 1]) j++;
            if (j <= m) f[i] = j, j++;
            else f[i] = -1;
        }
        g[n + 1] = m + 1;
        for (int i = n, j = m; i > 0; i--) {
            while (j > 0 && s[j - 1] != t[i - 1]) j--;
            if (j > 0) g[i] = j, j--;
            else g[i] = -1;
        }

        auto check = [&](int X) {
            for (int i = 1; i + X - 1 <= n; i++) {
                int L = i - 1, R = i + X;
                if (f[L] == -1 || g[R] == -1) continue;
                if (f[L] < g[R]) return true;
            }
            return false;
        };

        int head = 0, tail = n;
        while (head < tail) {
            int mid = (head + tail) >> 1;
            if (check(mid)) tail = mid;
            else head = mid + 1;
        }
        return head;
    }
};

Question C Substring XOR Queries

题意

给定一个长为n的01串s，给定一个长为m的查询序列q，q中的每个查询包括两个值first和second，对于每个查询，求一个01串s最短子串使满足：这个字串的十进制值（下面记作val） ^ first = second。$(n \le 1e4, m \le 1e5)$

题解

考察异或的性质，预处理。首先我们会注意到，val ^ first = second，这里我们已知first和second，能不能知二求一把val求出来？显然可以，val ^ first = second => val = val ^ first ^ first = second ^ first => val = first ^ second。异或运算正好满足这样的性质。那这个事情看起来简单一些了，因为val的数量是有限的（query数量可数），而且所有可能的串也是有限的（因为query范围只有1e9，我们只需要最长枚举长度为31位的，长度是1e4，只有3e5）个串。考虑预处理这两个有限的值做一个dict就行了，我这里写的代码是预处理可能的串。

typedef long long ll;
class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        vector<vector<int>> ret;
        int n = s.length();
        map<int, vector<int>> mp;
        for(int i = 0; i < n; i++){
            int res = 0;
            for(int len = 1; len <= 31 && i + len - 1 < n; len++){
                res *= 2, res += (s[i + len - 1] == '1');
                if(mp.count(res) == 0 || mp[res][1] - mp[res][0] + 1 > len){
                    mp[res] = vector<int>{i, i + len - 1};
                }
            }
        }
        for(auto &q : queries){
            int goal = q[0] ^ q[1];
            if(mp.count(goal) != 0){
                ret.push_back(mp[goal]);
            }
            else ret.push_back(vector<int>{-1, -1});
        }
        return ret;
    }
};

Question B Count the Number of Fair Pairs

题意

给定一个长为n的数组nums，以及上下界lower和upper，问存在多少二元组(i, j)满足:
1. 0 \le i < j < nums.size()
2. $lower \le nums[i] + nums[j] \le upper$

题解

考察stl的使用。数组长度是1e5，那肯定是O(nlogn)的时间复杂度，这个题目让我们不难想到leetcode新手村的第一题：两数之和。实际上就是固定一个数nums[i]，来用二分查找看 $lower - nums[i] \le nums[j] \le upper$的数有多少，这是一个典型的二分查找问题。于是后面就变成考察stl里lower_bound和upper_bound会不会用了。要注意一个细节要求下标是i<j，所以这里用迭代器遍历数组会相对比较方便。

typedef long long ll;
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        ll ret = 0;
        sort(nums.begin(), nums.end());
        for(auto it = nums.begin(); it != nums.end(); it++){
//             l <= x + y <= u => l - x <= y <= u - x
            ret += (upper_bound(next(it), nums.end(), upper - *it) - lower_bound(next(it), nums.end(), lower - *it));
        }
        return ret;
    }
};

Question A Find The Array Concatenation Value

题意

给定一个数组，按照给定方式模拟：左指针从左到右遍历，右指针从右到左遍历，两个指针同时移动，每次将指针所指的数拼接之后加到sum里，直到两个指针相遇，返回sum。

代码

typedef long long ll;
class Solution {
public:
    long long findTheArrayConcVal(vector<int>& nums) {
        ll ret = 0; int n = nums.size();
        for(int l = 0, r = n - 1; l <= r; l++, r--){
            if(l < r){
                ll resl = nums[l], resr = nums[r];
                ll res = 1;
                while(resr){
                    resr /= 10, res *= 10;
                }
                ret += nums[l] * res + nums[r];
            }
            if(l == r){
                ret += nums[l];
            }
        }
        return ret;
    }
};