Leetcode周赛374

这是目前第一次周赛都没AK😭（当然之前第一次打周赛就经历了FST🤡）

这场主要是第三题没想到好的方法，写法比较麻烦，浪费了很多时间。第四题一时间也没想出来，处于半放弃状态了。

¶2953. 统计完全子字符串

¶题意

给定字符串word和整数$k$，word的一个子字符串s被称为完全字符串，仅当：

• s中每个字符恰好出现$k$次
• s中相邻字符在字母表中顺序至多相差2

求word中完全子字符串的数量。

$len(word) \le 10^5, 1\le k \le len(word)$

¶做法

第二个条件是很容易想到可以尺取的，关键是对于子区间$[i, j]$怎么快速统计满足第一个条件的子字符串。

首先枚举起始点$i$，显然最多只有26个可行的子字符串，即最后一个字符是第$k$次出现的a、b、c、…、z，依次检查即可。另一种做法是枚举这个子字符串中包含的字母个数，字母个数如果是$x$，那么长度就是$kx$。其实以上两种方式是相似的，本质都是只需要检查26个子串即可。复杂度为$O(n2626)$。

我比赛时的做法是先枚举首字符，这样结尾一定落在该字符第$k$次出现到第$k+1$出现这个区间里，这个可以尺取。复杂度可以是$O(n26)$，但是很难写，还不如写成$O(n26*26)$的了。

class Solution {
public:
    int countCompleteSubstrings(string word, int k) {
        int n = word.size();
        int ans = 0;
        for (int i = 0; i < n; ) {
            int j = i + 1;
            while (j < n && abs(word[j] - word[j - 1]) <= 2) ++j;
            array<int, 26> cnt{};
            vector<vector<int>> pos(26);
            for (int k = i; k < j; k++) pos[word[k] - 'a'].push_back(k);
            for (int c = 0; c < 26; c++) {
                if (pos[c].size() < k) continue;
                int bad = 0;
                for (int l = pos[c][0], r = l, t = 0; l < j; t++) {
                    if (l == r) {
                        cnt[word[r] - 'a'] = 1;
                        if (cnt[word[r] - 'a'] != k) ++bad;
                        if (!bad) ++ans;
                        ++r;
                    }
                    int nxt = j;
                    if (t + k < pos[c].size()) nxt = pos[c][t + k];
                    while (r < nxt) {
                        cnt[word[r] - 'a']++;
                        if (cnt[word[r] - 'a'] != k) {
                            if (cnt[word[r] - 'a'] == 1 || cnt[word[r] - 'a'] == k + 1) ++bad;
                        } else if (k > 1) --bad;
                        ++r;
                        if (!bad) {
                            ++ans;
                        }
                    }
                    int nxt2 = j;
                    if (t + 1 < pos[c].size()) nxt2 = pos[c][t + 1];
                    while (l < nxt2) {
                        if (cnt[word[l] - 'a'] == k) {
                            if (k!=1) ++bad;
                        }
                        else if (cnt[word[l] - 'a'] == 1 || cnt[word[l] - 'a'] == k + 1) --bad;
                        cnt[word[l] - 'a']--;
                        ++l;
                    }
                }
            }
            i = j;
        }
        return ans;
    }
};

¶2954. 统计感冒序列的数目

给定整数$n$和升序数组sick，该数组包含了所有初始被感染的小孩的下标，在每一秒小孩$i$会进一步感染$i - 1$或$i + 1$，每秒至多一个小孩会被感染。问所有可能的感染序列。答案模1e9 + 7。

$n \le 10^5$

¶做法

当时第一想法以为是填坑DP，但看了一眼至少得$O(n^2)$，然后就没有然后了。。寄了，摆了

一个很重要的观察是初始的sick把$[0, n - 1]$划分成了若干的段，它们是互不干扰的。考虑小孩$i$，它左侧最近的感染者是$j$，右侧最近的感染者是$k$，$i$要么被$j$感染，要么被$k$感染。下面独立考虑每个段，如果开头或结尾的段，则只有一种感染方式，否则就有$2^{k-j-1}$种。最后只需要将每个段依次两两合并即可。考虑一个长度为$x$和一个长度为$y$的段，总共有$x+1$个空位，插入$y$个数，相当于$x+1$个大于等于0的变量求和等于$y$，方案数为$C(x+y, x)$。

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
int fac[N], ifac[N];
int Pow(int a, int b) {
	int ans = 1;
	while (b) {
		if (b&1) ans = 1ll*ans*a%MOD;
		a = 1ll*a*a%MOD;
		b >>= 1;
	}
	return ans;
}
void init(int n) {
	fac[0] = 1;
	for (int i=1; i<=n; i++) fac[i] = 1ll*fac[i-1]*i%MOD;
	ifac[n] = Pow(fac[n], MOD-2);
	for (int i=n-1; i>=0; i--) ifac[i] = 1ll*ifac[i+1]*(i+1)%MOD;
}
int C(int a, int b) {
	if (a<b||b<0) return 0;
	return 1ll*fac[a]*ifac[b]%MOD*ifac[a-b]%MOD;
}
class Solution {
public:
    int numberOfSequence(int n, vector<int>& sick) {
        init(n + 1);
        vector<int> two(n + 1);
        two[0] = 1;
        for (int i = 1; i <= n; i++) two[i] = (two[i - 1] << 1) % MOD;
        int ans = 1;
        int pre = sick[0];
        for (int i = 0; i + 1 < sick.size(); i++) {
            int cur = sick[i + 1] - sick[i] - 1;
            if (!cur) continue;
            ans = 1ll*ans*two[cur - 1]%MOD*C(cur + pre, pre)%MOD;
            pre += cur;
        }
        ans = 1ll*ans*C(n - 1 - sick.back() + pre, pre)%MOD;
        return ans;
    }
};