线性表 #
- uva12657 https://www.udebug.com/UVa/12657 移动盒子, 静态链表。
- uva11988 https://www.udebug.com/UVa/11988 悲剧文本, list, insert返回新插入元素的迭代器。
- uva12100 在queue中存放数组的下标，用单独的数组存放权重并排序。
区间最值查询(RMQ) #
Sparse Table #
- bailian3438(Balanced Lineup) Sparse Table模板题，练习创建SparseTable类。
- poj3368(Frequent values) Sparse Table，用动态规划先算出log2数组，对累计后的数据做Sparse Table，查询要比较两部分区间中的最值，从左侧开始的区间的最值要手动判断，右侧区间则可用ST查询。
- hdu3486(Interviewe) Sparse Table结合二分搜索。无法找到的情况可以快速判断。
- bailian2019(Cornfields) 二维区间最值查询，用ST数组来解决。
树状数组(Binary Indexed Tree) #
- bailian2352(Stars) 一维树状数组模板题。星星按y升序排列，y相同，则按x升序排列。y列数据读取后并无用处。计算级别时，假定x值先读到5，再读到3时，这个x为3的新星必定不会对已经有的x为5的星星的等级产生影响，因为它的y值肯定会更大一些。最终，星星的等级即为该x位置的前缀和，算完前缀和后，再为其增1。
- poj3067(Japan) bailian2352的数据已经排了序，而本题则要自己排序。最后结果会超出int范围，很难看出来。输入输出会影响判题。
线段树(Segement Tree) #
- hdu1166(敌兵布阵) 线段树模板题。节点不存储区间信息的解法。
- bailian3243(A Simple Problem with Integers) 线段树延迟标记的处理，使用内部Node的形式，以区间覆盖为查询判断条件。
- hdu4902(Nice boat) 需要非常灵活地应用线段树，进一步提升的好题。
- K-th Number(bailian2104,poj2104,acwing255) 可持久化线段树，利用多个版本数据之差来计算。
Number Theory #
- luogu1075 sqrt(n)数量级判断素数，入门题。
- cf776B 可用埃氏筛法找出素数，入门题。素数个数少的情况需要单独判断。
- Prime Distance(acwing196) poj2689 运用两次筛法，中等难度。
- Divisors(阶乘分解) acwing197 poj2992 要通过数学得到计算公式，计算时需要注意将乘法转换为除法，否则会越界。
并查集 #
- hdu1232(畅通工程) 并查集入门题，实现路径压缩和启发式合并。
字符串 #
-
luogu1308(统计单词数) 练习brute force字符串匹配算法，字符串前后加空格，以方便处理。
-
luogu3375(【模板】KMP) KMP模板题，需要在一次循环中找出所有匹配。
-
bailian2503(Babelfish) Trie模板题，也能用map过。
散列表 #
- bailian3088(Snowflake) 先用哈希函数过滤掉一部分比较对象，再逐个雪花比较。注意两片雪花比较时，有同为顺时针，或一个顺时针另一个逆时针。
- bailian1840(Eqs) 求方程解的个数，可直接使用unordered_map.
- bailian2002(Squares) 使用unordered_map可能会超时，需要自己实现Hash。需要知道平面直角坐标系下已知两点求正方形另外两点的坐标。
Links #
sheet:STL sheet:junior sheet:Graph sheet:Tree sheet:DynamicProgramming sheet:Search