P3613 【深基15.例2】寄包柜题解

gzr_csdn

364人浏览 · 2026-03-03 20:47:12

gzr_csdn · 2026-03-03 20:47:12 发布

一、P3613 【深基15.例2】寄包柜

题目描述

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

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

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

输入格式

第一行 2 个整数 $n$ 和 $q$ ，寄包柜个数和询问次数。

接下来 $q$ 个行，每行有若干个整数，表示一次操作。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

118014
1

说明/提示

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

二、题解

解法一

存储数量不定，而总数一定，听起来像极了链表的题，一个朴素的想法是，定义n个链表，然后每个链表上面挂物品。

此时遇到了一个问题，直接按照格子的编号来挂会浪费大量节点，因为大部分格子可能是空的，那么不难想到我们可以用一个结构体把格子编号和格子物品的值打包成为一个节点，每次新插入直接挂在储物柜对应链表的末尾，无需考虑顺序，每次查询时按顺序依次查询。

**接着遇到问题，直接尾插无法解决格子覆盖/清除的问题。**由于在尾插的时候会经过这个储物柜链表的所有节点，那么我们只要每一次修改第一个找到的格子，就能确保每一个格子都不会在链表上重复尾插。

**接着我们来尝试计算一下时间复杂度。**虽然说超市里面最多有 $10^7$ 格子， $10^5$ 查询次数，但是，存入物品的次数的上限也是 $10^5$ ，也就是说存入的物品的上限是 $10^5$ ，我用的链表，那么 $10^7$ 这个数字就和问题无关了，这样潦草一算查询的时间复杂度是 $10^5$ （查询数量） * $10^5$ （物品数量极限情况全部挂在同一个链表上），由于存入与查询共享操作次数总数，所以实际复杂度达不到 $10^5$ * $10^5$ ，并且不一定所有的物品全都挂在同一个链表上，并且查询次次都查询末端数据，所以设计的这个算法应该是一个常数很小的 $O(n^2)$ 算法，如果数据不强的情况下可以通过。

#include<iostream>
using namespace std;

class MyLinkedList {
public:
	struct LinkedNode {
		int pos;
		int val;
		LinkedNode* next;
		LinkedNode(int pos, int val) : pos(pos), val(val), next(nullptr) {}
	};
	
	MyLinkedList() {
		_dummyHead = new LinkedNode(0, 0);
		_size = 0;
	}
	
	void addAtTail(int pos, int val) {
		LinkedNode* cur = _dummyHead;
		while(cur->next != nullptr)
		{
			cur = cur->next;
			if(cur->pos == pos)
			{
				cur->val = val;
				return;
			}
		}
		LinkedNode* newnode = new LinkedNode(pos, val);
		cur->next = newnode;
		_size++;
	}
	
	int search(int target)
	{
		LinkedNode* cur = _dummyHead;
		while(cur->next != nullptr)
		{
			cur = cur->next;
			if(cur->pos == target)
			{
				return cur->val;
			}
		}
		return 0;
	}
	
private:
	LinkedNode* _dummyHead;
	int _size;
};

MyLinkedList linkedlist[100001];

int main()
{
	int n,q;
	cin>>n>>q;
	for(int num=1;num<=q;num++)
	{
		int i,j,k;
		int choice;
		cin>>choice;
		if(choice == 1)
		{
			cin>>i>>j>>k;
			linkedlist[i].addAtTail(j,k);
		}
		else
		{
			cin>>i>>j;
			cout<<linkedlist[i].search(j)<<endl;
		}
	}
	return 0;
}

在这里插入图片描述

事实上确实通过了，但是被新增的hack数据卡掉了。
（这里不由得想到如果采用链表首插法能否克服hack数据？尚未实践）

解法二

这其实本来是数组的存储、访问的问题，只是使用数组存储空间放不下。
那么不难想到，我们可以尝试动态数组或者map映射。
这里我们采用map+pair映射。

#include<iostream>
#include<map>
using namespace std;

map <pair<int, int>, int> cabinet;

int main()
{
	int n, q;
	cin >> n >> q;
	while(q--)
	{
		int op, i, j, k;
		cin >> op;
		if (op == 1)
		{
			cin >> i >> j >> k;
			cabinet[{i, j}] = k;
		}
		else
		{
			cin >> i >> j;
			cout << cabinet[{i, j}] << endl;
		}
	}
	return 0;
}

解法三

由于包柜和格子的数量最大值都是 $10^5$ ，因此我们可以想到用两个 int 拼成一个 long long 的做法来进行状态压缩。（若数据范围更大，可改用字符串）
上面使用map是因为unordered_map没法叠加使用pair，那么这里我们可以改为unordered_map。

特性	`unordered_map`	`map`
底层实现	哈希表	红黑树（平衡二叉搜索树）
元素顺序	无序	按键升序排列
查找/插入/删除时间复杂度	平均 O(1)，最坏 O(n)（哈希冲突严重时）	O(log n)
内存使用	通常较高（哈希表需要额外空间）	较低（节点只存储键值对和指针）
迭代器类型	前向迭代器（至少是单向）	双向迭代器
键的要求	需提供哈希函数和相等比较	需提供比较函数（默认 `operator<`）
适用场景	追求速度，不关心顺序，键可高效哈希	需要有序数据，或无法设计好的哈希函数

#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<long long, int> a;
long long i,j;
int c,k;
int main()
{
	int n,q;
	cin>>n>>q;
	for(int cnt=1;cnt<=q;cnt++)
	{
		cin>>c;
		if(c==1)
		{
			cin>>i>>j>>k;
			a[i*1000000+j] = k;
		}
		else
		{
			cin>>i>>j;
			cout<<a[i*1000000+j]<<endl;
		}
	}
	return 0;
}