1.27学习总结

2024-01-28 06:20
文章标签 学习 总结 1.27

本文主要是介绍1.27学习总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天做了些队列的题：
1.逛画展（单调队列）
2.打印队列 Printer Queue（优先队列）
3.[NOIP2010 提高组] 机器翻译(模拟队列)
4.求m区间内的最小值(单调队列板子题)
5.日志统计(滑动窗口，双指针)

总结一下：单调队列使用STL的deque进行模拟，也可以用数组和双指针(head,tail)，有两种操作，删头和去尾，实现一个区间内单调增或减的队列，经典的例题是滑动窗口，在用单调队列做题时，尽量队列内存的是索引，而不是这个数据本身

优先队列（堆）可用于求区间最值，数据较大的时候容易TLE

逛画展https://www.luogu.com.cn/problem/P1638

题目描述

博览馆正在展出由世上最佳的 �m 位画家所画的图画。

游客在购买门票时必须说明两个数字，�a 和 �b，代表他要看展览中的第 �a 幅至第 �b 幅画（包含 �,�a,b）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 �,�a,b，数据保证一定有解。

若存在多组解，输出 �a 最小的那组。

输入格式

第一行两个整数 �,�n,m，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 �n 个整数 ��ai​，代表画第 �i 幅画的名师的编号。

输出格式

一行两个整数 �,�a,b。

输入输出样例

输入 #1复制

12 5
2 5 3 1 3 2 4 1 1 5 4 3

输出 #1复制

2 7

说明/提示

