P4147「玉蟾宫」 1. 题目 题目链接：P4147「玉蟾宫」 。 题目背景 有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。 题目描述 这片土地被分成 N×MN\times MN×M 个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。 现在 freda 要在这里卖萌。 2020-08-26 Technique ACM 题解 Technique ACM 题解
单调栈 1. 简介 单调栈是一种用来解决首递增序列问题的数据结构，其满足从栈顶元素到栈底元素单调的性质。单调栈还可以用来解决求矩形统计图中最大内矩形面积的问题，进一步可以用来求最小矩阵和问题。 2. 概念 首递增序列 对于序列 a1,a2,⋯ ,aNa_1,a_2,\cdots,a_Na1,a2,⋯,aN，定义从左往右 aia_iai 的首递增序列为 ab0=ai,ab1,ab2,⋯ ,ab 2020-08-26 Technique ACM 算法 数据结构 Technique ACM 算法 算法 数据结构 数据结构
单调栈 1. 简介 单调栈是一种用来解决首递增序列问题的数据结构，其满足从栈顶元素到栈底元素单调的性质。单调栈还可以用来解决求矩形统计图中最大内矩形面积的问题，进一步可以用来求最小矩阵和问题。 2. 概念 首递增序列 对于序列 a1,a2,⋯ ,aNa_1,a_2,\cdots,a_Na1,a2,⋯,aN，定义从左往右 aia_iai 的首递增序列为 ab0=ai,ab1,ab2,⋯ ,ab 2020-08-26 Technique ACM 算法 数据结构 Technique ACM 算法 算法 数据结构 数据结构
POJ3250「Bad Hair Day」 1. 题目 题目链接：POJ3250「Bad Hair Day」 。 Description Some of Farmer John's NNN cows (1 ≤ NNN ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to coun 2020-08-26 Technique ACM 题解 Technique ACM 题解
后缀数组 1. 简介 后缀数组是处理字符串的一种强有力工具，高效而且容易编程实现，可应用于求字符串的多种子串问题中，可谓处理字符串的一大利器。 2. 思想 2.1 子串 字符串 SSS 的子串 s[i..j], i≤js[i..j], \ i \leq js[i..j], i≤j 表示串 SSS 中从第 iii 个字符到第 jjj 个字符形成的字符串。 2.1.1 重复子串 字符串 sss 在字符串 SSS 2020-08-24 Technique ACM 算法 字符串 Technique ACM 算法 字符串 算法 数据结构
后缀数组 1. 简介 后缀数组是处理字符串的一种强有力工具，高效而且容易编程实现，可应用于求字符串的多种子串问题中，可谓处理字符串的一大利器。 2. 思想 2.1 子串 字符串 SSS 的子串 s[i..j], i≤js[i..j], \ i \leq js[i..j], i≤j 表示串 SSS 中从第 iii 个字符到第 jjj 个字符形成的字符串。 2.1.1 重复子串 字符串 sss 在字符串 SSS 2020-08-24 Technique ACM 算法 字符串 Technique ACM 算法 字符串 算法 数据结构
桶排序 【注】参考自教材「算法导论」。 1. 简介 桶排序是将待排序序列分到有限数量的桶中，然后对每一个桶分别进行排序。桶排序的前提假设为被排序序列的关键字数值符合均匀分布，此时桶排序的平均时间复杂度为 O(n+n2k+k)O(n + {n^2 \over k} + k)O(n+kn2+k)，最坏时间复杂度为 O(n2)O(n^2)O(n2)，其中 kkk 为桶的数量。当桶数量 k≈nk \appr 2020-08-24 Technique ACM 算法 排序 Technique ACM 算法 排序
桶排序 【注】参考自教材「算法导论」。 1. 简介 桶排序是将待排序序列分到有限数量的桶中，然后对每一个桶分别进行排序。桶排序的前提假设为被排序序列的关键字数值符合均匀分布，此时桶排序的平均时间复杂度为 O(n+n2k+k)O(n + {n^2 \over k} + k)O(n+kn2+k)，最坏时间复杂度为 O(n2)O(n^2)O(n2)，其中 kkk 为桶的数量。当桶数量 k≈nk \appr 2020-08-24 Technique ACM 算法 排序 Technique ACM 算法 排序
希尔排序 1. 简介 希尔排序又称缩小增量排序，其也属于插入排序类算法。相较于一般的插入算法、折半插入算法、2-路插入算法以及表插入算法，希尔排序在时间效率上更加优秀。 2. 思想 对于普通的插入算法，其时间复杂度为 O(n2)O(n^2)O(n2)，且在序列有序时，可以达到最好的时间复杂度 O(n)O(n)O(n)；而且当 nnn 较小时，由于移动的元素较少，插入排序效率也比较高。 因此，我们可以采用分治 2020-08-22 Technique ACM 算法 排序 Technique ACM 算法 排序
希尔排序 1. 简介 希尔排序又称缩小增量排序，其也属于插入排序类算法。相较于一般的插入算法、折半插入算法、2-路插入算法以及表插入算法，希尔排序在时间效率上更加优秀。 2. 思想 对于普通的插入算法，其时间复杂度为 O(n2)O(n^2)O(n2)，且在序列有序时，可以达到最好的时间复杂度 O(n)O(n)O(n)；而且当 nnn 较小时，由于移动的元素较少，插入排序效率也比较高。 因此，我们可以采用分治 2020-08-22 Technique ACM 算法 排序 Technique ACM 算法 排序