HBUACM

河北大学暑期程序设计训练每日知识分享-day19 每日分享——Trie树 说明 Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。Trie 树不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串。 举个简单的例子来说明一下。我们有 6 个字符串，它们分别是：how，hi，her，hello，so，see。我们希望在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低。 这个时候，我们就可以先对这 6 个字符串做一下预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。 匹配 当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那我们将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 ...

河北大学暑期程序设计训练每日知识分享-day18 每日分享——前缀和&差分前缀和：给定一个长度为n的序列，当我们需要频繁的求某一段区间内的和的时候，我们可以使用 前缀和 来减少运算次数。 前缀和是一个典型的以空间换时间的小技巧。其实就是我们高中学过的前n项和。 给定一个数组 a[n],我们使用s[i]来表示a[]的前i项和。 12345//a[]的有效数据从1开始 1~n//构造前n项和s[n]s[0]=0;for(int i=1;i<=n;++i) s[i]=s[i-1]+q[i]; 因为循环中需要用到i-1我们的下标从1开始避免错误，所以可以让a[]数组从1开始存储有效数据。（当我们程序中用到[i-1]时，经常下标从1开始）。 查询第l个数到第r个数的和： 1234567int getSum(int l,int r){ return s[r]-s[l-1]; //s[r]: a[1]+...+a[r] //s[l-1]: a[1]+...+a[l-1] // a[l]+...+a[r]} 今年上半年的csp的 ...

河北大学暑期程序设计训练每日知识分享-day17 每日分享——sizeof-strlen-size-length理解运算符：sizeof函数：strlen()、size()、length() sizeof计算变量、常量名或是数据类型名占用的空间字节数；strlen传入C语言字符串（字符数组名或字符指针，以\0结尾），返回从传入的第一个字符到\0的长度；size和length都是string类的成员函数，两函数完全相同，返回C++字符串的长度。起初string是没有size函数的，后来C++引入STL后为保持各容器统一才加入的 其实归根结底还是区分开char*和string，搞清楚指针。推荐一本对于理解指针很有帮助的书——《深入理解C指针》，指针学着并不难，难的是学会了依旧看不懂别人指针的玩法。

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。 输入格式：输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。 随后 N 行，每行按以下格式描述一个结点： 1地址 键值 下一个结点 其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。 输出格式：首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。 输入样例：12345600100 599999 -7 8765423854 -15 0000087654 15 -100000 -15 9999900100 21 23854 输出样例：1234500100 21 2385423854 -15 9999999999 -7 -1000 ...

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。 输入格式：输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、/以及运算数，不同对象（运算数、运算符号）之间以空格分隔。 输出格式：输出前缀表达式的运算结果，保留小数点后1位，或错误信息ERROR。 输入样例：1+ + 2 * 3 - 7 4 / 8 4 输出样例：113.0 思路求前缀表达式的值，需要从右向左读，遇数字压栈，遇符号使用两次栈顶元素进行计算，并将结果压栈。最后若栈内元素唯一，则为最终结果。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <iostream>#include <stdlib.h>#include <cstdio> ...

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。 输入格式：输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。 输出格式：按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。 输入样例：18 2 1 3 9 4 11 13 15 输出样例：11 3 2 9 11 4 13 15 思路利用两个queue A，B，并按照顾客奇偶序列号来存储，模拟排队时的先进后出。输出时注意先输出A队列中的顾客序号。 代码123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include &l ...

彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。 假设彩虹瓶里要按顺序装 N 种颜色的小球（不妨将顺序就编号为 1 到 N）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一箱过来。 如果工厂里发货的顺序比较好，工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色，工厂按照 7、6、1、3、2、5、4 这个顺序发货，则工人先拿到 7、6 两种不能装填的颜色，将其按照 7 在下、6 在上的顺序堆在货架上；拿到 1 时可以直接装填；拿到 3 时又得临时码放在 6 号颜色箱上；拿到 2 时可以直接装填；随后从货架顶取下 3 进行装填；然后拿到 5，临时码放到 6 上面；最后取了 4 号颜色直接装填；剩下的工作就是顺序从货架上取下 5、6、7 依次装填。 但如 ...

一种自动包装机的结构如图 1 所示。首先机器中有 N 条轨道，放置了一些物品。轨道下面有一个筐。当某条轨道的按钮被按下时，活塞向左推动，将轨道尽头的一件物品推落筐中。当 0 号按钮被按下时，机械手将抓取筐顶部的一件物品，放到流水线上。 一种特殊情况是，因为筐的容量是有限的，当筐已经满了，但仍然有某条轨道的按钮被按下时，系统应强制启动 0 号键，先从筐里抓出一件物品，再将对应轨道的物品推落。此外，如果轨道已经空了，再按对应的按钮不会发生任何事；同样的，如果筐是空的，按 0 号按钮也不会发生任何事。 现给定一系列按钮操作，请你依次列出流水线上的物品。 输入格式：输入第一行给出 3 个正整数 N（≤100）、M（≤1000）和 S max（≤100），分别为轨道的条数（于是轨道从 1 到 N 编号）、每条轨道初始放置的物品数量、以及筐的最大容量。随后 N 行，每行给出 M 个英文大写字母，表示每条轨道的初始物品摆放。 最后一行给出一系列数字，顺序对应被按下的按钮编号，直到 −1 标志输入结束，这个数字不要处理。数字间以空格分隔。题目保证至少会取出一件物品放在流水线上。 输出格式：在一行中顺序 ...

河北大学暑期程序设计训练每日知识分享-day16 每日分享——LeetCode-技术成长平台力扣（LeetCode) https://leetcode-cn.com/力扣是一个全球极客挚爱的技术成长平台，致力于帮助程序员们学习算法知识、训练算法题目，以提升自身技术能力、斩获 Dream Offer。力扣上的题目偏求职面试风格，题目难度分简单、中等、困难三个等级，力扣的题解版块汇集了各路算法大神的解题思路，优秀的题解不少，非常值得一看。 除此之外，力扣周赛 / 双周赛是全球同步的算法比赛，可以与全球的小伙伴一决高下。每次比赛结束后都会有一个全球 / 全国排名。在比赛结果页面还可以去学习一下大神们的解题思路，开拓算法思维。每场比赛共有四道题目，比赛时间为 1 小时 30 分钟。每题各种各样复杂度的算法都出现在比赛中。此外，对 Bug Maker 非常友好，在比赛时能告诉你哪个（非样例）点错了。

给定一个初始为空的栈和一系列压栈、弹栈操作，请编写程序输出每次弹栈的元素。栈的元素值均为整数。 输入格式：输入第1行为1个正整数n，表示操作个数；接下来n行，每行表示一个操作，格式为1 d或0。1 d表示将整数d压栈，0表示弹栈。n不超过20000。 输出格式：按顺序输出每次弹栈的元素，每个元素一行。若某弹栈操作不合法（如在栈空时弹栈），则对该操作输出invalid。 输入样例：1234567871 11 20001 30 输出样例：123421invalid3 思路c++ stl 中容器stack的基本使用，注意需要使用s.empty()来判断栈是否为空 代码123456789101112131415161718192021222324#include <iostream>#include <stack>using namespace std;int main() { stack<int> s; int n; cin >> n; for (int i = 0; i < n; i++)  ...