首页 > 其他分享 >洛谷每日一题(P1540 [NOIP2010 提高组] 机器翻译)

洛谷每日一题(P1540 [NOIP2010 提高组] 机器翻译)

时间:2024-09-26 14:51:05浏览次数:13  
标签:count set word NOIP2010 int 机器翻译 内存 memory 洛谷

原题目链接:

P1540 [NOIP2010 提高组] 机器翻译 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

原题目截图:

思路分析:

读懂题意,直接模拟过程即可。这是一道很简单的题目。

思路过程很类似 模拟页面置换算法中的 先进先出(FIFO)策略。

因此我们很容易想到,要用队列来实现。

下面是具体步骤:

  • 遍历文章中的每一个单词。
  • 对于每个单词,检查它是否已经在内存中(即在memory_set集合中):
    • 如果页面不在内存中(memory_set.count(word) == 0),则需要访问外存,然后将其加载到内存:
      • 增加访问外存的次数count
      • 检查内存中的 word 数量是否已经达到上限m
        • 如果是,从队列(内存)中移除最早进入的单词(que.front()),并从memory_set中删除该单词。
      • 将当前单词加入队列(模拟加载到内存)。
      • 将当前单词加入memory_set集合(模拟内存中的单词)。
  • 遍历结束后,输出访问外存的次数count

解决代码:

#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include<queue>


int main() {
	int m, n;
	cin >> m >> n;
	vector<int>article(n);
	queue<int>que;
	for (int i = 0; i < n; i++) {
		int word;
		cin >> word;
		article[i] = word;
	}
	set<int>memory_set;
	int count = 0;//访问外存次数
	for (int word : article) {
		if (memory_set.count(word) == 0) {
			count++;
			if (que.size() >= m) {
				int first = que.front();
				que.pop();
				memory_set.erase(first);
				//从内存抹去最早进入的
			}
			que.push(word);
			memory_set.insert(word);

		}
	}

	cout << count;
	return 0;
	

}

今天的题目比较简单,愿诸君共勉之。

标签:count,set,word,NOIP2010,int,机器翻译,内存,memory,洛谷
From: https://blog.csdn.net/weixin_70448721/article/details/142547217

相关文章

  • 洛谷 P2241 统计方形(数据加强版)
    统计方形(数据加强版)题目背景1997年普及组第一题题目描述有一个n×mn\timesmn×m方格的棋盘,求其方格包......
  • 洛谷题单指南-分治与倍增-P3517 [POI2011] WYK-Plot
    原题链接:https://www.luogu.com.cn/problem/P3517题意解读:有n个连续的点p1,p2,...,pn,将这n个点分成不超过m堆,每堆点连续,每一堆都缩成一个点qi,要使得原来的点p1~ps距离qi的最大值最小(最相似),求这个相似度,并计算一共分成几堆,以及每堆缩到的点qi的坐标。解题思路:要使得若干点缩到一......
  • bfs 与优先队列————洛谷p1126(历经两个小时总算AC了,哭晕)
    机器人搬重物题目描述机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径\(1.6\)米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个\(N\timesM\)的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时......
  • 题解 洛谷P3398 仓鼠找 sugar
    原题链接:P3398仓鼠找sugar题解里大部分都是用的lca,然而我看不懂那些关于lca的性质是怎么证明出来的。不过这题可以直接用树链剖分来写,把模板套上去就好了。题意为查找两条路径是否存在公共点,我们只需要把其中一条路径上的点都赋值为1,然后查询另一条路径上的点的总和,如果总和......
  • 洛谷 P3385 【模板】负环
    题目链接:P3385【模板】负环思路    负环模版题,套一个SPFA板子,判断一下每个节点进入队列的次数,当进入队列的次数大于等于n次时,表示当前节点迭代次数超过了n-1次,即为存在负环。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstllI......
  • 洛谷题单指南-分治与倍增-P3509 [POI2010] ZAB-Frog
    原题链接:https://www.luogu.com.cn/problem/P3509题意解读:n个点,每个点上有一只青蛙每次跳到距离自己第k近的点,m次之后跳到哪个点。解题思路:1、计算距离每个点第k近的点,存入ne[N]给定一个点i,距离i第k近的点一定在长度为k+1个点的窗口内,窗口包括i并且,第k近的点只能是左端点或者......
  • 【洛谷】P2261 [CQOI2007] 余数求和 的题解
    【洛谷】P2261[CQOI2007]余数求和的题解洛谷传送门题解这还是蓝题,这还是省选qaq题目看着很简单,但是真的很考验思路,思路对了,代码不到555分钟写完。刚开始做的时......
  • bfs与优先队列 [NOIP2017 普及组] 棋盘————洛谷p3956
    [NOIP2017普及组]棋盘题目背景NOIP2017普及组T3题目描述有一个\(m\timesm\)的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的),你只能向上、下、左、右......
  • 【洛谷】P10417 [蓝桥杯 2023 国 A] 第 K 小的和 的题解
    【洛谷】P10417[蓝桥杯2023国A]第K小的和的题解题目传送门题解CSP-S1补全程序,致敬全A的答案,和神奇的预言家。写一下这篇的题解说不定能加CSP2024的RP代码#include<bits/stdc++.h>#definelowbit(x)x&(-x)#defineendl"\n"usingnamespacestd......
  • 洛谷P5683 [CSP-J2019 江西] 道路拆除
    立下flag:今天一定AC这道题!题目意思:思路:然而并没有分。。输出-1,祈求CCF的施舍(30%的数据,有\(s_1=s_2\)求1号点到\(s_1\)最短路,再计算不需要的路径。SPFA,启动!#include<bits/stdc++.h>usingnamespacestd;constintmaxn=3010;constintmaxm=3010;intm,n;i......