[Algorithm][综合训练][小红的子串][kotori和抽卡][ruby和薯条]详细讲解

---

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.题目链接

• kotori和抽卡

---

2.算法原理详解 && 代码实现

• 解法：代入概率公式 --> $C_n^m\ast p^m\ast (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题目链接

• ruby和薯条

---

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;
  }