permutation: 在遇到全排列问题时，在数据量较小的情况下可以使用dfs的做法求得全排列，同时我们也知道在STL中存在函数next_permutation和prev_permutation,这两个函数可以较快的求出全排列，而这两个函数的实现却不是依赖于搜索算法（dfs）的。 分析： 以next_permutation为例，数据以1，2，3，4，5为例，对于一个排列我们知道其按照从小到大排序后的结果就是字典序最小的一个排列，而对于它的下一个排列为1，2，3，5，4比较这两个排列我们发现，排列的前三位没有改变，而最后两位发生了交换，原因是，对于一个排列而言他的从大到小排列（以下称倒序...

RMQ问题： RMQ问题是Range Maximum Query的缩写顾名思义就是区间最大值问题，对于这类问题的求解方法是——ST算法，ST算法采用一种类似动态规划的求解方式，可以在O(nlogn)内处理，O(1)询问，但是不支持修改，因此适用于极大数据量的查询问题。 ST： 对于a[1],a[2],a[3],a[4],.......a[n]的n个数的数组，我们用 f[i][j]表示数组a[i],a[i+1],a[i+2].....a[i+2j-1]的区间最大值，因为区间长度为2j所以我们可以将区间分成两部分，一部分为a[i],a[i+1],.....a[i+2(j-1)-1],第二部分...

GCD： 题目描述： 给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一： 1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。 2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。 对于每个询问，输出一个整数表示答案。 输入： 第一行两个整数N,M。 第二行N个整数A[i]。 接下来M行表示M条指令，每条指令的格式如题目描述所示。 输出： 对于每个询问，输出一个整数表示答案。 每个答案占一行。 样例输入： 5 5 1 3 5 7 9 Q 1 5 C 1 5 1 ...

任务安排一 题目描述： N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。 例如：S=1；T={1,3,4,2,1}；F={3,2,3,3,4}。如果分组方案是{1,2}、{3}、{4,5}，则完成时间分别为{5,5,10,14,14}，费用C={15,10,...

求和 题目描述： 出题人很困，所以不编题面了。 给一个长度为n的序列，你需要求出其中连续m个数的和的最大值是多少。 输入： 第一行给出一个数字T，表示数组总数 （t<100） 每组数据的第一行有两个数字 n,m （0<m≤n≤1e5） 第二行有n个数字ai (0<ai<1e9) 输出： 对于每组数据，输出最大的连续m个数之和 样例输入： 2 5 2 2 5 4 1 6 8 3 3 5 8 2 1 8 9 7 样例输出： 9 24 题解： 一道简单地前缀和。 /*************************...