数据结构

仓库日志 原题链接：https://oj.haizeix.com/problem/379 某仓库购入新的货物并将一部分老货物发出，这个过程会有软件对数据以日志形式保存，规则如下： 该日志记录了两类操作： 第一类操作为入库操作，以及该次入库的货物数量； 第二类操作为出库操作。 这些记录都严格按时间顺序排列。入库和出库的规则为先进后出，即每次出库操作货物为当前在仓库里所有货物中最晚入库的货物。 为了便于分析，现在加入了第三类查询操作，每次查询时输出当前仓库数量最多的货物的数量。 输入： 包含 N+1行： 第一行为 1 个正整数 N，对应于日志内所含操作的总数。 接下来的 N 行，分别属于以下三种格式之一： 0 X ：一次入库操作，正整数 X 表示该次入库的货物的数量 1 ：一次出库操作，（就当时而言）最后入库的货物出库 2 ：一次查询操作，要求分析程序输出当前仓库内数量最多的货物的数量 当仓库为空时你应该忽略出库操作，当仓库为空查询时你应该输出 0。 初始时仓库状态为空。 输出： 输出行数等于日志中查询操作的次数。每行为一个正整数，表示查询结果。 样例： 1234567891011121314130 10 220 40 221211212 1234524410 代码12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<stack>using namespace std;stack<int> stack1;//存储仓库货物的数量stack<int> stack2;//存储当前仓库内数量最多的货物数量int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; switch (x) { case 0://入库操作（入栈操作） int num; cin >> num; stack1.push(num); if (stack1.size() == 1) stack2.push(num); else ...

讲话模式 原题链接：https://oj.haizeix.com/problem/577 每个人讲话都有口头禅，现在给出一个字符串，需要求出其中出现次数最多的单词。 输入： 输入一行，若干个长度小于或等于 10 的只包含大小写字母的字符串。 输出： 输出一行，为出现次数最多的单词和它出现的次数，以一个空格隔开。如果出现次数最多的单词有多个，则输出字典序最小的那个。这个单词必须完全以小写的形式输出。注意，所说的单词不区分大小写字母。 样例： 1Can a can can a can It can 1can 5 代码 解法1：定义两个变量string、int，轮回最终保留一个出现次数最多的结果，如果有多个则保留字典序最小的单词。 解法2：当处理完所有的数据后，遍历一遍数组保留最终的结果。 123456789101112131415161718192021222324252627282930#include<iostream>#include<map>#include<string>using namespace std;map<string, int> mp;string ans;//最终答案int count;//答案出现的次数int main() { string t; //大小写转换 while (cin >> t) { for (int i = 0; i < t.size(); ++i) { if (t[i] >= 'A' && t[i] <= 'Z') { t[i] += ('a' - 'A'); } } mp[t]++; } //数据处理 使用有序map for (auto it = mp.begin(); it != mp.end(); ++it) { if (it->second > count) { ans = it->first; count = it->second; } } cout << ...

上网统计 原题链接：https://oj.haizeix.com/problem/566 在一个网络系统中有 N 个用户、 M 次上网记录。每个用户可以自己注册一个用户名，每个用户名只包含小写字母且长度小于 1000 的字符串，每次上网日志里都会有记录，现在请统计每个用户每次浏览了多少个网页。注意，有可能有用户没有访问记录。 输入： 第 1 行包含两个正整数 N （1 ≤ N ≤ 1000） 和 M （1 ≤ M ≤ 5000）。 第 2 ~ M+1 行，每行包含 2 个字符串，分别表示用户名和浏览的网页名。 输出： 共 x 行，x 表示有访问记录的用户数量， 每行的第一个字符串时用户名，接下来的若干字符串是这个用户依次浏览的网页名(之间用一个空格隔开)。 按照用户名出现的次序排序输出。 样例： 123456785 7goodstudyer bookshopalikespacea spacewebgoodstudyer bookshopblikespaceb spaceweblikespacec spaceweblikespacea juiceshopgameplayer gameweb 12345goodstudyer bookshopa bookshopblikespacea spaceweb juiceshoplikespaceb spaceweblikespacec spacewebgameplayer gameweb 代码12345678910111213141516171819202122232425262728293031323334353637#include<iostream>#include<string>#include<vector>#include<unordered_map>using namespace std;int cnt;//当前用户访问记录所在的行数int n;//用户的个数int recordNum;//上网记录的条数unordered_map<string, int> mp;//用于记录vector在第几行的信息（unordered_map满足按用户名出现的次序进行输出）int main() { cin >> n >> r ...

