1.小红的子串
1.题目链接
2.算法原理详解 && 代码实现
- 解法:前缀和思想 + 滑动窗口
- 求种类个数在
[1, count]
区间内⼦串的个数:滑动窗⼝ - 两次滑动窗口:利⽤前缀和的思想,求种类个数在
[l, r]
区间内⼦串的个数,等于求[1, r]
区间内个数[1, l - 1]
区间内个数
#include <iostream> #include <string> using namespace std;int n = 0, l = 0, r = 0; string str;long long Find(int x) {if(x == 0){return 0;}int left = 0, right = 0;int hash[26] = { 0 }, kinds = 0;long long ret = 0;while(right < n){if(hash[str[right] - 'a']++ == 0) {kinds++;}while(kinds > x){if(hash[str[left] - 'a']-- == 1){kinds--;}left++;}ret += right - left + 1; // 字符的个数等于新多出来的字串的个数right++;}return ret; }int main() {cin >> n >> l >> r >> str;cout << Find(r) - Find(l - 1) << endl;return 0; }
- 求种类个数在
2.kotori和抽卡
1.题目链接
2.算法原理详解 && 代码实现
- 解法:代入概率公式 --> C n m ∗ p m ∗ ( 1 − p ) n − m C_n^m * p^m * (1-p)^{n-m} Cnm∗pm∗(1−p)n−m
#include <iostream>
using namespace std;int main()
{// Cnmint n = 0, m = 0;cin >> n >> m;double ret = 1.0;for(int i = n; i >= n - m + 1; i--) {ret *= i;}for(int i = m; i >= 2; i--){ret /= i;}for(int i = 0; i < m; i++){ret *= 0.8;}for(int i = 0; i < n - m; i++){ret *= 0.2;}printf("%.4lf", ret);return 0;
}
3.ruby和薯条
1题目链接
2.算法原理详解 && 代码实现
-
解法一:排序 + 二分
-
解法二:排序 + 滑动窗口 + 前缀和
#include <iostream> #include <algorithm> #include <vector> using namespace std;int n = 0, l = 0, r = 0; vector<int> arr;// 找出差值在[0, x]之间一共有多少对 long long Find(int x) {int left = 0, right = 0;long long ret = 0;while(right < n){while(arr[right] - arr[left] > x){left++;}ret += right - left;right++;}return ret; }int main() {cin >> n >> l >> r;arr.resize(n, 0);for(auto& x : arr){cin >> x;}sort(arr.begin(), arr.end());cout << Find(r) - Find(l - 1) << endl;return 0; }