coderwait

最大子段和Description:给出一段序列，选出其中连续且非空的一段使得这段和最大。Input:第一行是一个正整数N（N<= 200000），表示了序列的长度。第接下来的N行包含N个绝对值不大于10000的整数A[i]，描述了这段序列。Output:仅包括1个整数，为最大的子段和是多少。子段的最小长度为1。Sample Input:72 ...

1.归约：通过一个问题解决另一个问题。2.P问题：在常规计算机上可以以多项式时间内解决的问题。3.非确定性（Non-deterministic）和NP问题：假设有这样一台计算机，它是可以同时测试所有可能答案的超级计算机。考虑这样一些问题，给出解的某个猜测，看看是否可以在多项式时间内检验这个猜测。如果可以，这样的计算机称为非确定性计算机。非确定性就是指这种猜测问题的正确答案或者并行检...

https://www.cnblogs.com/llhthinker/p/4924654.html

二分求幂思想注意点1. 设置矩阵的结构体便于计算。2. 注意初始化单位矩阵。3. 二分求幂int pow(int a,int b){ int ans=1;//对于矩阵:单位阵 while(b!=0) { if(b%2==1) ans*=a; b/=2; a*=a; } return ans;}矩阵二分求幂代码//矩阵二分求幂#in...

有关的字符串问题的基础使用#include<bits/stdc++.h>using namespace std;int main(void){ string str1="March"; string str2="11th"; //原型 const char *c_str() //注意 c_str()返回一个指向正规C字符串的指针，内容和string类对象相同 ...

回溯法在问题的解空间树中，按深度优先策略从根结点出发搜索解空间树。算法搜索到解空间树任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树继续按照深度优先策略搜索。两种剪枝策略1. 用约束函数在扩展结点处减去不满足约束的子树。2. 用限界函数剪去得不到最优解的子树。伪代码模板void dfs(int...

最长上升子序列Description:老师有n个题目，他希望出一张考试试卷，从中选取一定数量的题目，在不改变给定题目顺序的情况下，要求选取的题目难度严格递增，为了防止有人AK，老师希望在考试中出尽可能多的题目，求最大题目数量。Input:每个测试点只有一组测试数据。第一行一个整数n表示题目数量，第二行n个整数ai表示题目难度。Output:输出一个整数ans，一场考试中...

DP基本思想将求解的问题分解成若干子问题，先求解子问题，再从这些子问题得到原问题的解。DP的两个基本要素（重要性质）：1. 最优子结构性质。即问题的最优解包含了其子问题的最优解。2. 重叠子问题性质。有的子问题可能会被计算多次。因此采用备忘录方法避免对相同子问题的重复求解。DP编程关键状态转移方程、边界条件最长公共子序列(LCS)Description:给两个长...

DP求解核心：状态转移方程和边界条件。最朴素的01背包问题注意点：1. 理解dp[][]的意义，表示前i种物品在重量为j时的最大价值。2. 在选择放入物品时，注意对背包大小判断。//二维数组 #include<iostream>#include<cstring>#include<algorithm> #define N 10...

适用范围：（1）计算两个日期相差多少天。（2）某天是星期几。（3）几天后是日期是什么。主要思路：构造Date类，初始化计算出每天到某个日期的天数差值。然后根据实际情况进一步处理。如（1）直接相减，（2）与已知的某天的天数差值对7取模，（3）循环适用nextDay()函数。注意点：（1）闰年的判断是：年份被4整除且不被100整除，或者被400整除。（2）闰月的处理，nex...

思想二分方法降低求幂问题的时间复杂度。以2的31次方为例：而可以由得到，可以由得到。我们的目标就是将分解成若干个的的积，并尽可能减少分解结果的个数。这就是二进制数分解。循环次数 a(下一位的权重) b(当前待分解) ans 0 31 1 1 15 2 7 3 ...

素数筛法常规思路：如果能被整除，则不是素数。素数筛选：换一个角度。当获得一个素数的时候，就把它的所有倍数标记为非素数。这样，当我们遍历到一个数时，如果其已经被标记，则说明存在一个更小的数，是它的因子，因此它不是素数，否则它是素数。素数题目描述输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-...

主要思想：模仿手算除法。举例：将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。思路：相当于是不断除以2，直到为0（大数除法的循环），关键是记录每一次除法的余数。注意点：1. 经典的while循环：注意每一次除法结束后，通过对num[]前导零的判断，以确定位数有没有减少（即控制被除数开始的位置）。2.考虑十进制转二进制的实际过程，结果ans[]需要倒序输出。注意：可...

大数加法基本思路：以字符串读入，然后分解数位到数组中，然后模拟加法/乘法过程，逐个数位运算。加法和乘法的思路是类似的。注意点（模拟加法）：（1）注意要根据长度判断（可以给位数少的大数增加前导0，使得长度相等）。同时注意可能有额外进位，但是对于加法至多一位。（2）注意为了使得位置对齐，在将字符串读入同时，需要倒序。同理，输出时对于string类要reverse()，字符串的要倒序...

原理：欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。gcd(a,b)=gcd(b,a mod b)；证明一：证明：a可以表示成a = kb + r，则r = a mod b假设d是a,b的一个公约数，则有d|a, d|b，而r = a - kb，因此d|r因此d是(b,a mod b)的公约数假设d 是(b,a mod b)的公约数，则d | b...

进制转换其实一类特殊的数位拆解问题。基本思路要完成m进制到n进制的转换，只需要完成（1）m进制转换成10进制，（2）10进制转换成n进制。对于（1），只需要依次计算每个数位与该位权重的积，然后累加即可。对于（2），只需要不断地对这个数对n求模，再除以n即可，这一点是和10进制的数位拆解相似的。注意点1.当以字符串形式读入一个数时，字符串的低位时数值的高位。例如读入str="...

这是一类简单的问题。1.对于不超过int的数，可以直接读入整数，通过不断求模再除以10的形式获得每一个数位，将它们存在数组里。2.对于超过int的数，考虑以字符串形式读入，然后依次处理每一位，将它们存在数组里面。需要注意的是，以字符串读入的时候，字符串的高位存储的是数的低位。数值转换题目描述求任意两个不同进制非负整数的转换（2进制～16进制），所给整数在long所能表达的范围之...

理论堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这样：该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：大顶堆：arr[i] >= arr[2i+1] &&am...

归并排序基本思想二分法、分治法、递归思想。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序基本流程说法1.按照二分思想，先将序列分成两个大小大致相同的2个子集合，分别对2个子集合进行排序（段内有序），最终将排好序的子集合合并成为所要求的排好序的集合（段间有序）。 说法2.从整体来看，假设初始...

选择排序基本思想简单选择排序的第i趟，总是从（elem[i],elem[i+1],...,elem[n-1]）的未排序元素中选择最小的元素加入，然后只通过一次交换将当前最小的元素放在正确的位置。最好、最坏、平均时间复杂度都是，因为无论如何都要进行的循环次数是：稳定性选择排序是不稳定的！如序列[5 8 5 2 9]， 我们知道第一次选择第1个元素5会和2交换，那么原序列中2个...

快速排序基本思想：分治法快速排序基本流程选择序列的一个元素为枢轴（程序中选择第1个元素），然后设计两个指针（start和end），将所有剩余元素依次和枢轴进行比较，根据比较结果，将比枢轴大的元素都排在它的后面，比枢轴小的元素都排在它的前面，这样一趟排序以后（start==end），序列就以枢轴为界划分成了两个部分。然后，递归地对这两个部分再进行上述操作，直到每一部分都只有一个数据元素为止（...

冒泡排序基本思想在第0次循环中：从第0个元素开始，将两个相邻的元素两两比较，如果逆序则交换顺序。这样比较次（只有个数对）以后，最后的元素就是最大的元素。（之所以称之为冒泡排序，是因为关键字大的元素就像冒泡一样依次地浮出水面）这样依次进行次循环，这样序列就有序了。以比较次数作为基本操作分析：平均时间复杂度：最好时间复杂度：最坏时间复杂度：特性1.具有稳定性。2.冒...

插入排序基本思想将第0个元素看作是一个有序序列，然后依次从第1个元素开始逐个插入到这个有序序列当中，执行次就是有序序列了。平均时间复杂度最好时间复杂度（当原数组序列正好已经有序了，只需要比较次就可以了）最坏时间复杂度（当原数组序列是逆序的，需要比较次）特性具有稳定性（相同元素的相对位置不会改变）参考链接//插入排序 #include<...

折半查找原理：是一种二分查找方法。首先确定待查元素的范围，然后不断缩小区间，直到查找成功或者失败。注意：折半查找判定树。时间复杂度：#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#define N 1000using namespa...

二叉排序树的定义：（1）对于任何一个结点，如果左子树不空，其左子树的所有节点的关键字均小于它的根节点的关键字。（2）对于任何一个结点，如果右子树不空，其右子树的所有节点的关键字均大于它的根节点的关键字。（3）它的左子树、右子树都是二叉排序树。二叉排序树的特性：其中序遍历将得到的序列是从小到大的序列。二叉排序树的查找：只要关键字不相等，且当前节点不为空树就继续搜索。当小于...

方法1：重载运算符。方法2：重写cmp函数。关于strcmp函数（C/C++函数）：设这两个字符串为str1，str2，若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。大整数排序对N个长度最长可达到1000的数进行排序。输入描述输入第一行为一个整数N，(1<=N<=100)。接下...

作用：判断一个有向图是不是有向无环图（DAG）。步骤：1.邻接矩阵map[][]存储有向边的信息，indegree[]存储每一个结点的入度。2.在有向图中寻找一个入度为0（没有前驱）的结点并记录。3.删除该结点（indegree[i]置为-1）以及以该结点作为起点的边（若map[i][j]==1则置为0，同时indegree[j]--）。4.重复步骤2和3，直到所有结点都输出，...

算法流程1.使用结构数组存储所有的边的信息。2.对所有边按照边的权值进行从小到大排序。3.根据Kruskal算法，来自不同的分支，找到尽可能小权值的边将其联通起来。也就是说，排序后遍历每一条边，如果这条边的两个结点来自不同分支（采用并查集方式来记录同一分支），则可以使用这条边将两个分支联通。注意点1. 并查集记录该节点分支的根时，要注意优化findRoot()函数。2. 使...

算法流程1.初始化：所有的结点都是一个单独的分支，用Tree[]存储结点分支的根。2.对于每一条边，递归寻找其所属于的分支的根节点。（1）如果相同，说明它们属于同一个分支。（2）如果不同，则通过这条边可以连通，所以将它们合并成一个分支（注意必须对根节点操作，思考为什么？）。3.最后统计根节点数量。应用（1）图的分支数（畅通工程）；（2）单一分支最多的结点数（More i...

一种多源最短路径算法。时间复杂度DP转移方程参考链接#include<iostream>#include<cstring>#define MAX 0x3f3f3f3fusing namespace std; int d[101][101];int main(void){ int n,m;//节点数，边数 while(cin>...

是一种贪心的单源最短路径算法（可证明）。注意点：1. 图的链式存储（vector数组方式）。2. 循环n次。可分为两大步骤：加入新的节点后更新最短距离、寻找下一个节点（要有最短距离）并加入集合。时间复杂度：//Dijstra算法#include<cstdio>#include<vector>using namespace std;stru...