HBUACM

河北大学暑期程序设计训练每日知识分享-day21 每日分享——康托展开&逆康托展开定义康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。 设有n个数（1,2,3,4,…,n）,组成不同 n! 种的排列组合，其康托展开唯一且最大约为n!康托展开表示的就是当前排列在n个不同元素的全排列中的名次。时间复杂度O(n^2^) 适用范围搜索，动态规划中常常用一个数字来表示一种状态，大大降低空间复杂度 公式X=a1×(n?1)!+a2×(n?2)!+?+an×0!X代表当前排列在全排列中的排名，ai 代表当前数是数列中未出现的数中第几小的 从0开始计数，0是第一小的数 例如 4,2,3,14,2,3,1 4 是当前数列中未出现的数中第3 小的，X+=3?(4?1)! 2 是当前数列中未出现的数中第1 小的，X+=1?(4?2)! 3 是当前数列中未出现的数中第1 小的，X+=1?(4?3)!,因为22 已经输出过了，所以不算 1 是当前数列中未出现的数中第0 小的，X+=0?(4?4)!这要就求出了4,2,3,14,2,3,1 所唯一对应的在全排列中的名次X=22 注 ...

河北大学暑期程序设计训练每日知识分享-day20 每日分享——C++集合操作set函数求并集、交集、差集、对称差集beg1，end1容器1的开始、结束迭代器，beg2，end2容器2的开始、结束迭代器 求交集set_intersection() 函数原型：set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest) 作用：将容器1和容器2的交集存到目标容器，dest为目标容器的起始迭代器。 求并集set_union() 函数原型：set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest) 作用：将容器1和容器2的并集存到目标容器，dest为目标容器的起始迭代器。 求差集set_difference() 函数原型：set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator ...

河北大学暑期程序设计训练每日知识分享-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指针》，指针学着并不难，难的是学会了依旧看不懂别人指针的玩法。

给定一个初始为空的栈和一系列压栈、弹栈操作，请编写程序输出每次弹栈的元素。栈的元素值均为整数。 输入格式：输入第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++)  ...

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

给定仅包含“()[]{}”六种括号的字符串，请你判断该字符串中，括号的匹配是否是合法的，也就是对应括号的数量、嵌套顺序完全正确。。 输入格式：第一行一个整数T（T<=10） 其后T行每行一个字符串只包含[{()}]六种字符（字符串长度2e5以内） 输出格式：对于每个字符串，匹配输出Yes,否则输出No 输入样例：1232{()[]}([)] 输出样例：12YesNo 思路使用stack来存储符号，遇左压栈，如果为右括号判断是否与当前栈顶元素相匹配，若不匹配则为“No”，匹配则弹出当前栈顶元素（左括号），继续进行下一个括号匹配。最后为空栈则为“Yes”。 代码1234567891011121314151617181920212223242526272829303132#include <iostream>#include <stack>using namespace std;bool com(char a, char b) { if ((a == '{' && b == '}') || ...

输入十进制整数N和待转换的进制x（2、8、16），分别代表十进制N转换成二进制、八进制和十六进制，输出对应的结果。十六进制中A~F用大写字母表示。 输入格式：输入两个整数N（十进制整数N）和x（x进制），中间用空格隔开。 输出格式：输出对应的结果。 输入样例：1123 2 输出样例：11111011 输入样例：1123 16 输出样例：17B 思路利用辗转相除法进行进制转换，使用stack来存得到的结果，注意转换为16进制时，从10开始为A。 代码123456789101112131415161718192021#include <iostream>#include <stack>using namespace std;int n, x;int main() { cin >> n >> x; stack<int> s; do { s.push(n % x); n /= x; } while (n); while (!s.empty( ...

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如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> ...