数据规模与约定
  • 对于 30%30% 的数据，有 �≤200n≤200，�≤20m≤20。
  • 对于 60%60% 的数据，有 �≤105n≤105，�≤103m≤103。
  • 对于 
  • 100%100% 的数据，有 1≤�≤1061≤n≤106，1≤��≤�≤2×1031≤ai​≤m≤2×103。
  • 思路：当还没有满足条件的时候一直入队，直到情况满足的时候，开始从头出队，直到情况未满足，找到所有可能的情况，并取出最小值
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int hash_count[20005];
int main()
{deque<int>q;int m,n;cin>>m>>n;int t=0;int min_length=m+2,l=0,r=m-1;for (int i=0;i<m;++i){cin>>a[i];if (hash_count[a[i]]==0)t++;hash_count[a[i]]++;q.push_back(i);while (t==n)//2 5 3 1 3 2 4 1 1 5 4 3{if (min_length>q.back()-q.front()){min_length=q.back()-q.front();l=q.front(),r=q.back();}hash_count[a[q.front()]]--;if (hash_count[a[q.front()]]==0)t--;q.pop_front();}}cout<<l+1<<" "<<r+1;
}

求m区间内的最小值https://www.luogu.com.cn/problem/P1440

题目描述

一个含有 �n 项的数列，求出每一项前的 �m 个数到它这个区间内的最小值。若前面的数不足 �m 项则从第 11 个数开始，若前面没有数则输出 00。

输入格式

第一行两个整数，分别表示 �n，�m。

第二行，�n 个正整数，为所给定的数列 ��ai​。

输出格式

�n 行，每行一个整数，第 �i 个数为序列中 ��ai​ 之前 �m 个数的最小值。

输入输出样例

输入 #1复制

6 2
7 8 1 4 3 2

输出 #1复制

0
7
7
1
1
3

说明/提示

对于 100%100% 的数据，保证 1≤�≤�≤2×1061≤m≤n≤2×106，1≤��≤3×1071≤ai​≤3×107。

思路：模拟一个单调增的队列，队内没有的时候入队，有元素的时候判断，当前队尾元素是否小于将要入队的元素，如果不小于，那么队尾出队，直到找到一个小于的数或者队列空

#include <bits/stdc++.h>
using namespace std;
int a[2000005];
int main()
{int n,m;scanf("%d%d",&n,&m);deque<int>q;for (int i=0;i<n;++i){int x;scanf("%d",&x);a[i]=x;if (q.empty())printf("0\n");else printf("%d\n",a[q.front()]);while (!q.empty() && x<a[q.back()])q.pop_back();q.push_back(i);if (i-m==q.front())q.pop_front();}
}

日志统计https://www.luogu.com.cn/problem/P8661

题目描述

小明维护着一个程序员论坛。现在他收集了一份“点赞”日志，日志共有 �N 行。其中每一行的格式是 ts id，表示在 ��ts 时刻编号 ��id 的帖子收到一个“赞”。

现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为 �D 的时间段内收到不少于 �K 个赞，小明就认为这个帖子曾是“热帖”。

具体来说，如果存在某个时刻 �T 满足该帖在 [�,�+�)[T,T+D) 这段时间内（注意是左闭右开区间）收到不少于 �K 个赞，该帖就曾是“热帖”。

给定日志，请你帮助小明统计出所有曾是“热帖”的帖子编号。

输入格式

第一行包含三个整数 �N、�D 和 �K。

以下 �N 行每行一条日志，包含两个整数 ��ts 和 ��id。

输出格式

按从小到大的顺序输出热帖 ��id。每个 ��id 一行。

输入输出样例

输入 #1复制

7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3

输出 #1复制

1  
3

说明/提示

对于 50%50% 的数据，1≤�≤�≤10001≤K≤N≤1000。

对于 100%100% 的数据，1≤�≤�≤1051≤K≤N≤105，0≤��,��≤1050≤id,ts≤105。

思路：双指针+滑动窗口的做法，先按照时间排序。直到满足时间条件的时候，开始消除点赞数

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
struct Node{int time;int id;
};
struct Node  a[N];
int nums[N];//记录每个id的点赞数 
int flag[N];//记录是热评的 	
bool cmp(Node &a,Node &b)
{if (a.time!=b.time)return a.time<b.time;else if (a.time==b.time)return a.id<b.id;
}
int main()
{int n,d,k;cin>>n>>d>>k;	for (int i=0;i<n;++i)cin>>a[i].time>>a[i].id;sort(a,a+n,cmp);for (int i=0,j=0;i<n;++i){nums[a[i].id]++;while (a[i].time-a[j].time>=d){nums[a[j].id]--;j++;}if (nums[a[i].id]>=k)flag[a[i].id]=1;}for (int i=0;i<N;++i){if (flag[i])cout<<i<<endl;}
}

机器翻译https://www.luogu.com.cn/problem/P1540

题目描述

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 �M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 �−1M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 �M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为 �N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入格式

共 22 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 �,�M,N，代表内存容量和文章的长度。

第二行为 �N 个非负整数，按照文章的顺序，每个数（大小不超过 10001000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式

一个整数，为软件需要查词典的次数。

输入输出样例

输入 #1复制

3 7
1 2 1 5 4 4 1

输出 #1复制

5

说明/提示

样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

  1. 1：查找单词 1 并调入内存。
  2. 1 2：查找单词 2 并调入内存。
  3. 1 2：在内存中找到单词 1。
  4. 1 2 5：查找单词 5 并调入内存。
  5. 2 5 4：查找单词 4 并调入内存替代单词 1。
  6. 2 5 4：在内存中找到单词 4。
  7. 5 4 1：查找单词 1 并调入内存替代单词 2。

共计查了 55 次词典。

数据范围

  • 对于 10%10% 的数据有 �=1M=1，�≤5N≤5；
  • 对于 100%100% 的数据有 1≤�≤1001≤M≤100，1≤�≤10001≤N≤1000。

思路：队未满，开始入队，并且计数器要加1，队满开始出队和入队，计数器也加一

#include <bits/stdc++.h>
using namespace std;
int main()
{int m,n,cnt=0;cin>>m>>n;queue<int>q;//m是内存队列的长度最多等于m//这题主要难在找，用队列形成进去很简单int ans[1001];memset(ans,0,sizeof(ans));for (int i=0;i<n;++i){int x;cin>>x;if (ans[x]==0 && q.size()<m){q.push(x);ans[x]=1;	cnt++;}else if (ans[x]==1)continue;else if (ans[x]==0 && q.size()==m){ans[q.front()]=0;q.pop();	ans[x]=1;q.push(x);cnt++;}	}cout<<cnt; 
}

打印队列 Printer Queuehttps://www.luogu.com.cn/problem/UVA12100

学生会里只有一台打印机，但是有很多文件需要打印，因此打印任务不可避免地需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个1～9间的优先级，优先级越高表示任务越急。

打印机的运作方式如下：首先从打印队列里取出一个任务J，如果队列里有比J更急的任务，则直接把J放到打印队列尾部，否则打印任务J（此时不会把它放回打印队列）。 输入打印队列中各个任务的优先级以及所关注的任务在队列中的位置（队首位置为0），输出该任务完成的时刻。所有任务都需要1分钟打印。例如，打印队列为{1,1,9,1,1,1}，目前处于队首的任务最终完成时刻为5。

输入T 接下来T组数据 每组数据输入N，TOP。接下来N个数，TOP代表队列首

Translated by @HuangBo

输入输出样例

输入 #1复制

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

输出 #1复制

1
2
5

思路：用优先队列和普通队列存值，然后按照优先队列的出队顺序找到队列对应的值出队

#include <bits/stdc++.h>
using namespace std;
struct node{int x;int id;
}x2;
priority_queue<int>q;
queue<node>p;
int main()
{int t;cin>>t;while (t--){int m,n;cin>>m>>n;for (int i=0;i<m;++i){int l;cin>>l;q.push(l);p.push(node{l,i});}int tot=0;while (!q.empty()){int x1=q.top(); q.pop();while (x2=p.front(),x2.x!=x1){p.pop();p.push(x2);	}p.pop();tot++;if (x2.id==n){cout<<tot<<endl;break;}}while (!p.empty())p.pop();while (!q.empty())q.pop();} 
}

这篇关于1.27学习总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/652735。

相关文章

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

1.为什么要引入虚拟继承 虚拟继承是多重继承中特有的概念。虚拟基类是为解决多重继承而出现的。如:类D继承自类B1、B2，而类B1、B2都继承自类A，因此在类D中两次出现类A中的变量和函数。为了节省内存空间，可以将B1、B2对A的继承定义为虚拟继承，而A就成了虚拟基类。实现的代码如下： class A class B1:public virtual A; class B2:pu
阅读更多...
51单片机学习记录———定时器

51单片机学习记录———定时器

文章目录 前言一、定时器介绍二、STC89C52定时器资源三、定时器框图四、定时器模式五、定时器相关寄存器六、定时器练习 前言 一个学习嵌入式的小白~ 有问题评论区或私信指出~ 提示：以下是本篇文章正文内容，下面案例可供参考 一、定时器介绍 定时器介绍：51单片机的定时器属于单片机的内部资源，其电路的连接和运转均在单片机内部完成。 定时器作用： 1.用于计数系统，可
阅读更多...
问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
[word] word设置上标快捷键 #学习方法#其他#媒体

[word] word设置上标快捷键 #学习方法#其他#媒体

word设置上标快捷键 办公中，少不了使用word，这个是大家必备的软件，今天给大家分享word设置上标快捷键，希望在办公中能帮到您！ 1、添加上标 在录入一些公式，或者是化学产品时，需要添加上标内容，按下快捷键Ctrl+shift++就能将需要的内容设置为上标符号。 word设置上标快捷键的方法就是以上内容了，需要的小伙伴都可以试一试呢！
阅读更多...
AssetBundle学习笔记

AssetBundle学习笔记

AssetBundle是unity自定义的资源格式，通过调用引擎的资源打包接口对资源进行打包成.assetbundle格式的资源包。本文介绍了AssetBundle的生成，使用，加载，卸载以及Unity资源更新的一个基本步骤。 目录 1.定义： 2.AssetBundle的生成： 1）设置AssetBundle包的属性——通过编辑器界面 补充：分组策略 2）调用引擎接口API
阅读更多...
Javascript高级程序设计(第四版)--学习记录之变量、内存

Javascript高级程序设计(第四版)--学习记录之变量、内存

原始值与引用值 原始值：简单的数据即基础数据类型，按值访问。 引用值：由多个值构成的对象即复杂数据类型，按引用访问。 动态属性 对于引用值而言，可以随时添加、修改和删除其属性和方法。 let person = new Object();person.name = 'Jason';person.age = 42;console.log(person.name,person.age);//'J
阅读更多...
大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式，可以快速查找问题解析，加深对题目答案的理解。 1.快练题 这是一个网站 找题的网站海量题库,在线搜题,快速刷题~为您提供百万优质题库,直接搜索题库名称,支持多种刷题模式:顺序练习、语音听题、本地搜题、顺序阅读、模拟考试、组卷考试、赶快下载吧! 2.彩虹搜题 这是个老公众号了 支持手写输入，截图搜题，详细步骤，解题必备
阅读更多...
《offer来了》第二章学习笔记

《offer来了》第二章学习笔记

1.集合 Java四种集合：List、Queue、Set和Map 1.1.List：可重复 有序的Collection ArrayList： 基于数组实现，增删慢，查询快，线程不安全 Vector： 基于数组实现，增删慢，查询快，线程安全 LinkedList： 基于双向链实现，增删快，查询慢，线程不安全 1.2.Queue：队列 ArrayBlockingQueue：
阅读更多...
十五.各设计模式总结与对比

十五.各设计模式总结与对比

1.各设计模式总结与对比 1.1.课程目标 1、 简要分析GoF 23种设计模式和设计原则,做整体认知。 2、 剖析Spirng的编程思想，启发思维,为之后深入学习Spring做铺垫。 3、 了解各设计模式之间的关联，解决设计模式混淆的问题。 1.2.内容定位 1、 掌握设计模式的"道" ，而不只是"术" 2、 道可道非常道，滴水石穿非一日之功，做好长期修炼的准备。 3、 不要为了
阅读更多...
硬件基础知识——自学习梳理

硬件基础知识——自学习梳理

计算机存储分为闪存和永久性存储。 硬盘（永久存储）主要分为机械磁盘和固态硬盘。 机械磁盘主要靠磁颗粒的正负极方向来存储0或1，且机械磁盘没有使用寿命。 固态硬盘就有使用寿命了，大概支持30w次的读写操作。 闪存使用的是电容进行存储，断电数据就没了。 器件之间传输bit数据在总线上是一个一个传输的，因为通过电压传输（电流不稳定），但是电压属于电势能，所以可以叠加互相干扰，这也就是硬盘，U盘
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2