[洛谷]P3613 【深基15.例2】寄包柜

news/2024/10/31 2:22:58/

[洛谷]P3613 【深基15.例2】寄包柜

  • 一、问题描述
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
  • 二、思路分析
    • 1、算法标签
    • 2、算法思路
  • 三、代码实现

一、问题描述

[洛谷]P3613 【深基15.例2】寄包柜

题目描述

超市里有 n(1≤n≤105)n(1\le n\le10^5)n(1n105) 个寄包柜。每个寄包柜格子数量不一,第 iii 个寄包柜有 ai(1≤ai≤105)a_i(1\le a_i\le10^5)ai(1ai105) 个格子,不过我们并不知道各个 aia_iai 的值。对于每个寄包柜,格子编号从 1 开始,一直到 aia_iai。现在有 q(1≤q≤105)q(1 \le q\le10^5)q(1q105) 次操作:

  • 1 i j k:在第 iii 个柜子的第 jjj 个格子存入物品 k(0≤k≤109)k(0\le k\le 10^9)k(0k109)。当 k=0k=0k=0 时说明清空该格子。
  • 2 i j:查询第 iii 个柜子的第 jjj 个格子中的物品是什么,保证查询的柜子有存过东西。

已知超市里共计不会超过 10710^7107 个寄包格子,aia_iai 是确定然而未知的,但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 nnnqqq,寄包柜个数和询问次数。

接下来 qqq 个整数,表示一次操作。

输出格式

对于查询操作时,输出答案,以换行隔开。

样例 #1

样例输入 #1

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

样例输出 #1

118014
1

提示

upd 2022.7.26\text{upd 2022.7.26}upd 2022.7.26:新增加一组 Hack 数据。

二、思路分析

1、算法标签

这道题主要考察的是c++c++c++stlstlstlmapmapmap容器的使用

2、算法思路

这道题总结成一句话就是,我们先通过数据aaa找到柜子,再通过数据bbb找到柜子中的具体格子。所以我们需要两次索引值。

那么第一种方法就是创建一个二维数组,每一行代表一个柜子,每一行中的不同列代表的是柜子中的格子,但是题目中的数据量非常大,并且每个柜子中的具体格子数我们也不知道。所以创建二维数组的方式是不可取的。

因此,我们想到了另外一种可以用来索引的容器,mapmapmap。我们可以创建下列这种数据结构:

map<int,map<int,int>>map<int ,map<int,int>> map<int,map<int,int>>

其中第一个int代表的是柜子,内部嵌套的第一个int代表的是柜子中的格子,第二个代表的是我们放的物品。

这个数据结构的定义就是这道题的难点,那么接下来的步骤就很简单了。

我们直接上代码。

三、代码实现

#include<iostream>
#include<map>
using namespace std;
map<int,map<int,int>>q;
int n,m;
int main()
{cin>>n>>m;for(int i=0;i<m;i++){int a;cin>>a;int b,c,d;if(a==1){cin>>b>>c>>d;q[b][c]=d;}else{cin>>b>>c;cout<<q[b][c]<<endl;}}return 0;
}

在这里插入图片描述


http://www.ppmy.cn/news/5660.html

相关文章

2023年元旦倒计时案例

文章目录基于HTML实现2023年倒计时代码实现基于HTML实现2023年倒计时 代码实现 <!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>2023倒计时</title> <!-- <link rel"stylesheet" href"sty…

Linux进程概念

进程的概念 进程&#xff08;Process&#xff09;是计算机中的一个具有独立功能的程序关于某个数据集合的一次运行活动&#xff0c;是系统进行资源分配和调度的基本单位&#xff0c;是操作系统结构的基础。在早期面向进程设计的计算机结构中&#xff0c;进程是程序的基本执行实…

基于Canal+kafka监听数据库变化的最佳实践

1、前言 工作中&#xff0c;我们很多时候需要根据某些状态的变化更新另一个业务的逻辑&#xff0c;比如订单的生成&#xff0c;成交等&#xff0c;需要更新或者通知其他的业务。我们通常的操作通过业务埋点、接口的调用或者中间件完成。 但是状态变化的入口比较多的时候&#x…

FT2232作为JTAG烧录器的使用步骤详解

FT2232作为JTAG烧录器的使用步骤详解FT2232作为JTAG烧录器的使用步骤详解配置OpenOCD环境(已经配置好的可以跳过)【步骤 1】安装 FT2232HL 芯片的驱动&#xff0c;安装文件为 CDM21228_Setup.exe。【步骤 2】 安装 FT_Prog_v3.6.88.402 Installer.exe【步骤 3】 使用 FT Prog 软…

你易忽略的三极管电路问题1:下拉电阻

如下这个三极管共射极驱动电路中&#xff0c;B、E极之间的下拉电阻的作用&#xff1f;是否可以将其去除&#xff1f;该电阻有两个重要的作用&#xff1a;在驱动信号关闭时给三极管基极一个固定的电平。当驱动信号&#xff08;SIGNAL&#xff09;关闭时&#xff0c;若没有下拉电…

【Java基础知识复盘】String、StringBuffer、StringBuilder篇——持续更新中

本人知识复盘系列的博客并非全部原创&#xff0c;大部分摘自网络&#xff0c;只是为了记录在自己的博客方便查阅&#xff0c;往后也会陆续在本篇博客更新本人查阅到的新的知识点&#xff0c;望悉知&#xff01; String类 在 Java 中字符串属于对象&#xff0c;Java 提供了 Str…

矢量网络分析仪如何测量史密斯图及滤波器的带宽?

矢量网络分析仪是一种很神奇的测量仪器&#xff0c;它的功能很强大也值得人们去探索。今天&#xff0c;安泰测试工程师就针对矢量网络分析仪中的史密斯图及滤波器的带宽测量进行简单的介绍&#xff0c;希望能够让更多的人对此有所了解&#xff0c;并产生兴趣。 首先仪器了解一下…

试卷安全分发系统

摘要 高校教务管理过程中&#xff0c;试卷以明文形式传输和集中存储&#xff0c;存在数据泄漏安全隐患。现提出了一个基于数字证书的试卷防泄漏方案&#xff0c;采用算法加密试卷&#xff0c;试卷在传输过程中中以密文的形式传输&#xff0c;每次传输的时候都会对试卷进行签名…