首页 > 分享 > 算法的艺术

算法的艺术

花匠小妙招
2024-09-10 12:35

算法的艺术

关注

文章平均质量分 90

程序该被它的内部逻辑而非外部表现所指引，我们所钟爱的很大程度上是程序中所达到的完美的逻辑，而外部的东西只是拿出来与众人分享快乐的手段，对吗？

关注数：313 文章数：329 文章阅读量：425729 文章收藏量：46

ProLightsfxjh

UESTC 1592 An easy problem B 线段树区间合并题意：区间更新把该区间内所有的数异或1，区间查询该区间内最长连续1的长度。线段树区间合并每个节点维护十元组int summid[4*MAXN][2], suml[4*MAXN][2], sumr[4*MAXN][2], ans[4*MAXN][2], lazy[4*MAXN], rev[4*MAXN];summid[Ind][k]表示该区间的中间的最长连续k(0|1)的长度，suml[Ind][k]描述该区间从左端点开始的最长连续k(0|1)的长度，sumr[Ind][k]表示从该区间右端点结束原创 2017-05-16 18:06:18 · 862 阅读 · 0 评论 UESTC 1591 An easy problem A ST表、简单题题意：每次查询区间内极差。ST表、简单题可以用2个ST表，分别维护区间最大值和区间最小值先O(nlogn)的预处理出来，然后每次O(1)的查询，每次的极差即为区间最大值 - 区间最小值复杂度 O(nlogn) 原创 2017-05-16 17:59:45 · 643 阅读 · 0 评论 HihoCoder - 1044 状态压缩·一状态压缩dp 题意：给出一个序列，选出一部分值，连续的m个数里最短选取q个，求选出的值的和的最大值。状态压缩dpdpij表示当前考虑第i个数，且以i结尾的连续m个数的情况储存在j里，j用二进制表示以后比如m=5， 10100表示序列选了i-4, i-2,没有选i-3, i-1, i.状态转移的时候，先判断j里有几个1，如果cnt <= q,则为合法状态，t = j >> 1表示当前状态j表示的前 m-1个数的情况(不包括第i个数)如果 i < m则直接， dp[i][j] = dp[i-1][t] + (j 原创 2017-04-29 00:49:39 · 1052 阅读 · 0 评论 HihoCoder - 1043 完全背包基础dp、背包dp 题意：dp基础题，给出n种背包每种有无限个，每个花费为needi 价值为 valuei，总花费m，求最大价值和。基础dp、背包dpdpj表示，总花费为j时的最大价值和，dpj = dp[j- needi] + valuei;这里直接对于每个背包i，直接从0~m进行递推，dp[j- needi] 可以是上一个背包递推过来的，也可以是当前背包递推过来的。复杂度 O(n^2) 原创 2017-04-29 00:31:26 · 955 阅读 · 0 评论 HihoCoder - 1038 01背包基础dp、背包dp 基础dp、背包dpdpij表示当前考虑第i个背包，花费为j时的最大收获。由于状态转移只考虑当前状态和上一层状态，所以只能可以转化成一维，然后dp的是 j 从大到小的顺序进行递推，这样 dp[ j-need[i] ]必定必定是上一次的，而不是这一次的。复杂度 O(n^2) 原创 2017-04-29 00:24:23 · 877 阅读 · 0 评论 HihoCoder - 1037 数字三角形基础dp、朴素dp 题意：dp基础题，给出一个数字三角形，求一条从顶到底的路径，路径权值和的最大值。基础dp、朴素dp复习下dp基础知识，动态规划的一个核心概念在于不去计算已经计算的东西，不去计算不需要的东西，即"取出冗余"。且要满足，性质一：无后效性，即当前的抉择不会对后面的抉择产生影响；性质二：重复子问题，即把当前问题分解为k个问题。然后定义状态，写出状态转移方程，并从时间和空间的角度优化状态和状态转移方程。然后注意处理边界情况。这题直接定义 dpij表示走到第原创 2017-04-29 00:12:19 · 784 阅读 · 0 评论 HihoCoder - 1511 树的方差无根树的计数、分配式方差、分数取模题意：给出一个n，表示n个节点的无根树，每个节点的权值是deg[i]即节点的度，求所有节点个数为n的无根树的deg[i]方差的和。无根树的计数、平均方差、分数取模首先要用到一个分配式方差公式(笔者自己命的名)，表示把n个东西分配成m分时的方差。这里长度为n的无根树，则sigma{deg[i]} == 2*(n-1)。然后点的度数必定大于0，所以相当于把 2*(n-1) - n 个东西分配成 n 份的方差的和。这里节点数为n的完全图有 n^(n-2) 种无根树，所以答案是 (n-1) 原创 2017-04-28 18:50:30 · 1070 阅读 · 3 评论 HihoCoder - 1457 后缀自动机四·重复旋律7 后缀自动机+拓扑排序+递推、BFS 题意：所有字符串的不同子串的“和”（也就是把串看成数字，在十进制下的求和，允许有前导0）。后缀自动机+拓扑排序+递推、BFS首先如果只是一个字符串，则转移的时候，st[i] == v节点会转移到u节点，则 cnt[u] = sigma{cnt[v] * 10 + c * |substrings(v)| | trans[v][c] = u},其中cnt[v]表示以v结尾的不同子串的和， |substrings(v)| 即为以v结尾的不同子串的个数即从s到v的路径数。然后推广到这里的n个串，可以用原创 2017-04-22 19:02:27 · 1335 阅读 · 0 评论 HihoCoder - 1449 后缀自动机三·重复旋律6 后缀自动机、递推、DFS 题意：求一个字符串中，所有长度为K的子串出现次数最多的子串的出现次数，但是K不是固定的，求所有的K的答案。后缀自动机、递推、DFS首先 ans[MAXN] 必定是单调不增序列，一个子串出现的次数是它的endpos集合的大小，由于endpos[u]的集合为以u代表的子树的endpos集合的并集，可以跑一边dfs，预处理出所有的endpossz[i]。所以只需要根据pre树求出，ans[maxlen(st)] = max(ans[maxlen[st], endpossz[st]),然后从len~0递推，原创 2017-04-22 18:43:32 · 1108 阅读 · 0 评论 HihoCoder - 1445 后缀自动机二·重复旋律5 后缀自动机题意：统计字符串中不同子串的个数。后缀自动机这题是后缀自动机基础题，直接使用SAM上的pre树， sigma{val[np] - val[pre[np]]}复杂度 O(n) 原创 2017-04-22 18:30:30 · 1040 阅读 · 0 评论 HihoCoder - 1175 拓扑排序·二拓扑排序、BFS 题意：初始有k个节点上有一个病毒，病毒会沿着有向边向向来的节点复制传染一次，图保持无环，最后图上病毒的分布必定会到达稳定状态，求达到稳定状态时，图上的病毒数量。拓扑排序、BFS因为保证无环，所以可以BFS，每次选择入度为0的节点，把病毒数量传递下去。复杂度 O(n+m) 原创 2017-04-22 14:04:42 · 885 阅读 · 0 评论 HihoCoder - 1174 拓扑排序·一拓扑排序、BFS 拓扑排序基础题，判断图中是否有环。拓扑排序、BFS每次把入度为0的点删除后入队，进行BFS，最后如果有剩余没有删除的点，则存在环，否则没有。复杂度 O(n+m) 原创 2017-04-22 13:52:09 · 1096 阅读 · 0 评论 Codeforces Round #409 (Div. 2) D. Volatile Kite 计算几何、凸多边形、线段类题意：给出一个凸多边形，要求求出一个最大的dist，使得所有的点可以任意移动距离最大为第dist的路程，依然为凸多边形。计算几何、凸多边形、线段类对于凸多边形，每相邻的三个点可以构成一个三角形ABC，答案为B到AC的距离的一半，可以以每个点为圆心话圆，这里借用一下官方Tutorial里的图片☺☺然后借助下常用的点类和线段类即可，以下用的是红书上的线段类复杂度 O(n) 原创 2017-04-17 23:32:41 · 1062 阅读 · 0 评论 Codeforces Round #409 (Div. 2) C. Voltage Keepsake 二分题意：每个设备初始电量为bi，每秒消耗ai，然后充电器每秒可以给一个设备充电p，问所有设备同时工作的最长时长。二分很显然的要用二分来做，然后check函数该怎么写呢?这里题目中说 You can switch which device is charging at any arbitrary unit of time (including real numbers) ，这就表示可以整体处理，也就是说，首先把设备按照只用初始电量的工作时间(real number)排序，然后对于每个mid 进行che 原创 2017-04-17 23:14:43 · 1033 阅读 · 0 评论 Codeforces Round #408 (Div. 2) D. Police Stations 最短路、BFS 题意：有一棵无根树，有一些节点上有一些标记(police station)，初始时满足，每个节点至少与一个被标记过的节点相连且距离不超过d，要求去掉尽可能多的节点，使剩余的图依然满足，每个节点至少与一个被标记过的节点相连且距离不超过d。最短路、BFS本来用dfs写了一发，后来发现很多情况下会重复去掉边。用BFS来做比较好，从所有的被标记过的节点开始BFS，当接下来的边会导向已经访问过的节点时把这条边减去，否则放入队列。这样每个节点都会与一个被标记过的节点直接或间接的相连，且距离不超过d。最终会原创 2017-04-13 19:38:48 · 766 阅读 · 0 评论 Codeforces Round #408 (Div. 2) C. Bank Hacking 无根树、贪心、枚举题意：有一棵无根树，上面每个节点都有一个权值，可以任意选择一个节点删除，但这是和它相邻的节点即隔一个点间接相邻的点的权值都会增加1，求把所有的点都依次删除，中途会遇到的最大权值点的最小权值。无根树、贪心、枚举其实选定一个根时，根的权值是本身val[i]，根的子节点的权值是val[i]+1，其它节点的权值是 val[i]+2,这个时候只要枚举根和这个根的直接子节点，即可求出答案。其中取出的这些节点放在priority_queue1里剩余的其它节点放在priority——queue2里，这样就可以快原创 2017-04-13 19:36:27 · 1120 阅读 · 0 评论 UVALive - 3703 Billing Tables Tire、字典树题意：对于11位数字串(电话号码)，按优先级给定n个区间，每个区间有一个标记。若一个电话号码在某个区间内(如有多个则取优先级最高的区间)，则电话号码具有该区间的标记。求一个最小前缀与标记的对应表，使若一个号码的前面与某个前缀匹配，则该号码一定具有该前缀的标记，且不能再与其它前缀匹配。Tire、字典树把区间按照从上到下的顺序插入到Tire中，每个根到叶子节点的路径就是一个符合要求的前缀。每个节点都表示一个电话号码前缀，若某一个节点被一个区间完全覆盖或者几个具有相同标记的区间完全覆盖，则可作为一个叶子节点原创 2017-03-29 18:48:34 · 1115 阅读 · 0 评论 UESTC 1551 Hesty Str1ng 后缀数组+树状数组、回文串题意：给出一个字符串，要求选出子串A，然后自己搞一个长度小于A的子串B，把B接在A的后面，构成一个新的字符串T，要求T为回文串，求能构成的不同回文串的个数。后缀数组+树状数组、回文串刚开始的时候以为只是求不同子串的个数，匆匆忙忙就交了一发，果断wa了，自己还是太年轻了。然后发现，当选出的子串的末尾是以回文子串结尾时(确切的是以长度为偶数的回文子串，在化简一下其实是出现2个相同的字符(即最小半径了)，因为更大的半径所产生的新的构造方法和最小的半径的回文子串产生新回文串的构造结果是一样的，当然这些也是原创 2017-03-27 13:24:39 · 890 阅读 · 0 评论 Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem 2-SAT、并查集题意：每个门有且必须被2个开关所控制，一个开关可以控制多个门，给定n个门的初始状态和每个开关控制哪些门，问是否有方案打开一些开关使所有的门都为unlocked状态。2-SAT、并查集把由于每个门被2个开关控制，所以把门看成是边，把开关看成是点，每个开关有2种点，打开i和关闭i+m，从而变成一个经典的 2-SAT 问题。一个门分别被last[r] 和 i控制，则如果门是开的，则2个开关要么都关要么都开，_merge(last[r], i); _merge(last[r] + m, i + m);否原创 2017-03-22 01:26:12 · 1025 阅读 · 0 评论 Codeforces Round #400 (Div. 1 + Div. 2, combined) C. Molly's Chemicals 区间和、构造、前缀的后缀题意：给出n个数字，要求选出一段连续的数字，使它的和为k的非负整数次方，为这样的区间有多少个。区间和、构造、前缀的后缀这是一个很有趣的构造题，一个连续区间[a, b]，转化为 [1, b] - [1,a-1],如果差值，满足要求则这样的区间存在，然后换过来，对于每个k^j,对于 [1,b] - k^j == [1,ax-1],有多少个前缀和sum{[1,ax-1]}就有多少个多少个区间[ax, b] == k^j次。这里可以借助map来记录前缀和sum{[1,ax-1]} 出现的次数。此外要处理原创 2017-03-22 01:11:31 · 706 阅读 · 0 评论 Codeforces Round #400 (Div. 1 + Div. 2, combined) B. Sherlock and his girlfriend 素数筛法+贪心题意：给出一个n，表示有2、3、......n+1这n个数，要求给这些数涂色，如果一个数是另一个数的质因数则必须涂不同的颜色。素数筛法+贪心首先其实只有2种数，一种是素数，一种是以这个素数作为其其中一个因数的数，所以最多用2中颜色。用素数的O(nlogn)的筛法，边筛素数边涂色，如果i是素数，则涂1，然后对于i*j，(i*j<= n+1)涂上2.，并标记为非素数。复杂度 O(nlogn) 原创 2017-03-22 00:49:13 · 1176 阅读 · 0 评论 Codeforces Round #403 (Div. 2) C. Andryusha and Colored Balloons DFS 题意：给出一颗无根树，要求如果a-b相连 b-c相连，则要求abc涂上不同的颜色，要求用最少的颜色给这颗树上色且求具体涂色。DFS首先这个最少的颜色数必定是最大度+1，然后具体涂色的时候可以dfs来涂色，因为dfs的时候孙子节点的颜色只跟相应子节点和父节点有关，跟该父节点的其它子节点没有关系，所以用dfs来涂色。复杂度 O(n) 原创 2017-03-21 00:13:49 · 511 阅读 · 0 评论 Codeforces Round #403 (Div. 2) B. The Meeting Place Cannot Be Changed 三分题意：n个人每个人在xi位置且运行速度为vi，问他们相聚在一点的最短时间。三分打那次cf 的时候，三分还没有学，没办法。这里直接对[minx, maxx]的范围内进行三分即可，然后eps最开始的时候取了1e-12，后来TLE了，确实好像数据溢出了，double大概只能存十五六位有效数字。所以改成1e-6，就过来，这里给出的一是为了提醒eps的取值，然后可以算一下，用1e-6时，计算出的答案误差确实最大为1e-6，刚好可以满足<=1e-6的误差要求，所以可以放心使用。复杂度略大于 O(n 原创 2017-03-21 00:02:15 · 887 阅读 · 0 评论 SGU - 465 Fire Station Building floyd+三分题意：有n个城市m条双向边，计划在一条道路上建立一个消防局，并且它离城市的距离不能小于R，每个城市i有一个发生火灾的概率pi，要求找出最优的地点，是出警需要的期望路程最小。floyd+三分di表示消防局和j点的最短路程，则期望的路程是 sigma{di * pi}，所以枚举每一条可能可以设立消防局的边，然后在这个边的可行区域内进行三分，(这里二分应该是不行的，因为效果并不单调，而是呈现成凹函数)对于当前位置x，边是(u, v)，则 di = min{x + dist[i][u], w[u][v] - 原创 2017-03-20 22:21:59 · 904 阅读 · 0 评论 HDU - 3487 Play with Chain __ Splay 题意：对1~n这n个数，进行m次操作，分别可以进行区间移动和区间反转，求最终的序列。SplaySplay的基础题，按照要求进行区间移动和区间反转即可。复杂度 O(m*logn) 原创 2017-03-17 23:24:03 · 656 阅读 · 0 评论 Codeforces Round #404 (Div. 2) D. Anton and School - 2 前缀的后缀、范德蒙恒等式、容斥题意：给出一个只有"("和“)"的字符串，为有多少个子序列，它的长度为len，则左边len/2个字符为”("右边len/2个字符为")"，问这样的子序列有多少个。前缀的后缀、范德蒙恒等式、容斥子串为前缀的后缀，这里是子序列，所以s[i]为必取，作为序列的最后一个元素，然后前面的"("为选取，所以可以预处理出suml和sumr，分表表示i的左边有多少个"(", i的右边有多少个")".然后对于每个“("，必选这一个"("，然后i之前的(进行排列组合，选j个"("，就在sumr[i+1]里选j个") 原创 2017-03-16 01:44:40 · 1553 阅读 · 0 评论 Codeforces Round #404 (Div. 2) C. Anton and Fairy Tale 贪心+二分题意：初始是n，每次放入m，然后拿走i， n' = max(n, n' + m)，问i为多少的时候剩余的数为0.贪心+二分首先如果 m >= n 则ans = n;否则贪心，前m天，必定是拿完之后就重新填满的，这个时候剩余 n -= m;然后对这个新的n进行二分，找到最大的cnt，使得 (cnt + 1)*cnt / 2 <= n;然后如果最后得到的cnt，有 (cnt + 1)*cnt / 2 < n; 则还可以再拿一次，最后只有部分人可以拿到1个，cnt ++最后答案就是 ans = m 原创 2017-03-16 01:29:18 · 1132 阅读 · 0 评论 HDU - 4355 Party All the Time 三分题意：每个spirit有一个位置xi一个全中w[i]，如果确定聚会地点为s，则i的花费是 fabs(s - x[i]) ^ 3 * w[i]，求总花费。三分对位置xi进行三分，即把区间分为长度相等的三段，进行查找，这样的查找称为三分查找，三分查找通常用来迅速确定最值。复杂度略大于 O(nlogn) 原创 2017-03-15 00:59:10 · 1113 阅读 · 0 评论 HDU - 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置题意：每次给出一个字母ch和一个字符串s，求s中有多少个不同的子串含有字母ch。后缀自动机+二分、新增distinct子串的个数和位置首先这里要用到后缀自动机的一个性质，添加第i个字符时，自动机里新增了diff = val[np] - val[pre[np]] 个与原先不同的子串，它们分别是 s[0......i]，s[1......i]，……，s[diff-1......i]，这里可以证明，当k < j < i 时，如果 s[j......i]是新增的不同子串，则s[k......i]包括了s[j 原创 2017-03-12 22:48:34 · 701 阅读 · 0 评论 URAL - 1486 Equal Squares 哈希、二维hash、二分、卡大素数题意：给出n个长度为m的字符串(n,m <= 500)，然后问选取一个最大的正方形，使得有2个正方形区域的字符串是相同的，求出这个最大正方形的边长即两次出现位置的正方形左上角坐标。哈希、二维hash、二分、卡大素数题目直接就暗示着用哈希来做 ^_^，然后可以把每个字符串分别用同一个大素数hash掉，然后二分边长，check的时候，检查每个长度为mid的正方形是否再次出现，检查的时候再去另一个大素数pt，把横向的第一次哈希得到的一段字符串的哈希值作为一个元素，把这些元素再次进行哈希，然后在纵向的原创 2017-03-12 15:10:28 · 1243 阅读 · 0 评论 Codeforces 17E Palisection 回文自动机+邻接表题意：给出一个字符串要求找出多少对有相交部分的回文子串。回文自动机+邻接表首先，直接求这个问题比较麻烦，故可以转化为总的回文子串的对数减掉不相交的回文子串的对数。故先预处理出suml[i]表示从左到到，0~i-1内的回文子串的个数，然后倒的再建一个自动机，每次 lesr = num[last]表示插入这个字符以后以这个字符结尾的回文子串的个数，然后 suml[i] * lesr就是此时的不相交的回文子串的对数，然后对于每个i都求出不相交的回文子串的对数，然后总对数减去这个即可。之后就是超内存的问原创 2017-03-10 00:45:34 · 1087 阅读 · 0 评论 URAL - 1960 Palindromes and Super Abilities 回文自动机题意：逐个字符的添加一个字符串，问每添加一个字符显存的字符串的总不同的回文子串的个数。回文树自动机首先推荐篇比较好的讲回文自动机即回文树的博客， Palindromic Tree——回文树【处理一类回文串问题的强力工具】按照功能翻译是回文自动机，按照自字面翻译是回文树。然后这题把Palindromic_Tree原来的void add成员函数，改成在出现新的回文子串的时候(!nxt[cur][c])返回1否则返回0即可。复杂度 O(n) 原创 2017-03-07 22:04:53 · 782 阅读 · 0 评论 SPOJ - SUBLEX Lexicographical Substring Search 后缀数组、跑的非常快、开心、☺☺ 题意：给一个长度不大于90000的字符串，每次询问它的所有不同子串中，字典序第k小的，询问不大于500个。后缀数组本来是找了一个后缀自动机的题，看了题以后觉得用后缀数组做比较方便，结果交了一发，发现自己的代码竟然是目前为止vj上这个题史上最快的，害怕开心 Y ( ^ _ ^ ) Y，首先用字符串s，倍增算法跑出 sa和height，然后把询问根据v[j].q的大小排序然后对于每个i，(1<=i<=n)，cnt += (n - sa[i]) - height[i]; 表示截止当前后缀，所能表原创 2017-03-06 01:41:31 · 1288 阅读 · 6 评论 HDU - 4622 Reincarnation 后缀自动机题意：给出一个长度<=2000的字符串，然后给出q<=10000个询问，为s[l,r]内有多少个不同的子串。后缀自动机首先n <= 2000，故可以用O(n^2)的算法，故对于每个 i ~ n-1建立n个后缀自动机，每次添加一个字符就多出val[np] - val[pre[np]]个不同的子串，valx]表示x节点存储的字符串个数即能表示的最长子串。故用sum[maxn][maxn] n个前缀和来存储区间内不同子串的个数。复杂度 O(n^2) 原创 2017-03-05 19:04:21 · 1076 阅读 · 0 评论 SPOJ - LCS2 Longest Common Substring II 后缀自动机题意：给出n(n<=10)个字符串，求它们的最长公共子串。后缀自动机先用第一个字符串建立后缀自动机，然后用剩余的n-1个字符串在自动机上跑，每次把以节点i结尾的最长公共子串保存在minl[i]中，0<=i<= sam.tot。数组遍历一遍minl数组，找最大的minl[i]就是这n个串的最长公共子串了。复杂度 O(10length) 原创 2017-03-04 19:01:38 · 1028 阅读 · 0 评论 SPOJ - LCS Longest Common Substring 后缀自动机题意：求两个字符串的最长公共子串。后缀自动机看了很久 WJMZBMR 讲后缀自动机的ppt才大致把后缀自动机搞懂^_^,此外附上两个比较好的讲后缀自动机的博客后缀自动机模版，后缀自动机讲解这题直接用一个字符串建立后缀自动机，然后用另一个串在自动机上跑即可，操作和AC自动机有点类似，只是AC自动机匹配失败的时候用的fail指针，而这里用pre树跳转。复杂度 O(n) 原创 2017-03-04 18:54:55 · 845 阅读 · 0 评论 Codeforces Round #402 (Div. 2) D. String Game 二分+优先队列+字符串匹配题意：给出文本串和目标串，然后给出一个文本串删除字符的序列，从a1~an，要求删除s[a1 ~ ak]时剩下的字符串依然可以匹配，求尽可能大的k。二分+优先队列+字符串匹配从左往右是删除字符的顺序，倒着做，从右往做是添加字符的顺序，故check mid~n这个序列能否满足目标串的匹配，要求mid尽可能小，故二分这个剩余序列长度即可，每次check是用优先队列priority_queue<int, vector<int>, greater<int>> pq;，然后依次进行匹配。复杂度 O(nlognl 原创 2017-02-26 21:41:34 · 1050 阅读 · 0 评论 Codeforces Round #402 (Div. 2) C. Dishonest Sellers 贪心、排序题意：给个物品有2个权值ai和bi，要求至少选k个ai，然后求最小的权值和。贪心、排序v[i].diat = v[i].a - v[i].b; 故这个表示ai和bi的差值，差值越小越应当被选取(可以是负数)，所以对v[i].diat进行排序，然后选上前k个的ai，然后对于剩下的n-k个物品，如果diat值为负数则选ai，否则选bi。复杂度 O(nlogn) 原创 2017-02-26 21:32:24 · 1029 阅读 · 0 评论 CSU - 1632 Repeated Substrings 后缀数组、distinct substring 题意：给出一个字符串，找出出现2次及以上的子串的种数。后缀数组跑出sa数组和height数组，然后从i = 2 ~ n遍历，每次 ans += max(0, heigt[i] - lastheight);这里减掉的是已经计算过的子串种数，可参考比此题稍难的 HDU - 3948 The Number of Palindromes 后缀数组+ST表、distinct substring复杂度 O(nlogn) 原创 2017-02-22 23:57:59 · 669 阅读 · 0 评论 HDU - 3948 The Number of Palindromes 后缀数组+ST表、distinct substring 题意：给出一个字符串，求出其回文子串的种数。后缀数组+ST表把s变成 s + '#' + s'，其中s'表示s的反向串。所以当回文子串的长度为奇数时 [i+1, _rank[n - sa[i] - 1]] 的height最小值表示以s[sa[i]]为中心的回文子串的最大半径(算上中心)；长度为偶数时 [i+1, _rank[n - sa[i]]] 的height最小值表示以s[sa[i]]为半径起点的回文子串的最大半径；找这个最大半径，可以用ST表O(nlogn)的预处理出，然后每次O(1 原创 2017-02-22 23:11:54 · 897 阅读 · 0 评论