报数 原题链接：https://oj.haizeix.com/problem/382 N 个人围成一圈，编号分别为 1,2,3……N 第一个人从 1 报数，按照编号顺序依次报数， 报 M 的人会离开队伍，然后下一个人会继续从 1 开始报数，直到剩下一人，剩下的人的编号是多少？ 输入： 共一行两个数 N 和 M 输出： 输出一个数表示最后一人的编号。 样例： 17 3 14 代码1234567891011121314151617181920212223#include<iostream>#include<queue>using namespace std;queue<int> que;int main() { //队列模拟约瑟夫环 int n, m; cin >> n >> m; for(int i = 1; i <= n; ++i) que.push(i); int now = 1;//更新报1的位置 while(que.size() != 1){ if (now != m) { que.push(que.front()); now++; } else { now = 1; } que.pop(); } cout << que.front() << endl; return 0;}

海港 原题链接：https://oj.haizeix.com/problem/385 小李是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。 小李对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 i 艘到达的船，他记录了这艘船到达的时间 ti (单位：秒)，船上的乘 客数 ki，以及每名乘客的国籍 xi,1, xi,2,…, xi,k。 小李统计了 n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24 小时( 24 小时= 86400 秒）内所有乘船到达的乘客来自多少个不同的国家。 形式化地讲，你需要计算 n 条信息。对于输出的第 i 条信息，你需要统计满足 ti − 86400 < tp ≤ ti 的船只 p，在所有的 xp,j 中，总共有多少个不同的数。 输入： 第一行输入一个正整数 n，表示小李统计了 n 艘船的信息。 接下来 n 行，每行描述一艘船的信息：前两个整数 ti 和 ki 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 ki 个整数 xi,j 表示船上乘客的国籍。 保证输入的 ti 是递增的，单位是秒；表示从小李第一次上班开始计时，这艘船在第 ti 秒到达海港。 输出： 输出 n 行，第 i 行输出一个整数表示第 i 艘船到达后的统计信息。 样例： 12345//样例输入131 4 4 1 2 22 2 2 310 1 3 1234//样例输出1344 第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客， 分别是来自国家 4,1,2,2，共来自 3 个不同的国家 第二艘船在第 2 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4+2=6 个乘客，分别是来自国家 4,1,2,2,2,3，共来自 4 个不同的国家 第三艘船在第 10 秒到达海港，最近 24 小时到达的船是第一艘船、第二艘船和第 三艘船，共有 4+2+1=7 个乘客，分别是来自国家 4,1,2,2,2,3,3，共来自 4 个不同的国家 123456//样例输入241 4 1 2 2 33 2 2 386401 2 3 486402 1 5 12345//样例输出23334 第一艘船在第 1 秒到达海港 ...

桐桐的新闻系统 原题链接：https://oj.haizeix.com/problem/573 桐桐为期末的计算机作业设计了一套新闻系统，他把这套新闻系统称为 Argus。使用这套系统的用户可以向这套系统注册，然后这套系统就会以用户要求发送新闻的时间间隔向用户发送一次新闻。 向 Argus 注册的指令具有这样的格式：Register Qnum Period Qnum （0 < Qnum ≤ 30000） 是用户的 ID，Period（0 < Period ≤ 3000）是间隔。注册后 Period 秒，结果会第一次到达。 所有的用户都有不同的 Qnum。 桐桐测试了一段时间后，想知道系统前 K 次给谁发送新闻了。如果同一时间发送多个新闻，以 Qnum 的升序排列。 输入： 第一部分是注册指令，每条一行。指令数不超过 1000。此部分以 “ # ” 结束。 第二部分仅一行一个整数 K，K ≤ 10000。 输出： 输出前 K 个新闻发送到的用户的 Qnum，每行一个。 样例： 1234Register 2004 200Register 2005 300#5 1234520042005200420042005 代码思路：每次取时间最小的进行输出，同为时间最小时再按照ID进行排序，故应该使用优先队列进行处理。 1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>#include<queue>#include<string>using namespace std;struct node { int id; int offset;//获得新闻的时间 int next;//下一次获得新闻的时间（排序依据） bool operator<(const node &t) const {//重载小于号 实现大于号的功能(自定义优先队列的排序规则) if (this->next == t.next) return this->id > t.id; return this->next > t.next; }};priority_ ...

STL基本使用 STL六大组件： 容器 适配器 空间分配器：malloc 迭代器：高级指针 算法库：sort 仿函数：一个类重载一个括号 1.string类 string常用方法 find(what, start) substr(start, length) insert(start, what) replace(start, length, what) size()\length() 注意：find()返回值为第一个目标出现的下标值，若没有找到将返回string::npos(-1) 123456789101112131415161718192021222324252627#include <iostream>#include <string>using namespace std;int main(){ string str = "ABCDEF"; //1.输出字符串长度 cout << str.size() << endl; //2.查找字符串DE的位置 cout << str.find("DE") << endl; //3.输出没有查找到的结果 cout << (int)str.find("DE", 5) << endl; //4.字符串截取 cout << str.substr(3, 2) << endl; //5.字符串插入 str.insert(1, "abc"); cout << str << endl; //6.字符串替换 str.replace(2, 5, "000"); cout << str << endl; //7.一次性读入一行包含空格的字符串 string str1; getline(cin, str1); cout << str1 << endl; return 0;} ...