第 374 场周赛 解题报告 | 珂学家 | 拆位前缀和优化+分组滑窗+组合数学

class Solution {public List<Integer> findPeaks(int[] mountain) {List<Integer> res = new ArrayList<>();for (int i = 1; i < mountain.length - 1; i++) {if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) res.add(i);}return res;}
}

这题是结论题：

$$前缀和大于等于某个数，可以吸纳于集合中，并能自由组合构建1N的数$$

class Solution {public int minimumAddedCoins(int[] coins, int target) {        Arrays.sort(coins);int res = 0;int s = 0;for (int i = 0; s < target && i < coins.length; i++) {while (s < target && s + 1 < coins[i]) {s += s + 1;res++;}s += coins[i];}while (s < target) {s += s + 1;res++;}return res;}
}

思路: 拆位+前缀和

时间复杂度相对有些高, $O(26^2\ast n)$

class Solution {public int countCompleteSubstrings(String word, int k) {char[] str = word.toCharArray();int n = str.length;int[] valid = new int[n + 1];int[][] pre = new int[26][n + 1];for (int i = 0; i < n; i++) {int p = str[i] - 'a';for (int j = 0; j < 26; j++) {pre[j][i + 1] = pre[j][i] + (p == j ? 1 : 0);}if (i + 1 < n) {int t = Math.abs(str[i] - str[i + 1]);valid[i + 1] = valid[i] + (t > 2 ? 1 : 0);}}int res = 0;for (int i = 0; i < n; i++) {for (int j = i - k + 1; j >= 0; j -= k) {int s = valid[i] - valid[j];if (s == 0) {int t0 = 0, t1 = 0;for (int t = 0; t < 26; t++) {int x = pre[t][i + 1] - pre[t][j];if (x > 0 && x < k) t0++;else if (x > k) {t1++;break;}}if (t1 > 0) {break;} else if (t0 == 0) {res++;}} else {break;}}}return res;}
}

思路: 组合数学

如果一时找不到规律，按照灵神的建议

$$可以从特殊到一般$$

对于一个区间(长度为m)

• 内部的选择是$2^{(}m-1)$
• 最左侧/右侧为1

而从全局来看

区间和区间之间，它满足如下公式

$C(n_1,n_1)\ast C(n_1+n_2,n_2)\ast ...\ast C(n_1+n_2+...+n_t,n_t)$

最终的结果即乘法原理

$$内部和全局累乘即可$$

剩下的就是组合计算的板子题

对于n在$(10^6)$范围内，p很大(质数)，一般采用预处理

这样的话，整个复杂度为$O(n)$

class Solution {static long mod = (long)1e9 + 7l;static int SZ = 10_0000;static long[] fac = new long[SZ + 1];static long[] inv = new long[SZ + 1];static {fac[0] = 1;for (int i = 1; i <= SZ; i++) {fac[i] = fac[i - 1] * i % mod;}// 费马小定理inv[SZ] = ksm(fac[SZ], mod - 2);for (int j = SZ - 1; j >= 0; j--) {inv[j] = inv[j + 1] * (j + 1) % mod;}}// *) static long ksm(long b, long v) {long r = 1;while (v > 0) {if (v % 2 == 1) {r = r * b % mod;}v /= 2;b = b * b % mod;}return r;}long comb(int n, int k) {return fac[n] * inv[n - k] % mod * inv[k] % mod;}public int numberOfSequence(int n, int[] sick) {int holes = 0;long r = 1;holes += sick[0];for (int i = 0; i < sick.length - 1; i++) {int span = sick[i + 1] - sick[i] - 1;if (span > 0) {r = r * ksm(2, span - 1) % mod;holes += span;r = r * comb(holes, span) % mod;}}int m = sick.length;if (sick[m - 1] < n) {int span = (n - sick[m - 1] - 1);holes += span;r = r * comb(holes, span) % mod;}return (int)r;}}