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

目录

1.小红的子串

1.题目链接

• 小红的子串

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

• 解法：前缀和思想 + 滑动窗口 - 求种类个数在[1, count]区间内⼦串的个数：滑动窗⼝- 两次滑动窗口：利⽤前缀和的思想，求种类个数在[l, r]区间内⼦串的个数，等于求[1, r]区间内个数[1, l - 1]区间内个数#include<iostream>#include<string>usingnamespace std;int n =0, l =0, r =0;string str;longlongFind(int x){if(x ==0){return0;}int left =0, right =0;int hash[26]={0}, kinds =0;longlong 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;}intmain(){ cin >> n >> l >> r >> str; cout <<Find(r)-Find(l -1)<< endl;return0;}

2.kotori和抽卡

1.题目链接

• kotori和抽卡

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>usingnamespace std;intmain(){// 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);return0;}

3.ruby和薯条

1题目链接

• ruby和薯条

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

• 解法一：排序 + 二分
• 解法二：排序 + 滑动窗口 + 前缀和#include<iostream>#include<algorithm>#include<vector>usingnamespace std;int n =0, l =0, r =0;vector<int> arr;// 找出差值在[0, x]之间一共有多少对longlongFind(int x){int left =0, right =0;longlong ret =0;while(right < n){while(arr[right]- arr[left]> x){ left++;} ret += right - left; right++;}return ret;}intmain(){ 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;return0;}