so_hard.

分类

Android(6) BFS(7) DFS(10) DP(15) ESP32(1) HDUOJ(7) KMP(2) Linux(2) MySchoolOJ(1) NowCoder(3) PAT(7) PAT甲级题(5) POJ(1) STL(7) 三维(1) 二分答案(1) 前端学习(1) 图论(4) 字符串处理(1) 嵌入式实时操作系统(μC/OS)(3) 并查集(1) 心路历程(2) 思维(6) 扩展kmp(1) 技巧(3) 数学(4) 数论(7) 整理笔记(1) 新姿势(3) 暴力(1) 最小/大表示法(3) 未归档(203) 树状数组(1) 游戏(1) 游记(1) 离散化(1) 算法与数据结构(2) 线段树(2) 编程语言学习(1) 胡搞题(1) 蓝桥杯OJ(5) 蓝桥杯历届省赛题目(4) 贪心(3)

/ 注册

全部文章（共342篇）

C++string的使用(2)

#include <iostream> #include <string> #include <algorithm> #include <cstring> using namespace std; int main() { string st...

2019-02-07

0 362

DP分类

转载请注明出处，谢谢。 http://blog.csdn.net/cc_again?viewmode=list ———- Accagain 2014年5月15日动态规划一直是ACM竞赛中的重点，同时又是难点，因为该算法时间效率高，代码量少，多元性强，主要考察思维能力、建...

2019-02-07

0 455

HDU3336Count the string(dp+kmp_next表性质)

题目链接：hdu3336 题目大意：给一串n长度的字符串str，问str所有前缀(包括本串)在str中的匹配次数。解题思路：利用kmp爆搜得到一发TLE，参考kmp+dp 以及dp状态方程解释博客思路学会利用next数组的性质进行dp优化：next[i]表示不包含下标为i的字符（i下标之前的串...

2019-02-06

0 436

HDU4162Shape Number(一阶差分预处理+最小表示法)

题目链接：hdu4162 题目大意：总之就是在介绍计算机视觉中链码的东西。给一个数字串，先如果相邻差值为负数的话要将结果+8否则记录结果。最后将这个串看成一个循环串，打印字典序最小的串表示(求同构串)。解题思路：先预处理一下，注意边界相减是原串而不是更新完的结果！然后利用最小表示法求同构串。预...

2019-02-06

0 608

HDU2609How many(最小表示法+set去重)

题目链接：hdu2609 题目大意：给n段01串，问这些串***有几组同构串。同构串定义：两个字符串存在分别从x，y下标开始直到x-1，y-1（循环表示）字符都相等的表示，则这两个串同构。解题思路：用暴力O(n^2)搜索的话显然会超时，这里引进O(n)的字符串最小表示法，并且将串利用set...

2019-02-06

0 440

kmp流程复习

（原创）详解KMP算法 KMP算法应该是每一本《数据结构》书都会讲的，算是知名度最高的算法之一了，但很可惜，我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的文章，看久了好像也知道是怎么一回事，但总...

2019-02-06

0 460

字符串的最小(大)表示法

循环字符串的最小表示法的问题可以这样描述：对于一个字符串S，求S的循环的同构字符串S’中字典序最小的一个。由于语言能力有限，还是用实际例子来解释比较容易：设S=bcad，且S’是S的循环同构的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。对于字...

2019-02-06

0 508

HDU1305Immediate Decodability(字典树)

题目链接：hdu1305 题目大意：给一大堆01串，并以9表示一组01串输入结束，问这些串之间是否至少有一个串是另一个串的前缀。解题思路：毫无疑问，可以用Trie来维护这些串，每次插入时判断是否含有当前串str的前缀串或者自己是别的串的前缀串，代码种的查询时query2。查询的复杂度O(n)。...

2019-02-05

0 480

HDU2647Reward(拓扑排序+反向建图思维)

题目链接：HDU2647 题目大意：给一张n节点m条边的图，(n<=10000,m<=20000)。并且要求每次输入的u,v节点 v的价值大于u的价值。最终输出总价值的最小值。解题思路：利用拓扑排序输出的序列价值要递增比较容易建图，这张m边有向图边的方向满足 (v,u):u的价值大...

2019-02-05

0 508

HDU3342Legal or No(拓扑排序判环)

题目链接：HDU3342 题目大意：给一个n个点m条边的有向关系图，问这图中是否存在环，即判断是否是DAG 。解题思路：拓扑排序判环模板题 AC代码： #include <cstdio> #include <cstring> #include <cstdl...

2019-02-04

0 417