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

embedded/2024/11/9 16:43:08/

目录


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} Cnmpm(1p)nm
#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;
    }
    

http://www.ppmy.cn/embedded/104357.html

相关文章

石墨文档数据:合法抓取指南

如何使用爬虫技术合法地抓取石墨文档数据 在当今数字化时代&#xff0c;在线协作工具如石墨文档已成为团队工作不可或缺的部分。 然而&#xff0c;在某些情况下&#xff0c;我们可能需要自动提取这些文档中的数据进行分析等。 本文介绍了如何在遵循服务条款的同时&#xff0…

ER模型介绍

7.1.概述&#xff1a; 1.ER模型也叫做实体关系模型&#xff0c;是用来描述现实生活中客观存在的事物、事物的属性&#xff0c;以及事物之间关系的一种数据模型。2.在开发基于数据库的信息系统的设计阶段&#xff0c;通常使用ER模型来描述信息需要和信息特性&#xff0c;帮助我…

leetcode 899. Orderly Queue

原题链接 You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string. Return the lexicographically smallest string you could have after applying the mentioned step any number of moves. …

189.轮转数组

189.轮转数组 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: …

Linux 文件系统

1. 文件元数据 我们使用 ls -l 的时候看到的除了看到文件名&#xff0c;还看到了文件元数据。 每行包含7列内容&#xff0c;分别为 模式&#xff0c;硬链接数&#xff0c;文件所有者&#xff0c;组&#xff0c;大小&#xff0c;最后修改时间&#xff0c;文件名。 ls -l 读取存…

3.服务注册_服务发现

文章目录 1.服务注册_服务发现1.1服务注册概念及图解介绍2.2 CAP理论2.3 常见的注册中心(了解)2.4 Eureka组件介绍2.4.1.搭建注册中心2.4.2服务注册2.4.3服务发现 大家好&#xff0c;我是晓星航。今天为大家带来的是 服务注册_服务发现 相关的讲解&#xff01;&#x1f600; 1…

每日定期分享诗歌

安装schedule库 首先&#xff0c;确保你已经安装了schedule库。如果没有安装&#xff0c;可以使用以下命令进行安装&#xff1a; pip install schedulepython每日定期分享诗歌 import json import requests import schedule import timedef get_poem():# 这里使用一个公开的…

若依nodejs全栈(五:导出Excel与用户列表填坑)

回顾 上一章节中&#xff0c;我们学会了ruoyi用户列表简单的增删改查功能&#xff0c;但是上一节还存在一些问题&#xff1a; 查询的列表是全部数据&#xff0c;没加查询条件&#xff1b;没有导出功能&#xff1b;新增或修改时&#xff0c;用户关联的角色、岗位、菜单等没做关…