GreenHatHGのBlog

KMP是一个非常实用的字符串匹配算法 推荐网站： https://www.cnblogs.com/yjiyjige/p/3263858.html https://blog.csdn.net/starstar1992/article/details/54913261/ 视频： KMP字符串匹配算法1—-kmp如何运作 KMP字符串匹配算法2——代码实现 HDU - 1711 Number Sequence12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576/* Judge Status : Accepted Language : C++ Submit Time：2018-08-16 16:11:34 Exe.Time:748MS Exe.Memory：5.4MB*/#include <iostream>#include < ...

动态规划 入门DP入门参考：漫画：什么是动态规划？ 进阶参考：【DP专辑】ACM动态规划总结 http://www.cnblogs.com/raichen/p/5772056.html 动态规划原理 1-最优子结构 用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。 2-重叠子问题 在斐波拉契数列，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。 3-无后效性 将各阶段按照一定的次序排列好之后，对于某个给定的阶 ...

sprintf,Stringstream 参考：STL之Stringstream字符串流使用总结 sstream<sstream>库定义了三种类：istringstream、ostringstream 和 stringstream，分别用来进行流的输入、输出和输入输出操作。本次主要是讨论stringstream 注意，<sstream>使用string对象来代替字符数组。这样可以避免缓冲区溢出的危险。而且，传入参数和目标对象的类型被自动推导出来，即使使用了不正确的格式化符也没有危险。 重复利用stringstream对象如果你打算在多次转换中使用同一个stringstream对象，记住再每次转换前要使用clear()方法； 在多次转换中重复使用同一个stringstream（而不是每次都创建一个新的对象）对象最大的好处在于效率。stringstream对象的构造和析构函数通常是非常耗费CPU时间的。 常见基本类型互相转换string转int1234567891011121314151617#include <iostream>#include &l ...

B. Binary String Constructing（Div3—构造）,CodeForces - 1004C（Div2—思维）,CodeForces - 962D(Div2—较为精辟的解法),1055B - Alice and Hairdresser(思维),1088A. Ehab and another construction problem(暴力与O(1)), 1088C. Ehab and a 2-operation task(通过操作使数组递增) B. Binary String Constructing（Div3—构造）B. Binary String Constructing 题意：给出a，b，x，构造一个01串，有a个0，b个1。这个01串刚好有x个 S[i] 使得S[i] != S[i+1]。 思路：对于x，我们很容易就可以想到先输出x/2对0和1（n对0和1交错出现可以提供2*n-1个符合题意的S[i]），然后将剩余的0和剩余的1连续输出（提供1个符合条件的S[i]，这样就刚好是x个符合条件的S[i]了，需要注意的是，我们要优先将个数多的放在前面，例如，有1 ...

LinuxShell操作小总结 sed，获取当前路径，强制复制，du的用法命令格式sed [选项] ‘命令’ 输入文本 1sed [-nefri] ‘command’ 输入文本 选项与参数 选项 说明 -n 使用安静(silent)模式。在一般 sed 的用法中，所有来自 STDIN 的数据一般都会被列出到终端上。但如果加上参数后，则只有经过sed 特殊处理的那一行(或者动作)才会被列出来 -e 直接在命令列模式上进行 sed 的动作编辑 -f 直接将 sed 的动作写在一个文件内， -f filename 则可以运行 filename 内的 sed 动作 -r sed 的动作支持的是延伸型正规表示法的语法。(默认是基础正规表示法语法) -i 直接修改读取的文件内容，而不是输出到终端 常用命令 命令 说明 a 新增， a 的后面可以接字串，而这些字串会在新的一行出现(目前的下一行) c 取代， c 的后面可以接字串，这些字串可以取代n1,n2 之间的行！ d 删除，因为是删除啊，所以 d后面通常不接任何咚咚 i ...

