数论
欧几里得及其扩展，素数，模运算，快速幂，欧拉函数，快速乘。 欧几里得—最大公约数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}...
luogu题目
P1022 计算器的改良(解简单一元一次方程), P1583 魔法照片（多个信息多个处理系列（题意比较绕））, P1588 丢失的牛(倒逆思想), P1459 三值的排序, P2386 放苹果(递归、dp、dfs都可以做), P2562 [AHOI2002]Kitty猫基因编码，P1106 删数问题 （贪心）,P2758 编辑距离(dp)，P2404 自然数的拆分问题（回溯） P1022 计算器的改良(解简单一元一次方程)P1022 这道题如果直接读入一个字符串再一个个处理的话可以会想复杂，我之前这样的处理的话代码长还wa（菜鸡），如果采用栈的思想，则会简单很多 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <iostream>#include <cstdio>#include <cmat...
背包问题
部分背包，01背包，完全背包，多重背包 部分背包问题和01背包问题的区别就是：部分背包问题中的单个物品，可以取一部分装入背包。而0/1背包问题则是要么全部拿走，要么一无所有 完全背包与0-1背包问题的区别是：在0-1背包问题中，每个物品仅有一件；在完全背包问题中，每个物品有无限件 多重背包与完全背包问题的区别是：在完全背包问题中，每个物品有无限件；在多重背包问题中，每个物品有Mi件 混合背包问题相当于上面提到所有背包问题的混合：有的物品仅有1件，有的物品有无限件，有的物品有Mi件（有限件） 部分背包【部分背包】问题描述：n件物品，第i件物品价值 vi 元，重wi 磅。希望用 W磅的背包 拿走最重的物品。第i件物品可以都拿走，也可以拿走一部分。（物品可以分割所以称为部分背包） 因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。（1）先将单位块收益按从大到小进行排序；（2）初始化背包的剩余体积和当前价值；（3）从前到后考虑所有物品：a.如果可以完全放入，当前价值加上物品总价值，剩余体积减去物品总体积；b.如果可以...
递推(for beginner)
斐波那契兔子问题、斐波那契数－从爬楼梯问题、HDU2046 骨牌铺方格、ＨDU2044 一只小蜜蜂、HDU2048 神、上帝以及老天爷、HDU2049 不容易系列之(4)——考新郎、递推中的平面问题、HDU 2097 Children’s Queue、HDU2045 不容易系列之(3)—— LELE的RPG难题、HDU2047 阿牛的EOF牛肉、for beginner,HDU2563统计问题 递推的基本思想 首先确认，是否能很容易的得到简单情况的解 假设规模为N-1的情况已经得到解决 重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决 编程中的空间换时间的思想 并不一定是从N-1到N的分析 递推中的经典——Fibonacci sequence(斐波那契数列)先上递推中的fib数列的解题模板 1234567891011121314151617181920#include <isotream>#include <iostream>using namespace std;typedef long...
数字特点
能被整除的那些事 能被2整除若一个整数的末位是0、2、4、6或8，则这个数能被2整除。 能被3整除若一个整数的数字和能被3整除，则这个整数能被3整除。 能被4整除若一个整数的末尾两位数能被4整除，则这个数能被4整除 能被5整除若一个整数的末位是0或5，则这个数能被5整除 能被6整除能被6整除的数的特征末尾是0、2、4、6、8且各位上数字的和能被3整除能被6整除的数的特征既要符合能被2整除的数的特征,又要符合能被3整除的数的特征 能被7整除若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，余类推。 能被8整除若一个整数的未尾三位数能被8整除，则这个数能被8整除 能被9整除若一个整数的数字和能被9整除，则这个整数能被9整除 能被10...
map几道水题
uva156 codeforces 959B uva156题目描述输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本中的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中大小写，按照字典序进行排序。 输入1234ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIednoel dire Disk mace Rob dries# 输出1234567DiskNotEderaildrIedeyeladdersoon 解析其实这道题挺简单的，把所有单词变成小写，然后排序，然后放到map里面，没有重复的就输出，但是自己写的过程中还是出了点问题。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <map>#include <cctype&g...
c++/java思维导图各两张
c++/java思维导图各两张 c++ java还有一个网址，里面列出来了比较详细的思维导图 Java知识汇总——思维导图 转载自： Java基础知识思维导图 c++知识思维导图 C++初学者必看的知识思维导图
c++ map
map和multimap 开始 c++有map和multimap两种容器，区别在于multimap允许重复元素，map则不允许，在头文件中< map >中定义 Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字(key)，每个关键字只能在map中出现一次，第二个可能称为该关键字的值(value)）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的 </div> 它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。 自动建立Key － value的对应。key 和 value可以是任意你需要的类型。 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。 什么是一...
变量与内存那些简单的事
内存内存，内存才是永恒的真理 总的来说： 新建的对象开在 堆里 属性 开在 堆里的对象里 局部变量 参数变量 开在 栈里 由C/C++编译的程序占用的内存分的几部分栈栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。 堆堆区（heap）— 由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。 全局区（静态区）全局区（静态区）（static）— 全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。 文字常量区常量字符串就是放在这里的，程序结束后由系统释放 。 程序代码区存放函数体的二进制代码。 变量，对象，内存 Java把内存划分成两种：一种是栈内存，一种是堆内存。在函数中定义的一些基本类型的变量和对象的引用变量都在函数的堆栈中分配 。 当在一段代码块定义一个变量时，Java就在栈中为这个变量分配内存空间，当超过变量的作用域后，J...