WTSRUVF - 博客园

2018年8月17日

Distinct Substrings SPOJ - DISUBSTR(后缀数组水题)

摘要：求不重复的子串个数用所有的减去height就好了推出来的。。。阅读全文

posted @ 2018-08-17 18:19 WTSRUVF 阅读(185) 评论(0) 推荐(0)

摘要：题意：求可重叠的最长重复子串，但有一个限制条件。。要至少重复k次解析：二分枚举k，对于连续的height 如果height[i] >= k 说明它们至少有k个元素是重复的，所以判断一下就好了数据很水输入数据可能为0，所以s[i]++ s[n++] = 0; 要后缀数组要保证末尾加的字符比前阅读全文

posted @ 2018-08-17 17:21 WTSRUVF 阅读(197) 评论(0) 推荐(0)

Musical Theme POJ - 1743（后缀数组+二分）

摘要：求不可重叠最长重复子串对于height[i]定义为sa[i]和 sa[i-1]的最长公共前缀这个最长公共前缀的值肯定是最大的证明：设rank[j] < rank[k], 则不难证明后缀j和k的LCP的长度等于height[rank[j]+1], height[rank[j]+2],```, 阅读全文

posted @ 2018-08-17 11:19 WTSRUVF 阅读(162) 评论(0) 推荐(0)

2018年8月16日

后缀数组讲解

摘要：参考： https://chuna2.787528.xyz/shanchuan04/p/5324009.html 首先铭记几个数组的含义在看代码的时候一定要记住到底是什么意思把含义写在纸上一定要明确第一次循环以后x[i]和c[i]所代表的意义和第一次循环不同 sa[i] 排名为i的后缀第一关键字的阅读全文

posted @ 2018-08-16 22:17 WTSRUVF 阅读(411) 评论(0) 推荐(0)

Theme Section HDU - 4763（些许暴力）

摘要：题意：求出最长公共前后缀不能重叠而且这个前后缀在串的中间也要出现一次解析：再明确一次next数组的意思：完全匹配的最长前后缀长度求一遍next 然后暴力枚举就好了阅读全文

posted @ 2018-08-16 10:54 WTSRUVF 阅读(169) 评论(0) 推荐(0)

Wow! Such Doge! HDU - 4847（虽然是道水题但很有必要记一下）

摘要：就是求出现了多少次doge 不区分大小写巧用字符串函数 isalpha 判断是否是字母 tolower 转换为小写字母 toupper 转换为大写字母 strncmp字符串比较函数能限制比较的长度阅读全文

posted @ 2018-08-16 08:59 WTSRUVF 阅读(306) 评论(0) 推荐(0)

Girls' research HDU - 3294(马拉车水题)

摘要：题意：求最长回文串长度要大于等于2 且输出起点和终点输出回文串字符这个字符还是要以给出的字符为起点a 输出解析：分析一下s_new串就好了阅读全文

posted @ 2018-08-16 08:23 WTSRUVF 阅读(184) 评论(0) 推荐(0)

2018年8月15日

吉哥系列故事――完美队形II HDU - 4513(马拉车变一下形)

摘要：题意：求最长回文串。。。但这个回文串要符合从中间到两头逐个递减解析：在扩散的时候加一个判断就好了阅读全文

posted @ 2018-08-15 22:55 WTSRUVF 阅读(351) 评论(0) 推荐(0)

Best Reward HDU - 3613（马拉车+枚举+前缀和）

摘要：题意：给你一串字符串，每个字符都有一个权值，要求把这个字符串在某点分开，使之成为两个单独的字符串如果这两个子串某一个是回文串，则权值为那一个串所有的字符权值和若不是回文串，则权值为0 解析：先用Manacher算法求出以每个字母为中心的回文串的长度，并计算该字符串的前缀价值和。然后枚举切割点阅读全文

posted @ 2018-08-15 16:29 WTSRUVF 阅读(261) 评论(0) 推荐(0)

String Problem HDU - 3374（最大最小表示法+循环节）

摘要：题意：给出一个字符串，问这个字符串经过移动后的字典序最小的字符串的首字符位置和字典序最大的字符串的首字符的位置，和能出现多少次最小字典序的字符串和最大字典序的字符串解析：能出现多少次就是求整个字符串能出现几次循环然后就是最大最小表示法。。有点厉害。。。阅读全文

posted @ 2018-08-15 11:50 WTSRUVF 阅读(171) 评论(0) 推荐(0)

冰冻三尺非一日之寒

请让我看看你真正的力量

公告

冰冻三尺 非一日之寒

请让我看看你真正的力量

公告

冰冻三尺非一日之寒