并查集模板 参考：https://www.xuebuyuan.com/3256535.html 总体思路1. 初始化： 把每个点所在集合初始化为其自身。 通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。 2.查找： 查找元素所在的集合，即根节点 3.合并： 两个元素所在的集合合并为一个集合。 通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现 状态压缩建立门派的过程是用join函数两个人两个人地连接起来的，谁当谁的手下完全随机。最后的树状结构会变成什么样，我也无法预知，一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门，一共就两级结构，只要找一次就找到掌门了。哪怕不能完全做到，也最好尽量接近。这样就产生了路径压缩算法。 例题题目Input 输入多组数据 每组数据第一行是两个整数n（1＜＝n＜＝10＾6），m（1＜＝m＜＝10＾6）。分别表示元素数、操作数（初始时每个元素以自己为一个集合元素编号是1-n） 接下来m行，每行有如下几种输入: un ...

欧几里得及其扩展，素数，模运算，快速幂，欧拉函数，快速乘。 欧几里得—最大公约数gcd（a, b) = gcd(b, a mod b)123456int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a % )b;} 一波应用：线段上格点个数—-挑战编程—-欧几里得 algorithm库的std::_gcd函数123456789101112#include <iostream>#include <algorithm>using namespace std;int main(){ int a = 8; int b = 12; cout <<__gcd(a, b); //两个'_' return 0;}//out：4 //g++-4.8 最小公倍数(LCM)和最大公约数(GCD)lcm(a, b) = (a*b)/gcd(a,b) 扩展欧几里得基本算法：对于不完全为 0 的非负 ...

HDU1241 Oil Deposits(DFS模板题)，HZAU 1097 Yuchang and Zixiang ‘s maze(BFS模板题)，P1683 入门(bfs搜索没有终点)，P1162 填涂颜色(BFS联通块)，Poj-1321(DFS逐层搜索)，HDU-2553(N皇后） HDU1241 Oil Deposits(DFS模板题)题目：HDU1241 大意：和迷宫的输入差不多，‘*’是墙，‘@’是油田，以一个油田为中心，如果它的东南西北一个各个角落，一共八个方向也有油田的话，这些油田就算作一个油田。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<iostream>#include<cstring>#include<cstdio>char a[102][102];int row,col;int dir[8][2]= //八个方向{ {1, 0}, ...

P1022 计算器的改良(解简单一元一次方程), P1583 魔法照片（多个信息多个处理系列（题意比较绕））, P1588 丢失的牛(倒逆思想), P1459 三值的排序, P2386 放苹果(递归、dp、dfs都可以做), P2562 [AHOI2002]Kitty猫基因编码，P1106 删数问题 （贪心）,P2758 编辑距离(dp)，P2404 自然数的拆分问题（回溯） P1022 计算器的改良(解简单一元一次方程)P1022 这道题如果直接读入一个字符串再一个个处理的话可以会想复杂，我之前这样的处理的话代码长还wa（菜鸡），如果采用栈的思想，则会简单很多 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <iostream>#include <cstdio>#include <cmath&g ...

部分背包，01背包，完全背包，多重背包 部分背包问题和01背包问题的区别就是：部分背包问题中的单个物品，可以取一部分装入背包。而0/1背包问题则是要么全部拿走，要么一无所有 完全背包与0-1背包问题的区别是：在0-1背包问题中，每个物品仅有一件；在完全背包问题中，每个物品有无限件 多重背包与完全背包问题的区别是：在完全背包问题中，每个物品有无限件；在多重背包问题中，每个物品有Mi件 混合背包问题相当于上面提到所有背包问题的混合：有的物品仅有1件，有的物品有无限件，有的物品有Mi件（有限件） 部分背包【部分背包】问题描述：n件物品，第i件物品价值 vi 元，重wi 磅。希望用 W磅的背包 拿走最重的物品。第i件物品可以都拿走，也可以拿走一部分。（物品可以分割所以称为部分背包） 因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。（1）先将单位块收益按从大到小进行排序；（2）初始化背包的剩余体积和当前价值；（3）从前到后考虑所有物品：a.如果可以完全放入，当前价值加上物品总价值，剩余体积减去物品总体积；b.如果可以部分放 ...