qq1214917885
- 浏览: 9116 次
-
最新评论
文章列表
20.两个分数求最小公倍数：先得到两个最简的分数，然后用这两个分数的分子的最小公倍数 / 这两个分数的分母的最大公约数。即答案
19.用int开的数组MLE的时候可以考虑题目数据是不是在short的范围内改用short可以缓解。
如果不 ...
中文题意略。
就是要求排列组合a1Cn * a2C(n-a1) * a3C(n - a1 - a2)…………
不过要高精就是了。
通过这个题学到了高精度排列组合公式的简洁写法。同时掌握了高精乘法和除法。
void bign(int a, int n)//总值乘以n,除以a
{
int c = 0;
int i, j;
for (j = 0; j < N; ++j) //高精乘法
{
c = sum[j] * n + c;
sum[j] = c % 10;
c = c / 10;
}
c = 0;
for (j = N - 1; ...
以下引用自http://blog.csdn.net/lishuhuakai/article/details/8518245
(1) n条直线最多分平面问题
题目大致如:n条直线，最多可以把平面分为多少个区域。
析:可能你以前就见过这题目，这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手，才容易发现规律。当有n-1条直线时，平面最多被分成了f（n-1）个区域。则第n条直线要是切成的区域数最多，就必须与每条直线相交且不能有同一交点。 这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。而每条射线和线断将以有的区域一分为二。这样就多出了2+（n-2）个区域。
故：f ...
字符串匹配：KMP，就是给出一个长串T，给出一个短串P，求T是否包含子串P，若包含，输出第一个子串的位置。否则输出-1。
首先假定i是T的指针，j是P的指针。
对于传统的匹配模式，每当T[i] != P[j]时，我们会把j变成0，i跳回到刚才匹配的起始位置的下一个位置重新进行匹配，这样复杂度是O(n*m).
但是对于KMP思想，可以先构造一个next数组，next[j] = k 表示，短串中的子串0 ~ j的串中，以P[j]结尾的后缀串，与该子串中以P[0]开头的前缀串重复时，k的位置。
即有P[0] ~ P[k] = P[j - k] ~ P[j].
这样，在匹配过程中当短串匹配到j，长 ...
第一种，Prim算法.
算法：Prim算法和DIJ类似，整个代码也类似。
过程：假设顶点标号为1 ~ V,第一次先从所有未确定的点中找到距离1（此时只有1是确定的点）最近的点，然后将此点加入到已确定的点，并把该段距离加入总和。然 ...
第一种,bellman-ford算法;
算法：求单源的两点间最短路。
过程：每次枚举所有已知的边，更新一个点到源点的最短距离，重复V-1次，即可找到各个点离源点的最短距离。
证明：对于从源点出发到任意一点，最差的情况就是算出 ...
哈希表（Hashtable，也叫散列表），是根据关键码值(Keyvalue)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。 哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性 ...
字典序比较类的常用贪心法：按照字典序比较S和将S反转后的字符串S'；
实例1：每次从一个给定的S字符串的头或者尾取一个字母放入新的字符窜T中，要求得到新的字符窜T为字典序最小。
算法如下：按照字典序比较S和将S反转后的字符串S'；如果S较小，就从S的开头取出一个文字，追加到T的末尾；如果S'较小，就从S'的开头取出一个文字，追加到T的末尾；如果相同就随便取。
对于一些暴力循环嵌套的算法，例如抽签，从n个数里依次取4个数，每次取完皆放回。求取完4次后的数字是否有可能等于某个数。即a[i] + a[j] + a[k] + a[g] == m;
这样暴力的话就用4个for循环嵌套枚举每一种相加的和的可能性外加判断语句。但是这样复杂度是On^4，明显太大。
初步优化：那么想到，由于n个数是给定的，而且每次取的数字都在这个给定的数组里取，那么我们尝试把n^4给拆分掉，我们可以把求最后一个数的那个循环改写成二分查找，判断的数为m - a[i] - a[j] - a[k] 与目标区间的a[mid]相比较大小，最后判断得到的a[l]是否满足我们的 ...
论剑F题。。咋一看各种数据需要处理和判断，好像很麻烦。。但是仔细思考之后。其实可以将问题分解为若干个子问题概率来处理；
对于该概率问题，可以先用一个代表颜色的数组分别遍历一遍男主的衣服和裤子，然后 ...
二分法作为分治中最常见的方法，适用于单调函数，逼近求解某点的值。但当函数是凸性函数时，二分法就无法适用，这时三分法就可以“大显身手”~
如图，类似二分的定义Left和Right，mid = (Left + Right) / 2，midmid = (mid + Right) / 2;
如果mid靠近极值点，则Right = midmid；否则(即midmid靠近极值点)，则Left = mid;
模版如下:例如某函数值在当角度递增的时候呈凸性，那么我们可以对角度进行三分处理。
（注意浮点处理与整型处理的区别）
double l = 0, r = pi / 2;
while ...
树状数组：是一个查询和修改复杂度都为log(n)的数据结构，假设数组A[1..n]，那么查询A[1]+...+A[n]的时，间是log级别的，而且是一个在线的数据结构。
树状数组原理如下：主要是依靠神奇的二进制转换进行保存数据。所以我们需要 ...
⑴ 把0.4747……和0.33……化成分数。
想1： 0.4747……×100=47.4747……
0.4747……×100－0.4747……=47.4747……－0.4747……
(100－1)×0.4747……=47
即99×0.4747…… =47
那么 0.4747……=47/99
想2： 0.33……×10＝3.33……
0.33……×10－0.33……=3.33…－0.33……
(10-1) ×0.33……=3
即9×0.33……=3
那么0.33……=3/9=1/3
由此可见, 纯循环小数化分数,它的小数部分可以写成这样的分 ...
1.qsort 功 能: 使用快速排序例程进行排序
用 法: void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
各参数：1 待排序数组首地址 2 数组中待排序元素数量 3 各元素的占用空间大小 4 指向函数的指针
这个函数还可以对结构体进行二级排序噢
具体案例：
struct Q
{
int li, wi;
}haha[N];
int cmp( const void *a , const void *b ) //qsort 的配对配 ...
题意：有n条木棒，给出它们每条的l和w，用一台机器对它们进行加工，如果机器正加工的木条，与在它之前加工的木块有关系：l <= l'和w <= w'，则机器不用准备时间，否则需准备1分钟。问加工完全部木棒，机器最少需要准备多久。
理解：用贪心要找到一个最优的遍历方案，注意到题目是说与它之前加工的木块的关系。
那么可以认为两个循环，第一个从头开始，第二个循环从第一个循环的变量的下一个开始一直循环到尾部，找出所有满足条件不需要耗时的木块，并对这些木块进行标记，使得在第一个循环里不会再次对他进行计数。
核心代码如下。其中haha数组是以li作为升序排序，并尽量使wi小的在前面。
...