还是倒着讲吧,上周末约好一起打周赛的朋友摸了,加上周末有别的事儿于是我也摸了。今晚不想再接着摸就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;
}
};